Bloom Filters

What is a Bloom Filter?

A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. It can tell you with certainty when an element is not in a set, but it may give false positives (incorrectly stating an element is in the set when it’s not).

Key Characteristics

• Space-efficient: Uses significantly less memory than storing all elements
• Fast lookups: O(k) where k is the number of hash functions used
• No false negatives: If the filter says an element is not present, it definitely isn’t
• Possible false positives: May incorrectly report that an element exists
• Cannot remove elements: Once added, elements cannot be easily removed from a standard Bloom filter

How It Works

1. Start with a bit array of m bits, all set to 0
2. Choose k different hash functions that each map an element to one of the m positions
3. To add an element, feed it to each hash function and set the bits at the resulting positions to 1
4. To query if an element exists, check if all k bits at positions given by the hash functions are 1
   • If any bit is 0: the element is definitely not in the set
   • If all bits are 1: the element might be in the set

Simple Example

Let’s say we have:

• Bit array of length 10
• 2 hash functions (H₁ and H₂)

Adding “apple” to our Bloom filter:

1. H₁(“apple”) = 1 → Set bit 1 to 1
2. H₂(“apple”) = 7 → Set bit 7 to 1

Adding “orange” to our Bloom filter:

1. H₁(“orange”) = 3 → Set bit 3 to 1
2. H₂(“orange”) = 7 → Bit 7 is already 1

Our bit array is now: [0, 1, 0, 1, 0, 0, 0, 1, 0, 0]

Checking if “apple” exists:

1. H₁(“apple”) = 1 → Bit is 1
2. H₂(“apple”) = 7 → Bit is 1 Result: May exist (actually does)

Checking if “banana” exists:

1. H₁(“banana”) = 4 → Bit is 0
2. H₂(“banana”) = 9 → Doesn’t matter Result: Definitely doesn’t exist

Checking if “grape” exists:

1. H₁(“grape”) = 3 → Bit is 1
2. H₂(“grape”) = 7 → Bit is 1 Result: May exist (false positive)

Database Applications

1. Query Optimization: Quickly filter out table partitions that definitely don’t contain the searched value
2. Join Optimization: Reduce unnecessary lookups by filtering out rows that can’t possibly match
3. Cache Filtering: Determine if an item is definitely not in cache before checking slower storage
4. Distributed Systems: Minimize network requests by checking if data might exist on a remote node

Example in PostgreSQL

PostgreSQL uses Bloom filters in:

-- Create a table with Bloom index
CREATE TABLE products (
    id INT,
    name TEXT,
    category TEXT
);
 
-- bloom is a contrib extension, not built in
CREATE EXTENSION IF NOT EXISTS bloom;
 
-- Create a Bloom filter index on multiple columns
CREATE INDEX product_bloom_idx ON products USING bloom (name, category);
 
-- Query that can use the Bloom filter index
SELECT * FROM products WHERE name = 'Laptop' AND category = 'Electronics';

This query scans the whole Bloom index, which stores one signature per row (not per page). Rows whose signature says ‘Laptop’ and ‘Electronics’ definitely aren’t there are skipped; matches are lossy and get rechecked against the heap. It supports equality only (no ranges, no sorting).

Trade-offs

• Memory usage vs. accuracy: Larger bit arrays reduce false positives but use more memory
• Number of hash functions: More hash functions reduce false positives but increase computation cost
• Perfect for: High-volume filtering operations where occasional false positives are acceptable
• Not suitable for: Applications requiring exact results without additional verification

Notes

• Bloom filters are not suitable for counting occurrences of items.
• They are a great fit for scenarios where the dataset is large, and you want to minimize disk or network access.
• False positive rates can be tuned by adjusting the size of the bit array and the number of hash functions.
• Variants like Counting Bloom Filters allow for element removal but use more memory and are more complex.