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

Hi Dmitry,

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

Right. Reservoir sampling avoids the candidate array, but does not
necessarily use less CPU. My guess is that a xoroshiro128** call is cheaper
than another _bt_split_penalty() calculation, although the difference is
probably too small to matter here. Keeping the array is also fine once the
whole interval is examined and the candidates are reset whenever a lower
penalty is found.

> Let me experiment with this part, but otherwise I assume you find the
> patch idea sound?

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.

I would leave SPLIT_MANY_DUPLICATES and internal pages unchanged until we
have evidence that randomization helps them without weakening their current
policies. I think the important cost here is not a few random calls or a
short second pass, but additional complexity in nbtree, which already has
many interacting policies. From a large set of small possible improvements,
we should prefer a small set that are simple and orthogonal, particularly to
avoid bugs where their policies interact. So I would choose whichever
implementation keeps both this patch and its interaction with the existing
strategies simplest. 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.

Best regards, Andrey Borodin.