A level scaled by the queries it meets

A levelled store keeps its keys in levels of growing size, each with its own range filter, and a range query that a level’s filter can rule out costs that level nothing to read. The filters share a budget of bits a key, and the question several essays have worked on is how to divide it. A division chosen before the queries arrive fitted the division to the store’s own queries, a search over every way of giving each level a number of bits, and showed it was worth having. The rules since have tried to reach the fitted division without the search, from what the store knows when it writes a level.

The size rule gives each level a base number of bits plus a slope times the base-four logarithm of how much smaller it is than the largest level — small levels are cheap to protect, so they get more bits a key — with the base chosen so the budget is spent. A floor under every level added a floor of half a bit a key and found the rule within five points of the fitted division from one bit up, on a store filled in shuffled order and on one filled a cluster at a time. At half a bit it could not be: the floor is the whole budget there, every level gets exactly half a bit, and the two stores wanted opposite things from levels of identical sizes.

A span the queries do not see tried to tell the stores apart by their fences. A level filled a cluster at a time spans a few clusters and is ruled out by its first and last keys for most range queries; a shuffled level spans everything. Scaling each level’s bits by its span changed nothing at half a bit, where the floor still decided, and from one bit up it put the clustered store thirty points behind, because the queries were half uniform and half aimed at stored keys, and a level holding one cluster spans 0.004 of the key space but meets 4.4% of the key-aimed queries.

Its closing section proposed letting the floor step aside: apply it only when the budget is at least twice the floor, so that at half a bit the size rule divides freely, deepest level included. The prediction was precise. The shuffled store would come within ten points of the fitted division; the clustered store, whose fitted division at half a bit is the even split at most checkpoints, would lose 26 points as the unfloored rule had; and so the gap at half a bit would be shown to be a gap between workloads rather than between rules. This essay runs that, and then the repair the span plate itself pointed at: scaling each level not by the key space its fences span but by the share of the queries that can land inside them.

The floor, stepping aside #

Applying the floor only when the budget is twice it gives exactly what the proposal predicted at half a bit a key: 9.3 points behind the fitted division on the shuffled store, from 34.8, and 26.1 on the clustered store, from 9.1 — the two stores trade places, and at one bit it is the floored rule. Nothing here is surprising, and the plate’s value is that it is not. A prediction made from two measured rules about their splice should be exact, and a plate that confirmed it only roughly would have meant one of the earlier measurements had drifted — that the store, the queries or the fitted division were no longer what they were when those rules were measured. They are. The conditional floor is two existing rules spliced at one bit a key, so its numbers are the unfloored rule’s below one bit and the floored rule’s from one bit. What the plate settles is the proposal’s claim about them: no setting of the condition is right for both stores at half a bit, because each store wants the opposite rule.

The shuffled store at half a bit wants its deepest, largest level to get nothing and its small levels several bits — the fitted division gives 8, 4, half a bit and nought at the halfway checkpoint — and the floor forbids the nought. The clustered store wants half a bit everywhere, at four of the six checkpoints, and without the floor the size rule gives its largest level nothing and spends the bits on small levels that the clustered workload rarely asks about. One store is helped by a rule that lets a level go bare, the other by a rule that forbids it.

What a level’s fences can meet #

At the end of the fill the clustered store’s newest level spans 0.004 of the key space and holds 0.062 of the keys, so 3.3% of a workload half uniform and half aimed at stored keys can land inside its fences; every shuffled level meets about 90.8%. The reach is what the span rule should have measured. Half the queries start at a uniform point of the key space and meet a level in proportion to its span; half start at a stored key and meet it in proportion to the keys inside its fences. The clustered store’s newest level is one cluster, a sliver of the key space holding a sixteenth of the keys, and the span alone made it look twenty times less reachable than it is.

The shuffled store’s levels are all the same to the queries. Each spans from near the bottom of the key space to near the top — 0.816 at the end of the fill, since the clusters sit inside it — and holds every key’s neighbourhood, so each meets about 91% of queries. That uniformity matters in the next plate more than anything about reach.

The shuffled store, closed #

On the shuffled store at half a bit a key, scaling each level’s bits by the queries that reach it, with no floor, comes within 2.2 points of the fitted division at every checkpoint, where the unfloored size rule falls 9.3 behind and the floored rule, which can only give every level half a bit, 34.8. At half a bit this is the closest any rule measured has come to the fitted division on the shuffled store, and it is closer than the proposal’s ten points by a factor of four. The worst checkpoint for the unfloored size rule was halfway through the fill, where it gave four levels 6, 6, nought and nought bits and the fitted division gave 8, 4, half and nought; the reach-scaled rule gives 6, 4, half and nought.

The next plate is needed before believing that reach did it.

The same rule, the other store #

On the clustered store the same rule is the worst measured: at half a bit a key it falls 41.5 points behind the fitted division at three quarters of the fill, giving its four levels 0.5, 0, 1 and 0 bits a key, newest first, where the fitted division gives half a bit to each, against the floored rule’s 9.1 and the unfloored size rule’s 26.1. At half a bit the clustered store wants the even split, and the reach rule departs from it further than the size rule did. Scaling by reach multiplies each level’s target by its share of the queries — 3% for the newest level, more for each level below it, 91% for the largest — and at a budget this small the multiplied targets snap to the grid unevenly: the second level is snapped to nothing, the largest is given nothing as the unfloored size rule gave it, and the bits go to the third.

At one bit a key the failure has a cleaner shape. The reach rule, with the conditional floor, gives the clustered store’s newest level half a bit a key at the end of the fill, where the fitted division gives it twelve. The size rule’s slope was there to give small levels more bits a key, because they are cheap to protect; multiplying the newest level’s target by three hundredths takes those bits away again, and the budget flows to the levels whose bits are dear. That is why the reach rule stays near thirty points behind at every budget from one bit up.

The fitted division disagrees with that reasoning in a way the plates make plain. At one bit a key and above it gives the clustered store’s newest level six to sixteen bits a key, the most of any level, although that level meets a thirtieth of the queries. A level of 4,096 keys costs a fifteenth as much to protect as one of 61,440, so the bits a query it saves cost little however rarely it is asked. Reach tells a rule how often a level is worth protecting; it says nothing about how cheaply. A rule that scales by reach throws away the very thing the size rule’s slope encodes.

A slope, not a reach #

On the shuffled store every level meets the same 91% of queries, so scaling by reach is the size rule with its slope cut from 4 to about 3.6: unfloored at half a bit, the size rule at a slope of 3 or 3.5 is also 2.2 points behind, against 9.3 at 4 — and at one bit no slope comes within 6.7 without the floor. The shuffled store’s improvement is not about reach at all. A rule that multiplies every level’s target by the same 0.908 multiplies the base and the slope by it; the base is then re-solved to spend the budget, and what is left is a slope of 3.63 instead of 4. The size rule at that slope, with no reach in it anywhere, reaches the same 2.2 points.

So the plates say something narrower and more useful than the proposal hoped. At half a bit a key on the shuffled store the size rule’s slope of four was a little steep, and three to three and a half is right; at one bit the floor is what matters and the slope barely does. The slope had been set at four where the rule was introduced, on the full store at a bit a key and more, and the sizes a store passes through carried it through the fill; nothing since had swept it at half a bit.

Why the size rule’s slope was the right instinct #

It is worth saying why the size rule works as well as it does, since the plates have now twice shown a better-sounding measure doing worse. The small level’s share of a range filter found, on a four-level store, that most of the gap to a perfect range filter was false positives rather than prefix lengths, and that moving filter bits from the largest level to the small ones — twelve, twelve and eight bits a key against a few on the deepest — closed much of it. That is the slope’s whole content. A false positive costs a read whichever level makes it, and a small level’s false positives are cheapest to remove, because each bit a key there is a bit on few keys.

What the slope does not know is how often a level is asked. On the shuffled store that does not matter, because every level is asked about equally, and the slope only needs to be the right steepness — three to three and a half at half a bit. On the clustered store it matters a great deal, and in a direction a reach rule gets backwards. The filter rebuilt with every write found that a levelled store changes a level’s keys only by rewriting it, so a small level’s filter is always fitted to the keys it holds; the clustered store’s newest level holds the cluster that arrived last, and the key-aimed queries that land in it are aimed at exactly those keys. Few queries reach it, but those that do are queries a filter can turn away cheaply.

One length for the gaps and the clusters made the related point about a single filter: whether ranges fall between the clusters or at the keys changes which prefix length is right, and the right one has to be chosen for the workload. A level’s reach is a fact about where its fences sit, not about how its filter’s false positives fall, and the second is what the bits buy.

What the half-bit gap is #

The proposal’s own conclusion survives, and sharpened. At half a bit a key the two stores want opposite divisions — one wants a level left bare, the other wants every level protected equally — and no rule measured here gives both: the best on the shuffled store is the unfloored rule with a gentler slope, 2.2 points, and the best on the clustered store is the floored rule, 9.1. A rule reading the levels’ sizes, spans or reach can tell the stores apart, since the clustered store’s reach varies thirtyfold across its levels and the shuffled store’s not at all; but what it would need to do with that difference is not scale each level by its reach. It would need to choose between two rules.

One bit a key, divided proposed dividing the memory by what each level’s filter saves per bit, which is the quantity both of these rules approximate: queries a level meets, times what each costs, over the bits its keys take. The filter each run carries is where that arithmetic was first set out, for Bloom filters on a three-level store — five bits a key spread evenly wasted 0.279 reads a missing key, and the same memory moved to the small levels 0.201. A rule that scales by reach keeps the first factor and discards the third. On a clustered store the smallest level is the one a query-share rule protects least and the fitted division protects most, because the third factor is where its advantage lies.

What the measurement does not settle #

One workload. Queries half uniform and half aimed at stored keys, a few keys wide. A workload that aimed every query at stored keys would raise every level’s reach towards its share of the keys, and a uniform one would make reach the span.

Six checkpoints. The worst gap is taken over six points of the fill. A store’s divisions change between them, and a rule within two points at all six may be further out between.

A grid of bit settings. Every rule’s bits are snapped to the same grid the fitted division searches — nought, half a bit, one, two, three, four, six, eight, twelve and sixteen bits a key — so a rule can be wrong by a whole grid step on one level, and at half a bit a key a single step on the largest level is most of the budget. Some of the gaps above are snapping as much as division.

One store of each kind. Sixteen clusters, three or four levels. A deeper store would give the slope more levels to act on and might move its best value.

Still open: a rule that chooses which rule #

The plates leave a clean decision for a store to make at half a bit a key: on a store whose levels all meet about the same queries, give no floor and a slope of about three and a half; on a store whose newest level meets a small fraction of what the others do, floor every level at half a bit. Both quantities are known when a level is written. A rule could compute the ratio of the smallest level’s reach to the largest’s and switch between the two divisions at some value of it.

The measurement that follows uses that ratio, switching at a ratio of a half, at budgets of half a bit and three quarters, on both stores and on a third filled in an order between the two — clusters arriving in shuffled pairs — so that the switch has a case it was not shaped on. The prediction is that it comes within three points of the fitted division on the shuffled store and within ten on the clustered, and that on the intermediate store it lands within ten. It could fail on the intermediate store, whose reach ratio may sit near the switch, where a choice between two rules that disagree by twenty points makes a small error in the ratio a large error in the result. The question is whether a store’s own fences can tell it which of two divisions to use, or whether at half a bit a key the division has to be read from the queries themselves.