Skip to content

Commit a95806f

Browse files
jayzhan211Omega359
authored andcommitted
feat: transfer parent and dynamic filters across HashJoinExec equi-join keys (inner and semi joins) (apache#25255)
## Which issue does this PR close? No dedicated issue yet. Related: apache#18290, apache#19858, apache#7955 (dynamic filter pushdown follow-ups). ## Rationale for this change ### What "transferring a filter across join keys" means For an inner or semi join `ON a.k = b.k`, every output row has `a.k = b.k`. So a filter that only touches `a.k` (say `a.k IN (1, 3)`) is also true of `b.k` for every row that can match. Today `HashJoinExec` routes a parent filter only to the side that owns its columns, so that filter reaches `a` and never `b`. With this PR the join also pushes `b.k IN (1, 3)` to `b`. Static predicates already get this at the logical level (equality inference in `push_down_filter`). Dynamic filters do not exist there, and they are the ones that matter: the dynamic filter of a join above is a parent filter for the joins below it. Before, with `dim` (small, filtered) joined to `mid`, and `mid` joined to `fact`: ```text HashJoinExec on=[(d_key, m_key)] build: dim, probe: (mid ⋈ fact) ├── DataSourceExec dim └── HashJoinExec on=[(m_key, f_key)] build: mid, probe: fact ├── DataSourceExec mid predicate=DynamicFilter[d_key from dim] <- direct: m_key is a mid column └── DataSourceExec fact predicate=DynamicFilter[m_key from mid] <- only the lower join's own filter ``` After: ```text HashJoinExec on=[(d_key, m_key)] ├── DataSourceExec dim └── HashJoinExec on=[(m_key, f_key)] ├── DataSourceExec mid predicate=DynamicFilter[d_key from dim] └── DataSourceExec fact predicate=DynamicFilter[m_key from mid] AND DynamicFilter[d_key from dim, rewritten over f_key] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ transferred across m_key = f_key ``` The transferred copy is the same `DynamicFilterPhysicalExpr` with its key columns remapped, so it is populated when `dim` finishes building and prunes `fact` at the scan (file / row-group / page pruning always, row-level with `pushdown_filters=true`). Because `fact` is now pruned before the lower join builds, the lower join's own filter tightens too. Why the lower join's own filter is not enough on its own: - it is a hash-table lookup once the lower build side exceeds `hash_join_inlist_pushdown_max_size` / `_max_distinct_values`, which cannot prune files, row groups or pages, while the transferred filter carries the small table's min/max bounds and IN list; - it is absent when the lower join creates none (Partitioned mode without routing, `preserve_file_partitions`, null-aware joins with nullable build keys, a build-side scan that does not accept filters); - it can only be as tight as its own build input, whereas the transferred filter prunes that input first (see TPC-H Q5 below, where `customer` had no dynamic filter at all before). ### Semi-join routing bug fixed on the way The same mechanism replaces the semi-join special case in `gather_filters_for_pushdown`. That code added the key's *output index* to the non-output side's allowed set and then let `FilterRemapper::try_remap` map the column to that side by *name*. Two failure modes followed when the keys were named differently: - the name does not exist on the other side: the remap fails and nothing is pushed there (a missed optimisation); - the name exists on the other side but is not the key: the filter is pushed onto that unrelated column, and because a child accepted it the `FilterExec` above the join is removed. That is a wrong-result bug. Example: `LeftSemi` on `left.k = right.j` where `right` also has a non-key column `k`. A parent filter `k = 'x'` reached the right scan as `k@2 = 'x'`; with this PR it is `j@0 = 'x'`. The `RightSemi` branch had the mirror-image bug. The existing `test_hashjoin_parent_filter_pushdown_semi_anti_join` did not catch either, because both keys in it are named `k`. The transfer rewrites over the key *expression* on the other side, so column names no longer matter. ### Benchmarks **TL;DR:** JOB total 3 % faster with row-level parquet pushdown (16a 2.3x, 16c/16d 1.6x, 33a/33c 1.25x), TPC-H SF10 Q5 1.3x, everything else within noise, no reproducible regression. Details below. M4 Pro (12 cores / 24 GB), release binaries built in separate target dirs, sides alternated per round, per-query minimum over all iterations. `default` = stock parquet config (dynamic filters prune files / row groups / pages only); `pushdown` = `datafusion.execution.parquet.pushdown_filters=true`. | suite | mode | geomean ratio | total time | |---|---|---|---| | JOB (113 q), 2 x 5 iter | default | 0.997 | 51.07 s -> 50.95 s | | JOB (113 q), 2 x 5 iter | pushdown | 0.982 | 26.48 s -> 25.66 s | | TPC-H SF10 (22 q), 2 x 3 iter | default | 1.004 | 5.19 s -> 5.24 s (no query outside 5 %) | | TPC-H SF10 (22 q), 2 x 3 iter | pushdown | 0.996 | 6.49 s -> 6.42 s | Queries outside +/-5 % (pushdown mode, ms): | query | before | after | ratio | |---|---|---|---| | JOB 16a | 723 | 321 | 0.44 | | JOB 16d | 722 | 439 | 0.61 | | JOB 16c | 719 | 464 | 0.64 | | JOB 33a | 134 | 105 | 0.78 | | JOB 33c | 143 | 116 | 0.81 | | TPC-H Q5 | 416 | 324 | 0.78 | | JOB 18a / 17e / 17f | 208-329 | 221-349 | 1.06-1.07 (within run-to-run spread) | | JOB 16b | 874 | 990 | 1.13 (not reproducible: identical scan predicates on both binaries; interleaved re-timing gives before 922-1642 ms vs after 874-1144 ms) | Where the time goes, from per-scan `EXPLAIN ANALYZE` metrics in pushdown mode. JOB 16a: the top join builds on the filtered `title` (68 K rows) and its dynamic filter lands on `ci.movie_id`, the build-side key of the join below. Transferred across that join's keys it now also reaches two scans: | scan | dynamic filters before -> after | output rows before -> after | |---|---|---| | movie_companies | 1 -> 2 | 1.15 M -> 7.6 K | | cast_info | 2 -> 3 | 6.38 M -> 45 K | TPC-H SF10 Q5: the 5-row `nation` filter reaches `customer` through the key equivalence, which previously received no dynamic filter, and the pruning cascades down the join chain: | scan | dynamic filters before -> after | output rows before -> after | |---|---|---| | customer | 0 -> 1 | 1.50 M -> 300 K | | orders | 1 -> 1 | 2.28 M -> 457 K | | lineitem | 1 -> 1 | 9.10 M -> 1.83 M | Cost side: the transferred copy is rewritten over the target side's key expression, so where the join key is a `CAST` it pays a cast per row. The bounds builder also emits duplicated bound pairs when several key pairs share one column (pre-existing, visible in the before plans too, just more often now). ## What changes are included in this PR? - `HashJoinExec::gather_filters_for_pushdown`: after the plain column-based routing, every parent filter whose columns are all plain `Column` join keys of one side is rewritten over the other side's key expressions and marked supported for that child. Inner, LeftSemi and RightSemi only: outer, anti and mark joins also emit unmatched rows, so the transferred filter would not be exact there and `if_any` could wrongly drop the parent filter. Outer joins would need "prune-only" semantics and are left as a follow-up. - A `DynamicFilterPhysicalExpr` is rewritten through `with_new_children`, so the transferred copy shares the original's state and keeps tracking the build side. - Removed the name-based semi-join routing, now covered by the general transfer. This fixes the wrong-column pushdown described above. - A transfer only targets a side that `lr_is_preserved` permits, the same gate as the plain column routing (a no-op for the three permitted join types today, but it couples the two functions). Join keys are `debug_assert`ed to have equal data types, since the planner coerces them and `try_new` does not check. ## What is the testing strategy for this PR? - `test_hashjoin_parent_filter_transferred_across_join_keys`: key names differ; key filters land on both scans, a non-key filter stays on its side. - `test_hashjoin_parent_filter_transfer_semi_join_different_key_names` and its `RightSemi` variant: the case the old name-based routing missed (nothing reached the non-output scan). - `test_hashjoin_parent_filter_transfer_semi_join_key_name_shadowed_by_non_key`: regression test for the wrong-column pushdown, `LeftSemi` and `RightSemi`. - `test_hashjoin_parent_filter_transfer_uses_first_on_pair`: `ON k = x AND k = y` transfers over the first pair. - `test_hashjoin_parent_filter_transfer_cast_key_with_projection`: a `CAST` key with a projection that puts the other side's key at the same output index as the cast's inner column. The rewrite must not descend into the substituted expression, or it would loop forever. - `test_hashjoin_dynamic_filter_transferred_through_nested_join`: an upper join's dynamic filter reaches the lower probe scan. The lower build scan rejects filters, so the lower join's own filter still lists all four keys and the two pruned rows are attributable to the transfer alone (checked via scan metrics). - `join_dynamic_filter_transfer.slt`: SQL plan shape and results. - Two existing snapshots changed only by a build-key filter now also appearing on the probe scan. Full sqllogictest suite, physical-plan join unit tests, `cargo fmt` and `clippy -D warnings` pass. ## Are there any user-facing changes? No new configuration. `EXPLAIN` may now show a parent or dynamic filter on both scans of an inner or semi join where it previously appeared on one.
1 parent 1ffb342 commit a95806f

3 files changed

Lines changed: 1025 additions & 60 deletions

File tree

0 commit comments

Comments
 (0)