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

> On Mon, Aug 24, 2026 at 02:22:46PM +0300, Andrey Borodin wrote:

Thanks for looking into it.

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

v2 does not rely on the split points being sorted anymore, but reaching
20% before finding even better split location is indeed a bug in the
algorithm. I have to adjust the last condition to be something like
"we've reached 20% and it's a perfectpenalty", which will be equivalent
to the original implementation. Btw, I think the second approach,
nicknamed "shifted interval", is not affected by this since it uses very
same logic as in the original loop.

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

Yeah, I've actually concentrated my efforts on SPLIT_DEFAULT and haven't
tested other strategies, so it sounds reasonable to apply randomization
only to this strategy.

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

If I got you correct, we still would need to keep locations with the
true minimum penalty, so this part sounds similar to what already
happens in the v2.