Repository navigation
Commit a95806f
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
- datafusion
- core/tests/physical_optimizer
- physical-plan/src/joins/hash_join
- sqllogictest/test_files
0 commit comments