What is a runtime (bloom) filter in a star join, and how does it cut the fact-table scan?

## The shape of the problem A canonical star query filters the dimension and aggregates the fact: ```sql SELECT d.region, SUM(f.revenue) FROM fact_sales f JOIN dim_store d ON f.store_id = d.store_id WHERE d.region = 'EMEA' GROUP BY d.region; ``` The only predicate is on `dim_store`. `fact_sales` has no `region` column, so a naive plan scans every fact row, joins, and throws away the non-EMEA ones. If EMEA is 3% of stores, the engine has read roughly 33× more fact data than it needed. ## What a runtime filter does The insight is that the set of `store_id` values that can possibly survive is knowable *before* the fact table is scanned — it is exactly the set of keys the filtered dimension produces. So the engine: 1. Scans and filters the dimension side first (it is small, so this is cheap). 2. Builds a compact summary of the surviving `store_id` values. 3. Sends that summary to the fact-table scan operators. 4. The fact scan applies it as an additional predicate, skipping data that cannot match. Because the summary is built while the query runs, this is a *runtime* (or *dynamic*, or *sideways-information-passing*) filter, as opposed to a predicate the optimizer could write down statically. ## The three forms of summary **Min/max range.** Cheapest: record the smallest and largest surviving key. If the fact table's blocks carry zone-map min/max metadata for the key column, whole blocks outside the range are skipped without being read. Useless when the surviving keys span the full domain. **IN-list / exact set.** When few keys survive, ship them literally. Exact — no false positives — but only viable for small sets. **Bloom filter.** A bit array plus a few hash functions. Inserting a key sets several bits; probing a key checks those bits. A miss is definitive ("this key is certainly not in the set"), a hit is probabilistic ("probably in the set"). That asymmetry is exactly what a filter needs: false positives merely let a doomed row through to be rejected by the real join, while the absence of false negatives guarantees correctness. It is compact — a few bits per key — so it works for sets far too large to ship as literals. ## Where the filter is applied matters There is a large difference between applying the filter at three levels: - **Per row, after decode.** Saves join and network work but still reads and decodes everything. Modest win. - **Per block/row-group, using zone-map metadata.** Skips I/O entirely for blocks whose key range or set summary cannot intersect. Large win. - **Per partition — dynamic partition pruning.** If the fact table is partitioned on the join key (commonly a date key joined to a date dimension), the surviving key set determines which partitions are touched at all. This is the biggest win of the three and is why `JOIN dim_date d ON f.date_key = d.date_key WHERE d.fiscal_quarter = 'Q3'` can be made to read only that quarter's partitions instead of the whole history. ## Why it sometimes does nothing - **The dimension filter is not selective.** If 80% of dimension rows survive, the filter excludes almost no fact data and you have paid for building and probing it for nothing. Engines usually estimate this and drop the filter adaptively. - **Surviving keys are scattered.** Block-level skipping requires that matching keys be *clustered* into few blocks. If the fact table is ordered by time and the surviving keys appear in every block, no block can be skipped even though only a few rows per block match. This is the same correlation requirement that governs all zone-map pruning. - **The filter arrives too late.** The build side must complete before the filter can be pushed. If the fact scan has already started, only the remainder benefits. Some engines wait; some accept a partial benefit. - **False-positive rate too high.** A bloom filter sized too small for the key count degrades toward "everything matches." ## Diagnosing it in production The symptom of a *missing* runtime filter is a plan where the fact scan's actual row count is enormous relative to the join's output — a huge ratio of rows read to rows kept, with a small selective predicate on the dimension. The fix path is usually: confirm statistics on the dimension are current (the optimizer must believe the filter is selective), confirm the join is a plain equi-join on the raw key (wrapping the key in a function or casting it defeats the filter), and confirm the fact table's layout correlates with the key so block skipping is possible. Sometimes the honest fix is layout, not the filter: sorting or clustering the fact table on the key that gets filtered turns a useless filter into a very effective one. ## Interview framing The key sentence is: *the selective predicate lives on the small table but the expensive scan is on the big one, and a runtime filter is the mechanism that carries selectivity across the join.* Then name the forms (min/max, IN-list, bloom), the level of application (row, block, partition), and the two conditions for it to pay: a selective dimension filter and a fact-table layout correlated with the key.