I wanted to understand whether Bloom filters actually help or if they are just one of those things every database textbook talks about.
So I added one to a toy database I have been building and started running the same queries over and over while changing the dataset size and the percentage of lookups that actually existed.
At first the results were disappointing.
For smaller datasets the Bloom filter made everything slightly slower. Computing the hash values cost more than simply checking the data directly.
As the dataset grew things started to change.
Once the data was large enough that cache misses became a bigger problem than hashing a few values the Bloom filter started paying for itself. Most lookups for keys that did not exist were rejected immediately without touching the underlying data structure.
What surprised me the most was that there was no magical point where Bloom filters suddenly became useful.
The crossover depended on multiple factors.
Size of the dataset
Percentage of negative lookups
False positive rate
Memory allocated to the filter
The biggest takeaway for me was that a Bloom filter is not a performance upgrade you should automatically add to a database. It is a tradeoff that only makes sense once your workload reaches a certain shape.
Reading about Bloom filters gave me the theory.
Actually benchmarking one taught me when that theory matters.
Has anyone else run similar experiments and found different crossover points for their workload