CSE Roadmap

Specialist tier · about 2 hours · 5 parts

Part 2 of 5 · 1 min read

Bloom filters answer "definitely not here" or "maybe here"

A compact probabilistic structure rules out files cheaply, without ever storing the actual keys.

Think of a bouncer checking a heavily compressed guest list. It can only answer "this name is definitely not on the list" or "this name might be on the list, go check the real list to be sure."

In plain words: a Bloom filter is a compact, probabilistic structure that can be checked for a key before doing more expensive work, such as checking an SSTable from the previous page. It gives one of two answers: "definitely not present," which is always correct, or "possibly present," which might turn out to be a false alarm. A Bloom filter never gives a false "definitely not present" answer for a key that is actually there, which is exactly why it is safe to trust when it says no.

A worked example. Before checking an SSTable for customer_id = 999999, the storage engine first checks that SSTable's Bloom filter; if it answers "definitely not present," the SSTable is skipped entirely, with no disk read needed.

The key lines. No new SQL; a Bloom filter check is internal to how an LSM-tree-based storage engine decides which SSTables to actually read.

Bloom filter

A Bloom filter is a compact, probabilistic structure that answers either "definitely not present," always correct, or "possibly present," sometimes a false alarm, letting expensive lookups be skipped when the answer is "definitely not present."

Example: the compressed guest list that can safely say "definitely not on this list" is a Bloom filter over the party's guests.