Bloom Filters in Real Databases and Formats

In one line

RocksDB (bits per key, full, blocked and Ribbon filters, prefix filters), LevelDB, Cassandra (bloom_filter_fp_chance per table), HBase (ROW/ROWCOL filters per HFile), ScyllaDB, Parquet (split-block Bloom filters per column chunk) and PostgreSQL's bloom index extension all use membership filters to avoid I/O. Know the knobs.

0/3 · 0%

Think of it like this

Different libraries using the same card-catalogue idea with different card sizes and rules. The principle is the same; the settings differ by library.

Key ideas

01
RocksDB: BlockBasedTableOptions.filter_policy = NewBloomFilterPolicy(10) (10 bits/key) or NewRibbonFilterPolicy(10) (~30% less memory, slower build); whole-key vs prefix filtering; optimize_filters_for_hits skips filters on the last level to save memory when most lookups hit.
02
Cassandra: bloom_filter_fp_chance per table (commonly 0.01 by default, higher such as 0.1 for leveled compaction in older versions); filters live off-heap; lowering the chance increases memory. Changing it requires rewriting SSTables to take effect.
03
HBase: BLOOMFILTER => 'ROW' (default) or 'ROWCOL' per column family, stored in HFiles to skip files on Get.
04
Parquet: optional split-block Bloom filters per column chunk let query engines skip row groups for equality predicates on high-cardinality columns (where min/max statistics don't help).
05
PostgreSQL bloom extension: a signature-based index useful for equality queries on many columns combined arbitrarily (lossy; rechecks rows).
06
Search and warehouses: some engines use Bloom filters for join filtering (runtime filters) to skip rows on the probe side of a hash join.

Code & diagrams

configs.txttext

-- Cassandra
ALTER TABLE shop.orders WITH bloom_filter_fp_chance = 0.001;
-- then: nodetool upgradesstables -a shop orders   (rewrite SSTables so new filters apply)

# RocksDB (C++ / Java options)
table_options.filter_policy.reset(NewBloomFilterPolicy(10));      // ~1% FPR
table_options.filter_policy.reset(NewRibbonFilterPolicy(10));     // same FPR, ~30% less memory

# HBase shell
alter 'events', {NAME => 'd', BLOOMFILTER => 'ROWCOL'}

# Parquet writer (e.g. parquet-mr)
parquet.bloom.filter.enabled#user_id=true
parquet.bloom.filter.expected.ndv#user_id=5000000

Explain it without notes

Why does changing Cassandra's bloom_filter_fp_chance not take effect immediately?

Practice

For a Cassandra table with 3 billion partitions per node, estimate filter memory at fp_chance 0.01 and 0.001.

Trade-offs

↔
Lower FPR saves I/O but costs memory per node; tune by read pattern (many misses → lower FPR).

Done when you can

I can name how major databases and formats use Bloom filters and their main knobs.