Mehdi Akiki
Published on

Deleted Rows Do Not Shrink the File: Free Pages and VACUUM

Authors
  • Mehdi Akiki avatar
    Name
    Mehdi Akiki
    Twitter

Investigation · Part 9 of 10 · Inside a database index

Delete half of the rows of a table, and the database file becomes smaller. Right?

before the delete: page_count 24993, freelist_count 0, file 102371328 bytes
...
after the delete: page_count 24993, freelist_count 8207, file 102371328 bytes

Not one byte smaller. The table is the one million users of this series, with the index on email from part 1, and the delete is a retention rule: remove the users created before July 2024. That is 499,584 rows, half of the table. The file did not move. In this part I followed where the space went, who can use it again, and what the tools that give it back really do.

Where the deleted rows went

The dbstat lines after the delete tell two different stories:

after the delete: page_count 24993, freelist_count 8207, file 102371328 bytes
    users: 8251 pages, 508644 cells, 30412114 bytes payload, 241338 bytes unused
    users_email: 8534 pages, 500416 cells, 15895021 bytes payload, 17456591 bytes unused

The table went from 16,468 pages to 8,251. The deleted users were the oldest ones, so their rows were next to each other in rowid order, and whole leaf pages became empty. SQLite took these pages out of the table b-tree and put them on the freelist, that is the list of empty pages inside the file: 8,207 pages, about 34 MB, still in the file but not used by anything.

The index did not lose any page. In fact it has even 10 more than before (8,534). But its unused space went from 146,483 bytes to 17,456,591 bytes. The deleted emails were random in the index order, so each leaf page lost about half of its entries and stayed in the tree, half empty. Same amount of deleted data, two very different results: the table has free pages, the index has holes inside its pages.

One more thing I noticed: the DELETE took 2.43 s and passed 2,126,560,576 bytes to write(). It is the same effect as the random inserts of part 3. Each deleted email is on a random page of the index, so a delete probably also spills pages from SQLite's small cache.

Free pages are not wasted

Then I inserted 200,000 new users into the same file:

after 200000 new users: page_count 24993, freelist_count 4921, file 102371328 bytes
    users: 11537 pages, 711921 cells, 42508388 bytes payload, 348703 bytes unused
    users_email: 8534 pages, 700416 cells, 22189353 bytes payload, 10562259 bytes unused

The file did not grow. The table needed more pages, and it took them from the freelist: 8,207 free pages became 4,921. The index received 200,000 new entries without one new page: they went into the holes, and its unused space went down from 17.5 MB to 10.6 MB. So if a table will grow again soon, the free space is not a problem. It is a reserve, already allocated.

What "deleted" means in this file

There is a question behind free pages that is not about size. Is the deleted data really gone? I searched the raw bytes of the file for the email of the first user, who was deleted:

secure_delete = 1: rows with [email protected]: 0, copies of the text in the file: 0
    non-zero bytes in 50 free pages of 4096 bytes: min 0, max 0
secure_delete = 0: rows with [email protected]: 0, copies of the text in the file: 1
    non-zero bytes in 50 free pages of 4096 bytes: min 3962, max 4028

With secure_delete = 0, the row is gone for SQL, but its bytes are still in the file. The documentation says that with secure_delete on, "SQLite overwrites deleted content with zeros", and that the default "is normally off". On this laptop it is on by default. A new database file in the sqlite3 shell and a new connection in Python both answer 1, because this SQLite was compiled with the SECURE_DELETE option:

PRAGMA secure_delete;
1
...
SECURE_DELETE
...
python sqlite3 module 3.51.2 PRAGMA secure_delete: 1

I checked also the free pages themselves, with my decoder from part 1: with the option on, 50 free pages contained only zeros. With it off, between 3,962 and 4,028 of the 4,096 bytes of each free page were still old data. So check this on your own build, if deleted data must really disappear.

REINDEX packs one index

The half-empty index can be rebuilt alone:

after the delete and REINDEX users_email: page_count 24993, freelist_count 12462, file 102371328 bytes
    users: 8251 pages, 508644 cells, 30412114 bytes payload, 241338 bytes unused
    users_email: 4279 pages, 500416 cells, 15895021 bytes payload, 79171 bytes unused

REINDEX builds the index again from the table, like the drop and create of part 1, and the new index is packed: 4,279 pages and only 79,171 unused bytes. A smaller index means fewer pages for every range scan. But the freed pages went to the freelist again (12,462 now), and the file is still exactly the same size. REINDEX repacks, it does not give space back.

VACUUM builds a new file

VACUUM is the command that does both. The documentation says it "rebuilds the database file, repacking it into a minimal amount of disk space":

VACUUM: median 415.10 ms (min 411.88 ms, max 447.71 ms, 3 runs), load average 3.82 3.36 3.40
after VACUUM: page_count 12531, freelist_count 0, file 51326976 bytes

Half the file, no free pages, and both b-trees packed. Fast here, 415.10 ms, because the file is small and in the page cache. But I wanted to know what it costs in writes, so I ran it under strace and added the bytes of every write call, per file:

    written by VACUUM to etilqs_...: 51331072 bytes
    written by VACUUM to p09.db: 51326976 bytes
    written by VACUUM to p09.db-journal: 51442420 bytes

Three times the size of the result. First SQLite writes the new, packed database into a temporary file (the etilqs_ file, which it deletes as soon as it opens it, so you never see it in a directory listing). Then it copies the temporary database back over the original file, inside a normal transaction, and the rollback journal saves the old content of every page it overwrites. At the end it truncates the file. For a moment, the original file, the temporary copy and the journal exist together. This is why the documentation warns that VACUUM can need "as much as twice the size of the original database file" in free disk space. (I set SQLITE_TMPDIR in the run script, so these temporary files stay on the same disk as the database.)

auto_vacuum, and a small trap

SQLite can also give pages back automatically. But the setting must exist before the tables, and on my existing database it was ignored:

    PRAGMA auto_vacuum: [(0,)]
    PRAGMA auto_vacuum = FULL: []
    PRAGMA auto_vacuum: [(0,)]
    VACUUM: []
    PRAGMA auto_vacuum: [(1,)]

No error, the value just stayed 0, until a VACUUM rebuilt the file with the new setting. This matches the documentation: changing from "none" to "full" or "incremental" is possible only when the database is new or "by running the VACUUM command".

With auto_vacuum = FULL from the start, the same delete gave a file of 16,807 pages (68,841,472 bytes) and an empty freelist: SQLite moved the free pages to the end of the file and cut them at commit. But the index still had its 17,456,591 unused bytes. Auto-vacuum gives back free pages, not the holes inside pages, and the documentation even says that it "can actually make fragmentation worse", because it moves pages around.

auto_vacuum = INCREMENTAL keeps the free pages until you call PRAGMA incremental_vacuum(N). Here is the trap I found with Python:

after execute('PRAGMA incremental_vacuum(1000)'): page_count 25023, freelist_count 8206, file 102494208 bytes
...
after the same with fetchall(), 1000 rows: page_count 24022, freelist_count 7206, file 98394112 bytes

I asked for 1000 pages and got one. Strange. The reason is in the bytecode, read like in part 2:

3     IncrVacuum     0     7     0                    0   
4     ResultRow      1     0     0                    0   output=r[1]
5     AddImm         1     -1    0                    0   r[1]=r[1]+-1
6     IfPos          1     3     0                    0   if r[1]>0 then r[1]-=0, goto 3

The loop frees one page, returns one (empty) row, and only then continues. execute() in Python runs the statement until the first row and stops there, so one page. With fetchall(), the loop runs 1000 times. The sqlite3 shell always reads all the rows, so there it works as expected.

When VACUUM is worth it

So the free space after a delete is not lost, it is waiting. If the table will grow again, as most tables do, the next inserts use it, and VACUUM is a lot of writing for nothing. VACUUM is worth it after a big one-time delete, like this retention rule, when the file size matters (a file you copy, back up or download) or when the indexes are half empty and you scan them often. Then it is one big write transaction, about three times the size of the new database in writes, and temporary space for two times that size. If only one index is the problem, REINDEX is cheaper. And auto_vacuum is a decision for the day the database is created; later, only a full VACUUM can change it.

PostgreSQL makes the same separation, with other names. Its documentation says that the standard VACUUM "marks the space available for future reuse" but "will not return the space to the operating system" (except for free pages at the end of a table), while VACUUM FULL writes "a complete new version of the table file with no dead space", needs extra disk space for the copy and an ACCESS EXCLUSIVE lock.

The full output is in p09-free-pages.txt, and the defaults of this SQLite build are in p00-machine.txt.

References