Journal based VACUUM FULL

Hi Team.

New to contributing so hopefully this is the right place. I've searched the forum and it seems this is the place for feature requests/suggestions.

I was reading on VACUUM and VACUUM FULL and saw that the current implementation of VACUUM FULL writes to an entirely new file and then switches to it, as opposed to rewriting the current file in-place. I assume the reason for this is safety in the event the database shuts down in the middle of the vacuum, the most you will lose is the progress of the vacuum and have to start from scratch but otherwise the database will retain its integrity and not become corrupted. This seems to be an effective but somewhat rudimentary system that could be improved. Most notably, the rewriting of almost the entire database takes up basically double the storage during the duration of the rewrite which can become expensive or even simply inconvenient in IaaS(and probably other) installations where the drive sizes are scaled on demand. Even if the VACUUM FULL doesn't need to run often, having to reallocate drive space for an effective duplication is not ideal. My suggestion is a journal based in-place rewrite of the database files.

This means that the VACUUM FULL will do a "pre-processing" pass over the database and figure out at a fairly low level what operations need to be done to compact the database back to it's "correct" size. These operations will be written in their entirety to a journal which records all the operations about to be performed, with some mechanism for checking if they have already been performed, using the same principle described here: https://en.wikipedia.org/wiki/Journaling_file_system. This will allow an in-place rewrite of the file in a safe manner such that you are able to recover from an unexpected shutdown by resuming the VACUUM FULL from the journal, or by detecting where the copy hole is in the file and recording/ignoring it

The journal could be something as simple as a record of which byte ranges need to be copied into which other byte ranges locations. The journal should record whenever a byte range copy completes for the sake of error recovery. Obviously, each byte range will have a max size of the copy distance from the source to the destination so that the destination will not overwrite the source, therefore making recovery impossible(how can you know where in the copy you stopped?). However, this will have a snowball effect as the further you are in the rewrite, the further the source and destination ranges will be so you can copy bigger chunks at a time, and won't have to update the journal's completion flags as often. In the case of a shutdown during a copy, you merely read the journal, looking for the first copy that isn't completed yet, and continue rewriting from there. Even if some of the bytes have been copied already, there will be no corruption as you haven't overwritten the source bytes at all. Finally, a simple file truncate can take place once all the copies are complete, and the journal can be deleted. This means the headroom required in the filesystem would be much smaller, and would pay for itself in any copy of at least 17 bytes or more (assuming 2*8 byte pointers plus a bit as a completion flag). The only situation in which this system would consume more space than a total copy is if the database has more than 50% garbage, and the garbage is perfectly spread out i.e. isn't in large chunks that can be copied at once and therefore recorded in the journal at once, and each piece of garbage is smaller than 17 bytes. Obviously, the journal itself would need a error checking mechanism to ensure the journal was correctly and completely written, but this can be as simple as a total file hash at the end of the file.

An alternative to the completion flags is to compute a hash of the data to be copied and store it in the journal, and then in recovery you can compare the destination with the hash. This has the advantage of not needing to write to the journal to keep it up to date during the operations, but the disadvantages associated with having to compute many hashes while recovering and storing the hashes in the journal, taking up more space. It's also arguably less safe as there is always the chance(albeit extremely unlikely) of a collision, which would mean that the data is not actually validated. I would argue the risk of this is lower than the risk of bit-rot flipping the completion bit, however.