Bloom Filters are more than what you learn from 5-minute videos; let me tell you about an interesting variant of them called Prefix Bloom Filters. Here it goes…
Regular Bloom Filters hash your key and mark the corresponding bit as 1, registering its presence. This way, because of hash collisions, they suffer from false positives, i.e., they say “maybe it’s there” or “definitely not there”.
Prefix Bloom Filters hash only the prefix portion of keys (not the entire keys), thus creating fewer unique entries. This means a smaller memory footprint and better performance for range queries where you’re scanning multiple keys with the same prefix. But why and how?
Imagine doing range queries and prefix seeks in an LSM-tree-based database. Instead of checking every individual key, you can skip entire SST files based on prefix filtering.
Although this sounds smart, you trade accuracy for speed. Prefix BFs have higher false positive rates for non-prefix queries since fewer unique hashes exist in the filter.
By the way, what I explained is not theoretical stuff. This is used by Facebook, and it is used in MyRocks - the storage engine of MySQL built on top of RocksDB; and a fun fact, MyRocks powers the world’s largest MySQL deployment :)
Hope this made you curious :)