The sizes a store passes through

A division chosen before the queries arrive gave a levelled store a rule for dividing its range-filter memory that needs nothing but the levels’ sizes. The store keeps its keys in sorted levels, each a fixed multiple of the one above, and a range query that a level’s filter cannot rule out costs a read of that level. One bit a key, divided had found the best division by trying every assignment against the store’s own queries: the small levels want twelve to sixteen bits a key, the deepest one bit or less. The rule reproduces that shape from sizes alone. For each level, count how many factors of four it is smaller than the deepest, give it $\delta$ more bits a key for each, snap to a grid of bit counts, and raise the base until the budget is spent. At $\delta = 4$ it matched the fitted division on the full store at every budget, on both arrival orders, charged on queries neither had seen.

Its closing section noticed what the full store hides. A store is not full while it fills. Through the fill the deepest level is newer and smaller relative to its own eventual size, sometimes smaller than the level above will be at the end, and the ratios between levels change at every merge. A store writing a level mid-fill applies the rule to the sizes it has then. The prediction was that the rule, with $\delta$ fixed at four, would stay within a point and a half of the fitted division at every point of the fill the earlier essays measured, an eighth, a quarter, three eighths, a half, three quarters and the whole, on both orders at every budget. It named the risk: early in the fill the deepest level may be most of the store while the store has fewer keys than its budget was sized for, and the rule’s half bit for it could be too little.

The risk was named in the right place and with the wrong number. The rule’s trouble is not that its half bit is too little but that, part way through the fill, it gives the deepest level nothing.

The rule at six points of the fill #

The store, the queries and the accounting are the earlier essays’. The store holds $2^{20}$ keys in sixteen clusters and fills either shuffled or a cluster at a time, its filters chosen afresh at every write; each level’s range filter is a pair of prefix lengths chosen for the level’s keys, at each number of bits a key on the grid of nought, a half, one, two, three, four, six, eight, twelve and sixteen. At each of the six checkpoints of the fill, every level’s cost at every grid value is read on two seeds of queries. The fitted division is the assignment of grid values to levels, within the budget, whose cost on the choosing seed is least, found by trying all of them. The rule is the earlier essay’s at $\delta = 4$, applied to the sizes the store has at that checkpoint. Both, and the even split, are charged on the charging seed and reported as the share of a perfect filter’s saving they capture.

At the whole store the rule here is the earlier essay’s rule to the bit, and every division is checked to spend no more than its budget and to cost between a perfect filter and none.

Seventeen points behind, three eighths in #

On the shuffled store at one bit a key, the size rule captures 97.2% of a perfect filter’s saving on the full store, the same as the fitted division, and 68.3% three eighths of the way through the fill, where the fitted division captures 85.7%: 17.3 points behind. From three eighths to three quarters of the fill it trails by 12 to 17 points. It matches the fitted division exactly at a quarter of the fill and at the end, and nowhere else does it come within two points.

The prediction’s point and a half holds at two of six checkpoints at this budget. The rule is still well above the even split everywhere, by 15 to 23 points from three eighths to three quarters of the fill, so the sizes are telling it something; they are not telling it enough.

On the store filled a cluster at a time, at one bit a key, the rule falls 24.8 points behind the fitted division three eighths of the way through the fill, 75.1% against 99.9%, and 21.6 points behind at an eighth. Here the fitted division captures nearly all of a perfect filter’s saving at every checkpoint, and the even split comes within a few points of it from a quarter of the fill on. The rule, which beat the even split by 17 points on the full store, falls below it at four of the six checkpoints.

A deepest level given nothing #

Three eighths of the way through filling the shuffled store, at one bit a key, the deepest level holds 83% of the keys, and the size rule gives it no filter at all where the fitted division gives it half a bit a key. The rule’s division is 12, 4 and 0 bits a key on levels of 4,096, 61,440 and 327,680 keys; the fitted division’s is 16, 2 and 0.5. The difference in the small levels hardly matters here, though the small levels were where dividing the memory first found its saving: they hold 17% of the keys, and at twelve or sixteen bits a key both divisions already spend heavily on them. The difference in the deepest is the whole gap: with no filter, every range query that reaches the deepest level reads it, as a store with no range filter does at every level, and half a bit a key, the earlier essays found, already rules out a large share of those reads.

At the full store the same budget gives the deepest level half a bit because there it holds 94% of the keys. A budget of one bit a key, of which 94% must be spent somewhere, cannot be spent on the small levels alone, so the base the rule solves for lands at a half for the deepest level. Three eighths into the fill the deepest holds 83%, the small levels’ 17% can absorb most of the budget at high bit counts, the base falls below a half, and the snap to the grid rounds it to nothing.

Half way through filling the store a cluster at a time, at half a bit a key, the rule gives the two deepest levels nothing and the two small ones six bits a key each; the fitted division gives every level half a bit, the even split, and captures 82.0% of the saving to the rule’s 55.9%. The rule’s worst point on either order is this one, 26.1 points behind. Half way through, the store has four levels, the two deepest hold 94% of the keys between them and differ in size by a factor of two, which is half a factor of four, so the rule treats them as nearly the same size and spends nothing on either. On this order and at this budget, the queries want the opposite of what the rule assumes: a little filter everywhere rather than a lot on the small levels.

The shape of a store that is filling #

Through the fill the deepest level’s share of the store swings between 63% and 94% with every merge: 63% at an eighth of the keys, 94% at a quarter, 83% at three eighths, 63% at half, 83% at three quarters, 94% at the end. The full store, where the rule was measured, is one of the two points where the deepest level is largest relative to the rest. The rule’s arithmetic was right for that shape, where a level’s share of the store and its number of factors of four below the deepest go together. Mid-fill they do not. Half way through, the level above the deepest is half its size, a ratio of 0.5 in factors of four, and the rule gives it nearly the deepest’s bits, which at a small budget is nothing.

The two checkpoints where the rule matches the fitted division exactly are the two where the deepest holds 94%: a quarter of the way through and at the end. Everywhere else its share is lower, and on the shuffled store at one bit a key the rule gives the deepest level nothing at every one of the four. That is the failure the closing section named, in its mechanism. A store’s sizes do tell the rule how to divide its memory; the rule’s way of reading them, ratios to the deepest level alone, cannot tell a deepest level that is 94% of the store from one that is 63%.

How far behind, over the whole fill #

Over the whole fill the rule at δ = 4 trails the fitted division by at most 4.2 points from two bits a key up on either order, and by up to 17.3 points on the shuffled store and 26.1 on the store filled a cluster at a time at a bit a key or less. The prediction holds where the budget is large: at two and four bits a key on the store filled a cluster at a time the rule is within 0.7 points at every checkpoint. It fails where the budget is small, which is where the snap to nothing bites, since with two bits a key there is enough to give the deepest level at least half a bit at every point of the fill.

A smaller $\delta$ is no repair. At $\delta = 2$ the rule spreads its bits more evenly and gives the deepest level half a bit more often, which cuts the worst gap at one bit a key on the store filled a cluster at a time from 24.8 points to 1.6. It also gives the small levels too little at two bits a key on the shuffled store, where its worst gap rises from 4.2 to 10.8. No value of $\delta$ that was tried, nought, two, four or eight, stays within two points of the fitted division at every checkpoint and every budget on both orders.

The δ that would have served #

The best δ moves through the fill: on the shuffled store at one bit a key it is 2, 4, 2, 2, 2, 4 at the six checkpoints, and on the store filled a cluster at a time at half a bit it is 2, 0, 0, 0, 8, 6. Four is right at the full store, which is where it was chosen, and at a quarter of the fill, which has the same shape. Elsewhere the best value is two, or, half way through the clustered store at the smallest budget, nought, the even split. A $\delta$ chosen once cannot follow a store whose shape keeps changing.

Even a $\delta$ chosen afresh at every checkpoint does not reach the fitted division. On the shuffled store at one bit a key the best $\delta$ at each point captures 56.9%, 82.7%, 83.6%, 77.7%, 86.3% and 97.2%, against the fitted division’s 59.0%, 82.7%, 85.7%, 82.9%, 87.0% and 97.2%: within two points at four checkpoints, and 5.2 points behind half way through, where the store has four levels and no single rate of growth up the levels fits the bits the queries want. The parameter is not merely set wrong for the shape; at some shapes it is the wrong kind of parameter.

The rule’s parameter was doing two jobs at once on the full store. It set how much more the small levels get than the deepest, and, through the snap and the budget, whether the deepest got anything. On the full store those happen to be decided together, because the deepest is so large that the budget forces it a share. Through the fill they come apart, and a parameter that is right for the first job gives the wrong answer to the second.

What the prediction got right #

The closing section predicted that the rule would stay within a point and a half of the fitted division at every checkpoint, on both orders, at every budget, because the ratio between levels never falls below four in a levelled store and the rule’s arithmetic holds at any ratio that large. It holds at two and four bits a key on the store filled a cluster at a time, within 0.7 points everywhere. It fails at one bit a key or less on both orders, by up to 26 points, and by up to 4.2 at two and four bits on the shuffled store.

The premise about ratios was wrong in a way the full store could not show. Through the fill a levelled store is often not levelled: half way through, the two deepest levels differ by a factor of two, because the merge that will combine them has not happened yet. The named risk was in the right place, the deepest level early in the fill, and the wrong direction: the rule’s half bit for the deepest was not too little, it was not there, rounded away whenever the deepest level was not quite large enough to force it.

The question was whether a rule that reads sizes is right at every size a store passes through. Read as ratios to the deepest level, the sizes are enough at the full store and at a quarter of the fill, and not at the four checkpoints between.

What one store’s fill leaves out #

Six checkpoints. The fill is read at six points, and a store between them has other shapes still; the worst gaps here are the worst at those six, not over the whole fill.

One grid. The rule snaps to the earlier essays’ grid of bit counts, whose lowest step above nothing is a half. A grid with a quarter bit would give the snap somewhere to land short of nought, and might close part of the gap by itself.

Two seeds of queries and one store size. As before, the queries are two seeds of the same workload, one to choose on and one to charge on, and the store is $2^{20}$ keys in sixteen clusters.

Still open: a rule that never gives a level nothing #

The rule’s losses through the fill share one cause: a deepest level, or the two deepest, rounded down to no filter at all at a small budget. From one bit a key up, the fitted division never does that: it gives every level at least half a bit at every checkpoint on both orders. A rule could say the same thing outright: give every level a floor of half a bit a key, then divide what is left of the budget by sizes as before.

The measurement that follows gives the rule that floor and repeats every checkpoint, order and budget, at $\delta$ = 2, 4 and 8. The prediction is that the floor closes every gap larger than five points, since every one of them is a level given nothing, and brings the worst gap at one bit a key under three points on both orders, while costing nothing at two and four bits a key, where the rule already gives every level a bit or more. It could fail at half a bit a key, where a floor of half a bit is the whole budget and leaves the rule nothing to divide; there the rule becomes the even split, which is right half way through the clustered store and wrong on the full shuffled store by 34 points. The question is whether the rule’s real parameter is how fast bits grow up the levels or how little the deepest level may be given, and whether a floor alone, set before the store knows its shape, is enough for every shape it passes through.