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

> On Sat, Aug 29, 2026 at 01:57:04PM -0400, Peter Geoghegan wrote:
> 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

Here is the new versions. I've compared the reservoir sampling approach
with keeping an array of split locations, and in terms of performance in
my tests it looks like the former is only marginally faster than the
latter one (the test was a single-column integer index under insert-only
workload, where the size of the locations array gew up to ~30). But
eventually I've decided to stick to it, since it felt a bit more
naturally fitting to the code flow around.

I've also added a simple test to it. Originally I was already preparing
a new injection point and more elaborate test, only to realize that it
would be silly to verify that the split point is more variable now.
Instead the decision was to verify the end result -- more variable free
space distribution across index pages via building a histogram for it
and checking how many buckets we end up with.