The small levels' share of a range filter

The runs a range query can skip built a log-structured store and gave each of its runs a filter a range query can use. A prefix filter is a Bloom filter over the leading bits of each key. It can be asked whether a run holds any key beginning with a given prefix, and a range that touches only a few prefixes can skip a run whose filter says no to all of them. The store — the arrangement the writes nobody counted found cheap to write and one dial between two structures placed at one end of a range of designs — held 2^20 uniform 32-bit keys in four levels of 16,384, 65,536, 262,144 and 704,512 keys, with five bits of filter for every key a level held. On a workload mixing ranges of a tenth of a key, one key, ten and a hundred in equal shares, the best single prefix length, 20 bits, brought the cost from 5.95 block transfers a query to 4.51. A perfect range filter, skipping exactly the levels with nothing in the range, would reach 3.74.

The page’s closing section blamed the remaining gap on the compromise in “single”. The levels’ densities differ by a factor of 43, and at 20 bits the smallest level was skipped 79% of the time and the largest 26%, because the largest has a key in half of all 20-bit prefixes. It proposed a prefix length for each level. It predicted that a level four times denser would want a prefix two bits longer, and that lengths chosen that way would close most of the gap. It named one way this could fail: the dense levels might have no good length at all.

Each level does have a good length and does want its own. Choosing it closes a quarter of the gap. The rest of this page finds where the other three quarters went, and what recovers most of them, which is not a length.

Each level’s best length #

Nothing about a level’s filter affects another level’s read, so the cost of a query is a sum over levels, and each level’s best length can be found alone. The measurement builds every level’s filter at every length from 8 to 32 bits and charges each level its transfers on the same 4,000 ranges.

The best lengths are 18, 19, 21 and 22 bits, from the smallest level to the largest. Each curve has the shape the earlier page found for the store as a whole. Too short a prefix is occupied by keys outside the range, so the filter answers yes truthfully and the level is read. Too long a prefix cuts the range into many prefixes, and each is another chance for the filter to answer yes falsely. The bottom of each curve is broad: every level is within 5% of its best across three or four lengths.

With each level at its own length the mixed workload costs 4.319 transfers a query, against 4.514 at the shared 20 bits. That is 0.195 transfers of the 0.776 between the shared length and the perfect filter: a quarter of the gap. The earlier page predicted most of it.

The largest level does have a good length. At 22 bits it recovers 72% of what an oracle saves on it, and the failure the earlier page feared did not happen. Nor is 22 bits a poor compromise for that level, since three of its four range lengths leave little to skip. At ten keys a range, a level of 704,512 keys is never empty, and at a hundred keys no level larger than 16,384 ever is — the regime where the index not worth reading found that nothing short of a scan pays. Much of each level’s cost cannot be touched by any filter, and the gap that remains is in the part that can.

How the best length moves with density #

The earlier page’s rule — two more bits for every factor of four in density — can be tested one range length at a time.

The direction is right and the rate is lower. For ranges of a tenth of a key the best length rises from 19 bits on the smallest level to 23 on the largest, four bits across a 43-fold range of density. That is about 1.5 bits for every factor of four. For ranges of one key it rises by four bits too, and for ten keys by two across the three levels that ever have anything to skip.

The rule assumed the best prefix holds a fixed number of the level’s keys, so that each doubling of density would need one more bit. It does not, because false positives change the trade. On a denser level a longer prefix cuts the range into more pieces, and each piece is another probe that can come back falsely yes. At five bits a key a Bloom filter answers falsely about 9% of the time, so every extra probe costs. The best length is pulled back from where density alone would put it, and pulled back further on the dense levels, which need more probes.

That suggests the gap is not mainly about lengths at all.

Where the gap goes #

The gap between one shared length and the perfect filter can be taken apart by computing a sequence of costs, each a lower bound on the one before.

False positives are 61% of the gap. Length is 37% of it, and only a quarter can be reached by one filter a level. A length for every level and every range length is a bound no real filter reaches, since a level’s filter is built at one length and a query cannot choose another. It costs 4.227. Removing every false positive from that ideal, so a level is skipped whenever none of its keys lies in any prefix the range touches, brings the cost to 3.753 — within 0.015 of the oracle. What remains is coarseness: a range touching a prefix that holds a key of the level outside the range. At the best lengths that almost never happens.

The arithmetic of the multiplication is short. A range holding one key on average spans 4,096 values of key space, so at the largest level’s 22-bit prefixes, each 1,024 values wide, it touches four or five of them. A range of ten keys on the level of 262,144, at 19 bits, touches five or six. A level whose keys are absent from all of them is skipped only if the filter says no to every one. With a false-positive rate of 9% a probe, the chance that six probes all come back truthfully is 0.91 to the sixth power, about 0.57. So the filter throws away more than two fifths of the skips it was entitled to, on exactly the ranges where a skip was available. Shortening the prefix to cut the number of probes is the only remedy a length offers, and it is the remedy each curve’s left-hand side shows failing, because a shorter prefix is occupied by keys outside the range.

So a prefix filter’s real limitation on this store is not the prefix. It is the Bloom filter under the prefix. A range consults several prefixes a level, each consultation can be wrong, and at five bits a key the wrong answers cost more than the choice of length ever could. The lever that addresses false positives is the number of bits a filter has, and the store has a fixed number of those to divide.

What a bit a key buys on each level #

The filter each run carries divided a fixed filter memory among levels for lookups of absent keys. It found that the small levels should get more bits a key and the large level fewer. A bit a key on a small level is cheap in total memory, and a false positive on any level costs the same one read. A range filter is the same arrangement with a sharper incentive, since a range asks each level several questions rather than one.

The curves say what a bit a key is worth on each level, and the price of a bit a key is the level’s size. Going from five bits to twelve on the smallest level saves 0.154 transfers a query and costs 14 KB. Going from five to three on the largest costs 0.079 transfers a query and frees 172 KB, enough for that raise twelve times over. With every combination of eleven settings on four levels tried under the same memory, the best division is 12, 12, 8 and 3 bits a key, from the smallest level to the largest. Each level then takes its own best length at its own bits, 19, 21, 22 and 22, and the mixed workload costs 4.043 transfers a query.

The division has the shape the point-lookup page found, and for a reason that can be stated without the curves. A read saved on any level is worth one transfer, whichever level it is. A bit a key costs memory in proportion to the level’s size, and the largest level here is 43 times the smallest. So a bit a key on the smallest level is 43 times cheaper than on the largest, and it buys at least as much, since the small levels are empty for more of the ranges and their filters get asked the questions that can actually be answered no. An allocation that spends the memory where it saves the most transfers per bit therefore strips the largest level down to the few bits that still keep its false positives from dominating, and hands the rest to the small ones until their curves flatten.

The flattening is what stops it. Past twelve bits a key the smallest level’s curve is nearly level — 0.502 transfers at twelve, 0.490 at twenty — because by then its false positives are rare and what remains is ranges long enough that the level really does hold a key. Past that point a bit is better spent on the third level, which is still steep at eight.

The best length depends on the bits, which is why the two decisions are one. A filter with more bits a key can afford more probes, so its best prefix is longer: the smallest level’s best rises from 16 bits at one bit a key to 19 at ten. A length chosen at five bits a key and kept when the bits change is chosen for the wrong filter.

The memory the reallocation is worth #

At five bits a key, moving the bits recovers 61% of the gap to the perfect filter, against a quarter for moving only the lengths. With both chosen per level the store reaches 4.043 transfers a query; one shared length needs ten bits a key to reach 4.039. Dividing the memory well is worth doubling it. Divided well, three bits a key (4.207) beats five spread evenly with a length for each level (4.319).

Choosing the lengths per level still matters once the bits are moved: with the bits divided and one length shared by all four levels, the best any length reaches is 4.100, at 22 bits. The larger share of the gain is the bits, and the rest is the lengths following them.

The allocation was chosen on the same 4,000 ranges it is measured on, from 11^4 combinations, and that could flatter it. Charged on 4,000 ranges drawn with a different seed, the same allocation costs 4.067 transfers a query, against 4.348 for lengths alone and 4.512 for one length. The ranking holds and the margins barely move. The allocation is a property of the store’s shape, not of the queries it was fitted to.

What the division does to a lookup for an absent key #

The earlier page found the range filter’s price elsewhere: a store whose filters are built on 20-bit prefixes pays for them on every lookup of a key it does not hold. An absent key’s own prefix is present in the largest level half the time, because some other key shares it, and each such level is read. At five bits a key and 20 bits it measured 1.03 levels read for each absent lookup, against 0.37 for an ordinary filter over whole keys.

The division of bits changes that too, and for the better. Measured on 20,000 absent keys, the reallocated filters read 0.485 levels for each lookup: 0.034 on each of the two small levels, 0.084 on the third and 0.333 on the largest. Lengths chosen per level at five bits each read 0.729. The longer prefixes on the large levels are shared by fewer keys, and the small levels’ extra bits almost silence them. The price of serving ranges is now 1.3 times an ordinary point filter’s reads rather than 2.8 times, and all of the excess comes from the largest level, where three bits a key buys little.

That largest level is where the two workloads pull hardest against each other. A store whose traffic is mostly absent-key lookups would give that level more bits, and the division above would move. The division is a function of the mix, and the method that found it finds that one too.

What was measured and what was not #

Uniform keys. Every key is drawn uniformly, so every level’s prefixes are occupied evenly. Real keys cluster — a table’s rows under one tenant’s prefix, a time series under one day’s — and clustering changes which prefixes are occupied and how many a range touches. The read a filter has no key for and its successor both stated this, and it remains the largest unknown in this whole line of measurement.

One store shape. Four levels with a size ratio of four. More levels would give the reallocation more to divide and, if the point-lookup result is a guide, more to gain.

Allocations on a grid. Bits a key were chosen from eleven settings a level. A continuous allocation might do slightly better and would not change the ranking.

Transfers, not probes. Every cost is a block transfer, the unit one access, eight kilobytes introduced. A range that touches many prefixes asks the filter many times, and each probe is a few cache misses. At the best lengths a range probes one to a few dozen prefixes a level, and that cost of CPU time is not charged against the transfers saved.

Still open: a filter that answers the range rather than its prefixes #

Three fifths of the gap was false positives, and they arise because a range asks a Bloom filter one question for each prefix it touches, and every question can be wrong. The cost of a range grows with the number of questions, which is what pulls every level’s best length short. A filter that answered one question for the whole range would not pay that multiplication.

Such filters exist in principle. A structure over the level’s keys at several prefix lengths at once can answer whether any key lies in an interval by asking at the coarsest length that fits the interval inside one or two prefixes, then descending only where the answer is yes. It is the shape of a B-tree’s own descent, which a tree with nodes the size of a block priced: a question asked first at the coarsest level, and refined only below the branches that could hold an answer.

The measurement that follows builds such a filter on each level. Prefix filters at every length from 16 to 24 bits share one level’s memory, and a range is answered by asking at the longest length that covers it with at most two prefixes, then descending. It compares that with the divided single-length filters here at the same total memory. The prediction is that on short ranges it matches the single best length, since it asks the same one or two questions. On ranges of ten keys it should recover skips the single length loses, because it can ask at a coarser length without cutting the range into pieces. Whether it pays depends on the memory it takes from each length, since nine filters share what one filter had. The earlier page found that two filters sharing a budget lost to one, and the question is whether asking at the right resolution recovers more than the division costs.