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

On Fri, 3 Jul 2026, 21:14 Andrey Borodin, <x4mmm(at)yandex-team(dot)ru> wrote:
>
> Hello everyone,
>
> First, thank you for the v2 writeup. Reframing BTP_MERGED_AWAY as a
> tombstone that carries merge_xid "the same way deleted pages hold
> safexid" is seems the right thing to me, and I think it can be pushed
> further than the current draft does. Two observations, both aimed at
> shrinking the design rather than adding to it.

> 1. Forward dedup needs one watermark, not a saved TID set
> ---------------------------------------------------------
>
> The current forward-scan recovery keeps a per-page TID array:
>
> > The following fields are added to BTScanOpaqueData:
> > ItemPointerData savedMergeTids[MaxTIDsPerBTreePage];
> > ...
> > - Loop through currPos.items for R and remove any item that
> > exists in savedMergeTids.
>
> and Matthias already flagged the cost of carrying that around:
>
> > I think parallel btree scans need the [skip, need]MergeRecovery
> > flags, and possibly the item pointers themselves, too? I think that
> > could be a rather large amount of data for the parallel state.
>
> I don't think a set is needed at all for the forward direction. Since
> v12 the leaf level is totally ordered by (key, heapTID) -- heap TID is
> the tiebreaker in the suffix. So everything a forward scan has already
> returned is <= the last (key, heapTID) it emitted. When it steps onto
> a page that physically holds its already-seen tuples (post-merge R =
> old-L + old-R), it can just resume from the first item strictly
> greater than that single last-returned (key, heapTID). One item
> pointer plus its key, not MaxTIDsPerBTreePage of them. (Or even just
> find border by heapTID if it's not frequent operation.)

That is true, yet it requires key compares which can become expensive.
Not all index scans need key operations once the scan has started, and
I'd prefer to avoid adding a 'recover from possible concurrent merge'
step to every page access, especially when it involves more than just
O(small&constant)y in the case of "page was not merged"/"page has no
merged tuples".

It also adds a *requirement* for keeping track of the high (or, low)
water mark of accessed value ranges: Index scan keys can cause all
data on a page to be filtered out even if we access every page, so we
can't always rely on the scan state without losing performance once we
hit the merged data.
Note that it won't cause incorrect results if we use the last returned
matching tuple (i.e. don't track scan-level watermarks) because 1.)
merged tuples can't match the scan key (if they'd matched they'd have
been used as high water mark), and 2.) new tuples can't (shouldn't) be
visible to the scan, but we'd still possibly process (many) tuples
twice if we'd roll back to the last returned tuple, and I'd really
like to avoid that.

> Two things fall out of this that I find attractive:
>
> - It degrades to a no-op in the normal case. A normal right sibling
> begins above the left page's high key, i.e. above the watermark, so
> "skip <= watermark" skips nothing. The skip only fires on a merged
> right-step, which is exactly the overlap we want to suppress. So
> this can be a uniform rule ("resume the next page after the last
> returned (key, heapTID)") rather than a merge special case.
> If we know that page is not merged - we can optimize out this skipping.

As mentioned above, I disagree that a _bt_compare call, or a binary
search using _bt_compare to get to the next keys in the scan's
keyspace, is a no-op.

> - It handles "start the scan on a MERGED page", which was left open:

I don't think it's a fundamental issue in either design; I think it
can definitely be solved. I just don't want to spend time on fixing it
in my design, nor could I find a clear description of what'd happen in
her design.

As for "changing directions", I think that can safely be treated as
"starting a scan on the position you reversed direction at".

> > How do you detect it is the first page in the merge group? What if
> > you land on an M page after descending the tree?
>
> A scan that descended to R via the parent carries no watermark and
> simply reads R whole -- correct, because it never returned old-L.
> The discriminator for "dedup or not" is how you arrived at R (a
> right step carrying a watermark vs a downlink descent), which the
> scan already knows. It is not a property of the page, so the M flag
> is not even required for forward correctness.
>
> Backward direction still reduces to a single watermark (the low end),
> but the hard part there is navigation/left-links, not the size of the
> dedup state, so it needs separate care. And the whole thing assumes an
> ordered MVCC scan; unique checks / SnapshotDirty paths are a different
> conversation.

Unique checks/snapshotdirty scans both should only be doing forward
index scans, and SnapshotDirty scans should hold page locks in
scanning, so they both shouldn't be susceptible to undetected merges
causing key ranges to get skipped.

> 2. MERGED_AWAY looks like the pre-existing half-dead/deleted lifecycle
> ----------------------------------------------------------------------
>
> You already say:
>
> > * Resetting a BTP_MERGED_AWAY will make it HALF_DEAD.
>
> and
>
> > ... hold the merge_xid in the same way deleted pages hold safexid.
>
> I'd take that literally. L is empty the instant it becomes
> MERGED_AWAY; its values are gone; the only reason it must stay
> non-recyclable is that a scan holding a pointer to it can still step
> right through it -- which is precisely the deleted-page tombstone
> invariant Peter described:
>
> > Using XIDs for BTPageGetDeleteXid is just a convenient (though very
> > conservative) way to implement "the drain technique". [...] We must
> > always ensure that such a backend at least lands on a page marked
> > deleted/a tombstone page and then recovers by moving right.
>
> So MERGED_AWAY == a deleted/tombstone page whose safexid is the merge
> time. If we treat it that way, the genuinely new state is only
> BTP_MERGED on the surviving page during the drain window; L reuses the
> existing HALF_DEAD -> DELETED(safexid) -> recyclable machinery
> verbatim.

I don't think we can safely do this.

For HALF_DEAD (HD) pages we don't have any live tuples to worry about
when we move the keyspace, so no scan will mind failing to see that
page. Indeed, it's even possible that a scan will see the same
keyspace many times across a forward scan, if page splits and removals
happen at sufficiently inopportune moments (the last page visited
splits, and the newly created page gets immediately emptied by vacuum,
merging the keyspace onto the right page that the scan will access
next).

However, for MA/M pages we do have to care about the moved keyspace,
as it is not empty. The "MA,M+" page range gives scans a tombstone
that all scans will see at some point if they ever cross that
keyspace. This avoids many nasty scenarios that'd otherwise require
backtracking or more extensive bookkeeping in scans. My message of
last Wednesday gives an example of how to avoid backtracking, and how
it detects concurrent splits without holding O(keysize) memory nor
O(keysize) compares.

>
> That also lets us avoid stacking two horizons. The current plan is,
> as Kirk put it:
>
> > the visibility horizon on a future delete must be after the
> > visibility horizon on the cleanup process.
>
> i.e. one horizon to clear the M flags, then a second (safexid) horizon
> to recycle L -- which is the "one extra vacuum horizon" reclamation
> penalty Matthias called out. But both horizons protect the same
> population: scans that predate the merge. If L is unlinked at merge
> time with safexid = merge time, clearing R's MERGED flag and recycling
> L are gated by one and the same horizon, and the penalty goes away.

Correct, but I'm not convinced that in that eager-unlink scenario we
can safely and quickly detect which pages got merged unbeknownst to
scans that are between those pages.

The benefit of keeping the MA pages in the tree is that we know *with
certainty* that we can just follow its links in the structure of the
tree for the M-page cleanup. The same isn't true when we use an
M-flag-only approach: M can split and get deleted, and we'd be none
the wiser about that happening. We'd have to find the merged keyspace
using a tree-descent approach, and unset the M flags based on only
that which is a rather fragile approach; or try to find the live pages
based on deleted pages' leftover sibling pointers (another rather
fragile approach).

A query cancellation or error in the cleanup of MERGED pages can cause
a partial cleanup, which can allow the cleaned up pages to be merged
again in an M-flag-only design. Unless there is explicit information
attached to the merge range's cleanup about which part of the key
range has been cleaned up yet (which may increase WAL logging, or disk
space of MERGED pages), the cancelled cleanup will resume and "clean
up" the newly merged range, too - and in doing so corrupt the index
for the more recent merged pages.

The MA+M design has protection against that because there can be no M
immediately to the right of an MA that isn't part of that MA's "merge
range"; and because cleanup happens right-to-left any interrupts allow
the cleanup to still return to the rightmost M associated to an MA
without losing track, and without adding further page-level
bookkeeping for M pages.

> Net: I think the forward path can drop savedMergeTids entirely, and
> the L-side lifecycle can be the page-deletion lifecycle we already
> have, leaving BTP_MERGED on R as the one genuinely new concept to
> reason about. That feels much closer to Peter's "confine the
> complexity to the page deletion code" bar. I'm not certain about
> the backward direction under this framing.

Without the MA page in the tree (or other page that serves the
purpose), you can't detect the keyspace that got moved to the M page
when (in tree state L-R) after your scan reads R and before it reads
L, L splits into L-MA, and MA gets merged into R; you'll have skipped
reading the keyspace that MA got assigned in its split. Keeping MA in
the tree as 'normal but empty page, with no live keyspace attached',
the scan has to access MA, and will have to notice that MA's keyspace
was moved and merged into R.

Note that page deletion has the same issue of skipping key ranges in
backward scans, but there it is safe because the moved keyspace is
empty; it doesn't move any tuples that could be visible to the scan.

> WDYT?

Without more details about how you decide to cleanup which M pages,
and about how you detect skipped ranges in backward scans, I don't
think the "only M pages in the tree" approach can be safe; there must
be another, non-M page to indicate the left end of a merge range. I
think MA pages serve that purpose decently well.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)