Dynamic partition pruning and runtime filters

How does a join create a filter the query never wrote, and what does that cost?

Static mechanisms use information that is in the query text. The defining case here has none. In fact JOIN dim ON ... WHERE dim.attr = 'x', there is no predicate on the fact table at all. The filter that would prune 99% of the fact table exists only as a result of running part of the query. So the information has to be created at run time.

The mechanism

1. The build side of the join (the small side, from which a hash table is built) produces its set of join keys.
2. That set is turned into a filter: an IN-list when it is tiny, a Bloom filter when it is large, a min/max range when the key is clustered.
3. The filter is injected into the scan of the probe side (the large side). There it feeds the same pruning and skipping machinery as a predicate that someone wrote.

The fact scan gets a predicate that the user never wrote.

Dev's query. stores has 400 rows; one of them matches store_name = 'Koramangala'. The build side yields store_id = 17. The filter o.store_id IN (17) goes into the scan of orders. With data clustered by store, almost all files are skipped.

Why it is cheap. The filter is a byproduct of work already being done. The build side is building a hash table anyway, and extracting the key set costs nothing extra. Mechanisms that harvest information from work already committed are structurally different from mechanisms that pay for information.

Why it is not free. The filter must exist before the probe scan starts. That is a scheduling dependency: the probe cannot begin until the build ends. In a pipelined engine this serializes two operations that could have run at the same time, so runtime filtering trades parallelism for less I/O. In a stage-based engine (one that runs in stages and writes data out between them, as at a shuffle) the barrier already exists, so the dependency costs nothing.

This is the second time we see a pattern: dynamic mechanisms are cheap exactly where a barrier already exists. (Adaptive re-planning, in Execution decisions, is the other.) It explains a difference that people usually blame on engineering taste. Shuffle-based engines adopted dynamic pruning and adaptive execution readily. Pipelined single-node engines adopted them slowly. The reason is the structure of execution: an engine that already stops to materialize has a free place to think.

When the barrier is truly too expensive, there are two escapes:

• Run the dimension side twice: once as a small standalone subquery, only to get the pruning values. You pay |dim| to avoid scanning the un-pruned fact table. It is worth it only when |dim| is much smaller than the saving. This is why engines gate it on a broadcast-size threshold and on a fact-to-dimension size ratio, and do not apply it everywhere.
• Apply the filter late, after the scan has started. This saves CPU and join work but not I/O.

Sizing. A Bloom filter at a 1% false-positive rate needs about 10 bits per element.

• 10⁶ distinct keys: 10⁶ × 10 bits = 10⁷ bits = 1.25 MB, about 1.2 MB. Easy to broadcast to every worker.
• 10⁹ keys: about 1.2 GB. Not practical to broadcast.

So runtime filters have a ceiling on build-side cardinality that comes from transport cost, not from filter quality. The false-positive rate ε means that you read a fraction ε of the blocks you should have skipped. The cost is only wasted reads, which is the safe direction again, so the approximation is acceptable. You can trade exactness against broadcast bytes, and the error only ever costs I/O that you would have done anyway. Runtime-filter sizing also assumes that join keys are spread independently of how the probe side's files are laid out, which is another place where the independence assumption can fail.

Who uses the filter matters. The join algorithm that uses a Bloom filter to avoid probing (sometimes called sideways information passing) is a matter of how the join operator runs. The decision to build the filter, its size, its transport, and its use for pruning at the storage layer belong to the planner. The difference is large: a filter used by the join saves probe CPU. A filter used by the scan saves I/O, and the second saving is about an order of magnitude bigger.

In one sentence: runtime filters create predicates that the query never contained, harvested free from work already under way, paid for with a scheduling barrier and a broadcast whose size caps the build-side cardinality.