Bloom filters: optimize the lookup, not each filter

What a negative answer buys

A standard Bloom filter represents membership compactly. Insertion sets hashed bits; a query with any unset bit is absent, while all-set bits mean only possible membership. Properly inserted keys are not rejected by an intact filter. The original 1970 paper already motivates avoiding unnecessary disk accesses. [1, method 2]

A positive answer does not establish existence, freshness or integrity. The engine still checks the data. Nor does the no-false-negative property protect against corrupt filter bytes or mismatched insertion and query logic.

Sorted tables can contain older versions and deletion markers. Their immutable files are merged during compaction; this changes the files a read may need to consult. [5] In RocksDB, L0 files can overlap, whereas higher leveled runs are partitioned across SST files. Do not equate one level with one file. [4]

Optimize a sum under a memory budget

Monkey, by Dayan, Athanassoulis and Idreos, makes the objective explicit: for an absent point lookup, add the false-positive probabilities of the runs considered. Its allocation favors more bits per entry in smaller runs. At low budgets some large runs can receive no filter. [2, section 4.1]

Our independent evaluator isolates that idea with three invented runs. Let n_i be stored entries in run i, b_i its filter bits per entry, and c = ln(2)^2. Use the continuous ideal approximation p_i = exp(-c b_i)from the paper's equation 2. It assumes an optimal hash count; it is not an exact finite-filter formula. [2]

Minimize R = sum(p_i), subject to sum(n_i b_i) = M and b_i >= 0.

For every query here, the key is absent from every run. All filters and indexes are resident, and one false positive costs one equally weighted probe. Linearity of expectation gives the sum even without assuming independence between filter outcomes. It is not P(at least one false positive). Multiple probes can occur on one query, so R can exceed one.

Writing w_i = n_i / sum(n), the marginal-cost condition gives b_i = max(0, (t - ln(w_i)) / c). Our bounded solver adjusts t until the weighted bit budget matches. Zero allocated bits mean bypassing the filter and probing the run, not rejecting all queries with an empty filter. This convex objective makes the constrained solution a global optimum within this model.

The same 11.1 million bits

Assume 10,000, 100,000 and 1,000,000 stored entries, for 1,110,000 total. An average budget of 10 bits per entry gives 11,100,000 filter bits. It excludes indexes, headers, alignment, allocator overhead and caches. Equal allocation uses 10 bits per entry in each run. The optimized allocation below spends exactly the same ideal budget.

The largest run's false-positive rate gets worse than the equal-allocation baseline, while total expected probes improve. That is the useful diagnostic: optimizing each component to the same percentage can miss the system objective.

Download 14 cases, their 42 per-run rows, provenance JSON and the evaluator. No database was loaded and no physical I/O measured. These are new worked examples, not a replication of Monkey's benchmark.

What survives contact with an engine

Monkey's main experiments disabled the block cache, used direct I/O, and repeated trials three times; its error bars describe standard deviations, not universal guarantees. Its benchmark scope and our arithmetic are different evidence. [2, section 5]

RocksDB's cache-local full filters trade some ideal probability efficiency for CPU locality. Whole-key filters and prefix filters also answer different membership questions. A negative whole-key test is not a general range-query emptiness proof. [3]

Measure filter behavior using the right denominator. With the documented point-lookup counters, let P be full positives, Tfull true positives, and U useful negatives. Observed FPR is (P-T)/(P-T+U), not false positives divided by all reads. A zero denominator means no estimate. [3, statistics]

For a real comparison, hold the memory budget and query mix fixed; report absent versus successful lookups, overlapping files, cache residency, CPU time, actual storage reads and latency percentiles. A saved logical probe may save no device read when data is cached. Extra filter memory can also displace another useful cache. Our model deliberately prices neither effect.

Related context: SSD write-amplification assumptions. Database read amplification and NAND write amplification describe different work at different layers.

Corpus: Bloom filter, LSM-tree, SSTable.

Primary sources

1. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422-426 (1970), method 2. DOI: 10.1145/362686.362692.
2. Niv Dayan, Manos Athanassoulis and Stratos Idreos. Monkey: Optimal Navigable Key-Value Store. SIGMOD 2017, 79-94; sections 2, 4.1 and 5. DOI: 10.1145/3035918.3064054.
3. RocksDB project. RocksDB Bloom Filter: statistics, full filters and implementation trade-offs. Documentation reviewed 12 October 2026.
4. RocksDB project. Leveled Compaction: sorted levels, SST files and overlapping L0. Documentation reviewed 12 October 2026.
5. LevelDB project. Implementation: log files, sorted tables and compaction. Documentation reviewed 12 October 2026.

Reviewed 12 October 2026. Original code and computed rows: CC0. Source works retain their rights. No empirical discovery or confidence interval is claimed.