A span the queries do not see

A levelled store keeps its keys in sorted levels, each about four times the size of the one above it, and a range query reads every level that might hold a key in its range. The filter each run carries put a range filter in front of each level, so a query can skip a level the filter rules out, and the question since has been how to divide a fixed memory among the filters. A division chosen before the queries arrive found a rule that reads only the levels’ sizes: give a level more bits a key the smaller it is relative to the deepest, $\delta$ more for every factor of four. On the full store it matched the division fitted to the store’s own queries.

The sizes a store passes through ran the rule through the fill and found it rounded the deepest level to no filter at all whenever that level was not quite most of the store, and a floor under every level repaired that with a floor of half a bit a key: from one bit a key up the floored rule came within five points of the fitted division at every checkpoint on both arrival orders, the shuffled store and the clustered one, where keys arrive a cluster at a time. At half a bit a key it did not. There the shuffled store lost 35 points of a perfect filter’s saving to the fitted division under the floor and the clustered store lost 26 without it, and at half a bit the two stores wanted opposite divisions of levels whose sizes were identical. No rule that reads sizes alone could be right on both.

That essay’s closing section named what the sizes leave out. A level filled a cluster at a time spans a few clusters of the key space, and its fences — its first and last keys, which a store knows for nothing when it writes the level — rule it out of every query that falls outside them; a shuffled level spans everything and is ruled out by nothing. It proposed scaling each level’s bits by the share of the key space its fences span, before the snap to the grid of bit sizes and before the floor, so that a level most queries skip gets fewer bits and one every query reaches gets more. The prediction was that at half a bit a key this rule would match the fitted division within five points at every checkpoint on both orders, and that at a bit and above it would change nothing, since every shuffled level spans the whole key space and the floor already decides the clustered one. The risk named was the clustered store’s deepest level, which spans every cluster once the fill is complete.

A span, scaled in #

The store, the queries and the charges are the earlier essays’. Sixteen clusters of keys in a 32-bit key space, inserted in a shuffled order or one cluster at a time, measured at six points of the fill; range queries of four lengths, half starting at a uniformly random point and half at a stored key; a level read for a query costs one transfer plus one for every block of keys the range covers in it, and a filter that rules the level out saves the read. A division is scored by the share of a perfect filter’s saving it captures, measured on queries other than those the fitted division was chosen on.

The span rule takes the floored size rule’s target for each level — a base plus $\delta = 4$ bits for every factor of four a level is smaller than the deepest — multiplies it by the level’s span, the distance between its fences over the whole key space, then snaps it down to the grid of sizes the filters come in and raises it to the floor of half a bit. The base is searched, as before, for the largest that fits the budget.

Nothing at half a bit, and harm above it #

Scaling each level’s bits by the span of its fences changes nothing at half a bit a key — 34.8 points behind the fitted division on the shuffled store and 9.1 on the clustered one, as the floored rule — and from one bit up it puts the clustered store about 30 points behind, where the floored rule was within one. On the shuffled store it does no harm and a little good at one bit, 2.3 points behind rather than 4.1, because the shuffled levels’ spans are all alike and scaling them all by the same share changes only the base the budget search finds. On the clustered store it is the worst rule any of these essays has measured from one bit up.

The prediction was wrong on both halves, and the first half for a reason that needs no measurement at all.

The floor is the budget #

At half a bit a key the floor is the budget: every level gets half a bit under both rules at every point of the fill, so a scale on the span has nothing to move; the fitted division on the shuffled store gives the deepest level nothing and the shallow levels several bits — 8/4/2/0 at three quarters of the fill, 16/6/0 on the full store — which no floor can reach. A floor of half a bit a key on every level spends half a bit a key on the whole store, which is the whole of a budget of half a bit. Whatever the rule does before the floor, the floor then raises every level to half a bit, and the result is the even split. The span rule’s scaling happens before the floor, as proposed, and is erased by it.

The fitted division at that budget does the opposite of a floor. It takes the deepest level’s share, most of the store’s keys, gives it no filter at all, and spends those bits on the small levels, eight or sixteen bits a key on a level of a few thousand keys. On the shuffled store that is worth 35 points: a range query reaches every level, the deepest level must be read anyway by most queries, and a filter on it at half a bit a key rules out almost nothing, while a filter of eight bits a key on a small level rules it out nearly every time. The floor was introduced to stop the size rule giving the deepest level nothing at larger budgets, where that was a mistake; at half a bit giving the deepest level nothing is the right answer, and the floor forbids it.

So the half-bit gap was never the span’s to close. It is a conflict between the floor and the budget, and a rule that kept the floor could not close it however it read the levels.

What a level’s fences span #

Every shuffled level’s fences span 0.82 of the key space at every point of the fill — all the clusters, from the first to the last — while the clustered store’s levels span 0.004 to 0.82 when it is full: its small levels hold a cluster each, and its deepest spans all of them. The sixteen clusters lie across about four fifths of the 32-bit space, so 0.82 is the most any level can span, and every shuffled level, however small, holds keys from the first cluster and the last. In the clustered store a level written from the buffer while one cluster was arriving holds that cluster alone and spans four thousandths of the key space; a merge of several levels spans several clusters and whatever lies between them.

The risk the proposal named is on this plate: the clustered store’s deepest level spans 0.816 on the full store, as much as a shuffled level. But the rule’s damage at one bit is not on the deepest level. It is on the smallest.

The queries are aimed at the keys #

What the fences measure is not what the queries meet: on the clustered store at three quarters of the fill, a level holding one cluster spans 0.4% of the key space but holds 8.3% of the stored keys, and half the queries start at a stored key, so about 4.4% of queries can land inside it — eleven times its span. The workload these essays have used, like most real ones, is aimed at the data: half its range queries begin at a key the store holds. A level holding one cluster is therefore asked about in proportion to its share of the keys as much as to its share of the key space, and its share of the keys is twenty times its span. Every one of those queries lands in a dense cluster where the range almost always holds a key of that level — the reason its filter can only save by being precise.

The span rule reads the span alone, scales the one-cluster level’s target down to a two-hundred-and-fiftieth of what the size rule gave it, raises it to the floor, and spends the difference on the level that spans half the key space. The fitted division does the reverse. On the full clustered store at one bit a key it gives the shallowest level, one cluster, twelve bits a key, the next eight, and the deepest half a bit.

One bit a key, through the fill #

On the clustered store at one bit a key the span rule captures 70.2% of a perfect filter’s saving on the full store where the fitted division and the floored size rule both capture 99.8%: it starves the one-cluster levels the queries are aimed at and gives their bits to the deepest. At every checkpoint but one the floored size rule is within a point of the fitted division, and the span rule is fifteen to thirty points behind. The exception, three eighths of the way through the fill, is the one checkpoint where the clustered store’s shallowest level spans several clusters, 0.35 of the key space, and the span rule’s scale is mild enough to do little harm.

That is the measure of how well the size rule had already done. The earlier essays found the floored rule within five points everywhere from one bit up, and on the clustered store within one; whatever distinguishes the two stores at those budgets, the sizes had already captured it, because a level’s size and the queries aimed at it move together when queries are aimed at keys.

What separates the two stores #

The closing question was whether what separates the two stores is something a level can measure about itself, or only something the queries reveal. The fences are something a level measures about itself, and they measure the wrong thing for this workload: how much of the key space a level covers, when the queries are distributed by keys, not by key space. A level’s share of the keys it holds, which is its size, was already the better measure, and the span adds an error to it.

The small levels’ share of a range filter and one bit a key, divided both found that the small levels deserve more bits a key than their size alone suggests, and the fitted divisions here say so again: twelve bits a key on a one-cluster level of eight thousand keys. A rule that read the queries’ landing points — how often each level’s filter was consulted, and how often it could have saved a read — would see what the span cannot. One length for the gaps and the clusters found the same limit for a filter’s own design: what it should be tuned to is where the queries fall, which only the queries say.

What a store could read instead #

A store can know more about a level than its fences, and still for nothing. The filter rebuilt with every write builds each level’s filter when the level is written, and at that moment the store holds every key of the level in order: it can count, in passing, how many distinct clusters the level touches and how many keys sit in each, or keep a coarse histogram of its keys over the key space. Weighted by the store’s own key distribution, such a histogram would give a level’s share of the queries a key-aimed workload sends it — which, on this workload, is about half its span plus half its share of the store’s keys, the number the reach plate computed.

That number would have told the rule what the fitted division already knew: the one-cluster levels are asked about far more often than their span suggests, a twelfth of the keys meeting a twelfth of the queries aimed at keys. Whether a rule built on it would beat the floored size rule is another matter. On this store the size rule is within a point of the fitted division from one bit up on the clustered store, so there is almost nothing left to win there, and on the shuffled store every level’s share of the queries is the same. The place a better measure could help is half a bit a key, and there the floor, not the measure, is what stands in the way.

What the store does not show #

One workload. Half the queries start at a stored key and half anywhere. A workload of uniform range queries over the key space would make the span the right measure, and on it the span rule might do what was proposed; that workload was not run, and it is the obvious control.

Sixteen clusters. The clustered store’s levels hold one, a few or all of sixteen clusters. Many more, smaller clusters would make the spans of small levels larger relative to their key shares, and the rule’s error smaller.

A floor kept. The span rule was run with the floor, as proposed. Without the floor at half a bit, the span would have something to move; but the floor’s removal is what the fitted division wants at that budget, and the span would not be what decided it.

Still open: a floor that steps aside at half a bit #

The half-bit gap is a conflict between two rules that are each right somewhere. The floor is right from one bit up, where giving the deepest level nothing was the size rule’s mistake; at half a bit the fitted division gives the deepest level nothing on the shuffled store, and the floor forbids it. A rule could keep the floor only while the budget can pay for it and leave room above it: apply the floor of half a bit only when the budget is at least twice the floor, and otherwise let the size rule divide the budget freely, deepest level included.

The measurement that follows runs the size rule with that conditional floor at budgets of half a bit, three quarters and one, on both orders through the fill. The prediction is that at half a bit on the shuffled store the rule then gives the deepest level nothing and comes within ten points of the fitted division, while the clustered store, whose fitted division at half a bit is the even split at four of the six checkpoints, loses the 9 points it loses now to about 26, as the unfloored rule did — so that no single setting of the condition is right for both stores at that budget, and the gap at half a bit is a gap between workloads rather than between rules. It could fail if the unfloored division at half a bit on the shuffled store gives the bits to the wrong small level. The question is whether a budget of half a bit a key has a division that suits both stores at all, or whether below a bit a key a store must read its queries before it can choose.