Re: [GSoC 2026] - B-tree Index Bloat Reduction - Approach & Questions

Hello Hackers,

This is v4 of the B-tree leaf page merge patch series (3 patches
attached), rebased on current master. There are a lot of changes since
v3 [1].

1.) What is still the same

a. We merge two adjacent leaf pages L and R when they have the same
parent, both are below the threshold and the tuples of both fit in one
page under the fillfactor. All tuples of L move to R, and the parent
is updated, in one critical section and one WAL record.

b. L becomes a merged-away page (MA page, flag BTP_MERGED_AWAY), a
tombstone that keeps safemergexid. R becomes a merged page (M page,
flag BTP_MERGED) and keeps the MA blkno in pd_prune_xid. If an M page
splits, the new page is also M with the same MA blkno, so a group
looks like MA <--> M <--> M.

c. The idea of recovery is the same. A forward scan that reaches an M
page without passing its MA page has already read L before the merge,
so it must not return those tuples again. A backward scan that reaches
an MA page without reading its M pages missed the tuples of L, so it
walks right to the tail of the group and reads the group again
backward. The tail walk did not change.

---

2.) What is different

a. The MA page now stores a boundary key next to safemergexid. It is
L's last tuple, truncated to its key columns, with its highest heap
TID. It is written in the MERGE WAL record as the data of the MA
block. With it, the scan knows exactly where the tuples of L end
inside the M page.

b. In v3 the scan copied all TIDs of the last page it read into
savedMergeTids[MaxTIDsPerBTreePage], and after reading the M page it
removed them from currPos.items. This array is gone now, the scan only
keeps the boundary key and the MA blkno it came from.

_bt_readpage on an M page compares the matching tuples with the
boundary. It still saves all of them in currPos.items but sets
itemIndex to the boundary, the first tuple after it going forward, or
the last tuple at or below it going backward. A posting list with the
boundary key is split by heap TID. If nothing matches past the
boundary, _bt_readpage returns false and the scan goes to the next
page with the filter still on. Another M page of the group is filtered
with the same boundary, a normal page clears the flags, and going
backward the scan continues until the MA page and skips it.

Forward recovery then works like this: at an M page whose MA was
not passed, the scan unlocks the M page (keeps the pin), reads the
boundary from the MA page, and locks the M page again. The MA page
can't go away while we need it because of safemergexid. Backward
recovery does the same tail walk as v3 but loads the boundary from the
MA page and returns only what is at or below it.

c. The merge flags moved from BTScanOpaqueData to BTScanPosData.
markPos is a copy of currPos, so mark/restore now restores the merge
state of the page with it. In v3 a merge join that restored its mark
kept the flags of a later page and lost the tuples that came from L.

d. The merge takes a conditional cleanup lock on L instead of a write
lock and skips the pair if L is pinned, so tuples don't move away from
a page a scan still has pinned (index-only scans for example). Redo
takes a cleanup lock too, so a standby query with L pinned gets a
conflict.

e. A merge that runs while VACUUM is scanning the index can move
tuples from L into R when VACUUM already passed R, so VACUUM would
miss them. This is the same problem as a page split during VACUUM, and
we use the same fix: the merge stamps btpo_cycleid of both pages with
the current VACUUM cycle ID from _bt_vacuum_cycleid(). In
btvacuumpage, if a page has our cycle ID and its right sibling is a
block VACUUM already passed, VACUUM goes back and scans it. The
tombstone is only reclaimed when it is reached in the normal block
order, not during this backtracking.

f. Page deletion redo now keeps the M flag and the MA blkno, and a
backward scan whose M pages were all deleted skips the tombstone.

g. Smaller fixes: _bt_killitems() no longer touches a page that became
an MA page (reported by Yao Feng), and bt_merge() refuses to run
during recovery and on indexes older
than version 4, and returns 0 on an empty index.

---

3.) What is new

a. Parallel scans. The shared state keeps the blkno of the MA page
that was already handled, and processes check that instead of their
own flags. Forward is simple: each process recovers only the M page it
reads, and when one of them crosses the boundary it sets the shared
state so the rest of the group is read normally.

Backward is harder because recovery needs the whole group in order.
When a process hits an MA page that was not handled, it does the tail
walk alone and keeps the scan seized, the next page is not released to
the other processes until it is back at the MA page. Otherwise another
process could read left of the MA page while the group is not
finished.

b. Direction changes. All matching tuples of the M page stay in
currPos, so a cursor can turn around on it. If it then leaves in the
other direction, the rest of the group is read fully and the MA page
is skipped.

c. Mark/restore and merge joins. Besides the flags from 2.c, a copy of
the boundary is saved with the mark, because the scan can load another
group's boundary before the restore. In that case btrestrpos rebuilds
the boundary from the copy. This is what makes a merge join that
restores its mark across two merges return the right rows.

d. pageinspect 1.14 with docs, README updates, tests.

---

- Still missing: amcheck checks for the whole merge group and the
boundary key [2]. Also, I found a possible deadlock in backward
parallel recovery (3.a) when a merge group returns a lot of rows, I am
looking into it.

- Thanks to Nik for all the issues he reported [3], to my mentors
Kirk Wolak, Andreas Karlsson and Andrey Borodin for their help, and to
all reviewers.

- GSoC is ending soon, but I found a sponsor to continue working on
this project after GSoC. Any feedback is welcome.

[1] https://www.postgresql.org/message-id/CANBEAPFy8ig42RBqu0Y8gvi9P5n7ApyoX6dgypZ%3DAwUCPEPgTg%40mail.gmail.com
[2] https://github.com/NikolayS/postgres/issues/110
[3] https://github.com/NikolayS/postgres/issues/101

Best regards,
Salma Elsayed