The runs a range query can skip

The read a filter has no key for found the limit of the device that makes log-structured stores fast. A Bloom filter on each run lets a lookup for a missing key skip nearly every level: eight levels at five bits a key cost 0.72 transfers instead of eight. A range query cannot use it at all — the same limit the index that is not worth reading found from the other side, where a structure built for finding one row loses to a scan once the rows asked for are many. The filter answers one question — is this key in this run — and a range has no key to ask about. So a store’s level count, which the filters make nearly free for point lookups, is charged in full to every range query. Ten times the filter memory changed a range’s cost by nothing.

That essay’s closing section named a structure that can be asked about an interval. A prefix filter is a Bloom filter over the leading $b$ bits of each key rather than over whole keys. It answers “does this run hold any key beginning with $p$”. A range that lies inside one prefix, or a few, can then ask each prefix it touches and skip the run if every answer is no. Stores ship prefix filters, and their value depends on how well a query’s ranges line up with the prefixes the filter was built on.

The essay predicted the shape. Short prefixes match everything, so they skip nothing. Long prefixes match almost nothing but each covers only a sliver of key space, so a range touches many of them and each is another chance of a false yes. The useful band should be narrow, its position set by the range length rather than by the store, and a store serving mixed lengths would need several such filters. This page builds the store and measures all three claims. The first holds, the second holds more precisely than the prediction said, and the third fails.

A store built rather than modelled #

The earlier page could use closed forms because a filter over keys has a formula for its false-positive rate and a range query ignores it. A prefix filter’s behaviour depends on how many distinct prefixes each run holds, which depends on the keys, so everything here is built.

The store holds $2^{20}$ distinct 32-bit keys drawn uniformly — 1,048,576 of them — in a levelled arrangement with runs of 4,096 keys at the top and a size ratio of four. That gives four levels of 16,384, 65,536, 262,144 and 704,512 keys, each sorted. Each level carries a real Bloom filter over the distinct $b$-bit prefixes of its keys, at five bits for every key the level holds: the memory its point filter would have had. The filter each run carries is the page on how that memory might be divided between levels; here it is spread evenly.

A range query is an interval of key space wide enough to hold, on average, $r$ of the store’s keys, placed uniformly at random. For each level, the filter is asked about every $b$-bit prefix the interval touches. If every answer is no, the level is skipped. A level that is read costs one transfer to find the interval’s start and one more for every 64 of its keys inside the interval — the charge the earlier page used. A level that is read and holds nothing in the interval still costs its one transfer, and that transfer is exactly what a perfect range filter would save.

That perfect filter is the yardstick. The oracle skips every level that holds no key in the range and reads every level that holds one. No filter, prefix or otherwise, can skip a level holding a key in the range. A Bloom filter has no false negatives, and the implementation stops the run if one ever does. So the oracle is a floor under every line on these plates, and the question for each prefix length is what share of the oracle’s skips it recovers.

A band two bits wide, sliding with the range #

The prediction’s shape is exactly what the plate shows. Each range length has a peak, and on either side the filter’s usefulness falls away. The position of the peak is set by the range and by nothing else: it moves two bits for every tenfold longer range — 22, 20, 18, 16 — which is the prefix whose width in key space is about the width of the range. A range expected to hold one key spans $2^{32}/2^{20} = 4{,}096$ values of key space, and a 20-bit prefix covers exactly $2^{12} = 4{,}096$ values. The range touches one prefix or two, and asks each.

The band is not as narrow as the prediction said. Two bits either side of the peak, most of the recovery survives: for ranges of one key, 58% at 18 bits and 60% at 22 against 72% at 20. Four bits either side it has halved or worse, and six bits away it is gone. That matters for the question at the end of this page, because a band four bits wide can serve ranges a hundredfold apart in length at some cost to each.

Both edges have simple mechanisms.

Below the peak the prefix is wider than the range, and the prefix is not empty. A 16-bit prefix covers 65,536 values of key space, sixteen times a one-key range. The level of 262,144 keys holds keys in 64,350 of the 65,536 possible 16-bit prefixes, and the level of 704,512 holds 65,534 of them. The filter answers truthfully that the prefix is occupied — by keys outside the range — and the level is read. Nothing is wrong with the filter. It is being asked a coarser question than the one the query means.

Above the peak the range is wider than the prefix, and every prefix it covers is another chance of a false yes. A range of one key spans 16 prefixes at 24 bits and 64 at 26. Each probe of an absent prefix says yes about 9% of the time at five bits a key, close to what the formula everybody sizes filters with gives for that density — and every probe is another draw from it. The chance of 16 probes all saying no is $0.91^{16} \approx 0.22$, and of 64 it is about $0.002$. Beyond 64 prefixes the range is not probed at all and the level is read. That cap is more generous than real stores, which consult a prefix filter only when the range lies inside a single prefix. The plate’s right-hand side would fall off faster under their rule, not slower.

What there is to skip #

The share recovered says how good a filter is at its job. It does not say how much the job is worth, and the two come apart sharply as the range lengthens.

For short ranges the prefix filter is worth a great deal. A range expected to hold one key — “the most recent event for this device”, the shape of a large share of real traffic — falls from 4.76 transfers to 2.41, half. A range expected to hold a tenth of a key, most of which hold nothing, falls from 4.10 to 0.86. Those queries are nearly lookups for absent keys, and at the right prefix length the filter treats them almost as its point-filter cousin treats an absent key.

For long ranges there is nothing to buy. At a hundred keys the perfect filter itself saves only 0.21 transfers of 8.43, and the best prefix filter gets half of that. At a thousand keys every level holds part of the range on every query, so there is no empty level to skip, and every line meets.

The reason is in which levels are ever empty. A level holding a share $s$ of the store’s keys holds about $s \cdot r$ keys of a range of $r$. It is empty with probability about $e^{-sr}$. At $r = 100$ the smallest level, holding 1.6% of the keys, expects 1.6 of the range’s keys and is empty a fifth of the time; the next, at 6.3%, expects 6.3 and is almost never empty. A range filter can only skip the levels too small to hold any of the range, and as the range grows that set shrinks to nothing.

At one key a range, every level is often empty, even the largest, which holds two-thirds of the store and still has nothing in the range half the time. The filter recovers most of that in the small levels and about half of it in the large one. The gap has a mechanism. The largest level holds keys in 513,516 of the million possible 20-bit prefixes, so a range touching two prefixes finds one occupied — by a key just outside the range — more often than a small level does. A single prefix length is a compromise across levels whose densities differ by a factor of 43, a cousin of the question the bits given to the wrong keys asked inside one table, where keys arriving at different times were better served by fingerprints of different lengths. The section at the end takes that up.

So the structure’s value sits exactly where the read a filter has no key for said range queries were most expensive relative to their answer: short ranges, below the crossing near a thousand keys where the level count stops mattering. A prefix filter recovers some of the level count for those ranges and none of it for the others. The earlier page’s warning — that a store tuned on point lookups misprices short scans — gets a partial repair, and only where the scans are shortest.

The same memory, asked the other question #

A prefix filter is not free, and its price is not only memory. A store has five bits a key to spend. If it spends them on 20-bit prefixes, it has changed the filter every point lookup consults.

The two questions want opposite ends of the axis. A lookup for an absent key asks one prefix, its own, and a shorter prefix is more often occupied by some other key: at 20 bits the largest level holds half of all prefixes, so the absent key’s prefix is present there half the time, and the lookup reads that level. At the range’s best length the absent lookup costs 1.03 transfers, nearly three times the point filter’s 0.37. At 22 bits it is 0.57 and the range is 2.81. The curves cross nowhere useful. A store whose traffic is mostly lookups for absent keys — the store behind a cache, the store used as a set — is paying for its range filter on every one of them.

So “add a prefix filter” is not an addition. At fixed memory it is a replacement, and it trades one question’s cost against the other’s. The honest accounting keeps both filters, doubling the memory, or states the mix of traffic the one filter was chosen for. A filter has a selectivity is this collection’s standing reminder that a filter’s worth is a ratio between two costs. Here the same bits sit in the numerator of one query’s ratio and the denominator of another’s.

One filter or two #

The prediction’s third claim was that mixed range lengths need several filters, one per band. The band turned out wider than predicted, and that changes the answer.

One filter at 20 bits beats every pair. It brings the mixed workload from 5.95 transfers to 4.51, recovering 65% of what the perfect filter would. The best pair, 18 and 22 bits, reaches 4.67. Two filters sharing a budget each get two and a half bits a key. At that density a Bloom filter’s false-positive rate is about 30% rather than 9%, and a range that touches two prefixes is now wrong far more often. The second filter serves its band better and serves everything worse.

The general point is about the resolution of a budget. Splitting fixed memory between two structures that each answer part of a workload only pays if each part is badly served by the other structure. A prefix filter’s band is four bits wide at half strength, so a 20-bit filter already serves ranges from a tenth of a key to ten keys tolerably. Doubling the bits it has buys more than a second, thinner filter that serves a band the first already half-covers. One dial between two structures made the same kind of argument about a store’s size ratio: a family of designs looks like a choice between rivals until the parameter joining them is swept.

What was measured and what was not #

Uniform keys. Every level holds a uniform sample of the key space, which makes each level’s density the same everywhere and the per-level shares exact. Real stores often hold keys that cluster — by tenant, by time, by an entity identifier in the high bits — and on those a prefix aligned with the clustering is worth far more than here. A query for one entity’s rows is a single prefix, and a small level holds only the recently written entities, so most levels skip. The uniform case is the one where a prefix filter has least to work with.

Levels, not tiers, and fence keys ignored. Each level is one sorted run, the arrangement whose write cost the writes nobody counted priced. A real run also stores its smallest and largest key, and a range outside that interval skips the run with no filter at all. On uniform keys every run spans nearly the whole key space, so those fences never prune. On time-ordered keys they prune almost everything, and a prefix filter adds little to them.

One seek per level read, one transfer per 64 keys. The same charge as the earlier page, so the numbers line up with its plates, and the block as the unit of cost that one access, eight kilobytes set out. A level that is read and holds nothing costs one transfer. That is the whole of the saving a range filter can make, and it would be larger if a seek into a large level cost more than one block.

Probes are counted and not charged. A range touching 16 prefixes asks 16 questions, each several hash computations. They are in memory and cost nothing in transfers, but a range filter probed 64 times per level per query is not free CPU. The cap at 64 is where the model stops asking, and real stores stop at one.

One store, one seed. The four levels and their keys are one draw. With 2,000 ranges at each point, the recovered shares are good to about two percentage points, which is enough to trust the positions of the peaks and the order of one filter against two.

Still open: a prefix length for each level #

A single prefix length is a compromise across four levels whose key densities differ by a factor of 43. The levels plate shows the cost: at 20 bits the smallest level is skipped 79% of the time and the largest 26%, because the largest has a key in half of all 20-bit prefixes. A prefix fitted to one level’s density would be longer for the dense levels and shorter for the sparse ones. Nothing requires every level to use the same length, since each level’s filter is built and asked separately.

The measurement that follows gives each level its own prefix length and asks what that recovers of the oracle’s skips on the mixed workload, at the same five bits a key. The prediction is that the right length for a level is set by the range length plus the log of the level’s density, so a level four times denser wants a prefix two bits longer, and that the per-level rule closes most of the gap between 4.51 transfers and the perfect filter’s 3.74 on short ranges. It could fail in one way worth watching: a longer prefix on the dense levels means more prefixes per range and more false positives, so the dense levels may simply have no good length. In that case the rule reduces to filtering the small levels and reading the large one, which is what an oracle mostly does anyway.