A division chosen before the queries arrive

One bit a key, divided gave a levelled store a fixed budget of range-filter memory and divided it among the levels by what each level’s filter would save. The store holds a million keys in sixteen clusters, at full size in three levels of 4,096, 61,440 and 983,040 keys, and each level’s filter is a pair of prefix lengths, a coarse one and a fine one, chosen from the level’s keys when the level is written, the design the filter rebuilt with every write measured. The division was found by trying every assignment of bits a key to levels against the store’s own range queries, on one seed of queries, and charged on another. It gave the two small levels twelve to sixteen bits a key and the deepest level one, captured 99% of what a perfect range filter would save on both arrival orders, and left part of the budget unspent. Divided that way, one bit a key on average did what four bits spread evenly could not.

A store cannot divide its memory that way when it writes a level. It knows its levels’ sizes, and it knows what its filters do on its keys only by asking queries it has not yet been asked. That page’s closing section pointed at a rule the small levels’ share of a range filter and the filter each run carries had both reached for. A query that has to check every level pays each level’s false-positive rate, so for a level’s filter the saving from one more bit is about the same whichever level it is, while the cost of a bit a key is in proportion to the level’s keys. The bits a key should therefore grow by a fixed amount for every factor of four by which a level is smaller. It predicted the rule would come within a point of the fitted division’s 99% on the shuffled store and land at the even split’s 94% or a little above on the store filled a cluster at a time, where it would give the small levels bits they do not need; and it named the failure, the deepest level given less than half a bit, where its curve is steep.

The rule #

The store, its filters and the charges are the earlier page’s. Every level’s cost at every value on the earlier grid — 0, ½, 1, 2, 3, 4, 6, 8, 12 and 16 bits a key — is the transfers a range query spends on that level with its filter’s pair of prefix lengths chosen on the choosing seed of queries, and every division is charged on the charging seed, so that no division is scored on the queries it was chosen with.

The rule reads only the sizes. For each level it takes $r$, the number of factors of four by which the level is smaller than the deepest: 0 for the deepest, about 2 for the middle level, about 4 for the smallest, since the levels here grow by a factor of sixteen. A level gets $b + \delta r$ bits a key, rounded down to the grid, with $b$ the largest value whose division fits the budget. One parameter, $\delta$, is swept from 0, the even split, to 8. A store using the rule would choose $\delta$ once; it is chosen here on the choosing seed of queries, which a store could sample, and then charged on the other seed. And a single $\delta$ of 4 is charged at every budget, as a store would use it with no queries at all.

Matching the division that tried everything #

Charged on queries it was not chosen on, the rule matches the division that tried every assignment at every budget on both arrival orders: on the shuffled store 71.5%, 97.2%, 99.0% and 99.0% at 0.5, 1, 2 and 4 bits a key, where the fitted division captures the same, and on the store filled a cluster at a time 78.9%, 99.8%, 99.7% and 99.7%, against 78.9%, 99.8%, 99.6% and 99.6%. The prediction for the shuffled store holds exactly. The prediction for the store filled a cluster at a time is wrong in the rule’s favour: it does not land near the even split’s 94%, it lands on the fitted division and at two budgets a tenth of a point above it.

That a one-parameter rule can beat the fitted division at all is a statement about fitting. The fitted division chooses three grid values from ten on the choosing seed, a thousand candidate divisions, and the best of a thousand on one sample is a little worse than the best on another. The rule chooses one value from eight, and its choice transfers. At two and four bits a key on the store filled a cluster at a time, the difference is a tenth of a point, inside what a second seed would move; the claim is that the rule is not worse, not that it is better.

A single $\delta$ of four, set with no queries at all, does nearly as well. On the store filled a cluster at a time it captures 99.7% to 99.9% from one bit a key up. On the shuffled store it captures 97.2%, 97.5% and 98.5% at one, two and four bits a key, within a point and a half of the fitted division, and 70.6% at half a bit, within one point.

The parameter, and where it fails #

At two bits a key the share captured climbs with δ on both orders and flattens past four: on the shuffled store from 67.5% at δ = 0, the even split, to 97.5% at δ = 4 and 99.0% at 8; on the store filled a cluster at a time from 94.2% to 99.9% at four. The climb is steeper on the shuffled store because there the even split is worse: every level holds keys from every cluster, a coarse prefix cannot rule the small levels out of most queries, and their filters need many bits a key to do it with a fine one.

The failure the proposal named is visible at one bit a key. There a δ of four gives the levels 16, 8 and half a bit a key, smallest first, and captures 97.2% on the shuffled store. A δ of six asks for more bits in the small levels than half a bit a key can pay for while the deepest keeps anything, and the rounding to the grid takes the deepest level’s filter away entirely: 16, 12 and nothing. The share captured falls to 73.9%, and on the store filled a cluster at a time from 99.8% to 78.8%. The deepest level holds 94% of the keys, and with no filter every range query reads it; its half bit a key was doing more than the small levels’ extra four.

A store choosing $\delta$ from a sample of its queries never chooses six at one bit a key, because the sample shows the collapse. A store setting $\delta$ in advance has to know where its deepest level’s curve turns, and on these stores a δ of four leaves it half a bit at one bit a key and a full bit at two, which is enough.

How much the budget forgives #

On the shuffled store every δ from two up beats the even split at every budget, and the advantage shrinks as the budget grows: at half a bit a key the even split captures 37.6% and δ = 4 70.6%; at four bits 83.5% and 98.5%. A generous budget forgives a poor division because every level then has enough bits to do most of its job, and the division only decides who gets the surplus. A tight budget forgives nothing. At half a bit a key there is not enough memory to give every level a working filter, and the right division gives the small levels everything and the deepest level nothing: the fitted division at half a bit is 16, 6 and 0 bits a key, and the rule at δ = 4 is 12, 6 and 0.

That is the regime where a store most needs to be told how to divide, and where the rule does least well against the division that tried everything: 70.6% against 71.5%, the largest gap at any budget. The gap is the grid’s: a δ of six or eight reaches 71.5% by putting the smallest level at sixteen bits instead of twelve. At one bit a key and above, the curves for δ from four to eight sit within a point and a half of the fitted division, except where a δ is large enough to starve the deepest level, and the budget at which a store’s filters stop being the cost that matters is the budget past which the division stops mattering too.

What each level gets #

The rule reproduces the fitted division’s shape at every budget — the two small levels near the top of the grid, the deepest at nothing to three bits — and at two bits a key on the shuffled store it gives exactly the fitted division’s 16, 16 and 1 bits a key. Where the two differ, they differ in the small levels, which hold six per cent of the keys between them: a few bits a key more or less there moves the memory by a few per cent and the cost by almost nothing, because the small levels’ filters are already near-perfect at twelve bits a key.

The shape is forced by the arithmetic of a levelled store more than by anything about these keys. The deepest level holds 94% of the keys, so every bit a key it gets costs the budget almost a bit a key. The small levels hold six per cent between them, so sixteen bits a key there costs about one bit a key of budget. Any division that makes the small levels’ filters good and leaves the deepest a little uses the budget well, and the rule’s one parameter only has to say how good the small levels’ filters should be.

A δ from the other store #

A δ chosen on one arrival order and charged on the other loses at most a point of the saving against the δ the store would have chosen for itself, and from one bit a key up at most half a point. At one bit a key both orders choose four. At two bits a key the shuffled store chooses eight and the clustered store six, and each does within half a point of its own choice with the other’s. The sizes, which both orders share, carry what the division needs; the arrival order, which decided how much a filter could do, does not decide how its memory should be split.

That is the result the earlier pages had been circling. The filter rebuilt with every write found that arrival order mattered more than when the filter’s lengths were chosen, and one bit a key, divided found the division that tried everything gave the same shape on both orders. Here the shape needs no trying. A store can divide its filter memory from the sizes of its levels, which it knows the moment it writes them, and a constant it can carry from one store to another.

Why the sizes are enough #

The rule’s premise was that a level’s saving from a bit is about the same per query at every level, so that only the cost of the bit differs. These measurements do not test that premise directly, but they test its consequence, and the consequence holds better than the premise would suggest. The levels’ curves are not alike, on the earlier page’s evidence: the fitted division never gave the deepest level more than three bits a key at any budget, and never gave the small levels fewer than six above half a bit, which says the deepest level’s filter does most of its work in its first bit or two and the small levels’ keep earning into double figures. What the rule needs is not that the curves be alike but that the optimum put the deepest level near the bottom of its steep stretch and the small levels near the top of theirs, and that is what any curves of these shapes do when the levels differ in size by a factor of sixteen.

So the rule is less a model of the filters than a model of the store. A levelled store’s levels grow by a fixed ratio, the arrangement whose writes the writes nobody counted counted against a B-tree’s, and that ratio is what the rule reads; the runs a range query can skip found that what a range query pays is set by how many of those levels it has to enter. A store with a ratio of four between levels, rather than sixteen, would have more levels of more similar size, and a rule that reads sizes would have more to say about how to divide among them.

What one store cannot say #

One store shape. Every number is a store of three levels at full size, sixteen times apart. A store with more levels of closer sizes, or one partway through its fill, has a different distribution of keys among its levels; the earlier page measured its division through the fill, and the rule was measured here only at the end.

One grid. The bits a key are rounded to the earlier page’s grid, and the collapse at a δ of six is partly the grid’s doing: a deepest level allowed a quarter of a bit would keep a filter. A finer grid would soften the failure and could not remove it.

Two seeds of queries. The choosing and charging seeds are one each. A tenth of a point between the rule and the fitted division is inside what a third seed would move, and the claim the plates support is that the rule is as good as the division that tried everything, not better. The queries themselves are the earlier pages’ mix of range widths; a workload of point lookups alone would value the deepest level’s filter differently, and the δ it wants is not measured here.

Still open: a store whose levels are not yet full #

The rule was measured on the full store, where three levels hold 4,096, 61,440 and 983,040 keys. Through the fill the deepest level is smaller, sometimes smaller than the middle one is at the end, and the ratio between levels changes at every merge. A store writing a level mid-fill would apply the rule to the sizes it has then, and those sizes are what the rule must be right about.

The measurement that follows applies the rule, with δ fixed at four, at every point of the fill the earlier page measured — an eighth, a quarter, three eighths, a half, three quarters and the whole of the keys — on both orders at every budget, against the division fitted at that point. The prediction is that it stays within a point and a half of the fitted division throughout, since the ratio between levels never falls below four in a levelled store and the rule’s arithmetic holds at any ratio that large. It could fail early in the fill, where the deepest level is the newest and smallest relative to its own eventual size, and the store has fewer keys than its budget was sized for; the rule’s half bit for the deepest level could then be too little at a moment when that level is most of the store. The question is whether a rule that reads sizes is right at every size a store passes through, or only at the size it ends at.