> On Mon, Aug 24, 2026 at 02:22:46PM +0300, Andrey Borodin wrote: Thanks for looking into it.
> state->splits is ordered by distance from the desired space balance, not > by _bt_split_penalty(). The loop can collect 20% of locations with the > best penalty seen so far and stop before reaching a lower penalty later > in the interval. The existing early exit is safe because it only stops > at perfectpenalty, which is a known lower bound. v2 does not rely on the split points being sorted anymore, but reaching 20% before finding even better split location is indeed a bug in the algorithm. I have to adjust the last condition to be something like "we've reached 20% and it's a perfectpenalty", which will be equivalent to the original implementation. Btw, I think the second approach, nicknamed "shifted interval", is not affected by this since it uses very same logic as in the original loop. > There is also a special case in SPLIT_MANY_DUPLICATES. That strategy > widens the interval to the whole page, but still relies on delta order to > pick the nearest location with the required penalty. Randomizing among > equal-penalty locations changes that policy and might also avoid the > existing protection against repeatedly leaving unusable free space. > > Would it be simpler to initially restrict randomization to > SPLIT_DEFAULT leaf splits, Yeah, I've actually concentrated my efforts on SPLIT_DEFAULT and haven't tested other strategies, so it sounds reasonable to apply randomization only to this strategy. > examine the whole existing interval, and use > reservoir sampling among locations with the true minimum penalty? That > would need no extra array and would preserve suffix truncation exactly. 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.
