adriangb opened a new pull request, #24238:
URL: https://github.com/apache/datafusion/pull/24238
## Which issue does this PR close?
<!-- No existing issue covers this specific gap; filing the PR as a draft to
discuss whether it is worth pursuing. -->
- Closes #.
Related: #20195 (dynamic filtering on partitioned data from a file source),
#24095 (A/B benchmark for dynamic filtering on range-partitioned hash joins).
## Rationale for this change
`datafusion/pruning` has no handling for `CaseExpr`. When a predicate is (or
contains) a `CASE`, `build_predicate_expression` falls through to
`ConstantUnhandledPredicateHook`, which rewrites it to `lit(true)` — i.e. the
predicate contributes **nothing** to container pruning.
That matters because dynamic filters pushed down from a **hash-partitioned**
join arrive at the scan wrapped in a partition switch, one arm per partition.
This is a real plan from TPC-H q18 at `target_partitions=12` (`dfbench
--debug`, `orders` scan):
```
DynamicFilter [ CASE hash_repartition % 12
WHEN 0 THEN o_orderkey@0 >= 857959 AND o_orderkey@0 <= 4290656 AND
o_orderkey@0 IN (SET) (...)
WHEN 1 THEN o_orderkey@0 >= 6882 AND o_orderkey@0 <= 5832321 AND
o_orderkey@0 IN (SET) (...)
...
ELSE false END ]
```
On `main` this whole thing is invisible to pruning: the `orders` scan has
**no `pruning_predicate` at all**.
## What changes are included in this PR?
A `CaseExpr` arm in `build_predicate_expression`
(`datafusion/pruning/src/pruning_predicate.rs`) that rewrites a `CASE` used as
a predicate into the **disjunction** of its arms:
```text
CASE [expr] WHEN v1 THEN t1 WHEN v2 THEN t2 ELSE e END
=> prune(t1) OR prune(t2) OR prune(e)
```
The `WHEN` values are deliberately dropped. A container (row group, file,
...) can only be pruned if *no* row in it can pass, and a container may hold
rows from any partition, so the arms must be OR'd. Dropping the `WHEN`s only
weakens the predicate — container pruning is inherently a relaxation, so this
is sound.
Details:
* A missing `ELSE` is an implicit `NULL`, which never passes a filter, so it
contributes nothing (it must **not** become `true`).
* An arm that is statically `false` (empty partitions are emitted as
`lit(false)`) drops out.
* An arm that cannot be rewritten becomes `true` via the unhandled hook,
making the whole disjunction `true` — no pruning, never a wrong prune.
* If every arm drops out the result is `false` and all containers are pruned.
## Are these changes tested?
Yes — 7 new unit tests in `datafusion/pruning/src/pruning_predicate.rs`
covering both `CASE` shapes (with and without a base expression), a
missing/`NULL` `ELSE`, `false` arms dropping out, an all-`false` `CASE` pruning
everything, an unhandled arm degrading to `true`, and an end-to-end prune with
the partitioned-ranges shape a hash-partitioned dynamic filter actually
produces.
`cargo test -p datafusion-pruning --lib` → 96 passed. Full `sqllogictest`
suite → 502/502 files, no `.slt` changes needed. `cargo fmt --all --check` and
clippy with the CI feature set are clean.
## Are there any user-facing changes?
No API change. The only user-visible effect is that scans behind a `CASE`
predicate may now prune containers. **Please read the measurements below before
judging this worth merging — the honest summary is that the win is narrow and
there are costs.**
---
## Measurements
TPC-H SF=1, parquet, 12 physical cores, `target_partitions=12`. Both
binaries built from the **same worktree and the same target dir** (build change
→ copy binary aside → revert the file → rebuild → copy aside; the two binaries
were asserted to differ). 12 rounds × `--iterations 5`, median per round,
**ordering counterbalanced within rounds** (change-first on odd rounds,
baseline-first on even). q1 and q6 are **controls**: they have no joins and no
dynamic filters, so this change cannot affect them, and their measured delta is
the noise floor.
Positive % = the change is slower.
| query | base ms | case ms | order A,B | order B,A | pooled | IQR | verdict
|
|---|---|---|---|---|---|---|---|
| **q1 (control)** | 34.1 | 35.0 | +2.18% | +2.26% | **+2.26%** | [+1.40,
+3.61] | noise floor |
| **q6 (control)** | 13.2 | 12.8 | −0.48% | −5.61% | **−3.60%** | [−5.76,
+0.49] | noise floor |
| q3 | 22.3 | 23.1 | +0.77% | +6.38% | +3.88% | [+0.10, +8.70] | not
established (order-dominated) |
| q5 | 29.0 | 29.9 | +2.75% | +6.11% | +3.52% | [+2.61, +7.57] | within
noise floor |
| q7 | 32.5 | 33.5 | +4.41% | +1.74% | +3.57% | [+0.53, +5.29] | within
noise floor |
| q8 | 28.3 | 28.7 | +1.25% | −0.40% | −0.34% | [−1.60, +4.36] | within
noise floor |
| q9 | 35.4 | 35.9 | +1.91% | +2.00% | +1.91% | [+1.04, +3.35] | within
noise floor |
| q12 | 20.5 | 20.8 | +1.55% | +1.35% | +1.39% | [+0.86, +4.32] | within
noise floor |
| q17 | 54.1 | 55.2 | +2.26% | +0.62% | +1.38% | [+0.14, +5.73] | within
noise floor |
| **q18** | 51.7 | 46.2 | **−9.92%** | **−10.12%** | **−9.92%** | [−13.77,
−6.46] | **real win** |
| q19 | 23.3 | 23.2 | −2.55% | +2.19% | +0.34% | [−2.37, +3.11] | within
noise floor |
| q20 | 21.0 | 22.0 | +5.00% | +5.61% | +5.35% | [+4.24, +6.41] | real
regression |
| q21 | 42.4 | 42.5 | +1.50% | +2.28% | +1.82% | [+1.19, +3.61] | within
noise floor |
**The control floor is ±3.6%.** Note that control q1 shows a
*sign-consistent* +2.26% across both orderings for a change that provably
cannot affect it — so there is a systematic build/code-layout bias of about +2%
on top of run-to-run variance. Nothing in the table below ~3.6% should be read
as an effect of this change, and the earlier numbers I had on this branch (a
claimed +1–5% spread of regressions on q7/q9/q12/q19/q3/q5/q21) do **not**
survive this protocol.
What survives:
* **q18: −9.9%**, reproduced in both orderings independently (−9.92% /
−10.12%), roughly 3× the control floor.
* **q20: +5.35%**, sign-consistent in both orderings with a tight IQR. Real,
though only ~1.5× the floor.
* **q3: +3.88% pooled, but +0.77% vs +6.38% depending on ordering** — that
is an ordering artifact, not an established regression.
### Mechanical evidence for q18 (this is the part timing noise cannot fake)
`dfbench --debug`, TPC-H q18, the `orders` scan:
| | `pruning_predicate` | row groups | `bytes_scanned` |
|---|---|---|---|
| main | **absent** | 16 → 16 matched | **30.19 MB** |
| this PR | present | 16 → **15** matched | **23.65 MB** |
A row group is pruned and 6.5 MB less is read. That is the whole win.
I also diffed `bytes_scanned` and row-group counts for **every** scan in all
13 queries above:
> **q18 is the only query in the set where the change alters what is read at
all.** For q1, q3, q5, q6, q7, q8, q9, q12, q17, q19, q20 and q21 the plans
scan byte-identical data and prune identical row-group counts on both builds.
So for everything except q18 this change is pure cost with zero benefit, and
q20's +5.35% is that cost showing up above the noise.
### Why the effect is nil for most hash-partitioned joins
The q18 `orders` scan carries *two* dynamic filters. The one on `o_custkey`
is useless, and it shows exactly why:
```
WHEN 0 THEN o_custkey >= 20 AND o_custkey <= 149989
WHEN 1 THEN o_custkey >= 1 AND o_custkey <= 149999
WHEN 2 THEN o_custkey >= 13 AND o_custkey <= 149996
... (12 arms, domain is [1, 150000])
```
Hash partitioning **scatters** keys, so on a dense key column every
partition's min/max converges on the full domain, and the OR of 12 near-full
ranges *is* the full domain. This is not a weakness of the rewrite — no
min/max-based rewrite can do better on this input.
q18 wins only because its *other* dynamic filter comes from a semi-join
against `... group by l_orderkey having sum(l_quantity) > 300`, whose build
side is tiny and sparse. There each arm is genuinely narrow and their union
still excludes a row group.
**The realistic conclusion: this helps selective semi-joins / small build
sides, and does nothing for hash-partitioned equi-joins on dense keys.**
### Known follow-up (the lever, if the cost needs fixing)
The generated predicate repeats the null-count guard twice per arm:
```
o_custkey_null_count != row_count AND o_custkey_max >= 20 AND
o_custkey_null_count != row_count AND o_custkey_min <= 149989 OR ...
(×12)
```
That is ~4 redundant subterms per arm, and the arm count scales with
`target_partitions` — so the predicate this builds grows linearly with core
count while its selectivity does not. **That redundancy, not the OR structure
itself, is the lever** if the q20-style regression needs to be addressed;
deduplicating the guards (or hoisting them out of the disjunction) should
remove most of the added evaluation cost without changing what gets pruned.
Filed as a draft because the cost/benefit above is genuinely marginal and I
would like input on whether it is worth carrying.
--
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]
