Re: Randomize B-Tree page split location to avoid oscillating patterns

Hi Dmitry, Peter, Andres,

On Tue, Jun 16, 2026 at 10:13 AM Dmitry Dolgov wrote:
> We search either until all the split points are evaluated, or we've
> collected 20% of all possible locations in the list of equally good
> split points.

I like Peter's formulation that the random choice should only be among
split points that are equally good according to the existing criteria.
I do not think v2 quite guarantees that yet.

state->splits is ordered by distance from the desired space balance, not
by _bt_split_penalty(). The loop can collect 20% of locations with the
best penalty seen so far and stop before reaching a lower penalty later
in the interval. The existing early exit is safe because it only stops
at perfectpenalty, which is a known lower bound.

There is also a special case in SPLIT_MANY_DUPLICATES. That strategy
widens the interval to the whole page, but still relies on delta order to
pick the nearest location with the required penalty. Randomizing among
equal-penalty locations changes that policy and might also avoid the
existing protection against repeatedly leaving unusable free space.

Would it be simpler to initially restrict randomization to
SPLIT_DEFAULT leaf splits, examine the whole existing interval, and use
reservoir sampling among locations with the true minimum penalty? That
would need no extra array and would preserve suffix truncation exactly.
The existing default interval is deliberately narrow, so I would first
measure the cost of scanning it completely before adding an early exit.

On Mon, Apr 27, 2026 at 7:49 PM Andres Freund wrote:
> Couldn't we instead release the lock on the page, acquire an empty page,
> reacquire the lock, recheck that the split is still needed and, if so,
> split the page without needing to do IO while holding the lock?

Releasing and reacquiring the page lock sounds somewhat risky to me. A
concurrent inserter may change the page or split it, so this turns into a
restart protocol, with an acquired page that may no longer be needed.

Could we instead keep a small reserve of pages that can be acquired
without victim writeback or relation extension, replenished in the
background or in batches? Heap already uses ExtendBufferedRelBy() to
extend by multiple blocks and makes the extra pages available through a
BulkInsertState or the FSM, while _bt_allocbuf() requests exactly one
page. I am not sure whether a reserve belongs in bufmgr, the FSM, or the
access method, but it might avoid changing the B-tree locking protocol.

Thank you!

Best regards, Andrey Borodin.