Bloom Filter Playground

Where this shows up in production

ClickHouse's ngrambf_v1/tokenbf_v1 skip indexes, Parquet's per-column bloom filters, and Cassandra's row/partition bloom filters all use exactly this trick: before reading a whole block, file, or SSTable off disk, check a tiny in-memory bit array first. If the filter says "definitely not present," the block is skipped — guaranteed correct, because a bloom filter never produces false negatives. If it says "possibly present," the engine still has to do the real read, which may turn out to be unnecessary.

• A false positive costs you an extra read — never wrong data. That asymmetry is what makes bloom filters safe to use as a pre-filter anywhere a false negative would be a correctness bug.
• The false-positive rate climbs as the filter fills. A bloom filter sized for the traffic you have today can silently degrade as the underlying set (rows in a file, keys in an SSTable) grows past what it was sized for.
• Sizing is a real capacity decision: given an expected item count n and a target false-positive rate p, you choose m (bits) and k (hash functions) up front — the same way you'd size a partition count or a cache, not something you tune reactively after the fact.
• This estimate uses the standard closed-form approximation (1 − e^(−kn/m))^k; a real bloom filter's exact false-positive rate is measured, not assumed, but the formula is close enough to drive a sizing decision.