PostgreSQL Free Space Map and Visibility Map

The idea: two small maps beside every table

A PostgreSQL table is a heap: a file of 8 KB pages with rows wherever there is room. Two questions come up all the time: which page has room for this new row? and is every row on this page visible to everyone? Reading the pages to find out would be slow, so each table has two small side files, called forks, that answer them: the free space map (file <relfilenode>_fsm) and the visibility map (<relfilenode>_vm). Indexes have a free space map too, but no visibility map.

The free space map is a max-tree

The FSM stores one byte per heap page: the page's free space divided by 32 (8192 / 256), so 48 means at least 1536 bytes. Inside each 8 KB FSM page these bytes are the leaves of a binary max-tree: every inner node holds the max of its two children, so the root holds the most free space on any page it covers. A large table has a three-level tree of FSM pages built the same way.

An INSERT that needs N bytes asks for ceil(N / 32). If the root is smaller, no page has room and the table is extended by a new page. Otherwise the search goes down, at each node to a child that is big enough, and reaches a page in a few steps instead of reading the table. Demo: INSERT walks the FSM tree asks for 48 units (1.5 KB) and lands on page 2.

Real PostgreSQL does not always start from the left: each FSM page keeps a fp_next_slot hint, so that backends inserting at the same time spread over different pages, and a backend first tries the page it last inserted into.

The FSM is only a hint

An INSERT or UPDATE that uses space does not lower the page's FSM entry: writing the map on every insert would cost too much. Only VACUUM writes the real values. So an entry can be too high. When a backend follows the map to a page and finds it too full, it writes the page's real value into the leaf, the parents are recomputed, and it searches again (RecordAndGetPageWithFreeSpace). Demo: stale FSM entries, search again hits two stale leaves before it finds room on page 7.

The FSM is not WAL-logged in full and is not crash-safe; a wrong value only costs an extra page read, and VACUUM repairs it.

The visibility map: two bits per page

Bit	Meaning when set	Who sets it	Who clears it
all-visible	every row on the page is visible to every transaction; no dead rows	VACUUM	any INSERT, UPDATE or DELETE on the page
all-frozen	every row is also frozen: it never needs freezing again	VACUUM that froze the page	the same, together with all-visible

The map is conservative: a 1 is a promise, a 0 means only "don't know". A page full of committed rows that were just inserted is visible to everyone, yet its bit stays 0 until VACUUM looks at it. Demo: UPDATE and DELETE clear VM bits clears the bits of pages 2 and 4. Unlike the FSM, the VM is WAL-logged and crash-safe, because a wrong 1 would return wrong answers.

Index-only scans and Heap Fetches

An index entry has no xmin/xmax, so on its own it cannot say whether its row is visible. An Index Only Scan checks the VM for the heap page each entry points to. If the page is all-visible, the value comes straight from the index; if not, the executor fetches the heap row to check it. EXPLAIN ANALYZE reports those visits as Heap Fetches.

So a recently changed table makes index-only scans slow until it is vacuumed. Demo: index-only scan and Heap Fetches runs the scan, VACUUM, then the scan again: 12 heap fetches, then 0.

VACUUM uses and maintains both maps

• Skip. Plain VACUUM reads the VM and skips all-visible pages: they cannot hold dead rows. On a big, mostly static table this is what makes VACUUM cheap. Demo: VACUUM skips all-visible pages reads only pages 3, 5 and 6.
• Clean. On each page it reads, it removes dead rows (and their index entries) and compacts the page.
• Record. It writes the page's real free space into the FSM and sets the all-visible bit when every row left is visible to all.
• Freeze. An aggressive VACUUM (VACUUM (FREEZE), or the anti-wraparound one autovacuum starts) must freeze old rows, so it can skip only all-frozen pages; after freezing a page it sets both bits. Demo: VACUUM (FREEZE) sets all-frozen.

Practical consequences

• Check index-only scans with EXPLAIN (ANALYZE): a high Heap Fetches means the table needs vacuuming more often (tune autovacuum_vacuum_scale_factor or, for insert-only tables, autovacuum_vacuum_insert_scale_factor).
• pg_class.relallvisible is what the planner uses to cost index-only scans; the pg_visibility extension shows the bits of each page, and pg_freespacemap shows each page's FSM value.
• Free space found by VACUUM is reused through the FSM, but the file does not shrink, except for empty pages at its very end.

See also How PostgreSQL Runs a Query (heap, MVCC, HOT updates and VACUUM), the 8 KB heap page, transaction ID wraparound and freezing, PostgreSQL index types, bitmap scans and MVCC and isolation levels.

What the page leaves out

• The page header (24 bytes), line pointers and fillfactor; real page free space is a little smaller.
• The multi-level FSM (a tree of FSM pages), fp_next_slot and the "last page used" target block; the search here always prefers the left child.
• Real VACUUM skips only runs of at least 32 all-visible pages (SKIP_PAGES_THRESHOLD), so the operating system's read-ahead keeps working; here it skips every one.
• Other sessions: a long-open snapshot keeps VACUUM from removing recent dead rows and from setting the all-visible bit on their pages.
• Opportunistic pruning during reads, PD_ALL_VISIBLE in the page header, COPY FREEZE (which sets the bits at load), and freezing of rows older than vacuum_freeze_min_age by a plain VACUUM.

References

Free Space Map (PostgreSQL documentation)

Visibility Map (PostgreSQL documentation)

Index-Only Scans and Covering Indexes

src/backend/storage/freespace/README (PostgreSQL source)