Part 3 of 5 · 1 min read
Why false positives happen but false negatives cannot
The compression that makes a Bloom filter small also makes it occasionally overconfident, but never wrong in the unsafe direction.
Think of the compressed guest list again. The compression is so heavy that two different names can end up looking identical in compressed form. That can cause the bouncer to say "might be on the list" for someone who is not actually on it. But the compression never erases a name that really is on the list.
In plain words: a Bloom filter achieves its small size by hashing each key into a shared bit array, the same bit array used by every other key, rather than storing keys individually. Two different keys can set overlapping bits, which can cause a key that was never actually inserted to still appear "possibly present," a false positive. However, a key that genuinely was inserted always leaves its bits set, so checking for it can never incorrectly report "definitely not present," which is why there are never false negatives.
A worked example. A Bloom filter might say "possibly present" for customer_id = 999999 even though it was never inserted, triggering an unnecessary but harmless SSTable check; it would never say "definitely not present" for a customer_id that actually was inserted.
The key lines. No new SQL; the false-positive-only guarantee is a mathematical property of how Bloom filters are built, not something a query configures.
False positive (Bloom filter)
A false positive in a Bloom filter is a "possibly present" answer for a key that was never actually inserted, caused by shared bits overlapping between different keys; a Bloom filter never produces the opposite, unsafe kind of error.
Example: the bouncer's "might be on the list" for someone who was never invited, caused by the guest list's heavy compression, is a false positive.