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

Hi Dmitry,

On Mon, Aug 24, 2026 at 11:03 PM Dmitry Dolgov wrote:
> 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.

Right, the early-stop problem does not apply to the shifted-interval
variant. Its two loops together scan

[0, rand_offset)
[rand_offset, highsplit + rand_offset)

rather than the original [0, highsplit) interval. The new upper bound is
not capped at state->nsplits and, even when capped, extends the search
beyond the original balance interval.

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

Separately, I followed up on my suggestion in response to Andres and
tried extending B-tree indexes in batches. PFA a prototype.

When _bt_allocbuf() exhausts the FSM, it extends the index by several
pages, returns the first page to the split, and records the rest in the
FSM. The batch grows geometrically for small indexes and is capped at
16 pages. This amortizes relation extension without changing the
B-tree locking protocol.

The act of extending a relation is not WAL-logged directly.
FSM updates are hints, but MarkBufferDirtyHint() can emit an
XLOG_FPI_FOR_HINT record, so an FSM page can reach a standby. The standby
can therefore have an FSM entry past the end of its main fork. This is
the issue exposed by heap bulk extension [0]. The prototype relies on
the later FSM fix [1], which rejects such entries. Its test covers the
length difference and continued index use after promotion.

In a custom fixed-work pgbench test, 32 clients each performed 50,000
prepared single-row inserts with increasing int8 keys into an unlogged
table with a 3-million-entry B-tree. Batches of 16 reduced extension
calls from about 5,635 to 354 and extension time from about 96 ms to 9
ms. The three paired TPS changes were +4.5%, +1.9%, and +1.3%; p99
latency improved by about 12%. One client showed no throughput change,
while its p99.99 became worse, as expected for a rarer but larger
extension.

Best regards, Andrey Borodin.

[0] https://postgr.es/m/20221029025420.eplyow6k7tgu6he3@awork3.anarazel.de
[1] https://postgr.es/m/1878547.tdWV9SEqCh@aivenlaptop