A reach that follows the stream

A key passed along the row gave a full B±tree leaf one parameter: how many siblings away, in either direction, it may look for room before it splits. The two kinds of stream it measured asked for opposite settings. On random insertion the reach is expensive, and more so the further it goes: a reach of four writes 3.01 pages a key for leaves 92.6% full, and the whole parent writes 17.07 for 98.9%. On a nearly ascending stream it is almost free: the whole parent in reach writes 2.36 pages a key against the adjacent rule’s 2.25, for 14% fewer leaves. The fixed reach that suits one stream is wrong for the other by a wide margin.

A tree is not told which stream it is receiving, and a run is a property of the input is the page on why “nearly sorted” is a measurement rather than a label a caller can supply. That essay’s closing section pointed out that the tree can nonetheless read it off its own behaviour. Every redistribution is a walk of some number of siblings, and the walks already made say whether room has been near or far. A run of short walks means the neighbourhood has space; a run of long ones means it is full. It proposed a reach that follows those walks, predicted that it would track the better fixed reach on each pure stream within a few per cent and beat both fixed reaches on a stream that changes, and named the number to watch: how many insertions it takes to notice the change.

A reach with one rule #

The rule is as small as it can be. The tree counts overflows — insertions that find their leaf already full. Every 64 overflows it looks at the redistributions among them and takes the mean distance their keys were passed. If that mean is at or below a target, the reach doubles, up to the whole parent of 64. If it is above, the reach halves, down to one. An overflow that ends in a split has no walk and does not enter the mean, though it counts towards the 64. The reach starts at one.

That is the whole of it: one number, the target, and a window of 64. Everything else — the trees of 131,072 keys, leaves of 64 keys and a fan-out of 64, the pages counted as every leaf and parent an insertion writes — is exactly the arrangement of the earlier essay, so every fixed-reach point below is one of its points and can be read against its plates. Every tree is checked for key order and for separators that name the first key of the subtree after them.

The target has a natural reading in the currency the earlier page used. A redistribution that walks $d$ siblings writes $d$ leaves and one parent, and a split writes two or three pages. A walk of two costs about what a split does. So a target of two says: keep widening while the tree’s typical redistribution costs no more than the split it replaces, and back off when looking further has begun to cost more than giving up would.

On the frontier, wherever the target puts it #

On random insertion there is no single best reach. There is a frontier: fewer leaves for more pages written, and a reader’s ratio of scans to insertions picks the point. So the first test is not whether the adaptive rule hits some particular reach, but whether it lands on that frontier at all or somewhere inside it.

Every target lands on the frontier. Target two ends with 2,220 leaves at 3.06 pages a key, beside a fixed reach of four at 2,211 and 3.01. Target three sits between reaches four and eight, target eight between sixteen and thirty-two. The largest departure from the frontier at the same cost is 0.9%, and three of the six are on the favourable side of it. The adaptive rule is not choosing a reach at random and averaging badly. It is moving along the same curve the fixed reaches trace, to a point its target sets.

That is a stronger result than it first looks. Across a random stream the reach does not settle. With target two it changes 1,336 times over 131,072 insertions and spends 74% of them at a reach of four, eight or sixteen, 9% at the whole parent and the rest below four. A rule that oscillated between a cheap reach and an expensive one could easily have ended with the costs of the expensive one and the leaves of the cheap one. It does not, because the walks it measures are the cost it pays. When long walks make a window expensive, the next window is narrower.

The target is therefore the ratio the earlier page declined to set — the same kind of ratio one dial between two structures found choosing between a B-tree and a log-structured store — written as a quantity the tree can measure: how far it is willing to pass a key, on average, to avoid a split. The sibling a full leaf asks first found that the rule databases use is one fixed setting of this trade that suits one stream. Here the trade has a knob, and the knob’s position is a walk length rather than a reach.

Every ordered stream finds the whole parent #

On the three ordered streams the prediction holds exactly. Ascending and descending insertion end with 2,048 leaves, every leaf full, at 2.69 pages a key — the same tree a fixed reach of two builds. On the nearly ascending stream with one key in a hundred late, the adaptive tree ends with 2,096 leaves at 2.36 pages a key. A fixed reach of 32 gives 2,095 at 2.37 and the whole parent 2,096 at 2.36. In both cases the adaptive rule reaches the whole parent 861 insertions from the start and stays there, changing its reach 9 times on ascending keys and 49 on the late stream.

That is what the walks say. On an ordered stream the nearest room is almost always one sibling away, so every window’s mean walk sits below two and the reach keeps doubling until it hits the parent’s width. It never needs the width. The earlier essay’s walk histogram had 88% of redistributions on the late stream stopping at the first sibling. But the reach is free to be wide because walks stay short whatever it is, and the rare late key that needs to travel far is allowed to.

A stream that changes halfway #

The case the prediction said the adaptive rule should win is a stream whose order changes. Two are measured. In one, the first 65,536 keys arrive in random order and the next 65,536, all larger, arrive ascending with one in a hundred late. In the other, the first half arrives nearly ascending and the second half is random keys interleaved among the first half’s, so that the random keys land in the leaves the ordered half filled.

On the stream that turns from random to ordered, the adaptive rule beats every fixed reach. It ends with 2,162 leaves at 2.75 pages a key. A fixed reach of four costs 2.69 pages and ends with 2,224 leaves; a fixed reach of eight gets 2,175 leaves for 3.40 pages. The adaptive tree has fewer leaves than reach eight at about the cost of reach four, 57 leaves under the frontier at its cost. No fixed setting does that, because no fixed setting is short on the random half and wide on the ordered half.

The other direction does not go the same way.

On the stream that turns from ordered to random, the adaptive tree ends 16 leaves inside the frontier — 0.7% more leaves than a fixed reach at the same cost. The first half costs it nothing: it runs at the whole parent and fills the leaves as the late stream always does. The second half is where the loss is. The random keys land in leaves the ordered half filled completely, so there is no room anywhere nearby, and the first window after the change finds long walks and halves. The reach has to come down from 64, and in the windows it takes to come down, every overflow walks far. The fixed reach of four never had that bill to pay.

So the prediction is half right. An adaptive reach beats both fixed ones when the change is towards order, because widening costs nothing on the side it widens into. When the change is away from order it pays a toll for having been wide, and a fixed small reach that was worse on the first half is marginally better overall. How large the toll is depends on how fast the reach comes down.

How long it takes to notice #

The two directions are noticed at very different speeds, and the asymmetry has a plain cause. A turn to random is noticed in 62 insertions. The ordered half has filled its leaves, so the first random key to overflow walks a long way. Overflows come fast — every leaf is full — and one window of 64 overflows arrives within a few dozen insertions. Its mean walk is 12.9 siblings, and the reach halves. Three more windows bring it to four by 275 insertions after the change, and one more to two by 346.

A turn to order takes 779 insertions to reach the whole parent. The ordered keys go to new leaves at the right of the tree, where walks are short, and a window of 64 overflows passes in about ninety insertions, so four doublings from eight would take under four hundred. What slows it is the one key in a hundred that arrives late. A late key lands among leaves the ordered keys have already filled and walks a long way — one window after the change averages 6.4 siblings, a later one 14.4 — and each such window halves the reach. It takes three setbacks of that kind before a run of short-walk windows carries the reach to 64, at 779 insertions. From there it stays at the whole parent for 98% of the second half, dipping for a window whenever a late key walks far.

The asymmetry is the right way round for a rule of this kind. Being too wide on a random stream costs many pages per key; being too narrow on an ordered one costs a few leaves not yet filled, which later redistributions can still fill. A rule that backs off fast and widens slowly errs towards the cheaper mistake. Its window is still a real parameter. At a window of 16 overflows the turn to random is noticed in 22 insertions and the turn to order in 213, but the reach changes 2,700 times over the stream instead of 680. At 256 it takes 980 and 3,285 insertions, and the adaptive tree on the ordered-to-random stream ends 0.09 pages a key more expensive. Sixty-four was chosen before measuring and it is a reasonable middle, not a tuned one.

The floor under the target #

The target is a walk length, and an ordered stream has a walk length of its own.

Below a target of 1.75 the ascending stream thrashes. It ends with 2,470 leaves where every other target gives 2,048, and its reach changes about 1,237 times. The mechanism is the ordered stream’s own geometry. Once the reach is two, a full leaf at the right end redistributes into the two-thirds-full leaf behind it, and on an ascending stream those walks alternate between one sibling and two: over the whole stream they average exactly 1.500. A window’s mean scatters around that value, 1.46 in one window and 1.55 in the next, so a target of 1.5 sees half its windows above it and halves the reach to one. At one the leaf’s neighbour is full, so it splits; a window of splits has no walks, its mean is zero, and the reach doubles again. The tree alternates between the rule that cannot fill ordered leaves and the one that can, and ends up about halfway between their fills.

So the target has a floor, and the floor is not arbitrary: it is the mean walk the ordered stream needs, 1.5, plus the scatter of a 64-overflow window around it. A target set below it is asking the tree to accept less than the minimum any redistribution on that stream costs. The keys that arrive late found the same kind of fragility in the rightmost-split rule, which is perfect on one stream and collapses on a small departure from it. The adaptive rule’s failure is at a stated number rather than at an input.

The late stream is milder. At targets of 1, 1.25 and 1.5 it ends with 2,282, 2,192 and 2,116 leaves against 2,096 from 1.75 up. Its walks are a mix of ordered short ones and the occasional long walk of a late key, so it sits partly above the floor. On random insertion the target is simply a price: target one gives 2,386 leaves at 1.69 pages, target three 2,165 at 4.12, and every target in between is a point on the same frontier.

What was measured and what was not #

One size of tree and one seed per stream. 131,072 keys, leaves of 64, a fan-out of 64. The frontier positions on random insertion are within a per cent of each other, and a second seed would move the adaptive points by about as much. The claim that it lands on the frontier holds at that resolution. The claim that it beats the frontier on the random-to-ordered stream by 57 leaves is larger than that, and the claim that it loses by 16 on the other is of the same order as the noise.

Pages, not time. Pages written count every leaf and parent an insertion touches, as on the earlier page and as the writes nobody counted first counted them. A walk’s writes are to adjacent leaves, which on a real device are often adjacent blocks, and the block that is not a block lists why such writes are cheaper than a page count says. That favours the wide reaches, and so favours the adaptive rule on ordered streams.

No concurrency. A walk of $d$ siblings locks $d + 1$ leaves and the parent. The adaptive rule’s reach is wide exactly on ordered streams, where walks are short, so its lock footprint is small where its reach is large. That is an argument, not a measurement.

The change is abrupt. Both changing streams switch order at one insertion. A stream whose order drifts slowly would be noticed as soon as its walks cross the target and not otherwise, and a drift that stays near the target would leave the reach oscillating. Neither was measured.

Internal levels keep even splits. As on the earlier page, only the leaves redistribute. One access, eight kilobytes is the reminder that the leaves are where the pages are, so that is where the rule was measured.

Still open: a reach per region of the tree #

The adaptive rule has one reach for the whole tree. The stream that turned from random to ordered shows why that is coarse. After the change the ordered keys go to new leaves at the right edge, where walks are short and the whole parent is right, and the random half’s leaves are never touched again. On a stream that interleaves — a clock-ordered stream of new events alongside random updates to old ones — both kinds of insertion arrive at once, in different parts of the tree, and one reach has to serve both. The window’s mean walk is then a mixture, and the reach settles at a compromise that is wrong for both regions.

A parent node already knows which region it is: it is the node whose children the chain walks along. The measurement that follows gives every parent its own window and its own reach, costing a few bytes a parent. It runs the interleaved stream with ordered and random insertions mixed in shares from 10% to 90%, and compares the per-parent rule with the tree-wide one and with every fixed reach. The prediction is that the per-parent rule tracks each region’s own best reach, and so beats the tree-wide rule by more as the mixture approaches half and half. The risk is the window: a parent sees far fewer overflows than the whole tree does, so its window takes far longer to fill, and a per-parent rule might never have enough walks in hand to change its mind before the region’s order changes again.