hhhizzz opened a new pull request, #23934:
URL: https://github.com/apache/datafusion/pull/23934
## Which issue does this PR close?
- Closes #23933.
## Rationale for this change
HashJoin dynamic filters normally combine inclusive min/max bounds with exact
membership:
```text
min <= probe_key
AND probe_key <= max
AND probe_key IN (build_keys)
```
Keeping both is useful for a gapped build domain: bounds provide cheap
short-circuiting and statistics pruning, while membership removes values in
the gaps. For a single-column integer domain, however, membership is exactly
equivalent to the bounds when:
```text
distinct_key_count == max - min + 1
```
The distinct build keys are a subset of the inclusive `[min, max]` integer
interval. If the two sets also have the same cardinality, they are equal.
Evaluating an `InListExpr` or `HashTableLookupExpr` after that proof adds
per-row CPU cost without rejecting any additional probe rows.
This PR canonicalizes that exact case to bounds only. It deliberately keeps
the bounds for their pruning and short-circuit value, and retains the
existing
`bounds AND membership` form whenever equivalence cannot be proven.
This differs from #23701: that PR proposes skipping membership based on
filter
placement when `pushdown_filters=false`. This change is based on domain
equivalence and remains applicable when Arrow `RowFilter` pushdown is
enabled.
## What changes are included in this PR?
- Carry the build hash map's existing distinct-key count with the `InList`
pushdown strategy; map-backed strategies reuse
`Map::num_of_distinct_key()`.
- For a single, same-typed integer bound, compare the inclusive range
cardinality with the distinct-key count using a widened `u128` comparison.
- Skip construction of the redundant `InListExpr` or
`HashTableLookupExpr` after the proof succeeds, while preserving the bounds
predicate.
- Apply the same check to `CollectLeft` filters and to each reported
`Partitioned` filter branch. The count and bounds always describe the same
build-key set.
- Add `dynamic_filter_membership_elided_count`, incremented once for each
membership predicate omitted at finalization, so the optimization is
visible
in execution metrics.
- Fail closed for gapped domains, multiple join keys, non-integer or
mismatched bound types, missing or reversed bounds, and ranges whose
cardinality cannot be represented safely.
There is no additional scan or deduplication pass, no new configuration, no
Arrow dependency change, and no public API change.
## Are these changes tested?
Yes. Focused unit coverage verifies that:
- contiguous and duplicate-containing `InList` inputs produce bounds only;
- gapped `InList` inputs retain membership;
- contiguous map-backed (`ArrayMap`) inputs omit the resulting
`HashTableLookupExpr`;
- gapped map-backed (`ArrayMap`) inputs retain the resulting
`HashTableLookupExpr`;
- signed ranges crossing zero are handled;
- multi-column, non-integer, mismatched-type, and extreme ranges fail closed;
- the elision metric increments only when the proof succeeds;
- existing partitioned CASE and cancellation composition tests continue to
pass.
The following checks pass:
```text
cargo fmt --all -- --check
cargo test -p datafusion-physical-plan
joins::hash_join::shared_bounds::tests --lib
```
The focused test run completed with 13 passed and 0 failed.
### End-to-end benchmark
I compared the unchanged baseline with this patch on TPC-DS SF10, all 99
queries, using 10 alternating release rounds. Both arms used the same clean
Arrow commit and enabled Parquet pushdown filters, filter reordering, and
pruning. All queries completed successfully.
| Component | Baseline | Candidate |
| --- | --- | --- |
| DataFusion | `f34a676302e2320526172705503a5ac8222804ea` |
`3a4c7b3f1ad3110d74e0a4fd6935a45b7da434f0` (at measurement time) |
| Arrow | `b8b59fb38dcc5930d7a087bc3e17bd955a6c9f21` |
`b8b59fb38dcc5930d7a087bc3e17bd955a6c9f21` |
Ratios are candidate/baseline; values below 1 favor the candidate.
| Metric | Ratio | 95% CI | Elapsed-time change |
| --- | ---: | ---: | ---: |
| Suite total | 0.974989 | [0.961237, 0.986387] | -2.50% |
| Equal-query geomean | 0.970103 | [0.962453, 0.978634] | -2.99% |
| q39 | 0.953432 | [0.943056, 0.963989] | -4.66% |
No query triggered the predeclared median or p95
relative-plus-absolute regression guards. The largest relative slowdown was
q20, with a ratio of `1.245455` (95% CI `[1.117048, 1.400882]`) and a median
absolute increase of `7.802 ms` (95% CI `[3.210, 15.901]`). Its absolute
lower
confidence bound remained below the guard's `10 ms` threshold. The benchmark
is end-to-end evidence for the patch; the runner did not collect per-query
membership-elision metric hits, so this is not a claim that every TPC-DS
query
exercises the optimized path.
## Are there any user-facing changes?
There are no public API or configuration changes. The rewrite is
semantics-preserving. For a qualifying contiguous integer build domain, the
generated dynamic filter is displayed as bounds only, and execution metrics
may include `dynamic_filter_membership_elided_count`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
