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.
