One length for the gaps and the clusters

The resolution a range filter can afford set two designs against each other on a four-level log-structured store of $2^{20}$ keys. The first keeps one Bloom filter a level over the keys’ prefixes at a single length, chosen for the level and the memory. The second keeps prefix filters at every length from 16 to 24 bits in the same memory and asks a range from the coarsest length down, refining only below the answers that come back yes. Chosen again for each memory, one length a level won at every memory from two bits a key to thirty-two. The reason was a plate of occupancies. On uniform keys the largest level holds a key in every 16-bit prefix and in 93% of 18-bit ones. A coarse question there is truthfully answered yes and rules out nothing, and the memory spent on coarse filters buys no skip.

Its closing section said the uniform keys were the reason and proposed clustered ones. Timestamps arrive in bursts and identifiers are handed out in blocks, so a key space of 32 bits holding a million keys in a few dense regions has most of its coarse prefixes empty. The prediction was that the coarse filters would then say no to long ranges between the clusters, and that the multi-resolution filter would pay on clustered keys and not on uniform ones. It named the way it could fail. Clustering might make the fine prefixes inside a cluster denser, so that the best single length moved finer inside the clusters and coarser between them, and one level would want two lengths at once.

The store, the clusters and the questions #

The store is the earlier pages’ in everything but where its keys come from: four levels of 16K, 64K, 256K and 688K keys, charged one transfer to find a range’s start in a level and one more for every 64 keys it reads there. A level is skipped only when its filter can show that no prefix the range touches holds a key, and every skip is checked against the level’s keys. Here the keys are drawn from a stated number of windows of key space, each placed at random and filled uniformly, the windows together covering a sixteenth of the space. Five stores are measured: uniform keys, and keys in 65,536, 4,096, 256 and 16 clusters. The multi-resolution filter now keeps eleven lengths, 12 and 14 bits and every length from 16 to 24, since on a clustered store a 12-bit prefix can be empty, and as before each stored prefix gets the same share of the level’s memory.

A range is the same width as before, wide enough to hold a tenth of a key, one, ten or a hundred keys on the uniform store. On a clustered store the width matters more than the count, because a range of that width holds sixteen times as many keys inside a cluster and none in a gap. So where ranges start is now part of the question. Three workloads are measured: ranges that start anywhere in key space, most of which on a clustered store fall in the gaps; ranges centred on a stored key, which fall inside the clusters; and half of each.

Most coarse prefixes are empty #

On the largest level, keys in sixteen clusters leave 94% of 12-bit prefixes empty and 94% of 16-bit ones, where uniform keys fill all of them. The clusters cover a sixteenth of key space, so at any length coarse enough for a cluster to span many prefixes the occupied share settles at about 6%. Only at the finest lengths, where the prefixes are narrower than the gaps between keys inside a cluster, does the share start to fall again, and by 24 bits every store is near the uniform one’s 4%. The premise of the prediction holds as stated: on clustered keys a coarse filter has something to say no to. A penalty set by the block put a filter’s whole value in the questions it can answer no, and on the uniform store the coarse filters had none.

There is a second consequence the prediction did not name, and it matters as much. A multi-resolution filter divides its memory among its lengths by distinct prefixes, and on a clustered store the coarse and middle lengths have few. On the largest level at ten bits a key, uniform keys give the filter about four million distinct prefixes across its eleven lengths, and the 24-bit filter gets 17% of the memory — 1.8 bits for each prefix it stores. Sixteen clusters give it 1.4 million distinct prefixes. The 24-bit filter gets 37% of the memory and every stored prefix 5.1 bits. A floor on the bits set the least a membership structure can spend at the logarithm of one over its false-positive rate, and 1.8 bits a prefix is below any useful rate. On clustered keys the same division leaves each filter nearly three times the bits, and the coarse ones cost almost nothing to keep: lengths 12 to 18 together hold 2% of the memory.

Clustering alone changes nothing #

Asked only in the gaps or only at the keys, one length a level beats the multi-resolution filter on every store, clustered or not. At ten bits a key and ranges starting anywhere, the margin falls from 0.186 transfers a query on uniform keys to 0.019 on sixteen clusters, and it never changes sign. At ranges centred on keys it falls from 0.161 to 0.064. The prediction said the multi-resolution filter would pay on clustered keys. On any workload that asks one kind of question it does not, and the reason is on the next plate.

Asked both, on a clustered store, the multi-resolution filter wins: by 0.109 transfers a query on 4,096 clusters, 0.165 on 256 and 0.172 on 16. It loses on uniform keys, by 0.172, and on 65,536 clusters, where the clusters are small enough to fill most prefixes down to 16 bits, by 0.046. Three cells of fifteen are negative, and they are the three where the store has large empty regions and the workload puts ranges both inside and between them. The choice between the two designs is a property of the keys and the questions together. Neither is enough on its own, and that is the failure the section named: one level wanting two lengths at once.

What a single length does when it is chosen #

One length a level, chosen again for the workload, already does what the prediction expected only the coarse filters could do. For ranges that start anywhere, on sixteen clusters, the largest level’s best length is 16 bits; for ranges at the keys it is 26. A 16-bit prefix is 65,536 values of key space wide, so a range of a hundred keys’ width falls in seven or eight of them, and in a gap the filter answers every one of them no. The coarse length does the gaps’ work at one resolution, and nothing else asks this level anything. For ranges centred on keys the gaps never come up, and the level’s length moves as fine as its memory affords, because every range now lies inside a cluster where only a fine prefix separates it from the keys around it.

The four levels pull further apart than they did on uniform keys. The uniform store’s best lengths at ten bits a key run from 19 bits on the smallest level to 24 on the largest. On sixteen clusters they run from 18 to 16 for the gaps and from 23 to 26 at the keys. A level’s best length is its best compromise between separating a range from its neighbours, which wants fine prefixes, and not asking too many questions of too sparse a filter, which wants coarse ones. The first matters inside a cluster and the second in a gap. When one kind of range dominates, the compromise is easy.

With half of each it is not. Chosen for the mix, the four levels take 20, 20, 21 and 16 bits, and on the three smaller levels that is between what either kind of range wants. The largest level keeps 16 bits. It holds two thirds of the keys, so a range at a stored key usually finds some of them there and its filter has little to skip; its length is chosen by the gaps. The smaller levels cannot make that choice. A fine length there turns a long gap range into thousands of prefixes, which exceed the probe limit of 256 and read the level. A coarse one answers every short range inside a cluster with a yes.

What the compromise gives up, range by range #

Split by kind, the compromise length costs 0.883 transfers a query on ranges in the gaps and 12.855 on ranges at the keys; the multi-resolution filter costs 0.817 and 12.585. Each kind’s own best length costs 0.797 and 12.522. On either kind alone the multi-resolution filter is a little behind the length chosen for that kind, which is why it loses on every single workload. Against the length chosen for the mix it is ahead on both kinds. It closes 48% of the compromise’s excess over the oracle in the gaps and 64% at the keys, because it asks each range at the resolution that range turns out to need.

The saving is not where the prediction put it. It expected the coarse filters to earn their keep by skipping long ranges between clusters. They do skip them, but the single length already skipped most of them, and on ranges of a hundred keys’ width in the gaps the multi-resolution filter saves only 0.17 transfers against the compromise, 2.12 against 2.29. The large saving is on the shortest ranges inside the clusters: a range of a tenth of a key’s width at a stored key costs 3.62 transfers with the multi-resolution filter and 4.50 with the compromise length, and the share of empty levels read wrongly falls from 53% to 16%. That is the 24-bit filter doing what a 20-bit filter cannot, separating a tiny range from the keys a few thousand values away in a dense cluster.

The coarse filters are what let the fine one exist. A single length of 24 bits on the smaller levels would have served the short ranges at the keys and lost every long range in the gaps to the probe limit. In the multi-resolution filter a long gap range is answered no at 12 or 14 bits in one or two questions and never reaches the 24-bit filter’s thousands of prefixes. So the coarse filters’ contribution is mostly indirect. They take the long gap ranges off the fine filter’s hands, and the fine filter then serves the short ranges at the keys that the compromise could not. A tree with nodes the size of a block descends only into branches that could hold an answer, and the descent here does the same over prefix lengths. On clustered keys, and not before, the upper branches are empty often enough for the descent to prune. The layout that is told nothing found a structure that needed no parameter to be near the best at every block size; the descent is the filter’s version of that, near the best for both kinds of range without being told which one it is answering.

The crossing moves with the memory #

On sixteen clusters the multi-resolution filter overtakes one length a level between five and eight bits a key and stays ahead at every memory above, by 0.172 transfers a query at ten bits and about 0.13 from sixteen to thirty-two. At two bits a key it is far behind, 0.939 transfers, because eleven filters in two bits a key are too starved to say no reliably even with the clustered store’s economy of prefixes. At five bits it is level. On uniform keys it is behind at every memory up to twenty bits and ties at thirty-two, −0.001, within the noise of 600 ranges of each size. That is the earlier page’s result, reproduced on the mixed workload.

The gap between the two lines at high memory is the part that no amount of memory closes. At thirty-two bits a key both designs have filters reliable enough that false positives barely matter. On uniform keys the difference then goes to zero, because one well-chosen length serves every range. On sixteen clusters it stays at 0.13 transfers a query. That residue is the price of one length for two kinds of range, and it is a property of the workload rather than of the filter’s accuracy. The margin at ten bits, 0.172, is larger than that residue. The difference is plausibly the division of memory, which works better on clustered keys than on uniform ones; that split was argued from the two curves, not measured separately.

What decides it #

The earlier page’s conclusion was that a store should choose its prefix length for each level and each memory, a choice cheap to make and expensive to avoid. On clustered keys that conclusion survives for any workload that asks ranges of one kind. The small levels’ share of a range filter found that each level wants its own length, and this page finds each workload does too. The two designs part only when the workload asks both kinds of range of one level. Then no length is right, and the design that holds several and chooses among them per query wins by as much as the single length’s compromise costs.

That is a stronger condition than clustering, and a store can check it. The runs a range query can skip chose one length for the whole store from the workload it measured, and the same measurement, split by kind of range, is enough here. The two kinds of range are distinguishable after the fact: a range that the oracle skips in every level fell in a gap, and one whose levels all hold keys fell in a cluster. A store that counts both over a recent window knows whether it has a single-kind workload, where one length is enough, or a mixed one on keys with empty regions, where it is not. The filter each run carries put the store’s filter memory where the lookups are. The same kind of accounting could choose between a filter design and its alternative.

The limits of the measurement #

One shape of clustering. Clusters are windows of equal width, placed at random, filled uniformly, and together covering a sixteenth of key space. Clusters of unequal size, or clusters with dense cores and sparse edges, would give a different occupancy at the middle lengths. How much the result depends on the equal widths was not measured.

Three workloads, and one mix. Half the ranges start anywhere and half at a stored key. A workload asking nine in ten ranges at the keys would weight the compromise towards the keys’ lengths, and the multi-resolution filter’s margin would move. Only the half-and-half mix and the two pure workloads are measured.

Lengths chosen on the ranges they are charged on. Each single length is the best of fifteen, from 12 bits to 30, on the same 600 ranges of each size that it is then scored on, which flatters it slightly. The earlier page found that choosing on one set of ranges and charging on another moved the cost by under 1%. The margins that decide this page, 0.11 to 0.17 transfers a query on totals between 4.5 and 6.9, are larger than that.

Every stored prefix gets the same bits. The multi-resolution filter divides a level’s memory by distinct prefixes, as the earlier page’s did. A design that gave the fine lengths a larger share, since they carry the short ranges, might widen its margin; it is not measured.

Transfers, not probes. At ten bits a key on sixteen clusters, the multi-resolution filter asks 27 filter probes a query on the shortest ranges, where the compromise length asks 4, and 553 on the longest against 410. A Bloom probe is a few memory reads and a transfer is a disk block, so on a store on disk the transfers decide. The read a filter has no key for is where that exchange rate was first set, and a store in memory would weigh the probes differently.

Still open: two lengths chosen per level #

The multi-resolution filter wins on a mixed workload with eleven lengths, of which the analysis above says two do almost all the work: a coarse one for the gaps and a fine one for the keys. On uniform keys a pair would have had nothing to do, since one length was enough there. On clustered keys and a mixed workload the pair has a job, and it holds its memory in two filters rather than eleven.

The measurement that follows gives each level two lengths, chosen together for the store, the workload and the memory, and asks a range at the coarse one first and the fine one only below a yes. It asks what share of the multi-resolution filter’s margin over one length the pair recovers, and at what memory. The prediction is that it recovers nearly all of it. The coarse length’s filter holds few prefixes on a clustered store and costs almost nothing, so nearly all the memory goes to the fine one, more than the fine length receives when it shares with twelve others. The pair should therefore beat the multi-resolution filter on the short ranges at the keys and match it in the gaps. It could fail on a store whose clusters come in two sizes. There a gap between large clusters and a gap between small ones want different coarse lengths, and only a design that holds a whole range of lengths can serve both.