MIME-Version: 1.0
References: <11A59C0C-A8C8-4642-8493-292D5DF8311D@yandex-team.ru>
 <CAEze2Wg2a8LQDRocVPa7Df2qXQLrTz-xSu1k3xP3x_6ABVo1Jw@mail.gmail.com>
 <CACLU5mRude0L5psEj5WS0DVDv=AHN0McfZBKV5eBoW0JqwwZDA@mail.gmail.com> <CAKw2Pb2wV=L4yeAqj27wJ1wptHt1mnBaQ5t4YuLLe+M5aU6ESg@mail.gmail.com>
In-Reply-To: <CAKw2Pb2wV=L4yeAqj27wJ1wptHt1mnBaQ5t4YuLLe+M5aU6ESg@mail.gmail.com>
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: Fri, 27 Feb 2026 13:06:50 +0100
Message-ID: <CAEze2WhPwEAszAOV+3_Oc63V=8JcnsY_4FD3XRLzRi0q0nNdUA@mail.gmail.com>
Subject: Re: [WiP] B-tree page merge during vacuum to reduce index bloat
To: Madhav Madhusoodanan <madhavmadhusoodanan@gmail.com>
Cc: Kirk Wolak <wolakk@gmail.com>, Andrey Borodin <x4mmm@yandex-team.ru>, 
	pgsql-hackers <pgsql-hackers@postgresql.org>, Nikolay Samokhvalov <nik@postgres.ai>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://www.postgresql.org/message-id/CAEze2WhPwEAszAOV%2B3_Oc63V%3D8JcnsY_4FD3XRLzRi0q0nNdUA%40mail.gmail.com>
Precedence: bulk

On Thu, 26 Feb 2026 at 22:03, Madhav Madhusoodanan
<madhavmadhusoodanan@gmail.com> wrote:
>
> On Tue, Aug 26, 2025 at 2:11=E2=80=AFPM Kirk Wolak <wolakk@gmail.com> wro=
te:
> > I do have a question, one of the IDEAS we discussed was to ADD a new pa=
ge that combined the 2 pages.
>
> Would the flow then be as follows? Please correct me if I'm wrong:
> Start: Parent page P, with adjacent child pages A -> B -> C -> D.
> Pages B and C are sparse enough and are about to be merged.
> 1: Acquire lock on pages B and C
> 2: Create a new page N, which copies the tuples in pages B and C
> 3: Acquire lock on parent page P, update the separator keys in P,
> release lock on P
> 4: Update pointers such that pages link like so: A -> N -> D
> 5: Release lock on pages B and C

That is one part of the picture (the merging part), but it's missing a
lot of details:
- How do concurrent workloads (index scans, backwards index scans,
index insertions) detect and recover from concurrent merges when they
step through pages?
- Do you have a theory or proof of correctness for the above?
- Can this scheme be implemented without adding significant overhead
to current workloads that don't benefit significantly from the new
feature?

One example for a problem with the given flow: where (and how) do you
update the sibling pointers in pages A (to N from B) and D (to N from
C)?
You haven't explicitly locked pages A and D by the time you get to
step 4, even though locking pages is critical to guarantee correct and
safe operations. Simply locking them in step 4 isn't sufficient, as
another process may have locked page A in preparation for a split,
which would then be waiting to get a lock on page B. If you've already
locked page B before locking page A, you'll have a deadlock.

Additionally, how does this work when you find out in step 3 that your
pages B and C each are linked to from a different parent page? You'd
have to update both parent pages, but that would also require locking
more than just the one parent page per level that currently gets
locked during page deletion.


Kind regards,

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