Broadcast, shuffle and runtime filters

When does a runtime filter earn its barrier?

Broadcast, shuffle, and the partitioning you already have

A shuffle join repartitions both inputs by the hash of the join key, then runs a local join on each partition. The network cost is roughly |R| + |S| (each row moves once). The payoff is that per-node build memory becomes build/P. Dividing the memory problem by the parallelism is the whole point.

A broadcast join copies the small side to all P nodes. The network cost is |S_small|·P. The large side never moves and, importantly, it keeps its partitioning. A later aggregation or join on the same key then also avoids a shuffle. Property preservation compounds down the plan; a local cost saving does not.

The network break-even is |S_small|·P < |R| + |S_small|. This reduces to: broadcast when the size ratio exceeds the parallelism (|R| / |S_small| > P roughly).

The network arithmetic permits far larger broadcasts than any engine allows, because two other costs bind first:

• The small side must be resident on every executor, so the memory used is |S_small|·P. The shuffle's cost was relocated into memory, not removed.
• The hash table is built P times instead of once, so the total build CPU is P× higher.

So the claim "broadcasting a small table is always free" is wrong. With P in the hundreds, a 500 MB broadcast is 100 GB of cluster memory and a hundred or more redundant builds. In engines that route the broadcast through a central driver process, it is also a serialization point that fails hard instead of slowly.

The third option costs nothing at run time: both tables pre-partitioned on the join key at write time (bucketing, co-partitioned tables, a shared DISTRIBUTED BY clause). The network cost is zero. This is a write-time investment being cashed in. Its price is paid where you do not see it:

• every other query is now partitioned on a key it does not want;
• the bucket counts on both sides must match or divide evenly;
• any rewrite of either table that changes the bucketing silently invalidates the plan.

It is the highest-leverage and the most brittle option in this article.

---

Sideways information passing: move the summary, not the rows

The idea: send a compact description of the build side's keys to the probe side's scan before the probe side moves any data, and discard non-matching rows at the source. In practice this is a runtime filter, usually a Bloom filter.

Its leverage is the ratio of the filter's size (about 10 bits per key) to the rows it keeps from moving (often hundreds of bytes each), and its cost is that the filter must exist before the probe side is scanned, a barrier between two pipelines that were independent. How big to make the filter, which kind to build (min/max, IN-list or Bloom) and when it earns its barrier are the planner's decision (Dynamic partition pruning and runtime filters). On the join side, what matters is what the filter does to correctness.

Why the approximation is safe here. A Bloom filter's false positives let a few non-matching rows through. But an exact join follows the filter, so those rows are removed later. False positives cost work, not correctness. This is the general safe pattern: an approximate pre-filter in front of an exact operator gives an exact answer at reduced cost. Compare approximate aggregation in Aggregation algorithms, where the approximation is in the answer itself. Same mathematics, very different risk.