A floor under every level

The sizes a store passes through followed a rule for dividing a levelled store’s range-filter memory through the store’s fill. The rule reads only the levels’ sizes: $\delta$ more bits a key for every factor of four a level is smaller than the deepest, snapped to a grid of bit counts, the base raised until the budget is spent. On the full store it matched the division fitted to the store’s own queries. Through the fill it fell up to 17 points of a perfect filter’s saving behind on the shuffled store and 26 on the store filled a cluster at a time, at a bit a key or less, and every large loss had one cause. Part way through the fill the deepest level holds a smaller share of the store, the small levels can absorb most of the budget, the base for the deepest level falls below half a bit, and the snap rounds it to nothing: a level holding most of the keys gets no filter, and every query that reaches it reads it.

Its closing section proposed saying outright what the fitted division did implicitly. From one bit a key up, the fitted division gives every level at least half a bit at every checkpoint of the fill on both orders. A rule could give every level a floor of half a bit a key and divide what remains of the budget by sizes as before. The prediction was that the floor would close every gap larger than five points, since each was a level given nothing, would bring the worst gap at one bit a key under three points on both orders, and would cost nothing at two and four bits a key, where the rule already gives every level half a bit or more. It named the failure in advance: at half a bit a key the floor is the whole budget, the rule becomes the even split, and the even split is right half way through the clustered store and wrong on the full shuffled store by 34 points.

All three parts of that came true, the failure included, and the failure turns out to be about the arrival order rather than the floor.

Half a bit before anything is divided #

The store, the queries, the checkpoints and the accounting are the earlier essays’. The store holds $2^{20}$ keys in sixteen clusters, filled shuffled or a cluster at a time, and is read at an eighth, a quarter, three eighths, a half, three quarters and the whole of its keys. At each checkpoint every level’s filter cost at every grid value from nought to sixteen bits a key is read on two seeds of queries; the fitted division is the cheapest assignment on the choosing seed, and every division is charged on the charging seed as the share of a perfect filter’s saving it captures.

The floored rule computes each level’s bits exactly as the rule chosen before the queries arrive did, $\delta$ times its factors of four below the deepest plus a base, snapped to the grid, and then raises any level below half a bit to half a bit. The base is then the largest whose division fits the budget. When the budget is under half a bit a key the floor is dropped, and when it is exactly half a bit the floor uses all of it. It is run at $\delta$ = 2, 4 and 8, and the rule at $\delta = 4$ without a floor is the earlier essay’s to the bit.

Seventeen points become four #

On the shuffled store at one bit a key, the floor brings the rule’s worst gap to the fitted division over the fill from 17.3 points to 4.1: 86.4% of a perfect filter’s saving three eighths of the way through, where the unfloored rule captured 68.3% and the fitted division 85.7%. At three eighths the floored rule is a little above the fitted division on the charging seed, by seven tenths of a point, which the fitted division, chosen on a different seed, can lose by. At an eighth it now matches exactly. At three quarters it trails by 1.6 points.

The floor does what the diagnosis said it would. Three eighths of the way through, the rule now gives the levels 8, 3 and half a bit a key where it gave 12, 4 and nothing; the half bit it gives the deepest level costs it a third of the small levels’ bits, and buys back seventeen points, because the deepest level holds 83% of the keys and every range query reaching it was a read.

On the store filled a cluster at a time, at one bit a key, the floor brings the worst gap from 24.8 points to 0.9. The unfloored rule had fallen below the even split at four of the six checkpoints; floored, it is within a point of the fitted division at all six. The prediction’s under-three holds here with room to spare, and misses on the shuffled store by a point.

What the last four points are #

The remaining gap on the shuffled store is half way through the fill, where the store has four levels of 12,288, 20,480, 163,840 and 327,680 keys. The floored rule gives them 8, 6, a half and a half bits a key; the fitted division gives 6, 6, 1 and a half. The difference is the third level, which holds 31% of the keys and is half the size of the deepest: the fitted division gives it a whole bit, the rule only the floor.

That is the same blind spot one level up. The rule reads the third level as half a factor of four smaller than the deepest and gives it half of $\delta$ more bits, which at a budget of one bit a key and a base below nought is still under half a bit before the floor. A floor fixes the level that gets nothing; it cannot tell a level that deserves a little from one that deserves a whole bit. Half way through the shuffled fill, that difference is four points of the saving.

Where the half bit comes from #

The floor’s half bit for the deepest level has to come from somewhere in a fixed budget, and it comes from the small levels. Three eighths of the way through the shuffled fill, at one bit a key, the floored rule gives the smallest level 8 bits a key where the unfloored rule gave 12 and the fitted division gives 16; three quarters of the way through it gives 8 where the fitted division gives 16. The smallest level holds about 1% of the keys, so halving its bits frees a fifth of a bit a key across the store, and the deepest level’s half bit costs about that much.

The small level barely notices. At three eighths the floored rule captures 86.4% of the saving with 8 bits on the smallest level, and the fitted division 85.7% with 16. The earlier essays found the small levels’ curves flat at the top of the grid, as the point filters each run carries had found for lookups of missing keys, where the same memory moved from the large level to the small ones bought reads back, where every query that reaches a small level is already almost always ruled out, and the last eight bits a key buy almost nothing. The deepest level’s curve is steep near nought instead, and this plate measures how steep: its first half bit a key, paid for by the small levels, is worth eighteen points here. The small levels’ share of a range filter found the same trade from its other end, recovering more than half of a store’s gap by moving bits from the largest level to the small ones; it holds only until the largest level’s last half bit is taken. The floor moves memory from the flattest part of one curve to the steepest part of another, which is why a fifth of a bit a key buys so much.

On the clustered store the same exchange is cheaper still. Three eighths of the way through, the floored rule gives the levels 8, 3 and half a bit a key where the fitted division gives 16, 1 and half a bit, and captures 99.0% of the saving against 99.9%.

Nothing moves where the budget is larger #

At two and four bits a key the floor changes nothing at δ = 4: the worst gaps stay at 4.2 and 4.1 points on the shuffled store and 0.7 and 0.6 on the clustered one. At those budgets the rule already gives every level at least half a bit at every checkpoint, so the floor never binds. The prediction that it would cost nothing there holds exactly.

The plate also settles $\delta$. With the floor, four is the best of the three values tried at one bit a key on both orders, 4.1 and 0.9 points against 6.7 and 1.6 at two and 5.4 and 4.3 at eight. The sizes a store passes through found that no $\delta$ alone could stay within two points everywhere, because the parameter was doing two jobs; with the floor taking one of them, the earlier essay’s own $\delta$ is the right one again.

Half a bit, and two stores that want opposite things #

At half a bit a key the floored rule is the even split, and on the shuffled store it falls 16 to 35 points behind the fitted division at every checkpoint, against at most 9.3 for the unfloored rule. The named failure is exactly as named: on the full shuffled store the even split captures 37.6% and the fitted division 71.5%, a gap of 34 points, and three quarters of the way through it is 34.8.

On the store filled a cluster at a time the same floor costs little: the even split matches the fitted division at four of the six checkpoints, and trails by 5.3 points at an eighth and 9.1 at the full store, against the unfloored rule’s 26.1 at half way. So at half a bit the floor turns the worst case from the clustered store to the shuffled one and makes it worse. Neither rule is safe at this budget on both orders, and the next plate shows why no rule that reads only sizes could be.

Half way through the fill, at half a bit a key, the two arrival orders have identical levels and their fitted divisions are opposite: the shuffled store wants 8, 4, a half and nothing, the small levels richly filtered and the deepest bare; the clustered store wants half a bit everywhere. A rule that reads only sizes sees the same input on both stores and must give the same answer, so it is wrong on one of them whatever it gives. The unfloored rule gave 6, 6, nothing and nothing, near the shuffled store’s answer, and lost 26 points on the clustered store; the floored rule gives the clustered store’s answer and loses 26 on the shuffled one.

The likeliest reason, which this measurement does not isolate, is in what a filter buys on each store. Filled a cluster at a time, each level’s keys come from few clusters, so a level’s key range is narrow and most range queries fall outside it before any filter is asked; what is left for the filters is a little everywhere, and half a bit a key everywhere buys it. Filled shuffled, every level spans the whole key space and every query overlaps every level, so a filter is asked on every level for every query, and memory spent where it rules out the most reads per bit, on the small levels, is worth the most. One bit a key, divided found the arrival order mattering more than the choice of prefix lengths; at half a bit it matters more than the levels’ sizes too.

What the prediction got right #

The closing section predicted that a floor of half a bit a key would close every gap larger than five points. At one bit a key and above it closes all of them; the largest left anywhere at those budgets is 4.2 points. It predicted the worst gap at one bit would fall under three points on both orders: 0.9 on the clustered store and 4.1 on the shuffled one, where the remaining gap is a level given the floor that deserved a whole bit. It predicted the floor would cost nothing at two and four bits a key, and the worst gaps there do not move.

It named the failure at half a bit, that the floor would be the whole budget and the rule the even split, right half way through the clustered store and 34 points wrong on the full shuffled store, and both halves of that are measured to the point. What it did not say is that the failure belongs to the budget rather than to the floor: at half a bit the two orders want opposite divisions of identical levels, and the floor only decides which of them the rule is wrong on. The question was whether the rule’s real parameter is how fast bits grow up the levels or how little the deepest level may be given. At a bit a key and above, it is the second, and a floor set before the store knows its shape is enough for every shape it passes through. At half a bit it is neither; it is the order the keys arrived in.

What the floor leaves out #

A floor of one size. Half a bit is the grid’s lowest non-zero step. A floor of a whole bit was measured too, and at one bit a key it is the even split again, losing 44.6 points on the shuffled store; a floor is only safe well under the budget it sits under.

The orders as given. Two arrival orders, shuffled and a cluster at a time. A store that arrives partly clustered would want something between the two fitted divisions at half a bit, and no rule here is fitted to it.

Two seeds and one store. As before: one seed of queries to choose on and one to charge on, and one store of $2^{20}$ keys.

Still open: a rule that reads a level’s span #

At half a bit a key the two orders want opposite divisions because their levels differ in one thing the sizes do not show: how much of the key space each level spans. A level filled a cluster at a time spans a few clusters and is ruled out by its fences for most range queries; a shuffled level spans everything and is ruled out by nothing. A store knows each level’s key span when it writes the level, at no cost, since a level’s first and last keys are its fences.

The measurement that follows gives the rule a second input: each level’s bits are scaled by the share of the key space its fences span, before the snap and the floor, so that a level most queries skip is given fewer bits and one every query reaches is given more. The prediction is that at half a bit a key this rule matches the fitted division within five points at every checkpoint on both orders, where the floored rule loses 35 on one and the unfloored rule 26 on the other, and that at a bit and above it changes nothing, since every level’s span is the whole key space on the shuffled store and the floor already decides the clustered one. It could fail on the clustered store’s deepest level, which spans every cluster once the fill is complete and so looks shuffled to a span, at exactly the checkpoint where the fitted division gives it nothing. The question is whether what separates the two stores is something a level can measure about itself, or only something the queries reveal.