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

On Sat, Aug 29, 2026 at 1:38 PM Andrey Borodin <x4mmm(at)yandex-team(dot)ru> wrote:
> Yes. The idea makes sense to me in general, with the initial scope restricted
> to SPLIT_DEFAULT leaf splits. Picking randomly only among locations with the
> true minimum penalty preserves the existing suffix-truncation criterion,
> while the existing balance interval keeps every candidate reasonably close
> to the target occupancy.

+1

> I would leave SPLIT_MANY_DUPLICATES and internal pages unchanged until we
> have evidence that randomization helps them without weakening their current
> policies.

+1. I doubt that SPLIT_MANY_DUPLICATES is a good candidate for any
kind of randomized choice. It's only used when we have no choice but
to accept a lopsided split to keep a large group of duplicates
together on the same leaf page. Using an *even more* lopsided split
point is very risky because there's no reason to believe we'll
converge on fillfactor% utilization over time.

> The remaining question for the initial patch is
> empirical. Randomization deliberately lets some pages reach their next split
> earlier, spreading that work over time. The reduction in tail latency should
> be statistically significant, while the resulting reduction in average page
> occupancy should be statistically insignificant. The idea makes sense to me.

When I developed the parts of nbtsplitloc.c that deal with suffix
truncation (including the related handling of large groups of
duplicates), I found it useful to mostly ignore fixed CPU costs
earlier on. It was more important to develop the right general
approach, based on a set of realistic-ish benchmarks. The test results
were perfectly deterministic, and I only cared about space
utilization, so iterating was fairly easy. I was able to deal with
added fixed costs later on (actually, I don't think that they were
ever really a problem).

My guess is that a similar approach will work best here. The only
notable difference is that the primary goal here is to make the rate
of page splits steady over time (where the unit of time is each
inserted tuple). Space utilization will still matter, and it is
something to keep an eye on early, but only to avoid regressions;
there's no reason to expect it to improve.

--
Peter Geoghegan