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

> On Tue, Aug 25, 2026 at 04:27:25PM +0500, Andrey Borodin wrote:
> > 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.
>
> We only need to keep one selected location and the number of equally
> good locations seen so far. In pseudocode:
>
> if (penalty < bestpenalty)
> bestpenalty = penalty, selected = i, nmatches = 1;
> else if (penalty == bestpenalty)
> if (random(++nmatches) == 0)
> selected = i;
>
> After a full scan, this produces the same random choice among locations
> with the true minimum penalty as collecting those locations in an array
> and choosing an element at the end, without storing the array.

I see, but it will also require more calls of random number generation,
and it's not obvious to me that this would have less overhead. Let me
experiment with this part, but otherwise I assume you find the patch
idea sound?