Delete a million rows and the index that pointed at them keeps every page it ever allocated. There is no code in Postgres today that takes two half-empty B-tree leaf pages and makes them one. This is what it would take to add it — and why "just merge the pages" turns into a state machine.
An index is a file made of 8 kB pages. Rows you delete get cleared out of those pages by VACUUM, but the pages stay in the file. Postgres only reclaims a leaf page when it becomes completely empty. A page holding three surviving entries is a page you keep paying for — in disk, in cache, and in every scan that walks through it.
REINDEX CONCURRENTLY works, but it writes a whole second copy of the index first — so you need the free disk space, the I/O budget, and a maintenance window big enough for your largest index. Merging is the incremental alternative: a bit of bloat reclaimed at a time, by the vacuum you already run.You don't need to know nbtree internals, but you do need these four facts. Hover or tap the diagram to light each one up.
Two neighbouring leaf pages, L and R. We move everything from L into R and leave L behind as a marker. Three conditions have to hold, and every one of them is re-checked under an exclusive lock right before the write, because the tree can change while we're thinking.
R gets rebuilt: its own high key goes back on first, then L's rows, then R's original rows — still in key order, because L's keys all sort below R's. The parent's downlink for L is repointed at R, and R's now-duplicate downlink is deleted. L's own copy is cleared at the same time — it becomes an empty tombstone, not a duplicate of R.
The sibling chain. L is still linked between its left neighbour and R, and both still link back to it. L has left the tree from above but is still walkable from the side — that is the whole trick, and the next two sections are about paying for it.
BTP_MERGED_AWAY and stamped with a transaction id, empty of rows itself, but still occupying its place in the chain so the scan can notice something happened and go find its rows in R instead.Every page flagged M also records the block number of its tombstone. MA → M → M → …, all pointing back at the same block, is a merge set. That back-pointer is what makes the whole thing verifiable: a scan holding an M page can always go ask the tombstone whether this merge is still relevant.
A split inside a merge set copies the flag and the back-pointer into the new page. So the set can grow while it exists, and it always stays contiguous: MA followed by a run of pages that all name the same ma_blkno. The first page that doesn't name it is the end of the set.
/* src/include/access/nbtree.h — the whole merge-set test */ static inline bool BTPageIsMergedMember(BTPageOpaque opq, Page pg, BlockNumber ma_blkno) { return P_ISMERGED(opq) && P_ISLEAF(opq) && !P_ISMERGEDAWAY(opq) && BTMergedPageGetMABlkno(pg) == ma_blkno; }
The back-pointer is squeezed into pd_prune_xid, a four-byte page-header field that index pages never use — because a merged page may be completely full of tuples, there is nowhere else to put it.
Nobody stops the world for this. A scan may have read L one microsecond before the merge and arrive at R one microsecond after — and R now contains L's rows too. The flags exist so that scan can notice and correct itself. Turn the correction off below and watch the wrong answers appear.
On reaching a page flagged M, the scan compares against the row ids it just read and drops the repeats. It keeps only what's genuinely new.
Landing on a tombstone it wasn't expecting, the scan saves what it has, walks right to find the end of the merge set, then walks back through it filtering duplicates.
Duplicate rows on the way forward. That's a wrong answer to a plain SELECT — which is why none of this can ship until every scan variant is covered.
Here is the idea the whole design hangs on. When the merge happens, the tombstone is stamped with a transaction id. Queries that started before that stamp might still be walking through the merge set, so every later step has to wait until the oldest running transaction has moved past the stamp. Then the next step stamps its own id, and the waiting starts again.
Each star is a query starting. The bright line is now; the yellow line behind it is the horizon — the start point of the oldest query still running. One long query holds the horizon back and everything downstream waits for it. That's not a flaw in the design, it's the same rule that already governs ordinary page deletion and row cleanup in Postgres.
| State | Set by | Leaves when |
|---|---|---|
| MA | the merge, on L | horizon passes the merge stamp |
| M | the merge, on R and anything R splits into | vacuum clears the set, right to left |
| HALF_DEAD | vacuum, once the set is cleared | ordinary page-deletion path takes over |
| DELETED | vacuum, unlinking the page from its siblings | horizon passes the deletion stamp |
| REUSABLE | the free space map | the page gets handed out to a new split |
Finding a tombstone whose stamp is behind the horizon puts vacuum into a special routine: walk right to the end of the merge set, then come back leftwards clearing the M flag off each page, and only when you're home again turn the tombstone into a half-dead page. The order matters. Pull the plug halfway through and see what happens.
This is also what saves a scan that read an M page just before vacuum cleared it. The scan steps on and finds a page that isn't in the set — no M flag, or an M flag naming a different tombstone. So it goes and looks at the block the flag named. Not MA any more? Then the merge it was compensating for is long finished, that read was stale, and there is nothing to correct. One block read settles it.
| # | Step |
|---|---|
| 1 | Find neighbours L and R that share a parent, where L is nearly empty and R has room. |
| 2 | Under exclusive locks, re-check all of it. Anything changed? Walk away. |
| 3 | Copy L's rows into R. Point the parent's L-downlink at R, delete R's old downlink. |
| 4 | Flag R as M and write the tombstone's block number into it. Flag L as MA and stamp it with a transaction id. |
| 5 | Scans that straddle the merge use those flags to drop duplicates or to go find the rows that moved. |
| 6 | Splits inside the set inherit both the flag and the back-pointer, so the set stays contiguous. |
| 7 | Once the horizon passes the stamp, vacuum clears the M flags right to left, then makes the tombstone half-dead. |
| 8 | Half-dead goes through the ordinary deletion path: unlinked, marked deleted, stamped again. |
| 9 | Horizon passes that stamp too, and the block becomes reusable. The index just got one page smaller. |
Workers share scan position but not the per-scan memory the correction logic uses. Recovery across workers is a harder problem and isn't solved yet.
A tombstone holds no rows of its own — every entry moved to the page it merged into. There's nothing left inside it for vacuum to prune later.
Every state change here needs a WAL record and a redo path, and a standby replaying it has to keep its own queries correct too.
The WIP branch ships pageinspect functions so you can look for merge candidates in a real index before any of this is committed.
-- pairs of adjacent leaf pages that could be merged SELECT * FROM bt_find_merge_candidates('my_idx', 10.0, 90.0, 20); -- parent / left / right detail for one candidate pair SELECT * FROM bt_merge_detail('my_idx', 42, false); -- and, on the branch, actually do it SELECT bt_merge('my_idx', 10.0, 90.0, 20);