The resolution a range filter can afford

The runs a range query can skip put a Bloom filter over key prefixes on each level of a four-level store of 2^20 keys. A range query can skip a level whose filter shows that no prefix the range touches holds a key. The small levels’ share of a range filter gave each level its own prefix length, which took the store’s mixed range workload from 4.514 transfers a query to about 4.32, and then its own share of five bits a key, which took it to 4.043, against an oracle’s 3.738. It decomposed what was left: three fifths of the gap to the oracle was false positives. A range asks the filter one question for each prefix it touches, every question can come back yes wrongly, and a long range asks many.

Its closing section proposed the repair: a filter that answers the range rather than its prefixes. Keep prefix filters at every length from 16 to 24 bits in one level’s memory. Ask a range at the longest length that covers it with at most two prefixes, and descend to finer lengths only below the answers that came back yes, the way a tree with nodes the size of a block descends only into the branches that could hold an answer. The section predicted that on short ranges the filter would match the single best length, since it asks the same one or two questions, and that on ranges of about ten keys it would recover skips the single length loses. It asked whether asking at the right resolution recovers more than the division of memory costs.

The answer depends entirely on the memory, and at the memory the store actually has, it is no.

The filter, built and charged #

Each level keeps a Bloom filter for each stored length. Its memory, five bits for each of its keys, is divided among the lengths in proportion to the distinct prefixes each holds, so every stored prefix gets the same share. A range is asked at the longest stored length at which it touches at most two prefixes. Every prefix answered yes is replaced by its children at the next stored length that lie in the range, and those are asked in turn. The level is read if a yes survives to the finest length, and skipped if every branch has been answered no. Charges are the earlier pages’: a level read costs one transfer plus one for every 64 of its keys in the range. The single-length design is the earlier page’s lengths per level, 18, 19, 21 and 22 bits from the smallest level to the largest, with the memory spread evenly — the 4.32 design, so that every comparison here is at the same bits a key on every level. The workload is a thousand ranges each of four lengths, expected to hold a tenth of a key, one, ten and a hundred keys of the store.

A second way of asking is measured beside the proposal. Instead of starting where the range fits in two prefixes, it asks every stored length from the coarsest down, so that even a short range consults the coarse filters above it. Both are exact in the sense that matters: across every query, neither ever skips a level holding a key of the range.

Five bits a key, divided nine ways #

On ranges expected to hold a tenth of a key, the proposed filter costs 3.73 transfers a query where one length a level costs 0.91 — worse than the single length by four times, and the prediction said they would be equal. They ask the same one or two questions of the finest filter, as the prediction said, but not of the same filter. The single length’s filter holds all five bits a key. The proposed filter’s finest length holds about a ninth of them, since on a sparse level each of the nine lengths has about as many distinct prefixes as there are keys. A Bloom filter at under a bit a key says yes to almost everything. A floor on the bits put the least memory any membership structure needs at the logarithm of one over its false-positive rate, and a ninth of five bits is below that floor for any useful rate. Nothing about the descent can make a starved filter answer no. On ranges of ten keys, where the proposal was expected to gain, it costs 6.39 against 5.65, and it loses at every range length.

The false reads say where it goes wrong. On short ranges the proposed filter reads 91% of the levels it could have skipped, against the single length’s 19%. Asking every length from the coarsest down brings that to 32%, because a short range now meets eight coarser filters on its way down, and any of them can say no. That recovers most of the loss on short ranges, 1.45 transfers against the proposal’s 3.73. Averaged over the workload it costs 4.86 against the single length’s 4.32, still worse.

Coarse questions that are always answered yes #

The prediction’s picture was that a coarse question is a cheap way to rule out a range that spans many fine prefixes. It works only where a coarse prefix can be empty.

On the largest level every 16-bit prefix holds a key, and 93% of 18-bit prefixes do. A coarse question asked there is truthfully answered yes, and a correct yes rules out nothing. The largest level is where most of a range query’s transfers are spent, since its runs are the biggest, and it is the level where the coarse filters are useless. Their memory is not wasted there in the way a false positive is wasted; it is spent answering a question whose answer is known. On the smallest level, 22% of 16-bit prefixes are occupied, and a coarse no is common and worth having.

This is the same finding a penalty set by the block made about blocked Bloom filters in another form. A filter’s value lies in the questions it can answer no. A structure whose memory goes partly to questions the data always answers yes is paying for certainty it already had.

When the memory is there #

With more memory the multi-resolution filter improves quickly, and at first sight it overtakes. Asked at every length, it passes the single length at twelve bits a key, 3.966 against 3.977, and at twenty bits it costs 3.79 against 3.965, while the single length stays at 3.965 however much memory it is given. That looked like the answer to the section’s question. A length for each range, it seemed, recovers what one length a level cannot, once the memory can make nine filters reliable.

It is an artifact of the comparison. The single length in those numbers is the earlier page’s, chosen at five bits a key — 18, 19, 21 and 22 bits from the smallest level to the largest — and held there as the memory grew. Chosen again for each memory, one length a level costs 3.91 transfers a range query at ten bits a key against the multi-resolution filter’s 4.08, 3.76 at twenty against 3.79, and 3.760 at thirty-two against 3.767. It is ahead at every memory measured, from two bits a key to thirty-two, and within 0.03 of the oracle from twenty bits upwards. The multi-resolution filter’s apparent win came from its 23- and 24-bit filters answering short ranges more finely than an 18-bit filter could. A single length allowed to be 21 or 24 bits does the same thing, with all the memory behind one filter instead of a ninth of it.

The resolution a level can afford #

The best single length rises with the memory: on the smallest level from 16 bits at two bits a key to 21 at sixteen, and on the largest from 21 to 26. A finer prefix separates more of a short range from its neighbours in key space, which the oracle rewards. It also has more distinct prefixes to store, and so a higher false-positive rate at the same memory. Each memory has its own balance point between the two, and the balance moves finer as the memory grows. A length chosen at one memory is the wrong length at another, which is what the fixed single length on the first plate showed. It flattened at 3.965 because its lengths stopped being the right ones, not because one resolution had run out.

The multi-resolution filter is an attempt to avoid choosing the resolution. The measurements say the choice is cheap to make and expensive to avoid. A store knows its filter memory when it builds a level, and the best length for that memory is one sweep over a few lengths away. The earlier page found that each level wants its own length at a fixed memory. The same argument applies across memories: the length is a function of both the level and the budget. Nine lengths in one budget are nine filters each too starved to be sure of anything. The runs a range query can skip chose one length for the whole store at one memory, and this page adds the memory as the second thing the length depends on.

Trimming the lengths does not rescue it #

Two repairs suggest themselves, and both were measured. The first drops the lengths the occupancy plate shows are nearly always truthfully yes. Each level keeps only the lengths at which at most half its prefixes hold a key: all nine on the smallest level, 17 to 24 bits on the next, 19 to 24 and 20 to 24 on the two large ones. At five bits a key it costs 4.80 transfers a range query against 4.86 with all nine, a saving of a hundredth of the gap. The coarse lengths never held much memory. Memory was divided by distinct prefixes, and a coarse length on a dense level has few, so dropping them returns little. The memory is in the fine lengths. Each of them, on a sparse level, holds about one prefix for every key, so storing five fine lengths costs five times what storing one does. The filter each run carries found the same arithmetic spreading five bits a key across the levels of a store: memory divided among filters that each hold as many items as keys is memory each of them lacks. The multi-resolution filter makes that division inside one level.

The second repair stops each level’s lengths at the length a single filter would choose for the same memory, so that the descent never goes finer than the single length would. At five bits a key that costs 4.43 transfers against the single length’s 4.32, at ten bits 3.98 against 3.91, and at twenty 3.78 against 3.76. It closes most of the distance and never crosses. With the finest resolution the same, the coarse lengths above it only divide the memory, and on uniform keys they buy nothing for it.

What the descent asks #

There is one currency in which the multi-resolution filter does win. At twenty bits a key, the single length chosen for that memory asks 600 filter probes a query on ranges of ten keys and 972 on ranges of a hundred; the descent, asked at every length, asks 146 and 719. The single length’s fine prefixes are what make its transfers low, and they make a long range touch hundreds of prefixes, each a question. The descent answers a long range at a coarse length with two questions and only refines below its yes answers. On the shortest ranges it asks slightly more, 16.8 against 13.8, because it walks down through all nine filters. A Bloom probe is a few memory reads, not a transfer. For a store on disk, where a transfer costs a thousand probes, the transfers decide, and the single length wins. For a store held in memory, where a probe and a read cost about the same, the multi-resolution filter’s economy of questions could be the thing worth having. That would be a different comparison, charged in probes and reads together, and it is not made here.

Where the measurement stops #

One store, one key distribution. Keys are uniform over 32 bits, the store has four levels in a ratio of four, and ranges start at uniformly random points. A store whose keys cluster would have more empty coarse prefixes on every level, and the coarse filters would earn more.

Memory divided by distinct prefixes. Each stored length gets bits in proportion to how many prefixes it holds. The largest level’s coarse filters are therefore given little memory. They would be better given none, and a design that dropped every length a level’s occupancy makes useless would move the crossing below twelve bits. That design is not measured here.

A probe limit of 256 a level. A level asked more than 256 probes is read. The earlier pages used 64 for a single length, and the difference moves the single length’s floor, not its crossing with the descent.

Lengths chosen on the queries they are charged on. The single length for each memory is the best of thirteen lengths on the same thousand ranges of each size that it is then scored on. That flatters it slightly. The earlier page chose its allocation on one set of ranges and charged it on another, and the cost moved by under 1%. The margins that decide this page, 0.16 transfers at ten bits a key and 0.02 at twenty, are larger than that at ten bits and comparable at twenty. At twenty bits the honest reading is that the two designs are about equal, and the single one is simpler.

Four range lengths, equally weighted. The mixed workload gives ranges of a tenth of a key, one, ten and a hundred keys equal weight. A workload made mostly of long ranges would weight the probes plate’s economy more heavily in the multi-resolution filter’s favour, though still in probes and not transfers.

Transfers only. The bits a second threshold costs found a design that narrowed a spread and paid for it in table bits. Here the price is paid in bits and in probes, and only the transfers are optimised.

Still open: keys whose coarse prefixes are empty #

Every coarse question on this page was asked of uniformly spread keys, and on the large levels uniform keys fill every coarse prefix. The occupancy plate is the whole reason the coarse filters earned nothing: a filter can only help where a prefix can be empty. Real keys cluster. Timestamps arrive in bursts, identifiers are handed out in blocks, and a key space of 32 bits holding a million keys in a few dense regions has most of its 16-bit prefixes empty on every level.

The measurement that follows draws keys from a stated number of clusters, from uniform down to a handful of dense regions, and repeats the comparison: one length a level chosen for each memory, against the multi-resolution filter asked at every length. The prediction is that on clustered keys the coarse filters begin to say no on long ranges. A range of a hundred keys that falls between clusters would then be skipped by one coarse question, where a single fine length asks hundreds of questions or gives up and reads. If that holds, the multi-resolution filter pays on clustered keys and not on uniform ones, and the choice between them is a property of the key distribution, not of the filter. It could fail if clustering also makes the fine prefixes inside a cluster denser. The single length’s best resolution would then move finer inside the clusters and coarser between them — a different length for different parts of one level, which neither design here can express.