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

Hello Hackers,

I was looking at the latest version of the btree merge patch and found
that inserting into an index might not work correctly.

To reproduce it, you will need to apply the patches from Salma and
then apply the attached patch. Configure PostgreSQL with injection points
enabled,
and install the pageinspect and injection_points extensions.

Session 1:
CREATE EXTENSION pageinspect;
CREATE EXTENSION injection_points;
CREATE TABLE merge_test (id int);
ALTER TABLE merge_test SET (autovacuum_enabled = false);
INSERT INTO merge_test SELECT i FROM generate_series(1, 10000) i;
CREATE INDEX merge_test_idx ON merge_test(id);
DELETE FROM merge_test WHERE id % 20 != 0;
VACUUM merge_test;

Session 2:
SELECT injection_points_attach('before_leaf_level', 'wait');

Session 3:
INSERT INTO merge_test VALUES (381);

Session 1:
SELECT * FROM bt_merge('merge_test_idx', 10.0, 90.0, 10);

Session 2:
SELECT injection_points_wakeup('before_leaf_level');
SELECT injection_points_detach('before_leaf_level');

Session 1:
SET enable_seqscan = false;
SELECT * FROM merge_test WHERE id = 381;

After this, you will see that you cannot find the row with id = 381 in the
merge_test
table (session 1). I think that the index tuple has landed on a page with
the BTP_MERGED_AWAY flag.

I also think that you need to set mergedAwayBlkno inside _bt_readfirstpage
to really skip merge
recovery, because inside _bt_readnextpage, in a forward scan, you check
mergedAwayBlkno,
not skipMergeRecovery.

Best regards,
Michail Sirotkin

ср, 5 авг. 2026 г. в 01:01, Salma El-Sayed <salmasayed182003(at)gmail(dot)com>:

> 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
>
>