Bloom filters stop you from paying for “not found.

Every time an app asks a database “does this row exist?” and the answer is no, you still paid for a query: a connection, a plan, an index probe, maybe a disk read. At scale, those misses dominate. A Bloom filter sits in front of that path and answers one cheaper question first: have I almost certainly never seen this key?

If the answer is definitely not, you return immediately. No cache. No database. That is the whole product value.

What a Bloom filter actually promises

A Bloom filter is a compact bit array plus a handful of hash functions. You insert keys by setting bits. You look a key up by checking those bits.

You get two possible answers:

• Definitely not present — never wrong.
• Probably present — sometimes wrong (a false positive).

You never get a false negative on a standard Bloom filter. That asymmetry is why it belongs in front of a database. The expensive mistake is asking Postgres for a row that was never there. The cheap mistake is asking Postgres one extra time because the filter said “maybe.”

“Probably” is acceptable because it is fast and tiny. A few bits per key can represent millions of IDs in tens of megabytes. An exact set of the same keys can cost gigabytes.

The request path that actually saves money

Put the filter first, then cache, then the database:

1. Check the Bloom filter.
2. If it says the key is absent, return not found.
3. If it says the key might exist, check the cache.
4. On a cache miss, query the database.
5. If the database finds a row, write the cache and (if this is a new key) insert into the filter.
6. If the database finds nothing, you hit a false positive. Cache the empty result briefly if that is safe, then return not found.

Each layer catches what the previous one missed. The filter kills cheap misses. The cache serves hot hits. The database only sees queries that have a real chance of returning data — plus writes and the rare false positive.

This is also the standard defense against cache penetration: a flood of invented IDs that miss every cache layer and hammer storage. Caching empty values helps a little and wastes memory. A filter of valid IDs drops most of those requests before they become I/O.

Why databases already do this internally

This is not a clever application-layer trick. Storage engines have used Bloom filters for years to skip disk for absent keys: Bigtable, HBase, Cassandra, ScyllaDB, RocksDB, and others. SQLite used them to skip pointless B-tree probes in analytical joins and shipped the idea in 3.38. PostgreSQL and other engines use related filters to prune join input. The application-level version is the same idea, one layer higher.

The numbers that matter

Tune three things: expected n (how many keys you will insert), m (bits in the array), and k (hash functions). They set the false-positive rate.

A common working point is roughly 8–10 bits per element and a false-positive rate around 1% or lower. With a 0.001% target, most “maybe” answers are real keys; the database still sees almost only useful work. One vendor example put it plainly: at about one false positive per 100,000 lookups, you avoided 99,999 needless queries for every extra database hit.

False positives do not corrupt results. They only cost a lookup you hoped to skip. False negatives would hide real rows. Standard Bloom filters do not do that, which is why they are safe as a pre-check, not as a source of truth.

What breaks in production

Deletes. A classic Bloom filter cannot remove a key cleanly. Clearing bits would collide with other keys. Counting Bloom filters and Cuckoo filters exist if you must delete; most teams instead rotate: build a new filter daily or on deploy, dual-write for a window, then drop the old one.

Stale membership. If you insert a product ID into the filter and later delete the row, the filter still says “maybe.” That is a false positive until rebuild. Design for it: short empty-result cache, or accept the extra lookup.

Rebuilds and cold start. An empty filter says “no” to everything, including keys that exist in the database. Load it from a snapshot or a scan before you put it on the read path. During rebuild, fail open to the database, not closed to users.

Overfill. If you insert far more keys than you sized for, the false-positive rate climbs and the filter stops saving work. Size for peak cardinality, or shard filters.

Wrong question. Bloom filters help when a large share of lookups are true absences. They do little for “this key almost always exists.” They are also the wrong tool if you need exact counts, ranges, or ordered scans.

A practical rollout

• Start with one hot existence check: order ID, SKU, username, short link, session token.
• Size for 12–24 months of growth and a false-positive rate you can afford (often 0.1% to 1%).
• Keep the filter in memory next to the app or in Valkey/Redis-style Bloom modules so the check is a network hop cheaper than SQL.
• Measure four things before and after: miss-query rate to the database, p95 latency on not-found, false-positive rate (filter yes, DB no), and memory.
• Only then widen the pattern.

The sentence to remember

A Bloom filter is not a smaller database. It is a bouncer. It lets “this was never here” die in microseconds so the database can spend its budget on rows that might actually exist.