Bloom filters for database performance: Reducing unnecessary disk I/O

Last month, our primary key-value store started choking on a spike of negative lookups. Our application was constantly asking the database for IDs that didn't exist, forcing the storage engine to walk B-tree levels just to return a "not found" response. The latency hit was brutal, spiking our p99 response times by about 120ms during peak hours.

We realized that for high-cardinality datasets, checking the disk for every single request is a recipe for disaster. We needed a way to verify if a key might exist before ever touching the storage layer.

Understanding the Bloom filter advantage

A Bloom filter is a probabilistic data structure that tells you if an element is definitely not in a set or might be in the set. It’s perfect for this scenario because it’s incredibly space-efficient. When a lookup request hits your service, you check the Bloom filter first. If it returns false, you can immediately return a 404 to the user without querying the database.

If it returns true, you still have to query the database, because a Bloom filter can have false positives. But by filtering out the bulk of the "not found" queries, you drastically reduce your total disk I/O. As I discussed in my previous post on Bloom filters for efficient membership testing in high-cardinality data, this is the most effective way to protect your storage engine from unnecessary load.

The wrong turn: Attempting on-disk Bloom filters

Initially, we tried implementing Bloom filters directly inside our PostgreSQL schema using a custom extension. We thought keeping the logic close to the data would be cleaner. It was a disaster.

The overhead of updating the filter on every write transaction slowed our ingestion rate by roughly 30%. We were essentially trading read performance for write performance, which didn't solve our core issue of protecting the disk during read-heavy bursts. We learned the hard way that the filter needs to live in memory, either in the application layer or in a fast cache like Redis.

Implementing Bloom filters for database performance

We shifted our strategy to use Redis to maintain the Bloom filter. Since we were already using Redis for session management, adding a Laravel performance: Optimizing database query offloading with Bloom filters approach felt like a natural extension.

Here is the simplified flow of our implementation:

1. Write Path: When a new ID is inserted into the database, we add it to the Redis Bloom filter.
2. Read Path:
   • Client requests key X.
   • Application checks Redis: BF.EXISTS key_set X.
   • If 0 (False): Return null immediately.
   • If 1 (True): Execute the SQL query.

The code looks roughly like this in our middleware:

PHP
#6A9955">// Check the Bloom filter before hitting the DB
$exists = Redis::executeRaw(['BF.EXISTS', 'user_bloom_filter', $userId]);

if (!$exists) {
    return response()->json(['error' => 'Not found'], 404);
}

#6A9955">// Fallback to the DB
return $this->userRepository->findById($userId);

This simple check removed around 40% of the traffic hitting our disk. The latency improvement was immediate, bringing our average lookup time down from 140ms to a steady 15ms.

Managing trade-offs and accuracy

One thing you need to watch out for is the false positive rate. If your filter is too small for the number of keys you're storing, the false positive rate will climb, and you'll end up hitting the database for keys that don't exist anyway.

We used a target error rate of 0.1%. When initializing the filter in Redis, we had to estimate the total capacity:

Bash
# Initialize with capacity of 1 million items and 0.1% error rate
BF.RESERVE user_bloom_filter 0.001 1000000

If your dataset grows beyond your initial estimate, you’ll need a strategy to rebuild the filter. We currently just rebuild it during our nightly maintenance window. It’s not perfect—if a new key is added between the rebuilds and the filter isn't updated, the filter might return a false negative (which shouldn't happen) or we might miss an update.

To handle this, we occasionally cross-reference our cache with the database to ensure we aren't drifting too far. If you're dealing with massive, constantly changing data, you might also want to look into partial indexes for high-cardinality filtering: A deep dive as a complementary strategy to keep your index sizes manageable.

Final thoughts

Using Bloom filters isn't a silver bullet for every database problem. It works best when you have a high volume of read misses and a relatively stable set of keys. If your workload is dominated by range scans or updates, the complexity of maintaining the filter might outweigh the benefits.

I'm still tinkering with how to handle deletions. Bloom filters don't support deleting items natively—you'd need a "Counting Bloom Filter" for that, which uses much more memory. For now, we accept that our filter might have "ghost" entries after a record is deleted, which just leads to an extra database check. It’s a trade-off I’m happy to make for the performance gains we've seen.