The thread: A filter has a selectivity
The filter that feeds the table
A self-index answers exact queries and nothing else. Approximate matching needs a table with twenty thousand columns in it. The pigeonhole joins them — cut the pattern into k+1 pieces and at least one occurs exactly, and the index that cannot answer the question decides where to ask it.
When the algorithm flips a coinThe evidence a filter cannot remove
A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.
When it does not fitThe index that is not worth reading
An index turns a query over 65,536 rows from 1,024 transfers into four. At a thousand matching rows it costs 654 and still wins; at sixteen thousand it costs 1,027 and has lost. Where it turns is decided by the block size — a number the query does not contain, the schema does not mention, and nobody writing either has seen.
When the algorithm flips a coinThe intersection two filters cannot report
Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.
What a bound isThe branches an error opens
The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.
The data that is not a numberThe q-grams an error cannot destroy
A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.
The index that replaces the textThe search that spends a budget
A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.
When it does not fitThe filter each run carries
A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.
When the algorithm flips a coinA filter past its design size
A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.
What is taught wronglyThe filter that proposes everything
Seed-and-extend saves two thousand times the work at zero errors and costs more than doing nothing at four. Between them the selectivity falls through the floor, and where it falls is set by two numbers that can be computed before the filter is run — one of which does not contain the length of the text at all.
The index that replaces the textThe candidates a filter cannot avoid
A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.
The data that is not a numberThe errors the rest of the pattern needs
Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.
When the algorithm flips a coinA filter that grows by moving a bit
A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.
When the algorithm flips a coinTwo hash values and the keys they copy
A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.
When the algorithm flips a coinThe bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
When it does not fitThe read a filter has no key for
A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.
When the algorithm flips a coinPositions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
When the algorithm flips a coinTwo blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 35 keys instead of 51. The false-positive rate gets worse: 0.0997% against 0.0854%. At eight bits a key it nearly doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. At every density a filter is commonly built at, the repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
When the algorithm flips a coinA block the lookup can work out
Sending each key to the emptier of two blocks flattens the load and doubles the chance of a false positive, because a lookup cannot know which block was chosen. Give each block a threshold on a hash of the key instead and the lookup can work it out: one block read, one chance, and 46% of the load balance kept. At sixteen bits a key that is 0.0618% against one block's 0.0854% and two blocks' 0.0997%. The threshold costs 1.5% of the budget and two bits of it are nearly as good as sixteen.
When it does not fitThe runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
When the algorithm flips a coinThe day a filter cannot grow
A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.
When the algorithm flips a coinA penalty set by the block
A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.086% to 0.090% against a computed 0.086%, and the threshold design 0.060% to 0.065%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and its advantage shrinks from 40% at sixteen keys a block to between 5% and 13% at 128.
When it does not fitThe small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
What is taught wronglyThe threshold that reaches zero
At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.
When it does not fitThe resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
What is taught wronglyThree savings in three currencies
The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.
When it does not fitOne length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
When it does not fitTwo lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
When it does not fitThe filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
When it does not fitOne bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.