How does a per-block bloom filter help a columnar engine where min/max zone maps cannot?

## Why min/max runs out Block elimination in a columnar engine is normally driven by per-block min/max bounds. Those bounds answer one question well — *is the sought value outside this block's range?* — and answer nothing else. For a column whose values are scattered across the table (a user id, a device id, a request id in a time-ordered table), every block spans nearly the whole domain, every interval test passes, and pruning collapses to zero. The predicate is selective; the metadata simply cannot express that selectivity. What is needed is **set membership**, not range containment. ## What a bloom filter contributes A bloom filter is a fixed-size bit array plus a handful of hash functions. Inserting a value sets the bits at each hash position. Testing a value checks those bits: - any bit unset → the value was **definitely never inserted** → the block provably cannot contain it → skip it; - all bits set → the value is **possibly present** → read the block and check the rows. The structure is one-sided in the same direction as a zone map — no false negatives, so results never change — but it discriminates on identity instead of range. Build one per block per column and a point lookup on a scattered column skips the vast majority of blocks. The error rate is a design parameter. Roughly, more bits per distinct element means fewer false positives and a larger filter; too few bits and the array saturates until nearly every test says "possibly present", at which point you are paying for the filter and skipping nothing. A saturated bloom filter is the classic failure mode, and it happens exactly when someone attaches one to a column with far more distinct values per block than the filter was sized for. ## Set and other skipping structures Bloom is not the only choice, and engines expose a small family of block-level skipping structures: - **min/max** — the default, free, good for ordered or correlated columns and for ranges. - **bloom** — probabilistic membership; equality and `IN` only; best on high-cardinality scattered columns. - **set** — stores the *actual* distinct values in the block up to a cap, falling back to "unknown" above it. Exact, no false positives, and cheap when each block genuinely contains few distinct values (a status, a country, a tenant id) but the column is not the sort key. Some engines also let you build these over an *expression* rather than a raw column, so a filter on a token, a hash, or a JSON path can be skipped on. ## The cost side, which is what separates a senior answer 1. **Write cost.** Every block written must build and store the structure. On a high-ingest table that is real CPU and real bytes, paid on every insert and every compaction that rewrites blocks. 2. **Read-side memory.** Filters must be loaded to be consulted. A filter that is too large for the metadata cache turns into extra I/O on the hot path. 3. **Granularity.** These structures skip *blocks*, not rows. If your point lookup matches one row and the block is a million rows, the best possible outcome is still reading one whole block. If matching rows are spread so that one lands in most blocks — a moderately frequent value rather than a rare one — nothing is skipped at all, and no tuning saves you. 4. **They do not replace layout.** A bloom filter is a patch over an unfavourable physical order. If the workload is dominated by that access pattern, changing the sort order or maintaining a second ordered copy of the table beats bolting on filters. ## When to reach for one Good fit: a large table with a fixed, useful sort order; a secondary, highly selective equality lookup on a scattered high-cardinality column; that lookup frequent enough to matter but not frequent enough to justify re-sorting. Bad fit: range predicates (bloom filters cannot answer them at all); low-selectivity filters that match a large share of rows; columns already correlated with the sort key, where min/max already does the job for free; and small tables, where the whole scan costs less than maintaining the structure. ## How to evaluate it honestly Measure before and after with the engine's scan statistics — blocks scanned versus total, bytes read — for the target query, and separately measure ingest throughput and stored size. The only defensible justification is a measured drop in bytes scanned on real query traffic that outweighs the added write and storage cost. "We added bloom filters everywhere" is a smell: filters on columns nobody filters on are pure write-side tax.