VACUUM, and Why This Engine Rarely Needs It

Why this stage exists

"Vacuum" means two different jobs, and databases disagree about which one the word names.

The first job is sweeping dead rows. In PostgreSQL, an UPDATE or a DELETE does not remove the old row: it marks it dead and leaves it in the table, because another transaction may still need to see it. Dead rows pile up, and VACUUM has to come through and reclaim their space. Skip it, and tables grow forever.

This engine never has that job. A DELETE removes the cell from its leaf at once. A leaf compacts itself when an insert needs the room, and since borrow and merge, a node that falls below a quarter full is merged away, its page goes to the free list, and the next allocation takes it back. Delete half a table and insert it again, and the file does not grow by a page: the first test of this stage checks exactly that, five times over. A leaf that is only half empty stays as it is: its free bytes wait for the next insert that lands in it, and VACUUM does not repack it either.

The second job is giving space back to the operating system. The free list keeps pages for reuse, but they still sit in the file. Delete most of a large table and the file stays large: nothing in the engine so far ever makes it shorter. That is the job this VACUUM does, the one SQLite calls VACUUM and MySQL calls OPTIMIZE TABLE.

Two engines, two answers. PostgreSQL keeps old row versions in the table itself, so VACUUM must sweep them, and a background autovacuum runs it for you. InnoDB updates rows in place and keeps old versions in a separate undo log; a DELETE only marks the row, and a background purge thread removes it soon after, so nobody runs a sweep by hand. Shrinking the file is a separate, rarer job. This engine follows InnoDB. The multi-version half of the story, where old versions are needed at all, comes with Sessions and Concurrency.

What changes: only the end can go

A file can only be cut at its end. If page 9 of a 12-page file is free, there is no way to give back that page alone. So VACUUM first makes the end of the file free: every page in use past where the file will end moves into a free page before it.

With N pages and F of them free, the file will end at N − F. The pages in use at N − F or above are exactly as many as the free pages below it, so they pair up: the highest page in use goes to the lowest free page, the next highest to the next lowest. After the moves, every page past the end is free, and the file is cut there.

Here is a table of 30 rows after deleting rows 1 to 12. Borrows and merges freed pages 4, 5 and 6 of a 12-page file, so the file will keep 9 pages, and pages 9, 10 and 11 are in use past that end.

What changes: everything that names a page

Moving a page is the easy half: copy its bytes. The hard half is that other pages hold its number, and every one of them must now hold the new number, or the tree points at a free page. These are all the places a page number lives:

Find them all before moving anything, by walking from the header: the catalog's tree, each table's tree from its catalog row, and each cell's chain. A page in use that the walk never reaches, such as one only pager write touched, still moves, with its bytes; nothing needs fixing for it.

Order matters in one way. A place that names a page may sit on a page that moves too, before or after. Keep track of where each page is now, and fix the number where its holder is at that moment. A holder that has not moved yet carries the fixed number with it when it does.

The one exception. Since the first stage of the B+Tree, a tree's root has never moved: a split keeps the root on its page, and so does a collapse. VACUUM is the only operation allowed to break that rule. A root past the end moves like any other page, and its catalog row is updated, so catalog list shows the new page. The catalog's own root, on page 1, never moves, since nothing below it can be free.

Output contract for this stage

The full definition is on the output contract page, section 30.

pages_moved is the number of pages in use at N − F or above. SQL results after VACUUM are the same as before it; only page numbers change.

What you should see when done

With users holding rows 1 to 30 of 502 bytes, from an earlier session, as in the diagram above:

Welcome to droid!
>delete from users where id < 13;
Delete statement executed successfully (12 rows)
[EXEC] rows_examined=12
>db freelist
[DB] Free list: pages=3 chain=[6,5,4]
>pager status
[PAGER] Status: total_pages=12 cached=12
>vacuum;
Vacuum statement executed successfully
[VACUUM] pages_moved=3 pages_released=3 bytes_released=12288
>db freelist
[DB] Free list: pages=0 chain=[]
>pager status
[PAGER] Status: total_pages=9 cached=9
>.exit
exiting.. good bye!

Things to notice. The free list lists 6, 5, 4, but VACUUM fills the lowest first, 4, then 5, then 6: the list's order is the order of reuse, not the order of the file. And the file went from 49,152 bytes to 36,864, with the same 18 rows in it.

Common bugs in this stage

• Moving a page and fixing nothing. The tree then points at a page past the end, which the file no longer has. Every number in the table above must be fixed.
• Forgetting the parent fields. A moved internal node's children still say their parent is the old page. Nothing fails at once; the next split or merge that follows a parent field goes wrong.
• Forgetting the leaf link. Full scans skip rows, or read a page past the end, while lookups still work.
• Fixing a number on the old copy of a page. If the holder already moved, the fix must go to its new page.
• Leaving the catalog's root alone. A moved table root that the catalog does not name makes the table look empty, or broken, after the next restart.
• Writing pages past the end when the session ends. They are gone: drop them from the pool without writing, or the file grows back.
• Shrinking the file and not the free list. The header must say head 0, count 0, or the next allocation hands out a page past the end.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: an array of (page, offset) pairs per page number, built in one walk, makes the fixes a loop; ftruncate shortens the file.
• C++: a std::unordered_map<uint32_t, std::vector<Ref>> for what names each page, and std::filesystem::resize_file to shorten it.
• Rust: a HashMap<u32, Vec<(u32, usize)>> for the references, and File::set_len to shorten the file.
• Zig: a std.AutoHashMap(u32, std.ArrayList(Ref)) for the references, and file.setEndPos to shorten the file.