Why architecture matters here
In a distributed query engine, the shuffle is the tax you pay for parallelism, and it is a steep one. To perform a hash join across a cluster, Spark must repartition both tables so that rows with the same join key land on the same executor; that means serializing every row, writing it to local disk, transferring it over the network, and reading it back — for both sides of the join. When one side is a billion-row fact table, the shuffle of that side dominates the query's wall-clock time, its network utilization, and its disk-spill pressure. Anything that reduces the number of fact rows entering the shuffle reduces all three roughly in proportion.
The frustrating part is how much of that shuffled data is wasted. Analytical queries are overwhelmingly selective: a dashboard filters the dimension table to one region, one date range, one product category, and only fact rows joining to those few dimension keys matter. But the filter is on the dimension side, and in a naive plan the engine cannot use it to avoid shuffling the fact side — it shuffles all billion fact rows, joins, and only then does the dimension filter eliminate the 99% that never matched. The information needed to skip those rows existed before the shuffle; the plan simply had no way to carry it to the fact-side scan. Closing that gap is the entire purpose of runtime filtering.
A bloom filter is the right tool because it is small, cheap, and one-sided in exactly the way this problem needs. The set of surviving dimension keys might be millions of values — too large to broadcast as a literal IN list — but a bloom filter representing that same set is a few kilobytes to a few megabytes of bits, small enough to broadcast to every task for free. And its one error mode is asymmetric: it can occasionally say 'maybe present' for a key that is absent (a false positive), but it will never say 'absent' for a key that is present. For a pruning filter that guarantee is precisely correct — a false positive just means a doomed row survives to be dropped by the exact join, while the impossible false negative would have meant silently losing a valid result.
It is worth being explicit about why this is a runtime optimization and cannot be done purely at planning time. The set of surviving dimension keys is not known until the dimension side has actually been scanned and filtered — it depends on the data, not just the query text. A static optimizer can guess selectivity from statistics, but it cannot know the concrete key set, so it cannot build the filter. This is why the feature lives in Adaptive Query Execution: the engine runs the build side first, observes the real key set and its size, builds the bloom filter from actual data, and only then decides whether applying it to the probe side is worth the cost. The optimization is fundamentally reactive — it adapts the plan to what the data turned out to be, which is exactly the class of decision AQE was designed to make.
The architecture: every piece explained
Top row: building the filter. The build side is the small table — the dimension table after its own filters have been applied, so it is the reduced set of keys that can actually participate in the join. Spark hashes each of those join keys into a bloom filter: a fixed-size bit array where each key sets several bits chosen by independent hash functions. The result is a compact membership sketch of the surviving key set. Because it is tiny relative to the data, Spark broadcasts it to every task on the cluster — unlike a broadcast join, which must broadcast the whole small table's rows, here only the filter's bits travel.
Middle row: probing. The probe side is the huge fact table, scanned in parallel across many tasks. As each task reads rows, it applies the filter: it hashes the row's join key and checks whether all the corresponding bits are set. If any required bit is unset, the key is definitely not in the build set and the row is dropped on the spot; if all bits are set, the row passes as a possible match (true positive or occasional false positive). The output is a dramatically shrunken probe side — often an order of magnitude smaller — containing every genuine match plus a small false-positive tail.
Bottom rows: the real join and the decision to do all this. Only the survivors are shuffled, so network transfer and disk spill collapse, and the subsequent hash or sort-merge join does exact key matching that silently discards the false positives, yielding a correct result. Overseeing everything, the AQE / optimizer uses a cost model to gate the whole thing: building and probing a bloom filter is not free, so Spark applies it only when the build side is small enough, the probe side large enough, and the expected selectivity high enough that the pruning pays for the filter's construction — otherwise it skips straight to a normal join.
The two knobs that govern the filter's quality are the number of bits and the number of hash functions, and they trade off in a well-understood way. For a target false-positive rate against a known key cardinality, there is an optimal bit-array size and an optimal number of independent hash functions (each key sets that many bits); too few bits saturates the array so that most bits are set and nearly every probe returns 'maybe present,' collapsing the pruning, while too many hash functions wastes CPU per probe for diminishing accuracy. Because the build side's cardinality is only known at runtime — that is the whole reason this lives in AQE — Spark sizes the filter from the observed surviving key count rather than a static guess, which is exactly what lets it hit a sensible false-positive rate without either over-allocating memory or letting the filter degrade into a pass-everything sieve.
End-to-end flow
Trace a query joining a 2-billion-row sales fact table to a stores dimension filtered to one region (say 300 of 50,000 stores). AQE runs the dimension side first: it scans stores, applies region = 'west', and materializes 300 surviving store_id keys. Seeing that the build side is tiny and the probe side enormous, the optimizer decides a bloom filter is worth it. It hashes those 300 store_ids into a small bit array — a few kilobytes — and broadcasts it to every task that will scan sales.
Now the fact scan runs. Each of the many parallel tasks reads its slice of the 2 billion sales rows and, for each row, hashes store_id and probes the filter. A sale at a store in the east: at least one of its bits is unset, so it is dropped immediately — it never gets serialized, never gets written to a shuffle file, never crosses the network. A sale at a west-region store: all its bits are set, so it passes. Because only ~300 stores match, perhaps 1.5% of the 2 billion rows survive the filter — call it 30 million — plus a sliver of false positives where an east-region store's key happened to collide on every bit. The shuffle now moves 30-odd million rows instead of 2 billion, a ~60x reduction in the most expensive stage of the query.
The survivors shuffle, land on executors partitioned by store_id, and meet the 300 dimension rows in a hash join. The join does exact equality on the real keys, so the handful of false positives — rows that passed the probabilistic filter but do not actually match any of the 300 stores — find no join partner and are dropped, exactly as they would have been in a plain join. The result is identical to the unfiltered query, bit for bit; the bloom filter changed only which rows paid the shuffle cost, never the answer. That is the safety property that makes the optimization automatic: correctness is guaranteed by the exact join, and the filter is pure performance.
The composition with dynamic partition pruning is where this gets even stronger, and it is worth seeing why they are complementary rather than redundant. If sales is partitioned by store_id or by a column functionally dependent on the dimension filter, dynamic partition pruning can skip whole file partitions of the fact table before reading a single row of them — the coarsest and cheapest possible pruning. But most fact tables are partitioned by date, not by every dimension key, so partition pruning cannot help on the store dimension. The bloom filter operates at row granularity within the partitions that must be read, catching the selectivity that partitioning cannot express. Real query plans use both: partition pruning removes the partitions it can, and the runtime bloom filter prunes rows inside the survivors, together driving the volume entering the shuffle down to something close to the truly-matching set.