Computed examples / not database measurements

Bloom filter allocation: equal memory, different lookup cost

Fourteen deterministic cases compare equal bits per entry with optimized allocation across three invented runs. Expected probes, not measured latency.

JSON and provenance / Evaluator code / Research explanation

Method

Assume every absent point lookup considers every run, all filter/index metadata is resident, and each false positive costs one equally weighted probe. Use p=exp(-b*ln(2)^2). Minimize sum(p_i) subject to sum(n_i*b_i)=budget and b_i>=0 using KKT conditions and 100-step bounded bisection. Run sizes: 10000, 100000, 1000000 entries. Average budgets: 0, 1, 2, 4, 8, 10, 12 bits per stored entry. No random sample or device I/O.

Interpretation

Expected probes can be below one or above one. They are a sum of probabilities, not the probability of at least one false positive, and not milliseconds. The three copies of expectedProbes in each CSV case must not be added together.

Reproduce

The standalone module requires Node.js and no packages. The command performs no storage benchmark. The API accepts 1-64 positive-integer run sizes and an average budget of zero or 0.000001-64 bits per entry. JSON records code and CSV SHA-256 hashes; regeneration updates the generation timestamp, not the computed rows.

node --input-type=module -e 'import { toCsv } from "./bloom-allocation.mjs"; process.stdout.write(toCsv())'

Limits

• Invented run sizes and deterministic arithmetic, not a measured database population.
• Continuous ideal approximation with optimal hash count, not exact finite Bloom-filter probabilities.
• Only absent point queries: no successful-query early exit, ranges, cache misses, CPU or compaction cost.
• No L0 overlap or key-range pruning model; no claimed RocksDB setting or latency improvement.
• Zero bits means the run is always probed, not that an empty Bloom filter rejects all keys.
• No confidence interval applies to these computed examples; model applicability remains uncertain.
• This is not a replication of Monkey's implementation, experimental workloads or full design-space optimizer.

Column definitions

policy

equal: identical bits per entry; optimized: minimum sum of model false-positive probabilities.

budgetBitsPerEntry

Total filter budget / total stored entries, bits per entry; not bytes.

totalEntries

Sum of entries across the three invented runs, not distinct live database keys.

budgetBits

Total ideal filter bit budget, excluding headers, indexes and caches.

run

Run number, ascending by entry count; not a RocksDB level identifier.

entries

Assumed stored entry count in this run.

bitsPerEntry

Continuous ideal filter bits / this run's entries; not rounded hash counts.

filterBits

Continuous allocated bits for this run; need not be an integer.

falsePositiveProbability

Probability for a key absent from this run under exp(-bitsPerEntry * ln(2)^2); 1 means no filter.

expectedProbes

Sum of run false-positive probabilities for one absent point lookup, repeated for each case's three rows.

Sources and license

CC0-1.0 for Hesela's original implementation and computed rows; cited papers and documentation retain their own rights.

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.

Corpus: Bloom filter, LSM-tree, SSTable.