Bloom filter size and false-positive rate

Measure your machineNeeds Python with NumPy

Problem

A Bloom filter answers "might this key be in the set?" in a few bits per key, with false positives and no false negatives. Its false-positive rate depends only on bits per key and the number of hash functions, about (1 − e^(−k/b))^k, which for the best k is roughly 0.6185^b: each extra 4.8 bits divides it by ten. Planners use such filters to skip partitions and to drop non-matching rows early in a join.

For 1,000,000 keys, build filters at 5, 10 and 15 bits per key and measure the false-positive rate on 1,000,000 keys that are not in the set. Compute the size in MB (bits / 8 / 10⁶) and check that 10 bits per key is about 1.25 MB for 10⁶ keys.

The question. What false-positive rate does each size give, and how large is each filter?

Predict

At 15 bits per key, what false-positive rate does the Bloom filter measure?

About 1%About 0.1%About 0.01%

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

bloom-filter-size-and-false-positive.py46 linesDownload

View the code

bloom-filter-size-and-false-positive.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Bloom filter size and false-positive rate.

Builds Bloom filters for 1,000,000 keys at 5, 10 and 15 bits per key (with
the best number of hash functions, k = round(bits × ln 2)), measures the
false-positive rate on 1,000,000 keys not in the set, and computes each
filter's size in MB.
"""
import argparse, json, math
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--keys", type=int, default=1_000_000, help="Keys in the set.")
p.add_argument("--bits", default="5,10,15", help="Bits per key.")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

rng = np.random.default_rng(args.seed)
members = rng.integers(0, 2**62, args.keys, dtype=np.int64).astype(np.uint64)
others = rng.integers(2**62, 2**63 - 1, args.keys, dtype=np.int64).astype(np.uint64)  # disjoint from the members
def mix(x, seed):
    z = x + np.uint64(seed) * np.uint64(0x9E3779B97F4A7C15)
    z = (z ^ (z >> np.uint64(30))) * np.uint64(0xBF58476D1CE4E5B9); z = (z ^ (z >> np.uint64(27))) * np.uint64(0x94D049BB133111EB)
    return z ^ (z >> np.uint64(31))
rows = []
with np.errstate(over="ignore"):
    for b in map(float, args.bits.split(",")):
        m = int(b * args.keys); k = max(1, round(b * math.log(2))); bits = np.zeros(m, dtype=bool)
        h1, h2 = mix(members, 1), mix(members, 2) | np.uint64(1)
        for i in range(k): bits[((h1 + np.uint64(i) * h2) % np.uint64(m)).astype(np.int64)] = True     # double hashing
        o1, o2 = mix(others, 1), mix(others, 2) | np.uint64(1)
        hit = np.ones(args.keys, dtype=bool)
        for i in range(k): hit &= bits[((o1 + np.uint64(i) * o2) % np.uint64(m)).astype(np.int64)]
        rows.append({"bits_per_key": b, "k": k, "fp_pct": hit.mean() * 100, "formula_pct": (1 - math.exp(-k / b)) ** k * 100, "mb": m / 8 / 1e6})
for r in rows: print(f"{r['bits_per_key']:g} bits/key, k = {r['k']:>2}: false positives {r['fp_pct']:6.3f}% (formula {r['formula_pct']:6.3f}%), size {r['mb']:.3f} MB")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"filters": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run bloom-filter-size-and-false-positive.py
uv run bloom-filter-size-and-false-positive.py --help     # every knob
```

Knobs
Knob · default	What it changes
--keys1,000,000	Keys in the set.
--bits5, 10, 15	Bits per key.
--seed0	Random seed.

Our run

Three filter sizes, one million keys

Three filter sizes, one million keys
Bits per key	k	False positives	Formula	Size (MB)
5	3	9.21%	9.18%	0.625
10	7	0.814%	0.819%	1.25
15	10	0.076%	0.074%	1.88

Reference runApple M2 · 8 cores · 8 GB

Output · uv run bloom-filter-size-and-false-positive.py

5 bits/key, k =  3: false positives  9.215% (formula  9.185%), size 0.625 MB
10 bits/key, k =  7: false positives  0.814% (formula  0.819%), size 1.250 MB
15 bits/key, k = 10: false positives  0.076% (formula  0.074%), size 1.875 MB

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · run 2026-10-20

What we found

Measured rates were 9.21%, 0.814% and 0.076%, each within a few percent of the formula, and the 10-bit filter was 1.25 MB.

Read it

A megabyte or two lets a reader rule out 99% or more of keys that are not there, which is why Bloom filters are worth shipping in file footers and across the network in distributed joins. The size is chosen from the error you can tolerate; the number of keys sets everything else.