One bit a key, divided

The filter rebuilt with every write filled a levelled store of a million keys by insertion and gave each level a range filter made of two prefix lengths, a coarse one and a fine one, chosen from the level’s keys whenever the level is written. A levelled store changes a level’s keys only by rewriting it, so a filter can never go stale, and the essay found that what mattered was not when the lengths were chosen but the order the keys arrived in. The keys sit in sixteen clusters. Filled a cluster at a time, the small levels hold one cluster each, a coarse prefix rules them out of almost every query, and at two bits a key the filters capture 94% of what a perfect filter would save. Filled shuffled, every level holds keys from every cluster, and the filters capture 68%.

That essay’s closing section looked at where the remaining cost sat and proposed moving memory to it. On the store filled a cluster at a time, the small levels’ filters already capture nearly everything at two bits a key, so every bit a key there is spent on a question the coarse prefix has mostly answered. The deepest level, holding fourteen clusters, sits within a few thousandths of a perfect filter. The middle level was where memory could still pay. So it proposed a fixed total of filter memory, divided among the levels in proportion to what each level’s filter would save per bit and re-divided at every write. It predicted that on the store filled a cluster at a time almost all the memory would move to the middle and deepest levels, the store’s cost falling by a few hundredths of a transfer a query, and that on the shuffled store the even split was already close to right.

Dividing a budget by what it buys #

The store, its keys and its queries are the earlier essays’. 2^20 keys in sixteen clusters are inserted into a levelled store with a buffer of 4,096 keys and levels growing fourfold; at every write a level’s filter is rebuilt with the best pair of prefix lengths for its keys. A query asks a range expected to hold 0.1, 1, 10 or 100 keys, half placed anywhere and half centred on a stored key, and costs a transfer for every level the filter fails to skip and a transfer for every block of keys a level holds in range. A perfect filter skips every level holding nothing of the range and nothing else.

For each level, and for every number of bits a key on a grid from nought to sixteen, the best pair is chosen and the level’s cost is read. The division is the assignment of a grid value to every level, within a budget of memory, that makes the whole store cheapest; with three to five levels and ten grid values the search is exhaustive. The division is found on one seed of queries and charged on another, so it is not fitted to the queries it is scored on. The even split gives every level the average. The search is the exact optimum the proposal’s rule of thumb, memory in proportion to what it saves per bit, was a way of approximating.

Through the fill #

Divided by what each level saves, two bits a key capture 99% of a perfect filter’s saving on the full store whichever order the keys arrived in, against 68% and 94% split evenly. On the shuffled store the division recovers almost the whole of what the earlier essay found missing; on the store filled a cluster at a time it recovers the last six points. Through the fill the picture holds from a quarter full on. Only at an eighth full, with three levels and the deepest still small, does the shuffled store’s division stop at 78%.

The prediction had the size of the gain backwards as well as the direction. It expected a few hundredths of a transfer a query on the store filled a cluster at a time and little on the shuffled one. The gain is 0.13 transfers a query filled a cluster at a time and 0.59 shuffled, a tenth of the store’s whole cost.

The full store, level by level #

Every transfer the division saves is on the two small levels; the deepest level costs the same, within six thousandths of a perfect filter, under both splits. On the shuffled store the smallest level’s cost halves, from 0.809 transfers a query to 0.411, and the middle level’s falls from 1.108 to 0.911. Each lands within a hundredth of what a perfect filter would cost it.

The small levels cost as much as they do because they are small. A range the store holds keys in usually reaches the deepest level, which holds 94% of the keys, and that reach is a transfer nobody can avoid. The small levels hold a few thousand keys each, scattered over all sixteen clusters when the store is shuffled, and a range asks each of them whether it holds anything; at two bits a key their filters answer wrongly often enough to cost six tenths of a transfer a query more than a perfect filter between them. On the store filled a cluster at a time the small levels hold one cluster each and are wrongly asked much less, which is why the even split did well there and why the division has less to give.

Where the bits go #

The division gives the small levels twelve to sixteen bits a key and the deepest one bit, at every point of both fills. It is the reverse of the even split and the reverse of what the proposal expected. The proposal reasoned from where the filters were already good; the division reasons from what a bit a key buys on each level, and on a small level a bit a key is cheap in total memory and buys a great deal.

The small levels’ share of a range filter found the same direction for single prefix lengths on a static four-level store, 12, 12, 8 and 3 bits a key instead of 5 each, recovering half the gap to a perfect filter; the filter each run carries found it for point lookups. What is new here is how far it goes with a pair of lengths. One bit a key on the deepest level costs nothing measurable, because its coarse prefix rules out the gaps between clusters and its fine prefix needs little memory to separate keys that a level so dense holds in nearly every range anyway. And the arrival order, which decided so much at an even split, decides almost nothing once the memory is divided.

What a bit buys on each level #

The deepest level has 2.3% of its avoidable cost left at half a bit a key and 1.3% at one, and the two small levels need sixteen bits a key to get that close. That is the whole of the division’s reasoning on one plate. Half a bit a key on 983,040 keys is half a million bits; sixteen bits a key on the 65,536 keys of the two small levels together is a million. The even split’s two bits a key put two million bits on the deepest level, where everything past one bit a key buys almost nothing, and an eighth of a million on the small levels, where those few bits buy only half to two thirds of the saving that was there.

The curves’ shapes are the reason a budget divided this way stops spending. Past sixteen bits a key the small levels’ curves have nowhere left to fall, and the deepest level’s is flat from one bit on. At two bits a key on average the division spends 1.94 bits on the shuffled store and 1.69 on the store filled a cluster at a time; more memory buys nothing the grid can find.

Why the deepest level needs so little #

The deepest level holds 94% of the keys and every one of the sixteen clusters, so it is the level a range is least able to skip. Half the queries are centred on a stored key, and those meet the deepest level almost always, which a perfect filter charges as well. The other half are placed anywhere in the key space, and fifteen times in sixteen they fall between clusters. Two lengths that do the work of eleven built the pair for exactly that mixture: a coarse prefix that rules out the empty stretches between clusters with few bits, and a fine one for the ranges that land in a cluster. On a level this dense the fine prefix has little to do, because a range that lands inside a cluster usually does hold one of the level’s keys, and the coarse prefix needs only a few hundred prefixes to cover the clusters. Both fit in half a bit a key. At one bit a key the deepest level on the shuffled store chooses twelve and twenty bits, the same pair it chooses at eight. A twelve-bit prefix divides the key space into 4,096 parts, and the sixteen clusters, a sixteenth of the space, occupy about 256 of them; a filter that holds those 256 rules out almost every range between clusters with a few thousand bits. The small levels, given sixteen bits a key, move their fine length out to 23 and 25 bits, spending the memory on resolution inside the clusters.

The small levels are the opposite case. A few thousand keys scattered over every cluster leave most short ranges inside a cluster empty, so the fine prefix has real work and needs memory to do it without false positives. The runs a range query can skip found that by ranges of a hundred keys only the smallest level is ever empty; the small levels are where a range filter’s decisions are made, and the deepest level is where it confirms what was already likely.

How much memory the store needs #

Divided, one bit a key on average captures 97% of a perfect filter’s saving on the shuffled store; spread evenly, four bits a key capture 84%. The memory a range filter needs on this store is about one bit a key, if it is put where it buys something. Half a bit is too little for any division: the small levels can be given sixteen bits a key only by starving the deepest level to nothing, and a deepest level with no filter costs half a transfer a query.

The divided curves are flat from one bit on because the grid stops at sixteen bits a key and there is nothing left to buy. The last per cent between the division and a perfect filter is the small levels’ remaining false positives at sixteen bits a key and the deepest level’s at one, and closing it would take more bits on levels whose curves are already flat.

Where the memory goes #

Divided, the two small levels hold 6% of the keys and get half the memory on the shuffled store; the deepest level, 94% of the keys, gets the other half at one bit a key. On the store filled a cluster at a time the division leaves a sixth of the budget unspent, because the small levels’ single clusters are ruled out cheaply and twelve bits a key already finishes them.

The re-division at every write the proposal asked for comes free with the store. A levelled store rewrites a level whole, and rebuilds its filter, every time the level changes, so it can size the filter to the level’s current share at that moment. Those rewrites are the write cost the writes nobody counted measured, two elements written for every key stored, and they are paid whether or not the filter is resized; a division recomputed at each write adds the arithmetic of choosing and nothing else. The earlier essay priced choosing a pair at every write at 28 times the hashing of building one filter; a division adds a choice of bits a key to that choice of lengths, and the grid here multiplies the candidates by ten. The division plate through the fill is exactly that: at every point the levels’ sizes differ, and the division follows them.

What the counts depend on #

The division is fitted to the workload. It is found by trying every assignment against one seed of the actual queries, and charged on another seed of the same mixture. A store choosing its division before its queries arrive would have to predict what a bit a key buys on each level; the plate of curves shows the shape, and nothing here shows how well a prediction would track it.

A grid of bits a key. The levels are offered nought, half a bit and 1, 2, 3, 4, 6, 8, 12 and 16 bits a key. A finer grid would spend the leftover budget and close part of the last per cent; a coarser one would not change the direction.

Range queries only. The workload asks ranges, and the filters are prefix filters. A store answering point lookups as well would want its deepest level’s filter to separate keys, which half a bit a key cannot do; the read a filter has no key for measured how differently the two kinds of query use the same memory. A division for a mixed workload would weigh both, and was not measured.

One store, two orders. The keys are the earlier pages’ sixteen clusters. A store whose keys are spread uniformly would have small levels that a coarse prefix cannot rule out, and the division would have more to buy there.

Still open: a division chosen before the queries arrive #

The division here was found by trying every assignment against the store’s own queries, which a store cannot do 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. The small levels’ share of a range filter and the filter each run carries both point at a division set by the levels’ sizes alone: a level’s false-positive cost is about the same for every level per query, so the bits a key should grow by a fixed amount for every factor of four by which a level is smaller.

The measurement that follows divides the memory by that rule, from the sizes alone, with the extra bits a key per factor of four as its one parameter, and charges it on both orders through the fill against the division found here. The prediction is that on the shuffled store the rule comes within a point of the fitted division’s 99%, since the levels’ curves there differ mainly in their sizes, and that on the store filled a cluster at a time it gives the small levels bits they do not need, landing at the even split’s 94% or a little above. It could fail on the deepest level. The rule gives it the fewest bits a key, but if it gives it less than half a bit, the deepest level’s curve is steep there, and a rule tuned to the small levels could lose more on the deepest than it gains on them. The question is whether a store can size its filters from its levels’ sizes, or whether what a bit buys depends on where the keys sit, which only the queries can say.