Two lengths that do the work of eleven

One length for the gaps and the clusters put a million keys into sixteen clusters covering a sixteenth of key space and asked range queries of them. Half started anywhere in key space and so fell mostly in the gaps between clusters, and half were centred on stored keys. Each level of the four-level store carried a Bloom filter over key prefixes, and a range skips a level when the filter answers no for every prefix the range touches. One design gave each level a single prefix length, chosen for the store, the workload and the memory. The other, the multi-resolution filter, held every length from 12 to 24 bits in one level’s memory and asked each range from the coarsest length down, refining only below a yes. On that mixed workload, at ten bits a key, the multi-resolution filter won by 0.17 transfers a range query. It won on short ranges at the keys, which its coarse filters freed its fine one to serve.

Its closing section argued that two of the eleven lengths do nearly all the work: a coarse one that says no to the gaps and a fine one for the keys. It proposed a pair per level, chosen together, asked coarse first. It predicted that the pair would recover nearly all of the multi-resolution filter’s margin, because on a clustered store the coarse filter holds few prefixes and costs almost nothing, so the fine length would get nearly all the memory. And it named the store that could defeat a pair: one whose clusters come in two sizes, where the gaps would want different coarse lengths.

The store, the three designs and the search #

The store is the earlier pages’ to the key: four levels of 2²⁰ 32-bit keys in all, levels growing tenfold, a transfer charged for each level read and each block of keys it returns. Range lengths are 0.1, 1, 10 and 100 expected keys on a uniform store, 600 ranges of each, half anywhere in key space and half centred on a stored key. The filters are the same Bloom filters, one a level as in the filter each run carries, and a design that holds several lengths on a level divides the level’s memory between them in proportion to the distinct prefixes each holds, so every prefix gets the same number of bits. Every query checks that no filter skipped a level holding a key of the range.

A pair is chosen per level by trying all 105 pairs from the fifteen lengths the earlier page searched, from 12 bits to 30, and keeping for each level the pair that costs that level least. The single length a level is chosen the same way from the fifteen. The multi-resolution filter is the earlier page’s, lengths 12 to 24. Three stores are measured, all of the same density. The earlier page’s 16 clusters. Four large clusters and 64 small ones, each group holding half the keys. And 16 groups of 16 clusters, the groups spread over key space and the clusters inside each group close together. That store’s gaps come at two scales, wide between groups and narrow inside them, which is the property the earlier page said could defeat a pair.

More than the whole margin, at every memory #

At ten bits a key the best pair a level saves 0.226 transfers a range query against one length a level. The multi-resolution filter saves 0.172. The prediction was that the pair would recover nearly all of the margin. It recovers 131% of it. At 24 bits a key the pair saves 0.162 against 0.131, 124%. The pair is not an approximation to the multi-resolution filter that gives up a little. It is a better filter.

At four bits a key the difference is larger than a share. There the multi-resolution filter costs 0.200 transfers a query more than one length a level. Dividing four bits among eleven lengths leaves every filter too few bits to be selective, and the coarse questions that cost nothing at ten bits start answering yes at random. A Bloom filter with four bits for each of its items answers yes to about one absent item in seven, where at ten bits it is one in a hundred; a filter allowed to be wrong set out that bargain, and four bits divided eleven ways is well below the point where it is worth making. The pair saves 0.183 at the same memory. Where eleven lengths were worse than one, two are better than one.

The pairs chosen are consistent. At ten bits every level’s coarse length is 12 or 14 bits and its fine length 23 to 26. At four bits the fine lengths are shorter, 20 to 22, as the earlier pages found a starved filter should be. At 24 bits the coarse lengths rise to 14 to 20, because with more memory a finer coarse length can afford to hold more prefixes and says no to narrower gaps.

Where the memory goes, and why it cannot simply be moved #

The multi-resolution filter leaves its finest length between 14% and 37% of each level’s memory. The pair leaves its fine length at least 98%. The earlier page’s reasoning was right about the coarse filter. On sixteen clusters a level’s keys fall in 263 distinct 12-bit prefixes, so a coarse filter at 12 bits holds under 2% of the prefixes on the smallest level and under a twentieth of a per cent on the largest. What it did not weigh is that the multi-resolution filter’s lengths between 16 and 22 bits are not coarse. Inside a cluster, where every key is, a 20-bit prefix covers 4,096 key values, about sixteen keys’ worth, so on the large levels nearly every one of them holds a key. The middle lengths therefore hold nearly as many distinct prefixes as the finest, and dividing memory by distinct prefixes gives each of them nearly as much. The finest filter, the one that decides every short range at the keys, gets a seventh to a third of the level.

That suggests an easy repair: give the finest length most of the memory and leave the middle lengths the rest. Given 90% of each level’s memory for its finest length, the multi-resolution filter costs 7.375 transfers a query — worse than one length a level, and far worse than with its memory divided evenly. The middle lengths are not idle. The filter asks a range from the coarsest length down, and each yes is replaced by all its children at the next length. A middle filter starved of bits answers yes to most of its prefixes, so the number of children to ask multiplies at every step, and past 256 probes on a level the filter gives up and the level is read. With 90% to the finest, the filter makes 499 probes a query against 250, and reads levels it could have skipped. In a descent through eleven lengths, every length is load-bearing.

The pair has no middle to starve. After one coarse question it goes straight to the fine prefixes the range touches, and for a range short enough to be decided by the fine filter there are a handful of them. It needs two filters to be good, not eleven, and so it can give almost everything to one of them. Held to lengths of 24 bits or less, as the multi-resolution filter is, the pair costs 6.651 transfers a query, already under the multi-resolution filter’s 6.697. Free to go finer, it costs 6.643. Nearly all of the lead is the structure: one step where the multi-resolution filter takes ten.

This is the argument the small levels’ share of a range filter made about levels, turned inside a level, with a twist. There, dividing memory evenly between levels of very different sizes was the waste, and moving it recovered much of the gap. Here, the even division looks like the waste and moving it makes things worse, because the design that divides it depends on every part of it. The saving comes from changing the design, not its allocation.

Short ranges and long ones #

On the shortest ranges, a tenth of a key expected, the pair wastes 0.083 transfers a query above the oracle, against 0.215 for the multi-resolution filter and 0.697 for one length a level. On the longest, a hundred keys, 0.023 against 0.093 and 0.170. The short ranges are where the earlier page found the multi-resolution filter’s advantage: most of them sit inside a cluster, the coarse lengths all say yes, and the answer comes down to the finest length’s false-positive rate. The pair’s fine filter has between two and a half and seven times the multi-resolution filter’s finest memory, and its false reads fall accordingly.

The long ranges are the gaps’ business. A range of a hundred keys’ width that starts in a gap usually lies wholly in it, and a coarse filter that answers no for its few prefixes skips the level. Both designs have a coarse filter for this. The pair’s does better because it has only one step to take after a coarse yes: the fine filter. The multi-resolution filter, after a coarse yes at a gap’s edge, descends through every middle length, and each of those, holding a crowded cluster’s prefixes, can pass the range on. At ten keys neither design gains over one length. That range length is the one the single lengths were chosen closest to.

The store that was to defeat a pair #

On every store the pair is cheapest: 6.563 transfers a query against the multi-resolution filter’s 6.617 on clusters of two sizes, and 7.199 against 7.235 on clusters in groups, whose gaps come at two scales. The prediction’s failure case does not happen, and the reason is in what a coarse filter is asked. A gap is skipped when every prefix the range touches is empty. A prefix of 14 bits covers 2¹⁸ key values. It is empty inside a gap between groups, which is millions of values wide, and inside a gap between two clusters of one group, which is still wider than the prefix. How wide the gap is beyond the prefix’s width does not matter to whether the prefix is empty. One coarse length fine enough for the narrow gaps also serves the wide ones.

The chosen pairs show this. On the grouped store the coarse lengths are 14 and 16 bits, two bits finer than on sixteen plain clusters, which is what the narrower gaps inside a group ask for. The wide gaps did not ask for anything coarser. The pair’s margin over the multi-resolution filter is smaller on the grouped store, 0.036 transfers against 0.054, and all three designs pay more there, because clusters that sit close together leave fewer empty prefixes at any length.

The two scales do cost the pair something, but not in transfers. A long range in a wide gap touches many 14-bit prefixes, and the pair asks each one, where a coarser length would have covered the range in two questions. That cost is in the filters’ probes, which the earlier pages did not charge, and it is the one place a pair loses.

The same saving on queries that did not choose it #

Charged on 2,400 range queries that played no part in choosing it, the pair saves 0.224 transfers a query over one length a level on sixteen clusters at ten bits, against 0.226 on the queries that chose it. A pair is picked from 105 per level on the same queries it is then charged on, and a search that large can fit the queries rather than the store. The single length is picked the same way from fifteen, so both are flattered, the pair more. On fresh queries from another seed the saving holds on every store at every memory, from 0.124 to 0.228 transfers a query, and the pair stays below the multi-resolution filter in every one of the nine cells. The largest drop is on the grouped store at ten bits, 0.215 to 0.185, where the chosen pair fitted its queries a little more than elsewhere.

The resolution a range filter can afford proposed the multi-resolution filter as the design that would not need its lengths chosen at all. It needed them chosen too — the range 12 to 24 was a choice — and the lesson of the two pages since is that a filter holding every resolution pays for all of them, and cannot pay less for the ones its descent only passes through. Choosing two, and checking the choice on queries it did not see, costs a search of 105 pairs a level once, when the store is built or when its workload changes.

What the pair asks for its saving #

The pair asks its filters 280 times a range query on sixteen clusters, against 250 for the multi-resolution filter and 117 for one length a level. A probe is a hash and a few bit reads in memory, cheap beside a block transfer from storage, the unit the runs a range query can skip set for these range filters, and like the earlier pages this one charges transfers and not probes. But the pair’s saving is not free in probes. Its coarse length is fine by the multi-resolution filter’s standard, 12 to 14 bits against 12. A long range must be asked at many prefixes of that length, where the multi-resolution filter asks a 12-bit length first and descends only below a yes. On the grouped store the pair asks 4% more than the multi-resolution filter, on sixteen clusters 12% more. One length a level asks less than half as often as either, because it asks each range once, at one length, and pays for that in transfers.

That is the exchange a system choosing between them has to price. At a transfer costing thousands of probes, the pair is the better filter by a clear margin. On a store held in memory, where a transfer is a few cache misses, the multi-resolution filter’s fewer probes and the single length’s fewest could matter more than the pair’s fewer false reads. The read a filter has no key for found range filters bounded by what a range can name. This one is bounded by how many names a range has to be asked under.

The limits of the measurement #

One set of stores, one seed each. Every store is one draw of cluster positions, and every cost is 2,400 range queries. The fresh-query figure checks the choice against its own queries, not against another draw of the store.

Pairs, not triples. A third length per level, between the coarse and the fine, might recover the probes the pair spends on long ranges, and cost the fine filter a few per cent of its memory. It was not searched: 455 triples a level against 105 pairs.

Memory is divided by distinct prefixes. The pair’s coarse filter gets its share of the memory in proportion to its prefixes, the same rule the multi-resolution filter uses. A pair that gave the coarse filter a fixed fraction, or chose the division along with the lengths, might do slightly better. The coarse filter already holds under 2%, so the room is small. It is also small enough, a few hundred prefixes on the small levels, that its rate strays from the textbook formula, which the formula everybody sizes filters with found accurate for filters of thousands of keys; its false yeses were measured here, not predicted.

Transfers are charged, probes are counted. As on every earlier page about these filters, the cost is block transfers. The probes are reported so that the exchange is visible, not folded into the cost.

Still open: a pair that is chosen by the store as it fills #

Every design here is chosen once, for a store that holds all its keys. A log-structured store does not. Its small levels are rewritten constantly as data arrives and merges down, and a filter’s lengths are chosen when a level is written. The runs a range query can skip chose one length for every run; the pair adds a choice that depends on how the level’s keys cluster, and a small level’s keys are the ones that arrived most recently.

The measurement that follows builds the store by insertion, rewriting each level’s filters whenever the level is rewritten, and chooses each level’s pair from the keys it holds at that moment and the queries of the last period. It compares that with the pair chosen once on the full store. Keys are inserted in two orders: shuffled, so every level sees every cluster, and in batches that each land in one cluster, as time-ordered keys do. The prediction is that on shuffled arrivals every level chooses the pair it would have chosen on the full store. On batched arrivals the small levels see two or three clusters at a time, choose a pair for a store with wide gaps and few clusters, and pay for it, about a tenth of the pair’s saving, when the next batch lands elsewhere. The question is whether a pair chosen from a level’s own keys, as a real store would have to choose it, keeps the lead a pair chosen from the whole store has, or whether the two-length design needs the store to know its own shape better than a filling store can.