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

On Fri, 8 May 2026 at 16:40, Salma El-Sayed <salmasayed182003@gmail.com> wrote:

Hello Hackers,

My name is Salma El-Sayed, and I am working on B-tree Index Bloat Reduction as part of GSoC 2026. This is my introduction email[1]. I would like to share my current approach for page merging and get your feedback.

*The Core Idea*
Two sibling B-tree pages L (left) and R (right) are candidates for merging when both pages are below a size threshold (less than 10% full for example) and their combined size fits within the fill factor.

The merge copies all data from L into R, then:
1- R is marked BTP_MERGED --> it now contains L's data.
2- L is marked BTP_MERGED_AWAY --> it is logically gone but kept around temporarily for any active scan that still holds a reference to it.
3- L is unlinked from its parent. VACUUM will handle updating the right-link of L's left sibling as part of normal cleanup.

The merging of pages is the simple part. Making scans not skip or
return duplicated tuples is the hard part.

I think it's useful and important to have an up-to-date design with
all such considerations included, so that reviewers also are able to
have the whole picture in mind when providing guidance.

*Questions for the Community*

1- Triggering the merge: how aggressive should we be?

How should the merge process be triggered? I see two broad options:
a- Full-index scan: aggressively find all merge candidates in one pass.
b- Bounded scan: a separate dedicated scan that stops after a controlled number of pages, giving the user control over how much of the index to process at a time.

I suggest to keep track of candidate pages (i.e., leaf pages with more
than X% free space) in the btree vacuum scans. Whenever you hit a page
which are a merge candidate (or, would become a merge candidate), you
check if any of its sibling pages are already present as merge
candidate in a list of candidate merge pages. If one is, merge the
pages. If not; then add the current page not; and check if siblings of
the current page are in our candidate list. If so, try to merge with
the sibling; if they're not (or the merge failed), then you add the
current page to that candidate list.

Presumably, the amount of active candidates would remain small enough
to fit in a reasonable amount of memory; as merged candidates can be
removed once they've been used.

A possible interface for the candidate scanner might look something like:
bt_merge_pages(index regclass, min_fillfactor float8, max_fillfactor float8, max_pages int4)

I don't think a separate scan method for this makes much sense.

2- Flag naming and free bits

I am proposing two new flags in btpo_flags:
- BTP_MERGED: set on R to indicate it absorbed L's data.
- BTP_MERGED_AWAY: set on L to indicate it has been merged away.

** Are there free bits available in btpo_flags suitable for this purpose? And does the community see any objection to consuming two bits in this field for the merge mechanism?

btpo_flags has 16 bits, of which 7 don't yet have a meaning.

You might even be able to combine one new bit with BTP_HALF_DEAD, to
limit the need for new bits to just one: presumably, pages cannot be
both HALF_DEAD and MERGED/MERGED_AWAY at the same time.

Kind regards,

Matthias van de Meent

PS.
Some food for thought and questions in return:

1.) Page space usage
The idea that you shared in [0]/messages/by-id/CANBEAPFW64QUGmMYoPekV6jGrn5Yx8kTNfeEtcTG9CCBUUBoLQ@mail.gmail.com described a page-level "Merge ID".
Adding this to the page would affect the amount of space available on
btree pages (for at least merged btree pages), and that seems to imply
a possibly backward-incompatible change to currently indexed tables
(less space on a page available -> smaller max tuple size -> current
indexed data may not be reindexable with the new checks in place).

Have you thought about this, and/or figured out whether the decrease
in page space is relevant or can safely be worked around?

2.) changes to page lifecycle operations
There are various concurrent operations that may impact scan
consistency. You've covered how to recover from merges with documents
linked to from your earlier mail, but it's not clear to me if these
things work without causing issues w.r.t. scan output:

a. Deleting a BTP_MERGED page
When vacuum runs a second time all items on the target page may
now be removable; can that page be deleted safely?

b. Deleting a BTP_MERGED_AWAY page
BTP_MERGED_AWAY pages keep a copy of their old tuples around,
which you mention are used by backward scans. This means its contents
must also be cleaned up by subsequent VACUUM runs, as the backwards
IOS may otherwise return TIDs that have been recycled and recieved new
indexed values. This cleanup can result in an empty page - which can
happen earlier than the XID horizon in the MergeID. Does this design
allow those pages to be reclaimed?

c. A BTP_MERGED page must be split
What happens? And what happens if it keeps splitting, before any
further vacuum (maintenance) operations can affect the merged
contents?

d. Are BTP_MERGED_AWAY pages still part of the data structure?
So, is L still pointed to by both L's left sibling and R, or is it
immediately removed from the structure (or at least as immediate as a
HALF_DEAD page would)?
If it's kept in the structure for extended periods: Why?

e. When/how does VACUUM determine to recycle the BTP_MERGED_AWAY
page (mark it BTP_HALF_DEAD or BTP_DELETED)?
The docs [1]https://docs.google.com/document/d/1PIMG0N__4BIB0uDWOfcK-AruatNL8SCTlfTlBTCaoCo/edit?tab=t.0 linked from [0]/messages/by-id/CANBEAPFW64QUGmMYoPekV6jGrn5Yx8kTNfeEtcTG9CCBUUBoLQ@mail.gmail.com indicate MergeID is present only on
BTP_MERGED pages, so it can't be used to locally determine to start
the recycling process for a BTP_MERGED_AWAY page. What process is used
to clean up this index page?

3.) General performance
I'm worried about the cost of maintaining the scan boundary;
especially for index-only scans. Though it's likely you'll only have
to keep track of this at page boundaries, it's still a new and
possibly significant overhead; index key boundaries are not always as
small as int4/int8 + TID.

4.) Workload
Do you have an example workload that you expect to show improvements?

5.) Inner pages
Are inner pages ever considered for merging, or are you only
targeting leaf pages?

[0]: /messages/by-id/CANBEAPFW64QUGmMYoPekV6jGrn5Yx8kTNfeEtcTG9CCBUUBoLQ@mail.gmail.com
[1]: https://docs.google.com/document/d/1PIMG0N__4BIB0uDWOfcK-AruatNL8SCTlfTlBTCaoCo/edit?tab=t.0

Hi Matthias,

Thanks for your email and these detailed answers and questions.
Apologies for the delayed response, I am right in the middle of my
university final exams right now.

I am actively using your feedback to shape the design plan, but I
wanted to go ahead and address a couple of your specific questions
regarding BTP_MERGED_AWAY pages:

b. Deleting a BTP_MERGED_AWAY page
BTP_MERGED_AWAY pages keep a copy of their old tuples around,
which you mention are used by backward scans. This means its contents
must also be cleaned up by subsequent VACUUM runs, as the backwards
IOS may otherwise return TIDs that have been recycled and recieved new
indexed values. This cleanup can result in an empty page - which can
happen earlier than the XID horizon in the MergeID. Does this design
allow those pages to be reclaimed?

VACUUM will be taught to ignore the contents of BTP_MERGED_AWAY pages.
The entries inside are not live data, they are ghost copies cached for
exactly one case:
a backward scan that was positioned between R and L at the moment of the merge.
No other reader ever sees them. Forward scans see BTP_MERGED_AWAY and
skip via the right link.
New backward scans already read R (which now holds L's data) before
arriving at L, so they skip L too.
TID safety is guaranteed by MergeXID. The only scanner that can reach
L's "ghost copies" is one whose snapshot predates MergeXID. MVCC
guarantees that the heap rows those TIDs point to cannot be recycled
while any transaction predating MergeXID is still active, because
those rows are still visible to that transaction. Once MergeXID is no
longer visible to any active transaction, the page transitions to
HALF_DEAD normally. So VACUUM never needs to touch L's entries. The
page header does all the work.

d. Are BTP_MERGED_AWAY pages still part of the data structure?
So, is L still pointed to by both L's left sibling and R, or is it
immediately removed from the structure (or at least as immediate as a
HALF_DEAD page would)?
If it's kept in the structure for extended periods: Why?

L is unlinked from the parent as soon as it becomes BTP_MERGED_AWAY
and its key space will be assigned to R.
However, it does remain part of the leaf-level data structure (still
pointed to by L's left sibling and R).
This is necessary because backward scans that were positioned between
L and R during the merge still need to traverse left into L to read
the original data.
As soon as it is safe for L to become HALF_DEAD (the MergeXID horizon
is passed), it will be treated as a normal page deletion.

Best regards,
Salma El-Sayed

On Fri, May 8, 2026 at 10:40 AM Salma El-Sayed
<salmasayed182003@gmail.com> wrote:

A forward scanner that arrives at L after the merge sees BTP_MERGED_AWAY and follows through to R.
A backward scanner that arrives at R after the merge sees BTP_MERGED, reads R (which now contains L's data), and skips L entirely.

This seems OK for the first merge, but I think you need to be a lot
more explicit about what's going to happen after that. For instance,
what if you want to perform a merge on a page that is already marked
BTP_MERGED?

Or, for example, what happens if more splits happen after the merge?
Like if we have page A and then page B, we might mark A
BTP_MERGED_AWAY and B BTP_MERGED. Now suppose at the time this
happens, a scan is pointing to page A. Before the scan advances to
page B, that page gets split, so now we have: A(BTP_MERGED_AWAY) B0
(???) B1 (???). The problem is that we've already read page A, so we
need to use the logic that skips over tuples we may have already read
on both B0 and B1, both of which contain some of the tuples from B,
which now includes everything that we already read from A. So
presumably to make that work, we need to mark both B0 and B1 as
BTP_MERGED.

But if we do that, then there's no longer a 1:1 relationship between
BTP_MERGED_AWAY pages and BTP_MERGED pages. When we come to a
BTP_MERGED page, we don't know if it corresponds to some
BTP_MERGED_AWAY page we previously encountered, or some other
BTP_MERGED_AWAY page from long ago.

I'm not certain, but I am suspicious that using flag bits for this is
not going to work out. Maybe a flag bit is OK for the page that is
going away, because then it eventually transitions to half-dead like
you said. But for the surviving page, if that's just indicated by it
being marked BTP_MERGED, then eventually we can just end up with tons
of BTP_MERGED pages in the heap and there's nothing to unset those
bits. That's probably going to break something; if it doesn't, then it
seems unclear that BTP_MERGED needs to exists in the first place. I
feel like we might need to mark the surviving page using some kind of
indicator that "times out," like an XID or something, so that we don't
have to go back and clear BTP_MERGED flags later. But I don't really
know.

How should the merge process be triggered?

This seems really tricky. I think if the user has to manually run a
"try to merge pages" command or function, this functionality won't get
used very much. Ideally it would happen either automatically during
foreground operation, or as part of VACUUM. But that seems complicated
to make work, because there's a risk of merging pages too
aggressively, which could not only waste work but result in them being
split again soon afterward.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Thu, Jun 11, 2026 at 3:19 PM Robert Haas <robertmhaas@gmail.com> wrote:

On Fri, May 8, 2026 at 10:40 AM Salma El-Sayed
...

How should the merge process be triggered?

This seems really tricky. I think if the user has to manually run a
"try to merge pages" command or function, this functionality won't get
used very much. Ideally it would happen either automatically during
foreground operation, or as part of VACUUM. But that seems complicated
to make work, because there's a risk of merging pages too
aggressively, which could not only waste work but result in them being
split again soon afterward.

Totally agree, Robert!

Our goal on this project is:
1) Provably Solve the problem with ONLY a function (on demand)
2) Teaching AutoVacuum to reset BTP_MERGED* back to normal, after XID as
you suggested.
3) Experiment with various levels of how much work each function call
performs (we are being very conservative)

But the final progress might be:
A) A core function for people to run/use (fine tune control over how
aggressive)
B) Integrated into AutoVacuum (when it sees/makes mostly empty pages, it
spits out a request to merge them, out of process)
C) Integrated into AutoVacuum (it actually applies the merge). This is
currently a step way too far away.

But that is likely going to be over full versions of PG (probably years,
not months).

Kirk

On Thu, 11 Jun 2026 at 19:25, Salma El-Sayed <salmasayed182003@gmail.com> wrote:

Hi Matthias,

Thanks for your email and these detailed answers and questions.
Apologies for the delayed response, I am right in the middle of my
university final exams right now.

I am actively using your feedback to shape the design plan, but I
wanted to go ahead and address a couple of your specific questions
regarding BTP_MERGED_AWAY pages:

b. Deleting a BTP_MERGED_AWAY page
BTP_MERGED_AWAY pages keep a copy of their old tuples around,
which you mention are used by backward scans. This means its contents
must also be cleaned up by subsequent VACUUM runs, as the backwards
IOS may otherwise return TIDs that have been recycled and recieved new
indexed values. This cleanup can result in an empty page - which can
happen earlier than the XID horizon in the MergeID. Does this design
allow those pages to be reclaimed?

VACUUM will be taught to ignore the contents of BTP_MERGED_AWAY pages.
The entries inside are not live data, they are ghost copies cached for
exactly one case:
a backward scan that was positioned between R and L at the moment of the merge.
No other reader ever sees them. Forward scans see BTP_MERGED_AWAY and
skip via the right link.
New backward scans already read R (which now holds L's data) before
arriving at L, so they skip L too.
TID safety is guaranteed by MergeXID. The only scanner that can reach
L's "ghost copies" is one whose snapshot predates MergeXID. MVCC
guarantees that the heap rows those TIDs point to cannot be recycled
while any transaction predating MergeXID is still active, because
those rows are still visible to that transaction.

I don't think that's accurate. The index is not guaranteed to just
contain live or recently-dead rows: it is almost certainly going to
contain references to rows which are already dead to every session.
This is what VACUUM removes when it goes through index cleanup with
its calls into index_bulk_delete.

It is important to also note that it's not guaranteed that all current
dead rows are being cleaned up by a current index_bulk_delete() call -
if insufficient maintenance_work_mem was allocated, then only a subset
of currently dead rows will be included in the current
index_bulk_delete() call, and it's likely that cleanup will happen
again very soon.

So, if you merge a page that contains references to dead rows (which
you can't necessarily know when merging), the BTP_MERGED_AWAY page
might therefore contain references to rows which are (soon) ALL_DEAD
and would be cleaned up in the next VACUUM scan. So, if the page is
BTP_MERGED_AWAY with dead tuples that have been removed everywhere
else but whose tuples aren't cleaned up by vacuum by principle, then
that's an issue for scanners that took very long to continue on to
that page.

Once MergeXID is no
longer visible to any active transaction, the page transitions to
HALF_DEAD normally. So VACUUM never needs to touch L's entries. The
page header does all the work.

If a scan can return the items on a page (including BTP_MERGED_AWAY),
then vacuum *must* be able to clean up those items. If the index's
vacuum process doesn't clean up those items when requested, then the
index breaks the API contract of never returning TIDs that were
supposed to be removed in a completed ambulkdelete() call. In that
case, an index-only scan could encounter TIDs in the index that have
since been marked UNUSED by vacuum and gotten their page marked
ALL_VISIBLE; resulting in the dead entries being returned to the user.

d. Are BTP_MERGED_AWAY pages still part of the data structure?
So, is L still pointed to by both L's left sibling and R, or is it
immediately removed from the structure (or at least as immediate as a
HALF_DEAD page would)?
If it's kept in the structure for extended periods: Why?

L is unlinked from the parent as soon as it becomes BTP_MERGED_AWAY
and its key space will be assigned to R.
However, it does remain part of the leaf-level data structure (still
pointed to by L's left sibling and R).
This is necessary because backward scans that were positioned between
L and R during the merge still need to traverse left into L to read
the original data.
As soon as it is safe for L to become HALF_DEAD (the MergeXID horizon
is passed), it will be treated as a normal page deletion.

Could you expand on this "treated as" a bit more? Do you mean that
once the horizon has passed, the next time maintenance comes around
this page will be deleted like a normal empty page would during
vacuum? Or is it immediately considered dead?

Kind regards,

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

On Fri, Jun 12, 2026 at 11:07 AM Matthias van de Meent <
boekewurm+postgres@gmail.com> wrote:

On Thu, 11 Jun 2026 at 19:25, Salma El-Sayed <salmasayed182003@gmail.com>
wrote:
...

VACUUM will be taught to ignore the contents of BTP_MERGED_AWAY pages.
The entries inside are not live data, they are ghost copies cached for
exactly one case:
a backward scan that was positioned between R and L at the moment of the

merge.

No other reader ever sees them. Forward scans see BTP_MERGED_AWAY and
skip via the right link.
New backward scans already read R (which now holds L's data) before
arriving at L, so they skip L too.
TID safety is guaranteed by MergeXID. The only scanner that can reach
L's "ghost copies" is one whose snapshot predates MergeXID. MVCC
guarantees that the heap rows those TIDs point to cannot be recycled
while any transaction predating MergeXID is still active, because
those rows are still visible to that transaction.

I don't think that's accurate. The index is not guaranteed to just
contain live or recently-dead rows: it is almost certainly going to
contain references to rows which are already dead to every session.
This is what VACUUM removes when it goes through index cleanup with
its calls into index_bulk_delete.

It is important to also note that it's not guaranteed that all current
dead rows are being cleaned up by a current index_bulk_delete() call -
if insufficient maintenance_work_mem was allocated, then only a subset
of currently dead rows will be included in the current
index_bulk_delete() call, and it's likely that cleanup will happen
again very soon.

So, if you merge a page that contains references to dead rows (which
you can't necessarily know when merging), the BTP_MERGED_AWAY page
might therefore contain references to rows which are (soon) ALL_DEAD
and would be cleaned up in the next VACUUM scan. So, if the page is
BTP_MERGED_AWAY with dead tuples that have been removed everywhere
else but whose tuples aren't cleaned up by vacuum by principle, then
that's an issue for scanners that took very long to continue on to
that page.

Allow me to step in on this part of the conversation. BTP_MERGED_AWAY is
mostly a FLAG page.
That is really like a pre- BTP_HALF_DEAD page. NOBODY should be interested
in the contents.
Especially Vacuum. No NORMAL scans should read those contents.

We are leaving the contents on this "L" page (of L,R, and L+R notation),
for the 2 VERY specific Edge cases.
1) FWD Scans that already read "L", and finds the "L+R" instead of R. (it
was caught in the middle due to locks, etc).
It "knows" there are ghost copies left behind on "L" (BTP_MERGED_AWAY), and
it goes back, reads them,
and filters them out of the L+R results it just processed so the L records
are NOT duplicated.
2) BWD Scans that read "R" before the merge, then finds "L"
(BTP_MERGED_AWAY). It knows it did NOT
read the L+R page. So, like the previous logic, it can safely read the "L"
records.

outside of those two cases, which are clearly edge cases. NOBODY should
see those "ghost" records.
We are using them just to make the algorithm clean and efficient without
having to add something elsewhere
to handle the fixups.

Back to the question of VACUUM. And where your insight might be trying to
help us from making a terrible mistake.
My understanding is that there can be MANY "extra" references in any index
to records that have been LONG deleted.
And when the Table is read, those are removed from the result set (I
believe it's why index-only scans are limited to
mostly clean tables, freshly vacuumed, etc).

So, our assumption is that, if we envision a RACE condition, where VACUUM
is trying to remove the INDEX references.
BUT our scan is already past that BLOCK. Our scan does not restart, know
or care that vacuum wants to remove them
from the index (there is no "fixup" process required for a scan). And
that's our argument for keeping VACUUM ignorant
of anything on BTP_MERGED_AWAY. Because NO "normal" scan will read those
contents. Only one that was likely
blocked by our activity, and needs to "fix itself" (to avoid dupes or
skips). Any scan that runs after our lock doesn't care.
If they ran before our lock, and finished, they don't care. The 2 edge
cases care... Because it causes Skips (FWD scan),
and Dupes (BWD scan), otherwise.

We even avoid using BTP_HALF_DEAD in our case, to "keep this flag" for the
edge cases.
Technically if we could KNOW there are no more edge cases alive, we could
have VACUUM always force this
BTP_MERGED_AWAY into BTP_HALF_DEAD status. That was our original thought
process. But you see that
we cannot know we have an edge case... Until... No queries could possibly
see past our transaction marker.

Now, it's at this point that I wonder if we can actually just DELETE the
BTP_MERGED_AWAY page, by VACUUM.
But what we prefer, is that it gets marked half dead, and the
TXNID_Block_No is used to flip the BTP_MERGED page(s)
that follow (because there could have been page splits). And all of those
pages that are past that horizon, WILL BE
flipped back to NORMAL pages (from BTP_MERGED).

For now, for testing and validation... We want to get it working first,
and have it take a few steps so we
can watch the table "self-recover" from the merge with the Autovacuum.

This is why you will hear Salma defend vacuum "not looking" at the old "L"
records, certainly not changing them.
They are REQUIRED to be the snapshot for what was merged... Only for the 2
edge cases.

Thanks for the comments. And for the record, I am one of the mentors on
this GSoC for Salma.
(Today's lesson for her, is how to defend your position, while being
prepared for the public beat down (lol) where you might be wrong. Be wrong
out loud! You learn faster!)

Kirk

Hi Matthias,

Thanks for the response and detailed explanation.

Could you expand on this "treated as" a bit more? Do you mean that
once the horizon has passed, the next time maintenance comes around
this page will be deleted like a normal empty page would during
vacuum? Or is it immediately considered dead?

Regarding your question about how the page is "treated as" a normal deletion:

Because a BTP_MERGED_AWAY page is already unlinked from its parent, it
has essentially already completed the first stage of deletion. Once
the MergeXID horizon has safely passed, the page transitions to
HALF_DEAD and is handled exactly as described in the nbtree README for
the second stage of deletion:
"In the second-stage, the half-dead leaf page is unlinked from its
siblings. We first lock the left sibling (if any) of the target, the
target page itself, and its right sibling (there must be one) in that
order. Then we update the side-links in the siblings, and mark the
target page deleted."

To safely track this state transition, I need to store the MergeXID
and the blkno of the BTP_MERGED_AWAY page. As you pointed out
previously, adding these to the B-tree page header reduces available
space and risks backward incompatibility with max tuple sizes.
Given the constraints you mentioned, is modifying the header
completely off the table, or could we safely introduce this through a
new index version?

Also, I wanted to share my current implementation for forward scans
that were positioned between L and R before the merge. Since the
forward scan already read L, here is how I handle it:
When the scan encounters the BTP_MERGED page (R), it calls
_bt_readpage. After unlocking R, but before returning, it steps back
to read L (BTP_MERGED_AWAY). It saves L's tuples in a list inside
BTScanOpaqueData, compares them against the data just read from R
(so->currPos.items), and removes any duplicates.

Best regards,
Salma El-Sayed

On Tue, Jun 23, 2026 at 11:57 AM Kirk Wolak <wolakk@gmail.com> wrote:

Back to the question of VACUUM. And where your insight might be trying to help us from making a terrible mistake.
My understanding is that there can be MANY "extra" references in any index to records that have been LONG deleted.
And when the Table is read, those are removed from the result set (I believe it's why index-only scans are limited to
mostly clean tables, freshly vacuumed, etc).

It's not okay for VACUUM to ever fail to remove any TIDs from its
deadItems[] from the target index. If it fails to do that, the index
is already irretrievably broken; you cannot account for it at the scan
level.

Matthias explained why this is, but it boils down to this: that is a
core invariant, that all index AMs (with the possible exception of
BRIN) must follow at all times. It has nothing to do with what
concurrent scans might be doing when VACUUM runs; it's about
maintaining basic agreement between the index structure and the heap.
You can never allow the heap to recycle the same TID for a wholly
unrelated row/HOT chain, because doing so will result in the same TIDs
being reused for different logical rows some time after VACUUM runs.

Now, it's at this point that I wonder if we can actually just DELETE the BTP_MERGED_AWAY page, by VACUUM.
But what we prefer, is that it gets marked half dead, and the TXNID_Block_No is used to flip the BTP_MERGED page(s)
that follow (because there could have been page splits). And all of those pages that are past that horizon, WILL BE
flipped back to NORMAL pages (from BTP_MERGED).

For now, for testing and validation... We want to get it working first, and have it take a few steps so we
can watch the table "self-recover" from the merge with the Autovacuum.

This is why you will hear Salma defend vacuum "not looking" at the old "L" records, certainly not changing them.
They are REQUIRED to be the snapshot for what was merged... Only for the 2 edge cases.

Any design that lacks a completely airtight argument for why VACUUM
will reliably remove all of the TIDs from its deadItems[] in the
target index has zero chance of being accepted. Again, whether and how
that affects concurrent scans is irrelevant. The downstream problems
only start after VACUUM runs, when the heap starts to recycle TID
addresses that were supposed to be safe to recycle (safe because there
couldn't possibly be any references to the same TID left behind in
indexes).

--
Peter Geoghegan

On Tue, 23 Jun 2026 at 17:57, Kirk Wolak <wolakk@gmail.com> wrote:

On Fri, Jun 12, 2026 at 11:07 AM Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Thu, 11 Jun 2026 at 19:25, Salma El-Sayed <salmasayed182003@gmail.com> wrote:
...

VACUUM will be taught to ignore the contents of BTP_MERGED_AWAY pages.
The entries inside are not live data, they are ghost copies cached for
exactly one case:
a backward scan that was positioned between R and L at the moment of the merge.
No other reader ever sees them. Forward scans see BTP_MERGED_AWAY and
skip via the right link.
New backward scans already read R (which now holds L's data) before
arriving at L, so they skip L too.
TID safety is guaranteed by MergeXID. The only scanner that can reach
L's "ghost copies" is one whose snapshot predates MergeXID. MVCC
guarantees that the heap rows those TIDs point to cannot be recycled
while any transaction predating MergeXID is still active, because
those rows are still visible to that transaction.

I don't think that's accurate. The index is not guaranteed to just
contain live or recently-dead rows: it is almost certainly going to
contain references to rows which are already dead to every session.
This is what VACUUM removes when it goes through index cleanup with
its calls into index_bulk_delete.

It is important to also note that it's not guaranteed that all current
dead rows are being cleaned up by a current index_bulk_delete() call -
if insufficient maintenance_work_mem was allocated, then only a subset
of currently dead rows will be included in the current
index_bulk_delete() call, and it's likely that cleanup will happen
again very soon.

So, if you merge a page that contains references to dead rows (which
you can't necessarily know when merging), the BTP_MERGED_AWAY page
might therefore contain references to rows which are (soon) ALL_DEAD
and would be cleaned up in the next VACUUM scan. So, if the page is
BTP_MERGED_AWAY with dead tuples that have been removed everywhere
else but whose tuples aren't cleaned up by vacuum by principle, then
that's an issue for scanners that took very long to continue on to
that page.

Allow me to step in on this part of the conversation. BTP_MERGED_AWAY is mostly a FLAG page.
That is really like a pre- BTP_HALF_DEAD page. NOBODY should be interested in the contents.
Especially Vacuum. No NORMAL scans should read those contents.

We are leaving the contents on this "L" page (of L,R, and L+R notation), for the 2 VERY specific Edge cases.
1) FWD Scans that already read "L", and finds the "L+R" instead of R. (it was caught in the middle due to locks, etc).
It "knows" there are ghost copies left behind on "L" (BTP_MERGED_AWAY), and it goes back, reads them,
and filters them out of the L+R results it just processed so the L records are NOT duplicated.
2) BWD Scans that read "R" before the merge, then finds "L" (BTP_MERGED_AWAY). It knows it did NOT
read the L+R page. So, like the previous logic, it can safely read the "L" records.

outside of those two cases, which are clearly edge cases. NOBODY should see those "ghost" records.

My point is this: It is *exactly* a problem if BWD scans read L's data
if L's data is ignored by vacuum.

Consider this situation: L contains TIDs 1, 2, 3; R contains TIDs 4, 5, 6.

1. Session 1: Backward Index-Only scan finishes processing page R
2. Session 2: Deduplicates L + R, into R. L is marked BTP_MERGED_AWAY,
and contains remnants for (1, 2, 3). R now contains (1, 2, 3, 4, 5,
6), and is marked BTP_MERGED
3. Session 3: Vacuums the backing table, finds that TIDs 2, 3, 4 are
dead, and starts cleaning up indexes.
4. Session 3: As part of vacuum, cleans up page R, which now contains
only (1, 5, 6). L is untouched; contains (1, 2, 3).
5. Session 3: After finishing index cleanup; the LP_DEAD items are
removed from the heap, and all pages are marked all-visible;
6. Session 1: Continues the index-only scan. Finds page L, and returns
the remnants on that page L (1, 2, 3) to the IOS.
7. Session 1: IOS internally checks the visibility of the returned
tuples, finds the pages of those tids to be all-visible (see (5)), and
returns the TIDs and values associated with TIDs 1, 2, and 3, to the
higher scan node.

Note that in step (3), TIDs 2 and 3 are dead, and in step 5 they were
completely removed -- there shouldn't be any index scans that still
return those tuples (*). For all that the table knows, TIDs (2, 3, 4)
don't exist anymore. In step 7, however, they're suddenly visible,
because they weren't cleaned up from L by VACUUM.

To fix this; VACUUM *must* process page L, and remove the references
to TIDs 2 and 3, or otherwise mark those TIDs as "not to be returned
by scans", so that in step 6 the scan doesn't return TIDs 2 and 3 to
the IOS layer above.

(*) For Index-Only scans the original statement is accurate, but
normal Index scans (not IOS) will be able to return tuples after that
cleanup happened. However, instead of using the visibilitymap, those
scans will check the visibility of the rows on the heap page directly,
and will ignore (skip) invisible/missing line pointers.

We are using them just to make the algorithm clean and efficient without having to add something elsewhere
to handle the fixups.

Back to the question of VACUUM. And where your insight might be trying to help us from making a terrible mistake.
My understanding is that there can be MANY "extra" references in any index to records that have been LONG deleted.
And when the Table is read, those are removed from the result set (I believe it's why index-only scans are limited to
mostly clean tables, freshly vacuumed, etc).

Strictly speaking that's right, but indexes like btree, gist, spgist,
and hash, all have a guarantee that any tuple only has a single
location in the index at any point in time.
Scans may see the same TID pointing to a row (or the same TID pointing
to different versions of a row, or TIDs pointing to different versions
of different rows in case of tid reclamation through vacuum) several
times, but only one of those pointed-to rows can be visible to the
scan. The reason why it can see the same tid value several times is
because it takes time to traverse the index, and because the scan
doesn't have a snapshot view of the whole index. A scan only looks at
parts of the index at once, and the same tid value may be present at
different locations at different times, but only ever at one place in
the index at a time.

So, our assumption is that, if we envision a RACE condition, where VACUUM is trying to remove the INDEX references.
BUT our scan is already past that BLOCK. Our scan does not restart, know or care that vacuum wants to remove them
from the index (there is no "fixup" process required for a scan). And that's our argument for keeping VACUUM ignorant
of anything on BTP_MERGED_AWAY. Because NO "normal" scan will read those contents. Only one that was likely
blocked by our activity, and needs to "fix itself" (to avoid dupes or skips).

I think this argument is faulty; if only because scans (and queries
more generally) are not guaranteed to immediately run to completion
without stopping. The perfect example for that is an index scan that's
producing data for a cursor: Cursors may be paused for any amount of
time between any two amgettuple() calls.

Any scan that runs after our lock doesn't care.

Any scan that *starts* after the lock. Scans that started before the
lock but continue running after the lock *will* care.

And I'm not so sure about your claim that *any* scan doesn't care.
With scan boundary keys I think you may be right, but I'm yet to be
convinced that boundary keys provide sufficient performance to get
this into the tree.

If they ran before our lock, and finished, they don't care. The 2 edge cases care... Because it causes Skips (FWD scan),
and Dupes (BWD scan), otherwise.

Indeed.

We even avoid using BTP_HALF_DEAD in our case, to "keep this flag" for the edge cases.
Technically if we could KNOW there are no more edge cases alive, we could have VACUUM always force this
BTP_MERGED_AWAY into BTP_HALF_DEAD status. That was our original thought process. But you see that
we cannot know we have an edge case... Until... No queries could possibly see past our transaction marker.

Why do you need to read the TIDs from the MERGED_AWAY page? Can't you
keep just (and only just) the MERGED_AWAY status + its original key
range around, and use that to extract the moved tuples from the
_MERGED page (... and its successors in case of page splits of that
page)? It is probably a bit (lot) more effort, but it should avoid the
TID recycling issue mentioned above, in cases of backward scans.

For now, for testing and validation... We want to get it working first, and have it take a few steps so we
can watch the table "self-recover" from the merge with the Autovacuum.

What do you mean by "self-recover"? Recycle index pages and reduce in size?

This is why you will hear Salma defend vacuum "not looking" at the old "L" records, certainly not changing them.
They are REQUIRED to be the snapshot for what was merged... Only for the 2 edge cases.

I'm not convinced about that requirement being the right direction; we
can't afford to create a new known visibility bug just to fix known
scan edge cases for page merging.

Kind regards,

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

On Tue, Jun 23, 2026 at 1:53 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

On Tue, 23 Jun 2026 at 17:57, Kirk Wolak <wolakk@gmail.com> wrote:

Back to the question of VACUUM. And where your insight might be trying to help us from making a terrible mistake.
My understanding is that there can be MANY "extra" references in any index to records that have been LONG deleted.
And when the Table is read, those are removed from the result set (I believe it's why index-only scans are limited to
mostly clean tables, freshly vacuumed, etc).

Strictly speaking that's right, but indexes like btree, gist, spgist,
and hash, all have a guarantee that any tuple only has a single
location in the index at any point in time.

Minor clarification, for the benefit of others: the guarantee is that
the index cannot contain the same heap TID twice (which might point to
a hot chain with several versions).

Scans may see the same TID pointing to a row (or the same TID pointing
to different versions of a row, or TIDs pointing to different versions
of different rows in case of tid reclamation through vacuum) several
times, but only one of those pointed-to rows can be visible to the
scan.

I think that you meant that it can see different TIDs originating from
the same updated logical row.

A non-hot update can create 2 separate TIDs that point to different
versions of the same logical row. In that case, both TIDs must be
returned to the scan (assuming both have index tuple values that
satisfy the scan keys). This doesn't really matter to the index AM; it
doesn't know about updates at all.

What it boils down to is that the same TID must never exist in any 2
index tuples in the same index simultaneously. Currently, amcheck
cannot detect that condition because checking every index tuple
against every other one is inconvenient and expensive. However,
offering such a check would be useful; it wouldn't need to rely on
heap visibility information, as the simple fact that the same TID
appears a second time always indicates index corruption.

--
Peter Geoghegan

On Tue, 23 Jun 2026 at 20:16, Peter Geoghegan <pg@bowt.ie> wrote:

On Tue, Jun 23, 2026 at 1:53 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

On Tue, 23 Jun 2026 at 17:57, Kirk Wolak <wolakk@gmail.com> wrote:

Back to the question of VACUUM. And where your insight might be trying to help us from making a terrible mistake.
My understanding is that there can be MANY "extra" references in any index to records that have been LONG deleted.
And when the Table is read, those are removed from the result set (I believe it's why index-only scans are limited to
mostly clean tables, freshly vacuumed, etc).

Strictly speaking that's right, but indexes like btree, gist, spgist,
and hash, all have a guarantee that any tuple only has a single
location in the index at any point in time.

Minor clarification, for the benefit of others: the guarantee is that
the index cannot contain the same heap TID twice (which might point to
a hot chain with several versions).

Yes, I could have worded that better.

Scans may see the same TID pointing to a row (or the same TID pointing
to different versions of a row, or TIDs pointing to different versions
of different rows in case of tid reclamation through vacuum) several
times, but only one of those pointed-to rows can be visible to the
scan.

I think that you meant that it can see different TIDs originating from
the same updated logical row.

It could access and return the same TID twice, on multiple pages, if
the TID is recycled between the page accesses. But, as mentioned, at
most one of the rows indicated by the index' scan mechanism will be
MVCC-visible for the IndexScan executor node.

A non-hot update can create 2 separate TIDs that point to different
versions of the same logical row. In that case, both TIDs must be
returned to the scan (assuming both have index tuple values that
satisfy the scan keys). This doesn't really matter to the index AM; it
doesn't know about updates at all.

Except the indexUnchanged flag for aminsert() -which index AMs should
only use as a hint- but more generally, yes that's right.

What it boils down to is that the same TID must never exist in any 2
index tuples in the same index simultaneously.

Eventually, indeed, it boils down to this.

Kind regards,

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

On Tue, Jun 23, 2026 at 2:30 PM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

I think that you meant that it can see different TIDs originating from
the same updated logical row.

It could access and return the same TID twice, on multiple pages, if
the TID is recycled between the page accesses. But, as mentioned, at
most one of the rows indicated by the index' scan mechanism will be
MVCC-visible for the IndexScan executor node.

That might be true with SnapshotAny, but bringing visibility concerns
into this discussion doesn't seem useful.

The relevant invariant is that the same physical TID cannot appear
twice within the same index. It is useful to think of it as an
invariant that the index AM is directly concerned with (and to ignore
visibility stuff, which happens at a higher level, and shouldn't be of
concern to the index AM at all).

In general, nbtree page deletion (and merging underfull pages)
modifies a physical data structure to improve space efficiency. It
isn't relevant why VACUUM deleted some index tuples (making that free
space available and indirectly triggering deletion/merging).

Using XIDs for BTPageGetDeleteXid is just a convenient (though very
conservative) way to implement "the drain technique". It would still
be correct to implement it differently, provided this alternative
approach also ensures that no backend follows a downlink and ends up
on a wholly unrelated page due to concurrent deletion.

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 --
no scan can ever have an irredeemably bad picture of the tree
structure. But we don't fundamentally need to care about XIDs to make
that work -- this is a physical modification that's orthogonal to
logical/transaction considerations.

A non-hot update can create 2 separate TIDs that point to different
versions of the same logical row. In that case, both TIDs must be
returned to the scan (assuming both have index tuple values that
satisfy the scan keys). This doesn't really matter to the index AM; it
doesn't know about updates at all.

Except the indexUnchanged flag for aminsert() -which index AMs should
only use as a hint- but more generally, yes that's right.

That's just a hint used to trigger bottom-up index deletion, it really
isn't relevant.

--
Peter Geoghegan

On Tue, Jun 23, 2026 at 11:57 AM Kirk Wolak <wolakk@gmail.com> wrote:

On Fri, Jun 12, 2026 at 11:07 AM Matthias van de Meent <
boekewurm+postgres@gmail.com> wrote:

On Thu, 11 Jun 2026 at 19:25, Salma El-Sayed <salmasayed182003@gmail.com>
wrote:
...Thanks for the comments. And for the record, I am one of the mentors
on this GSoC for Salma.

(Today's lesson for her, is how to defend your position, while being

prepared for the public beat down (lol) where you might be wrong. Be
wrong out loud! You learn faster!)

Everyone. My apologies. Some people may not have detected the
sarcasm/humor in that last line.
Obviously this is NOT how this group works, and the moderators would not
tolerate it.

I stand by: "Be wrong out loud! You learn faster!"...

Because I certainly did!

Kirk

On Tue, Jun 23, 2026 at 4:46 PM Kirk Wolak <wolakk@gmail.com> wrote:

(Today's lesson for her, is how to defend your position, while being prepared for the public beat down (lol) where you might be wrong. Be wrong out loud! You learn faster!)

Everyone. My apologies. Some people may not have detected the sarcasm/humor in that last line.
Obviously this is NOT how this group works, and the moderators would not tolerate it.

Yeah, I don't think anybody's getting a beat down here. This is just
people discussing whether the algorithm as proposed is correct or
incorrect. Nobody's mad at Salma or at you, but a number of people (me
included, but on this topic my opinion isn't the one you should be
worrying about) think that the proposed algorithm is probably
incorrect -- and the vigor of their responses suggests, more than
anything, that they don't want anyone to waste a bunch of time on
something that will ultimately be a dead end. The fact that they care
enough to respond is a good sign, not a bad one.

From a certain point of view, the suspicion that the algorithm may be
incorrect is not at all surprising. The fact that we never merge
nbtree pages to improve space utilization is a limitation we've had
since I first got involved with PostgreSQL which was, at the risk of
dating myself, a long time ago. The fact that nobody's fixed yet means
it's probably really hard. The extremely intense discussion of page
deletion in the nbtree README also suggests the complexity of the
task: any concern that applies to page deletion probably also implies
in some way to page merging, and there are probably additional
complications that apply only to page merging, because page deletion
only involves empty pages, so there's no danger of seeing values
twice.

I suspect everyone here would love to see a solution to this problem,
but I would personally be beyond impressed if someone managed to come
up with even a working prototype for this in one summer. Even a
respectable amount of progress on figuring out an algorithm would be a
good result, IMHO.

I don't know what the rules for GSoC are, but if it's still possible
to switch to a different project, that might be worth considering. On
the other hand, there's certainly interesting work to be done on this.
I just don't see how anyone, no matter how smart or talented, could
show up and expect to get the algorithm completely right on the first
try. I'd be absolutely shocked if that happened. I've been shocked
before, of course: some time people do amazing things. But often
getting something like this right takes a lot of trial and error, or
just doesn't work out. That doesn't mean it isn't worth trying, but
having realistic expectations is good.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Fri, Jun 26, 2026 at 10:54 AM Robert Haas <robertmhaas@gmail.com> wrote:

From a certain point of view, the suspicion that the algorithm may be
incorrect is not at all surprising. The fact that we never merge
nbtree pages to improve space utilization is a limitation we've had
since I first got involved with PostgreSQL which was, at the risk of
dating myself, a long time ago. The fact that nobody's fixed yet means
it's probably really hard.

Page deletion is easily the most complicated part of the nbtree
design. That is a natural consequence of the absurdly permissive rules
for searchers under the Lehman & Yao design. Searchers never need to
lock more than one page at a time, on any level. But they can never
have an irredeemably bad picture of the tree structure, even with
concurrent page deletions.

In short, the eye-watering complexity of page deletion is the exact
cost you pay to completely avoid lock coupling with the Lehman & Yao
design. If you completely ignore page deletion (as in the original L&Y
paper), the concurrency rules are simple and intuitive. Most
individual nbtree code paths effectively do just that: they pretend
page deletion does not exist. Searchers can just move right (as with a
concurrent page split) when they land on a deleted page. Everything
works out because the real complexity is confined to the page
deletion/page recycling code.

Confining the complexity to the page deletion code is a very useful
property, and one that I *really* don't want to give up. I'm not
prepared to say that it could never make sense, but the bar for
accepting such a change is *very* high.

I suspect everyone here would love to see a solution to this problem,
but I would personally be beyond impressed if someone managed to come
up with even a working prototype for this in one summer. Even a
respectable amount of progress on figuring out an algorithm would be a
good result, IMHO.

I don't know what the rules for GSoC are, but if it's still possible
to switch to a different project, that might be worth considering.

+1

--
Peter Geoghegan

Hi hackers,

We want to share a new design we are working on for handling page merges.

Instead of using BTP_MERGED_AWAY simply as a cache, this design
repurposes it to direct scans for merge recovery and to hold the
merge_xid in the same way deleted pages hold safexid.

This design is based on the fact that the currPos.items array is only
overwritten by _bt_readpage, meaning the data remains intact until the
next _bt_readpage call for the subsequent page.

The core changes are centralized in _bt_readnextpage.

The following fields are added to BTScanOpaqueData:
bool skipMergeRecovery;
bool needMergeRecovery;
ItemPointerData savedMergeTids[MaxTIDsPerBTreePage];
int nSavedMergeTids; /* number of TIDs in the array */

Here is how the scan logic works across a sequence of pages:

*FORWARD SCAN*

Scenario: L(MA) <--> R(M) <--> A(M) <--> B(MA) <--> C(HD) <--> D(M)
(MA = MERGED_AWAY, M = MERGED, HD = HALF_DEAD)

subsequent MERGED pages happen due to the split of page R.

1) The scan steps into L and finds the MA flag. It skips L and sets
skipMergeRecovery = true.

2) The scan steps into R and finds the M flag. It checks skipMergeRecovery:
a) If true: It reads R as a normal page. Page A is treated the same way.
b) If false:
- currPos.items still holds the tuples read from L. We save
these items into savedMergeTids (we only do this step for the first M
page in the merge group).
- Read R by calling _bt_readpage.
- Loop through currPos.items for R and remove any item that
exists in savedMergeTids.
- Return tuples to the caller if any remain after filtering.
Otherwise, continue to the next M page in the group.

3) The scan steps into B (MA) and does the same as L.
4) The scan steps into C (HD) and skips it.
5) The scan steps into D (M) and does the same as R.

skipMergeRecovery is reset to false as soon as the scan steps onto a
normal (non-M, non-MA) page, making the scan ready for the next merge
group.

*BACKWARD SCAN*

Scenario: L(MA) <--> R(M) <--> A(M) <--> B(M) <--> C(normal page)

Definitions:
- skipMergeRecovery: The scan read a M page after a merge occurred,
requiring no recovery.
- needMergeRecovery: The scan read a M page before the merge, then
stepped into an MA page. The flag is set to true to start recovery.
Stepping into an MA page again while true means recovery is finished.

1) The scan steps into L:
a) If skipMergeRecovery OR needMergeRecovery is true: The scan read
merged pages and will skip this MA page. Reset both booleans to be
ready for the next merged group.
b) If neither is true: The scan read R before the merge, and
currPos.items still has the data read from it.
- Save these items into savedMergeTids.
- Walk forward until reaching C (the first page with no M flag).
- Set blkno = B, and lastcurrblkno = C (needed to recover from
splits in the backward scan).
- The scan continues walking backward from B.

2) The scan steps into B, A, or R:
a) If needMergeRecovery is false: The simplest case. Read the page
normally and set skipMergeRecovery = true, so that when the scan steps
left onto the MA tombstone, it knows to skip it cleanly.
b) If needMergeRecovery is true: The scan is in merge recovery.
- Call _bt_readpage to read the page.
- Loop through currPos.items and remove any item that exists in
savedMergeTids.
- Return tuples to the caller if any remain after filtering.
Otherwise, continue to the next M page in the group.

*VACUUM AND FLAG LIFECYCLE*

MERGED pages cannot be merged again until the flag is reset.

The MERGED_AWAY flag serves as a separator between merged groups and
directs scans to recover from the merge operation. Therefore,
MERGED_AWAY must stick around until all MERGED flags in its merge
group are reset.

Any MERGED page can be deleted at any point if VACUUM decides to
delete it, without breaking the algorithm. It is impossible to have a
normal page between MA and M pages. Having an HD page in between is
not an issue as long as the MERGED flag is never reset in that HD
page.

We can use the MERGED_AWAY page to save merge_xid as the page content,
exactly the same way safexid works for deleted pages.

When VACUUM steps into a MERGED_AWAY page and the transaction horizon
has passed, it MUST reset all MERGED flags first. VACUUM must locate
the end of the MERGED group, then walk backward to reset all pages
(similar to how the backward scan recovers). This guarantees a normal
page will never exist between MA and M pages.

* Resetting a BTP_MERGED flag means clearing it from btpo_flags,
leaving the page as a standard BTP_LEAF page again.
* Resetting a BTP_MERGED_AWAY will make it HALF_DEAD.

Best,
Salma El-Sayed

On Tue, 30 Jun 2026 at 19:37, Salma El-Sayed <salmasayed182003@gmail.com> wrote:

Hi hackers,

We want to share a new design we are working on for handling page merges.

Instead of using BTP_MERGED_AWAY simply as a cache, this design
repurposes it to direct scans for merge recovery and to hold the
merge_xid in the same way deleted pages hold safexid.

[... scan mechanism stuff, which I'll comment on below]

*VACUUM AND FLAG LIFECYCLE*

MERGED pages cannot be merged again until the flag is reset.

The MERGED_AWAY flag serves as a separator between merged groups and
directs scans to recover from the merge operation. Therefore,
MERGED_AWAY must stick around until all MERGED flags in its merge
group are reset.

This seems like it's the right idea.

Any MERGED page can be deleted at any point if VACUUM decides to
delete it, without breaking the algorithm. It is impossible to have a
normal page between MA and M pages. Having an HD page in between is
not an issue as long as the MERGED flag is never reset in that HD
page.

What happens when MERGED_AWAY's only MERGED sibling is deleted?
Presumably MERGED_AWAY can be cleaned up then, too, because its tuples
were removed, too?

We can use the MERGED_AWAY page to save merge_xid as the page content,
exactly the same way safexid works for deleted pages.

Yep.

When VACUUM steps into a MERGED_AWAY page and the transaction horizon
has passed, it MUST reset all MERGED flags first. VACUUM must locate
the end of the MERGED group, then walk backward to reset all pages
(similar to how the backward scan recovers). This guarantees a normal
page will never exist between MA and M pages.

Yes.

* Resetting a BTP_MERGED flag means clearing it from btpo_flags,
leaving the page as a standard BTP_LEAF page again.
* Resetting a BTP_MERGED_AWAY will make it HALF_DEAD.

In general I agree with the page lifecycle mechanism; I think it's the
only way to make this work.

---------

Now, on to the scan component:

This design is based on the fact that the currPos.items array is only
overwritten by _bt_readpage, meaning the data remains intact until the
next _bt_readpage call for the subsequent page.

The core changes are centralized in _bt_readnextpage.

The following fields are added to BTScanOpaqueData:
bool skipMergeRecovery;
bool needMergeRecovery;
ItemPointerData savedMergeTids[MaxTIDsPerBTreePage];
int nSavedMergeTids; /* number of TIDs in the array */

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.

Below some comments on the scan logic:

Here is how the scan logic works across a sequence of pages:

*FORWARD SCAN*

Scenario: L(MA) <--> R(M) <--> A(M) <--> B(MA) <--> C(HD) <--> D(M)
(MA = MERGED_AWAY, M = MERGED, HD = HALF_DEAD)

subsequent MERGED pages happen due to the split of page R.

1) The scan steps into L and finds the MA flag. It skips L and sets
skipMergeRecovery = true.

2) The scan steps into R and finds the M flag. It checks skipMergeRecovery:
a) If true: It reads R as a normal page. Page A is treated the same way.

This can be unsafe if you don't check that L is still the left-link of
R: If L got deleted (its fxid horizon expired and R got a new left
sibling) and the new left sibling got merged into R before we scan it,
then the data on L could contain items that we'd already scanned when
we accessed the now newly minted MERGED_AWAY page that's now R's left
sibling.

This can be detected by detecting that L is no longer the left sibling
(and "merge group separator") of R. Note that R (in this specific case
of R being the immediate sibling of L) cannot get a new left sibling
other than through concurrent deletion of L, which can allow the
former sibling of L to be merged into R.

b) If false:
- currPos.items still holds the tuples read from L. We save
these items into savedMergeTids (we only do this step for the first M
page in the merge group).

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?

- Read R by calling _bt_readpage.
- Loop through currPos.items for R and remove any item that
exists in savedMergeTids.
- Return tuples to the caller if any remain after filtering.
Otherwise, continue to the next M page in the group.

3) The scan steps into B (MA) and does the same as L.
4) The scan steps into C (HD) and skips it.

Shouldn't this page C be HD+M, given that it is a merged page in the
process of being deleted? Or did I miss something?

5) The scan steps into D (M) and does the same as R.

skipMergeRecovery is reset to false as soon as the scan steps onto a
normal (non-M, non-MA) page, making the scan ready for the next merge
group.

(see my comment above for the race condition that should be addressed)

*BACKWARD SCAN*

Scenario: L(MA) <--> R(M) <--> A(M) <--> B(M) <--> C(normal page)

Definitions:
- skipMergeRecovery: The scan read a M page after a merge occurred,
requiring no recovery.
- needMergeRecovery: The scan read a M page before the merge, then
stepped into an MA page. The flag is set to true to start recovery.
Stepping into an MA page again while true means recovery is finished.

1) The scan steps into L:
a) If skipMergeRecovery OR needMergeRecovery is true: The scan read
merged pages and will skip this MA page. Reset both booleans to be
ready for the next merged group.

What if L and R were M pages when the scan accessed R, but
subsequently their MA page (left of L) was deleted and L got merged
into R?
Then we'd skip the keyspace that was merged from L into R, right? I
think it's the same (but inverse) issue as I'd mentioned above, but
more difficult to correctly detect because the siblings pointers of R
don't change, nor do L's.

b) If neither is true: The scan read R before the merge, and
currPos.items still has the data read from it.
- Save these items into savedMergeTids.
- Walk forward until reaching C (the first page with no M flag).
- Set blkno = B, and lastcurrblkno = C (needed to recover from
splits in the backward scan).
- The scan continues walking backward from B.

This (b) confused me a bit.

IIUC, the order of operations for this condition to be hit is:

1. R was scanned;
2. L got merged into R; [L=MA, R=M]
3. R split into R, A, and B; [R=M, A=M, B=M]
4. the scan accesses L (and condition B is met, and the described
branch is executed).

Is that right?

2) The scan steps into B, A, or R:
a) If needMergeRecovery is false: The simplest case. Read the page
normally and set skipMergeRecovery = true, so that when the scan steps
left onto the MA tombstone, it knows to skip it cleanly.
b) If needMergeRecovery is true: The scan is in merge recovery.
- Call _bt_readpage to read the page.
- Loop through currPos.items and remove any item that exists in
savedMergeTids.
- Return tuples to the caller if any remain after filtering.
Otherwise, continue to the next M page in the group.

... and this is safe, because all M pages must be split _after_ the
merge happened, so they all contain the keyspace of [L+R], and the
tuples of R we'd already scanned are excluded. Am I understanding this
correctly?

-------

I have thought up an alternative approach with an incomplete scan
approach (more about "partial" below) that doesn't need to backtrack
and shouldn't have concurrent merge problems when we're already
scanning a merged range:

When merging pages, we attach the MergeID (MA block number, but
optionally with its NextFullTransactionId recycling horizon) to each
of the tuples we move into the right page (as "MERGED_AWAY_TUPLE"
tuples), in a way similar to how we have posting list tuples
(INDEX_ALT_TID_MASK+BT_IS_POSTING) and how we add TIDs to pivot tuples
(INDEX_ALT_TID_MASK+BT_PIVOT_HEAP_TID_ATTR). Vacuum can clean these
tuples away as normal, the merge id is used only by scans to determine
which page the merged tuple came from and decide whether to include it
based on that information.

This can then be used by forward scans to determine that it needs to
skip these tuples, when it did not see the MERGED_AWAY page _after_ it
was merged.
For backward concurrent-merge-recovery, we would keep a copy of the
old tuples around on the MERGED_AWAY page; whilst allowing VACUUM to
reclaim those tuples. These tuples will be accessed only by backward
scans who were stepping from R to L whilst the merge was going on.

Vacuum cleanup of the tuples can turn the page HALF_DEAD once the last
tuple is deleted, which can get the page removed from the tree
structure before the full expiration of the FXID horizon - a minor but
important optimization: An MA page without this would remain "in use"
for two vacuum horizons' timespans, whereas a normal page deletion
"only" takes one. Merging *could* therefore cause a page to take about
one more vacuum horizon in time before it is free for reuse, and so it
could hinder (not help) reclamation of pages.

Cleaning up the MERGED flag also means cleaning/removing the
MERGED_AWAY_TUPLE status off of any index tuples on those MERGED
pages. All MERGED_AWAY_TUPLE tuples must have the block id of the
associated MERGED_AWAY page.

So, we'd have the following:

BTScanPosData {
+  BlockNumber last_merged_away; /* FWD scans */
+  BlockNumber last_known_merged; /* BWD scans */
}

For FWD scans, we'd add the following ahead of processing any data on a page:

IF page is MERGED_AWAY
scan->last_merged_away = currentBlockNo;
(ignore the page)
ELSEIF page is MERGED
scan->last_known_merged = currentBlockNo;
read page data
ELSE /* page neither MERGED_AWAY nor MERGED: normal, or HALF_DEAD */
/* reset merge-related scan state */
scan->last_merged_away = InvalidBlockNo.
scan->last_known_merged = InvalidBlockNo;
read page data
ENDIF

Adjust _bt_readpage with
[...]
IF page_item is MERGED_AWAY_TUPLE and page_item->merged_away_block
!= scan->last_merged_away:
skip page_item; [^1]
ENDIF
[...]

[^1]: This allows us to avoid returning duplicates when the following
pattern occurs

(start): L1 (MA) <-> R1(M) <-> R2 (M),
s1: Scan L1
s1: Scan R1
[A]
s1: Scan R2
[B]

s2: Cleanup L1;
s2: Merge R1+R2;
(state: R1 (MA) <-> R2 (M))

There is no externally apparent distinction for s1 between when the
steps for s2 happen at [A] vs [B]; R2's sibling pointers would be the
same.
R1's tuples having been tagged with its block number allows us to
remove them from the set, as the scan knew about L1's merge, but not
R1's, and thus can skip R1's merged items (any tuples from that page
were either already returned or recently concurrently inserted).

For full BWD scans, you'd add the following to _bt_readpage:

IF page is MERGED
scan->last_known_merged = currentBlockNo;
_bt_readpage() as normal, if not deleted
ELSEIF page is MERGED_AWAY
scan->last_merged_away = currentBlockNo;
IF scan->last_known_merged != block->right_sibling
Scan page->remaining_items as if they were live /* recovers from
the concurrent merge */
ENDIF
ELSE /* page neither MERGED_AWAY nor MERGED: normal, or HALF_DEAD */
/* reset merge-related scan state */
scan->last_merged_away = InvalidBlockNo.
scan->last_known_merged = InvalidBlockNo;
_bt_readpage() as normal
ENDIF

Note: There is one major item in this algo that I haven't yet
considered and that would definitely cause issues: What happens when
you change scan directions somewhere in between pages in a merge
range? As written, it'd cause the tuples from the merge range's
MERGED_AWAY page to be skipped when going FWD, whilst they'd be
included in the BWD portion of the scan, and we really can't have
that. Something that's related to this, is determining what should
happen when you start your scan on a MERGED page, which I've also not
yet figured out.

I think there is an elegant solution to be found to these issues, but
I have not figured the details in the hours I've spent thinking about
this approach. The main issue (I think) is figuring out how to
correctly invert the direction of the scan; I suspect it needs a bit
more state tracking but I'm yet not sure what and where.

Overall, it's really great to see work being done on this hard
problem. Good job so far!

Kind regards,

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

On Fri, Jun 26, 2026 at 10:54 AM Robert Haas <robertmhaas@gmail.com> wrote:

On Tue, Jun 23, 2026 at 4:46 PM Kirk Wolak <wolakk@gmail.com> wrote:

(Today's lesson for her, is how to defend your position, while being

prepared for the public beat down (lol) where you might be wrong. Be wrong
out loud! You learn faster!)

... The fact that they care
enough to respond is a good sign, not a bad one.

...

I suspect everyone here would love to see a solution to this problem,
but I would personally be beyond impressed if someone managed to come
up with even a working prototype for this in one summer. Even a
respectable amount of progress on figuring out an algorithm would be a
good result, IMHO.

Okay, first, thanks for the thoughtful response(s) from everyone!

As for changing the GSoC project. Nah... We don't mind hard. Our
fallback position always was that the project
will be successful if it changed the discussion and made it "SEEM"
possible, and left behind the "currently unstated requirements"

Also, we have almost 7 full weeks to the mid-terms, and at this point, we
have a rough prototype, and will have the Vacuum Cleanup
process before the mid-term (it's a 22 week long project, ending in
November). We are crossing our Ts in this process, but will provide some
PoC code in order to garner "Feedback" once the vacuum and the complete
life cycle is handled.

To be clear. Our goal is the 80/20 level implementation. Something that
is provably correct, has very little impact on normal scans, etc.
We only work on LEAF nodes... Because that's where the 80/20 lays for
now. Honestly, with all of our restrictions, it will take MANY passes to
remove all of the bloat we can. The upside of this approach was
ACCIDENTAL... That it probably fits better INSIDE of autovacuum! (Again,
beyond our current scope).

We have a lot of hurdles to clear. Many of them, we probably do not even
know yet. But the feedback so far has helped us to rethink, rewrite and
improve the logic (no ghost records on the L page, no extra data required
on the BTP_MERGED pages).

Also, we have an assumption that we will not delete BTP_MERGED[_AWAY] pages
until the "Family" of leaf nodes have been reset back to normal. TBH, the
visibility horizon on a future delete must be after the visibility horizon
on the cleanup process. (Currently, the existence of a half_dead page in
the middle would break assumptions). But since it is vacuums job to reset
these to normal pages, as it does so, it can also start marking them
half_dead and ultimately remove them. (We are still studying Vacuum, so if
I sound like I am speaking tongues to those who KNOW better... Forgive
me. It's a high-level statement).

Suffice it to say. We are quite happy with the progress so far.

Kirk

On Fri, Jun 26, 2026 at 11:50 AM Peter Geoghegan <pg@bowt.ie> wrote:

On Fri, Jun 26, 2026 at 10:54 AM Robert Haas <robertmhaas@gmail.com>
wrote:
...

Page deletion is easily the most complicated part of the nbtree
design. That is a natural consequence of the absurdly permissive rules
for searchers under the Lehman & Yao design. Searchers never need to
lock more than one page at a time, on any level. But they can never
have an irredeemably bad picture of the tree structure, even with
concurrent page deletions.

In short, the eye-watering complexity of page deletion is the exact
cost you pay to completely avoid lock coupling with the Lehman & Yao
design. If you completely ignore page deletion (as in the original L&Y
paper), the concurrency rules are simple and intuitive. Most
individual nbtree code paths effectively do just that: they pretend
page deletion does not exist. Searchers can just move right (as with a
concurrent page split) when they land on a deleted page. Everything
works out because the real complexity is confined to the page
deletion/page recycling code.

Yes, and our solution may seem Naive. Our approach has the drawback that
it SLOWS DOWN page deletion,
and keeps it where it currently is. We are asking vacuum to NOT delete
LEAF pages that we have "MERGED".
That MERGED pages are in a repair state until nobody LEFT can see that
transition. Then vacuum flips them
back to normal pages. (BTP_MERGED_AWAY would become BTP_HALF_DEAD). And
the NEXT vacuum would
delete that page as normal. We chose this approach for PURE Simplicity of
proving correctness. By making sure
our MERGED pages do not get shredded until the "merge event" is over... We
keep things simple. While not as
bad of an idea as "eventual consistency" (IMO), it draws a line in the
sand. We also will NOT attempt to MERGE
pages that are currently in MERGED status... As that would break things.

This will cause vacuum to take more passes to clean everything up. But we
believe it is proveable this way.
Our goal, of course, is that this is all "naturally" built into autovacuum
at some point. Where it deletes 99%
of the entries on a page, and it can apply a proven process to "merge" the
1% into the next page and flag everything.

It's at this point, that doing this in SMALL increments makes the most
sense. And only merging 2 pages prevents
taking new lock chains that could cause issues. Furthermore those 2 pages
must have the same parent. Another
limitation, but we don't believe it is a major hurdle more than it is a
great safety feature.

We are truly trying to limit "extra" work to the edge cases, and normal
scans should not concern themselves.

...

I suspect everyone here would love to see a solution to this problem,

but I would personally be beyond impressed if someone managed to come
up with even a working prototype for this in one summer. Even a
respectable amount of progress on figuring out an algorithm would be a
good result, IMHO.

I don't know what the rules for GSoC are, but if it's still possible
to switch to a different project, that might be worth considering.

+1

LOL. It's hard to say if you did the +1 for the GSoC comment or the
"combination" which I assume.
It was addressed previously. We march forward! (And we continue to learn
about the 3rd rails in this process!)

Again, we appreciate the feedback. Keep it coming. I know seeing the code
will help.
Also, as we do this, it needs to be well documented... We will have to
settle on some nomenclature...
(BTP_MERGED_AWAY -> BTP_MERGED ... : Can we call this a MERGE SET? While
we only create 1 BTP_MERGED page.
we know page splits can and will happen, so there can be many. No other
NON-MERGE pages are allowed between)

Kirk
PS: I will let Salma speak to the code details.