The Free Space Map: Freed Is Not the Same as Available

<code>VACUUM</code> removing a dead row and the space becoming available to the next INSERT are two different events, and they can be four minutes apart. In between, the map that inserters consult still says the table is full, so every row that arrives extends the file instead.

The free space map — FSM from here on — is a second file next to your table. A table stored in base/16384/16401 has its map in base/16384/16401_fsm, and Postgres calls that file a fork of the relation. The map holds exactly one byte per heap page. That byte is not a pointer and not a byte count: it is the page's free space divided by 32 and rounded down, which gives 256 possible values for an 8 kB page.

Everything that makes this lesson surprising follows from two facts about that byte. It is written by VACUUM at one moment and read by an inserting backend at another, and those two moments are further apart than anyone expects. And it describes one page, so free space that is spread thinly is not free space at all — a row needs a single page that fits it, and the total across the table is never consulted.

The panel below runs one autovacuum pass over an 8 GB table while 5,000 rows a second keep arriving, then keeps running for the same length of time again. The slider that carries the lesson is maintenance_work_mem, and it moves the answer in the direction you will not predict. Start by just reading the decision log at the defaults.

At the defaults the log says something that should not be possible. The vacuum frees 1.53 GB. The file grows by 256 MB while it does so. Not before it, not after it — during it, while the thing whose job is to reclaim space is running and succeeding.

Now drag maintenance_work_mem down from 64 MB to 16 MB. The growth falls from 256 MB to 95 MB. Lowering the memory setting that every tuning guide tells you to raise made the table grow less. Drag it up to 512 MB and nothing changes at all — 256 MB again. The setting is not acting as a memory dial here. It is acting as a schedule.

One byte, and what it can say

The map cannot store a byte count, because a byte count of an 8 kB page needs 13 bits and the whole design depends on one byte per page. So freespace.c divides the page into 256 categories of 32 bytes each — FSM_CAT_STEP is BLCKSZ / 256 — and stores the category. Category 40 means "somewhere between 1,280 and 1,311 bytes free".

Both conversions round, and they round in opposite directions on purpose. Recording a page rounds down: fsm_space_avail_to_cat is avail / FSM_CAT_STEP, so a page with 2,076 bytes free is recorded as category 64, which claims only 2,048. Asking for space rounds up: fsm_space_needed_to_cat is (needed + FSM_CAT_STEP - 1) / FSM_CAT_STEP, so a request for 2,064 bytes asks for category 65. Between the two, up to 62 bytes of every page's free space is invisible to the search. The top category is special: 255 means "at least MaxHeapTupleSize", which is 8,164 bytes — an empty page — and is reserved so that a request for exactly that size can still be satisfied.

The number recorded is not the page's empty bytes either. It is PageGetHeapFreeSpace, which takes the gap between pd_lower and pd_upper and subtracts four more for the line pointer a new tuple will need. It also returns zero — flatly zero, whatever the page actually holds — when the page already has MaxHeapTuplesPerPage line pointers, which is 291 with the default 8 kB block, and none of them are free. That is the one case where a nearly empty page is honestly reported as full, and narrow rows plus a heavy delete workload is how you reach it.

Set row width to 2,000 bytes and rows dead when vacuum starts to 25%, and leave everything else alone. Four rows fit on a page, so the largest group — 442,368 pages, 42% of the table — comes out of the vacuum with exactly one 2,024-byte hole in it. That page has 2,076 bytes free and is recorded as category 64, meaning "at least 2,048". An incoming 2,024-byte row asks for category 64, gets it, and fits. The map is working.

Now drag new rows are wider by from 0% to 2%. The row is 2,040 bytes of data and 2,064 stored, so it asks for category 65. Every one of those 442,368 pages is recorded at category 64 and is skipped, even though each one has 2,076 bytes free and the row needs 2,064. A new row can use falls from 1.98 GB to 653 MB, and across the window the file grows 5.08 GB instead of 2.44 GB. The decision log states the loss exactly: 874 MB of recorded free space skipped, 43% of the total, and 871 MB of it would have held the row. A two percent change in row width doubled the growth, and nothing about the dead rows, the vacuum or the settings changed at all.

This is the part people mean when they say bloat "came back". It did not come back. The space was always there, sitting in the file, listed in the map, and 32 bytes short of being offered to anyone.

Why the space is invisible for minutes at a time

The map is a tree, not an array, and the tree is what makes a search cheap: to learn that no page in a 500 GB table has 2 kB free you read one byte. Each FSM page holds a binary tree in an array, where a leaf is one heap page's category and every non-leaf node holds the larger of its two children, so the page's root node is the maximum over everything below it. A bottom-level FSM page covers 4,069 heap pages, its parent covers 4,069 bottom pages, and one more level above that addresses the whole 2³²-block maximum relation size. The tree is always exactly three levels, and the root page is always physical block 0 of the _fsm fork.

GetPageWithFreeSpace starts at that root and walks down, taking any child whose value is at least the category it wants. This is the whole trick and it is also the whole trap: a value that has not reached the upper levels does not exist as far as the search is concerned.

VACUUM calls RecordPageWithFreeSpace for each page it has finished with. That writes the byte on the bottom-level FSM page and fixes up the parent nodes within that one page, and stops. It does not touch the level above. The comment in freespace.c says so without softening it: if the new value is higher than the old one, "the space might not become visible to searchers until the next FreeSpaceMapVacuum call, which updates the upper level pages."

So when does that call happen? vacuumlazy.c has exactly three answers, and none of them is "continuously":

• After every index-vacuuming cycle — that is, every time the store of dead row ids fills up, forcing a pass over each index and a second pass over the heap. The size of that store is maintenance_work_mem.
• On a table with no indexes at all, every VACUUM_FSM_EVERY_PAGES blocks, a constant defined as 8 GB worth.
• Once at the very end, covering everything not yet propagated.

That is why the memory slider behaves backwards. More memory means the dead row ids fit in one store, which means one index pass, which means the upper levels are refreshed exactly once — when the vacuum finishes. Less memory means more cycles, and every cycle is also a moment when the space freed so far becomes findable. At 16 MB the model does three cycles and the first advertisement lands at t=89 s; at 64 MB it does one and the first advertisement is at t=233 s, when the scan ends.

Do not take this as advice to lower it. Each extra cycle is a complete scan of every index on the table, which is usually the most expensive thing a vacuum does, and the simulation charges nothing for it. Trading one index pass for three to make free space visible two minutes earlier is almost always a bad deal. The point of the slider is diagnostic, not prescriptive: it shows you that the thing deciding whether your table grows during a vacuum is a refresh schedule you did not know existed, and that the schedule is a function of table size, dead-row count and a memory setting, in that order.

The lever that actually helps is the length of the vacuum. Turn the table size slider up to 32 GB: the vacuum now takes 932 s and the first advertisement is at 355 s. Turn it down to 1 GB and the whole vacuum finishes in 29 s, so the blind window is 29 s. Nothing about the mechanism changed; the table just spends less time in it. That is the storage argument for partitioning a large table and for vacuuming it often enough that each pass is short, stated in a currency you can measure.

Now tick vacuum is cancelled half way. The first advertisement reads never. The vacuum reached block 524,288, freed 784 MB, wrote every byte of it into the bottom level of the map, and was killed before any of it reached the root. Nothing in the system will fix that until another vacuum runs the table to a cycle boundary. This is the exact shape of the failure people report as "autovacuum keeps running and the table keeps growing": a backend that blocks on a lock an autovacuum worker holds signals it to cancel, and it raises ERROR: canceling autovacuum task and starts again from block zero next time. Two carve-outs matter. A worker running to prevent transaction-id wraparound is never cancelled this way — proc.c checks PROC_VACUUM_FOR_WRAPAROUND before signalling. And the restart is not a full redo: pages the killed pass already marked all-visible in the visibility map are skipped, so each attempt gets further. On a table that is churning fast enough, it still may not reach a cycle boundary before something cancels it again.

The three places the map is deliberately not told

Two of the mechanisms around the FSM withhold information on purpose, and one of them is the reason Heap-Only Tuple updates work at all.

On-access pruning never records anything. When an ordinary SELECT or UPDATE touches a page that is full or nearly full, heap_page_prune_opt may remove superseded row versions right there, without vacuum and without touching any index. It then does not tell the map, and pruneheap.c explains why in as many words: "We avoid reuse of any free space created on the page by unrelated UPDATEs/INSERTs by opting to not update the FSM at this point. The free space should be reused by UPDATEs to this page." Space freed by pruning is being held back for the next HOT update on that page. If an INSERT could grab it, the next update to a row on that page would have to go to a different page and write a new entry into every index on the table. The map's silence here is the feature.

A backend does not ask the map most of the time. RelationGetBufferForTuple in hio.c first tries RelationGetTargetBlock, a single block number cached per relation in the backend's relcache entry — rd_targblock — which is wherever that backend last successfully inserted. Only when there is no cached block does it call GetPageWithFreeSpace; when the cached page turns out to be too small it calls RecordAndGetPageWithFreeSpace, which corrects the map entry for that page and searches in the same descent. Either way, when the FSM comes back empty-handed it tries the very last block of the relation before giving up and extending. This is why a bulk load packs pages sequentially instead of scattering rows across every hole in the table, and it is also why two backends inserting at once do not fight over the same page: each FSM page carries an fp_next_slot hint so consecutive searches hand out different pages.

Nothing about the map is written to the write-ahead log. The FSM README is explicit that it "is not explicitly WAL-logged" and relies on self-correction instead: writes use MarkBufferDirtyHint rather than MarkBufferDirty, reads use RBM_ZERO_ON_ERROR so a checksum failure silently zeroes the page rather than raising an error, and every search that lands on a page with less space than its parent promised repairs the parent before retrying. After a crash the map can be wrong in both directions, and the system is designed to shrug. A map that says too little costs you a relation extension; a map that says too much costs you a retry.

Indexes have an FSM fork too, and it means something different there. For a B-tree the map tracks entirely unused pages, not free space inside pages, which is why pg_freespace on an index returns values that are only meaningfully zero-or-not. That single fact is the mechanical reason a B-tree index never shrinks: a leaf page that is 5% full is not in the index's free space map at all, because the map has no way to describe it.

And the boundary that no setting crosses: none of this returns disk. A perfectly maintained map, refreshed on every cycle, with every category accurate, describes free space inside a file that is still exactly as large as it ever was. VACUUM truncates only a wholly empty tail of pages. Watch the last line of the decision log at any setting: in an update-heavy run no page in the middle ever empties completely, and the ones that do are scattered. Getting the bytes back to the operating system is a rewrite, with the lock that implies — that is VACUUM FULL and pg_repack, and it is a different decision from anything here.

Checking it on a real system

The map is directly readable. CREATE EXTENSION pg_freespacemap; gives you pg_freespace, which reports the recorded value — always a multiple of 32 — for every block:

SELECT count(*)                        AS pages,
       pg_size_pretty(sum(avail))      AS recorded_free,
       count(*) FILTER (WHERE avail = 0)      AS pages_with_nothing,
       count(*) FILTER (WHERE avail >= 300)   AS pages_that_fit_a_300b_row
FROM pg_freespace('orders');

Replace 300 with the stored width of the rows you are actually inserting: the data plus a 24-byte header, rounded up to a multiple of 8. The gap between recorded_free and pages_that_fit_a_300b_row is the whole second half of this lesson made concrete. If the first number is large and the second is a small fraction of your page count, your free space is real and stranded, and no amount of extra vacuuming will change it.

For the distribution rather than the totals, bucket it:

SELECT width_bucket(avail, 0, 8192, 16) * 512 AS free_bytes_at_least,
       count(*)
FROM pg_freespace('orders')
GROUP BY 1 ORDER BY 1;

A healthy table under steady churn has a broad spread. A table whose reuse has failed has a tall spike in one low bucket — thousands of pages each holding one row's worth of hole, all of them just under what the next row asks for.

To catch the blind period itself, watch a running vacuum rather than the map. pg_stat_progress_vacuum has a heap_blks_scanned column and, crucially, index_vacuum_count:

SELECT p.pid, p.relid::regclass, p.phase,
       p.heap_blks_scanned, p.heap_blks_total,
       p.index_vacuum_count,
       now() - a.xact_start AS running_for
FROM pg_stat_progress_vacuum p JOIN pg_stat_activity a USING (pid);

index_vacuum_count is the number of refreshes that have already happened. If it reads 0 on a vacuum that has been running for an hour, then every byte that vacuum has freed in that hour is unfindable, and it will stay unfindable until the number becomes 1. That is the single most useful column on that view and almost nobody reads it that way.

Two more checks worth having. pgstattuple gives you the real per-page truth rather than the map's rounded version — SELECT * FROM pgstattuple('orders'); returns free_space and free_percent computed by actually reading every page, so a large gap between that and sum(avail) from pg_freespace means the map is stale rather than the space missing. And the size of the fork itself is pg_relation_size('orders', 'fsm'), which for a table of N pages is about N/4,069 bottom pages plus the two levels above: an 8 GB table carries a map of roughly 2 MB.

One last thing to unlearn. If you find advice about max_fsm_pages and max_fsm_relations, it is describing PostgreSQL 8.3 or earlier, where the map was a fixed-size shared memory area that genuinely could overflow and genuinely did cause the unbounded bloat those articles describe. PostgreSQL 8.4 replaced it with the per-relation fork this lesson is about, and both settings were deleted. A modern server cannot run out of free space map. It can only fail to tell you about the space in time.

Next: the other reason a page has no room when you need it, which is that the page was born full — fillfactor and HOT updates. And when the map is healthy and the file is still four times the size of its contents, the rewrite options and what they really lock.