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

Hello Hackers,

We want to share a v1 proof-of-concept patch series for B-tree leaf page
merging (3 patches attached). As we mentioned in our previous email
regarding the new design [1], we have completely gotten rid of the ghost
records in the left page.

I also attached a pdf (B-tree Page Merge PoC design.pdf) that puts all the
design details from this email and our previous one [1] into one place.

1.) The design is based on the following foundational principles:

a. We only merge two adjacent pages that share the same parent.

b. We need to keep the MA blkno saved in every M page to overcome the
race condition concern Matthias raised in his email [2]. We used
pd_prune_xid in the page header to store the MA blkno, as the comments
state it is "currently unused in index pages." This MA blkno serves as the
group identity.

c. When an M page splits, it inherits both the M flag and the MA blkno.
Therefore, in any merge group with multiple M pages, all M pages (except
the first one) result from M page splits.

d. The merged group must be contiguous (MA <--> M <--> M), meaning no
normal page (neither an MA nor an M page) can exist between an MA and an M
page from the same group. M pages can be deleted at any time; deleted or HD
(Half-Dead) pages in between do not break the group.

e. currPos.items in BTScanOpaqueData still retains the data of the last
read page.

f. We save a safemergexid in the MA page, ensuring VACUUM only clears
the flags after the XID horizon has passed.

2.) Besides the design details in [1], we have added a VACUUM cleanup
process for the merge group. To keep point 1.d always valid, VACUUM must
clean the group starting from the rightmost M page (the tail of the group)
and move backward.

When VACUUM encounters an MA page, it will:

a. Unlock the page and only keep a pin on it, allowing it to walk
forward and backward without causing deadlocks or violating lock ordering.
No index scan will change this MA page, only one VACUUM can run at a time,
and the MA block cannot split. Because of this, the MA page remains
unchanged after we drop the lock.

b. Walk forward to reach the end of the group (the tail M page). During
this walk, VACUUM doesn't clean anything; it only locates the tail to begin
cleaning from there.

c. Walk backward, starting from the tail, to clear both the M flag and
the saved MA blkno in each page until it reaches the MA page. Because these
pages will either be reached again by VACUUM or have already been cleaned
prior to this visit, we do not need to clean these pages entirely, they
will be cleaned eventually anyway.

d. On the MA page, clear the MA flag and transition the page to HD. We
then let the standard VACUUM handle the rest of the deletion process from
there.

3.) Open Question Regarding High Keys on MA Pages: When marking a page as
MA, completely emptying the page and saving the safemergexid may cause
crashes for concurrent searches that expect to find a high key.
One solution is to add MA pages to the P_IGNORE flag so searches skip them.
However, we want to avoid this because an MA page ("keyspace moved") has
different semantics than a Half-Dead page ("page empty"). Adding it to
P_IGNORE would require a massive and invasive audit of every P_IGNORE check
in the codebase.

Instead, we are considering keeping the old high key on the MA tombstone
page and only deleting the data tuples. This cleanly fixes the concurrent
search issue and also simplifies our VACUUM cleanup phase.

However, we have a concern regarding the lifespan of this high key: is it
safe to leave this "old" high key residing on the tombstone page during
concurrent scans until VACUUM eventually marks it as Half-Dead?

---
* A test script covering the basic merge, split on a merged page, and scan
recovery with injection points is available at [3]. The injection points
are included in the patch and fire only for the "merge_test_idx" index by
name.

* Note: WAL, parallel scan handling, and handling scans that change
direction have not been implemented yet, but they are next on our list.

Additionally, my mentors Kirk and Nikolay created a visualizer that
illustrates the merge process very clearly [4].

[1]
https://www.postgresql.org/message-id/CANBEAPFnx4eTOjNWnmtzoEYkZimSYC-7A2ouk76VcpzcfTrtNA%40mail.gmail.com
[2]
https://www.postgresql.org/message-id/CAEze2Wi9pfMG7n-CsPT0XuC5n6Qi%3D6b1PvQA_vSLpPTWE3kQcg%40mail.gmail.com
[3]
https://github.com/salmaaliia/postgres-btree-merge-tests/blob/main/first-patch-test-script.md
[4] https://kirkw.github.io/explainers/btree-merge-explainer.html

Best regards,
Salma El-Sayed