Bloom Filters

When you’re searching petabytes of data, you can’t afford to scan every record or even every file. You need a quick way to answer the question:

“Is this key possibly in my dataset?”

Bloom filters provide exactly that — with extreme speed and tiny memory usage — by trading a small amount of false positives for massive performance gains.

What is a Bloom Filter?

A Bloom filter is a probabilistic data structure that:

• Tells you if an element is possibly in a set or definitely not.
• Uses bit arrays and multiple hash functions.
• Never returns false negatives (if it says “not present,” you can trust it).

Key point: They are not about exact lookup, they are about fast elimination.

How It Works

1. Initialize a bit array of size m with all zeros.
2. Choose k independent hash functions, each mapping an input to one of m positions.
3. Insert an element:
   • Pass it through each hash function.
   • Set the corresponding bits in the array to 1.
4. Query an element:
   • Check the k bit positions.
   • If any bit is 0, the element is definitely not in the set.
   • If all are 1, the element is possibly in the set.

A Tiny Example

Let’s create a Bloom filter for a set of fruits: {apple, banana, cherry}.

Parameters:

• m = 10 bits
• k = 3 hash functions

Insert “apple”:

• Hash1(apple) → bit 3 = 1
• Hash2(apple) → bit 6 = 1
• Hash3(apple) → bit 9 = 1

Repeat for banana and cherry.

Query “grape”:

• Hash1(grape) → bit 2 = 0 → instantly “not present.”

Why It’s So Fast

• Bloom filters don’t store actual keys — just bit patterns.
• They can eliminate huge amounts of data before more expensive lookups.
• They’re compact enough to keep in CPU cache or even embedded in file metadata.

False Positives

• Sometimes, unrelated keys set the same bits, causing a false positive.
• The false positive rate depends on:

Where Bloom Filters Are Used

• Databricks Delta Lake – skips Parquet files without matching values (docs)
• Apache HBase – avoids reading unnecessary HFiles (docs)
• Apache Cassandra – speeds up SSTable lookups (docs)
• Google Bigtable – prevents unnecessary disk access (docs)
• Chrome Safe Browsing – quickly checks if URLs are on a malware list.

Advantages

• Extremely space-efficient
• Fast O(k) lookups (constant time)
• No false negatives
• Great for pre-filtering in large-scale systems

Limitations

• False positives possible (but tunable)
• No deletions in the basic version (use Counting Bloom Filters to allow removal)
• Must know or estimate n to size m and k correctly

Bloom Filters in Action – Databricks Example

When you create a Bloom filter index on a Delta table column:

CREATE BLOOMFILTER INDEX ON TABLE orders FOR COLUMNS (customer_id) OPTIONS ('fpp' = 0.01);

CREATE BLOOMFILTER INDEX ON TABLE orders FOR COLUMNS (customer_id) OPTIONS ('fpp' = 0.01);

• fpp = false positive probability target.
• Databricks stores the Bloom filter metadata alongside file statistics.

SELECT * FROM orders WHERE customer_id = 12345;

SELECT * FROM orders WHERE customer_id = 12345;

The Bloom filter tells the engine which Parquet files might have matching rows — avoiding scanning the rest.

Summary

Bloom filters are not about answering “what’s in my dataset” — they’re about quickly ruling out what’s not.
They are one of the most effective tools for reducing I/O in big data systems, especially when combined with columnar storage and metadata pruning.