The Free Space Map and the Visibility Map

Beside every table Postgres keeps two small side files. One remembers roughly how much room each page has, so an INSERT can find somewhere to put a row without searching. The other remembers which pages contain nothing but rows visible to everybody, so an index-only scan can answer from the index and a vacuum can skip work it does not need to do.

Each is tiny — a quarter of a megabyte of free space map and 32 KB of visibility map per gigabyte of table — and vacuum maintains both. That combination is why their failure mode always has the same shape: nothing errors, nothing appears in the query text, and a plan that used to be fast stops being fast without a line of it changing. Reading these two files directly is how you tell that story apart from the story where the query was wrong.

Forks: a Relation Is More Than One File

A relation on disk is a set of forks. The main fork holds the data. The _fsm fork is the free space map and the _vm fork is the visibility map, which tables have and indexes do not. A fourth, _init, exists only for unlogged tables and indexes: it holds the empty image the relation is reset to after a crash, and that is what "unlogged" means in practice. The suffixed files sit beside the main fork on disk, where the last topic of this chapter reads them.

SELECT pg_size_pretty(pg_relation_size('orders', 'main')) AS main,
       pg_size_pretty(pg_relation_size('orders', 'fsm'))  AS fsm,
       pg_size_pretty(pg_relation_size('orders', 'vm'))   AS vm;

  main  |   fsm   |   vm
--------+---------+--------
 14 GB  | 3760 kB | 480 kB

Forty million orders occupy 14 GB and about 1.8 million pages. The free space map that indexes those pages is under 4 MB, and the visibility map is under half a megabyte. Their size is the point. Both are small enough to sit in shared_buffers permanently, so consulting them is a buffer hit where reading the heap they describe is 1.8 million page reads.

The Free Space Map

The free space map is a tree. At the bottom level it stores one byte per heap page, recording approximately how much space that page has left — one byte, so the resolution is coarse on purpose. Above that, each node holds the larger of its two children's values, so the root of any FSM page carries the maximum free space available anywhere beneath it. An insert looking for a page with 200 bytes free descends that tree in a couple of lookups instead of walking the relation, and if the root says no page has room, it extends the relation instead of hunting. Every heap and index relation has one except hash indexes.

The map is only as good as its upkeep, and upkeep is vacuum's job: dead rows become reusable space when vacuum reclaims them, and the map is where that availability gets recorded. On a table where autovacuum has fallen behind — Chapter 7 makes that diagnosis properly — the map keeps saying there is no room, every insert extends the relation at the end, and the pages behind sit half empty holding tuples no transaction can see.

The Visibility Map, Bit One: All-Visible

The visibility map holds two bits per heap page. The first says the page contains only tuples visible to all active transactions, which also means there is nothing on it for vacuum to clean up. The map is deliberately conservative in one direction: when the bit is set the condition is guaranteed to be true, and when it is not set the condition may or may not hold. A stale visibility map therefore costs performance and never correctness, which is the property that makes it safe to treat as a hint.

The bits are set only by VACUUM and cleared by any operation that modifies the page. That asymmetry is the entire behaviour worth remembering: a single write clears the bit for a page instantly, and only a vacuum pass can put it back. Indexes carry no visibility map of their own; the bit always belongs to the heap page an index entry points at.

The Visibility Map, Bit Two: All-Frozen

The second bit records that every tuple on the page has been frozen, which allows an anti-wraparound vacuum to skip the page instead of reading it. Chapter 7 explains what freezing is and why transaction ID wraparound eventually forces every page to be visited; the storage-level consequence is worth stating on its own. With this bit, the pass reads what has changed. Without it, every wraparound vacuum on orders would have to read all 1.8 million pages of a mostly immutable table, forever, once per cycle.

Why an Index-Only Scan Stops Working

Index entries carry no visibility information, so a normal index scan has to fetch the heap tuple for every match just to find out whether the reader is entitled to see it. An index-only scan gets out of that by checking the visibility map bit for the heap page the entry points at. If the bit is set, the row is known visible and the data comes straight from the index. If it is not set, the heap tuple has to be visited after all, and there is no advantage left over a plain index scan. The trade pays because the map is four orders of magnitude smaller than the heap it describes and stays cached.

EXPLAIN ANALYZE
SELECT customer_id FROM orders WHERE placed_at >= DATE '2026-08-01';

 Index Only Scan using orders_placed_at_customer_idx on orders
   (actual time=0.048..1841.226 rows=412338 loops=1)
   Heap Fetches: 408112

Heap Fetches is the number of times the map said "not sure" and the scan went to the heap anyway. Here it is 408,112 out of 412,338 rows, so the index-only scan is doing the work of an index scan plus the cost of asking. The reason is not the index: these are August rows, they have been written since the last vacuum touched that end of the table, and their pages have no all-visible bit. Vacuuming orders fixes it. Adding columns to the index does not, and is the more common response because the plan node's name suggests the index is at fault.

The planner sees this through pg_class.relallvisible, the number of pages currently marked all-visible, refreshed by VACUUM, ANALYZE and a few DDL commands — Chapter 9 takes estimates apart in general. That count is what the planner uses to guess how many heap fetches an index-only scan would need, so a stale one distorts the choice of plan as well as the speed of the plan chosen.

Hints, Not Treasure

Give both files the right mental weight. They are derived data: vacuum rewrites them, and pg_visibility even ships pg_truncate_visibility_map() to throw one away deliberately so the next vacuum rebuilds it from scratch. They are not where your data lives, they are not a thing to tune, and they are too small to matter in a capacity plan — though a physical backup still has to copy them along with everything else in the directory.

SELECT * FROM pg_visibility_map_summary('orders');

 all_visible | all_frozen
-------------+------------
     1782940 |    1638400

Of roughly 1.83 million pages, 1,782,940 are marked all-visible and 1,638,400 all-frozen. When the first number sits well below the page count on a table you expected to be static, you have found either a write pattern nobody documented or a vacuum that is not keeping up. That is the direct answer to a question the plan only hints at: index-only scans over the older 97% of orders will be genuinely index-only, and over the recently written tail they will not.