Bloom Indexes: Multi-Column Equality at Minimal Cost
Five low-selectivity columns, queried in every combination. Five B-tree indexes cost 10MB combined. One bloom index covers all of them at 3.1MB.
An event log with columns like kind, host, region, env, and tier has a specific, awkward shape: each column individually only narrows the table down a little (only 4 possible values for kind, only 3 for env), but queries filter on arbitrary 2-to-5 column combinations, and there is no way to predict in advance which combination the next query will use. Building a composite B-tree index for every combination that might be queried is combinatorially expensive; building 5 separate single-column B-tree indexes helps individually but wastes space duplicating information PostgreSQL then has to combine at query time with a BitmapAnd.\n\nA bloom index solves this differently: it builds one signature per row, encoding a probabilistic membership test across every indexed column simultaneously, rather than a separate structure per column. A bloom filter never produces a false negative — if a row genuinely matches, its signature is guaranteed to indicate a possible match — but it can produce a false positive, a signature that looks like a match but is not, which is exactly why every bloom-indexed row still gets rechecked against the heap before being returned. That recheck is bloom's honest tradeoff for its size: probabilistic membership at a fraction of the storage cost of several individual, exact B-tree indexes.
One Bloom Index, Measured
CREATE EXTENSION IF NOT EXISTS bloom;
CREATE INDEX idx_events_bloom ON idx_events USING bloom(kind, host, region, env, tier);
SELECT pg_size_pretty(pg_relation_size('idx_events_bloom'));
-- 3152 kB
One index, all 5 columns, 3.1 MB on 200,000 rows.
Five Separate B-tree Indexes, Measured Against It
CREATE INDEX idx_ev_kind ON idx_events(kind);
CREATE INDEX idx_ev_host ON idx_events(host);
CREATE INDEX idx_ev_region ON idx_events(region);
CREATE INDEX idx_ev_env ON idx_events(env);
CREATE INDEX idx_ev_tier ON idx_events(tier);
-- combined: 10 MB
Roughly 3.2 times more storage for five separate structures than for the one bloom index covering the identical columns — and that gap widens sharply with more columns and more rows than this lab's scale, which is exactly why the curriculum's own production-scale example (8 columns, 800MB of separate B-trees versus under 50MB for one bloom index) describes a far larger version of the same real tradeoff measured here directly.
Bloom, By Default, at This Table's Real Scale
EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND region = 'us-east';
Seq Scan on idx_events (cost=0.00..4563.00 rows=12057 width=32)
Filter: ((kind = 'error'::text) AND (region = 'us-east'::text))
Worth being honest about: at this table's actual measured size, the planner's default choice is a Seq Scan, not the bloom index. A bloom index has no internal ordering — every bloom scan has to check every entry, similar in cost to reading the whole index — so it only wins decisively once either the table is significantly larger or the filter is selective enough that avoiding heap access for non-matching rows genuinely pays for that full-index cost.
Forcing Bloom On, and Reading the Recheck Step
SET enable_seqscan = off;
EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND host = 'host7' AND region = 'us-east' AND env = 'prod' AND tier = 't2';
Bitmap Heap Scan on idx_events (cost=5076.01..5173.97 rows=27 width=32)
Recheck Cond: ((kind = 'error'::text) AND (host = 'host7'::text) AND (region = 'us-east'::text) AND (env = 'prod'::text) AND (tier = 't2'::text))
-> Bitmap Index Scan on idx_events_bloom (cost=0.00..5076.00 rows=27 width=0)
Index Cond: ((kind = 'error'::text) AND (host = 'host7'::text) AND (region = 'us-east'::text) AND (env = 'prod'::text) AND (tier = 't2'::text))
All 5 columns land in a single Index Cond against one index — no BitmapAnd needed to combine several separate indexes — and "Recheck Cond" is bloom's probabilistic guarantee made visible: every row the bloom scan flags as a possible match gets checked against the real heap row before being returned, resolving any false positives the probabilistic signature might have produced.
Bloom filter (probabilistic membership)
A compact data structure that answers "might this be a member of this set" using a fixed-size bit signature per entry, rather than storing exact values. It guarantees no false negatives — a true member always tests positive — but permits false positives, entries that test positive without actually being members, at a rate controllable by the signature's size. A bloom index applies this idea per row, encoding several columns' values into one signature, which is why every bloom-indexed match still needs a heap recheck to rule out false positives before being returned.
Heap recheck (Recheck Cond)
A step where PostgreSQL re-evaluates the original WHERE condition directly against a candidate row's real heap data, rather than trusting an index's answer as final. Bitmap Heap Scans over lossy or probabilistic indexes (BRIN, bloom) always need this; exact indexes like a plain B-tree usually do not, except when checking visibility for an Index Only Scan. It is the mechanism that keeps a probabilistic or lossy index's result set always exactly correct, regardless of how approximate the index's internal signal is.
🫧 Build One Bloom Index Across All 5 Columns
Enable the bloom extension and create a single index covering kind, host, region, env, and tier together.
psql -U postgres -d beer_db -c "CREATE INDEX idx_events_bloom ON idx_events USING bloom(kind, host, region, env, tier);"psql -U postgres -d beer_db -c "SELECT pg_size_pretty(pg_relation_size('idx_events_bloom')) AS bloom_size;"student@lab:~$ psql -U postgres -d beer_db -c "CREATE INDEX idx_events_bloom ON idx_events USING bloom(kind, host, region, env, tier);" SET CREATE INDEX student@lab:~$ psql -U postgres -d beer_db -c "SELECT pg_size_pretty(pg_relation_size('idx_events_bloom')) AS bloom_size;" SET bloom_size ------------ 3152 kB (1 row)
📊 Build Five Separate B-tree Indexes and Compare, Then Drop Them
Create one B-tree index per column, measure their combined size against the bloom index, then drop them since the bloom index already covers every combination.
psql -U postgres -d beer_db -c "CREATE INDEX idx_ev_kind ON idx_events(kind);" -c "CREATE INDEX idx_ev_host ON idx_events(host);" -c "CREATE INDEX idx_ev_region ON idx_events(region);" -c "CREATE INDEX idx_ev_env ON idx_events(env);" -c "CREATE INDEX idx_ev_tier ON idx_events(tier);" -c "SELECT pg_size_pretty(pg_indexes_size('idx_events') - pg_relation_size('idx_events_bloom')) AS five_btree_total;"psql -U postgres -d beer_db -c "DROP INDEX idx_ev_kind, idx_ev_host, idx_ev_region, idx_ev_env, idx_ev_tier;"student@lab:~$ psql -U postgres -d beer_db -c "CREATE INDEX idx_ev_kind ON idx_events(kind);" -c "CREATE INDEX idx_ev_host ON idx_events(host);" -c "CREATE INDEX idx_ev_region ON idx_events(region);" -c "CREATE INDEX idx_ev_env ON idx_events(env);" -c "CREATE INDEX idx_ev_tier ON idx_events(tier);" -c "SELECT pg_size_pretty(pg_indexes_size('idx_events') - pg_relation_size('idx_events_bloom')) AS five_btree_total;" SET CREATE INDEX CREATE INDEX CREATE INDEX CREATE INDEX CREATE INDEX five_btree_total ------------------- 10 MB (1 row) student@lab:~$ psql -U postgres -d beer_db -c "DROP INDEX idx_ev_kind, idx_ev_host, idx_ev_region, idx_ev_env, idx_ev_tier;" SET DROP INDEX
🤔 See the Planner's Honest Default at This Table's Real Scale
Run a 2-column filter with default settings and see which plan the planner actually picks — not the one you might expect.
psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND region = 'us-east';"student@lab:~$ psql -U postgres -d beer_db -c "EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND region = 'us-east';" SET QUERY PLAN ------------------------------------------------------------------- Seq Scan on idx_events (cost=0.00..4563.00 rows=12057 width=32) Filter: ((kind = 'error'::text) AND (region = 'us-east'::text)) (2 rows)
🔬 Force Bloom On and Read the Heap Recheck Directly
Disable Seq Scan and run a highly selective 5-column filter, confirming genuine bloom index usage and its recheck step.
psql -U postgres -d beer_db -c "SET enable_seqscan = off;" -c "EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND host = 'host7' AND region = 'us-east' AND env = 'prod' AND tier = 't2';"student@lab:~$ psql -U postgres -d beer_db -c "SET enable_seqscan = off;" -c "EXPLAIN SELECT * FROM idx_events WHERE kind = 'error' AND host = 'host7' AND region = 'us-east' AND env = 'prod' AND tier = 't2';" SET SET QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on idx_events (cost=5076.01..5173.97 rows=27 width=32) Recheck Cond: ((kind = 'error'::text) AND (host = 'host7'::text) AND (region = 'us-east'::text) AND (env = 'prod'::text) AND (tier = 't2'::text)) -> Bitmap Index Scan on idx_events_bloom (cost=0.00..5076.00 rows=27 width=0) Index Cond: ((kind = 'error'::text) AND (host = 'host7'::text) AND (region = 'us-east'::text) AND (env = 'prod'::text) AND (tier = 't2'::text)) (4 rows)
Lab 3.2.7 complete — Block 3.2 complete. Bloom indexes, measured honestly including where they lose:\n\n\n Bloom index, 5 columns : ✅ 3152 kB\n 5 separate B-tree indexes : ✅ 10 MB — ~3.2x more, measured\n Planner's honest default : ✅ Seq Scan, at this table's real scale\n Bloom forced on, recheck shown : ✅ single Index Cond, real Recheck Cond\n
Enable JavaScript to run the live terminal and track your progress.