mattp5657 opened a new pull request, #24796:
URL: https://github.com/apache/datafusion/pull/24796
## Which issue does this PR close?
Closes #24280.
## Rationale for this change
`wrap_null_count_check_expr` attaches a null-count guard
(`col_null_count != row_count`) to every rewritten leaf comparison
independently, so a predicate that lowers to more than one leaf on the
same column (e.g. a `BETWEEN`-shaped range) duplicates its guard:
```
(col_null_count != row_count AND col_min <= hi)
AND
(col_null_count != row_count AND col_max >= lo)
```
Both copies get evaluated against every row group's stats at prune time.
Under three-valued logic, `(G AND P) AND (G AND Q) == G AND P AND Q` and
`(G AND P) OR (G AND Q) == G AND (P OR Q)`, so the guard can be hoisted
and evaluated once instead of once per leaf — same pruning decision,
less redundant work to reach it.
## What changes are included in this PR?
A `factor_common_guards` pass, run once in `PruningPredicateBuilder::
try_build`, applying that identity to `AND`/`OR` nodes:
- `flatten_chain_known_non_volatile` iteratively flattens nested
same-operator chains (no recursion, no stack-overflow risk on a long
chain).
- `factor_and` dedupes structurally-identical arms via `HashSet`.
- `factor_or` hoists whatever conjunct is common to *every* arm of an
`OR`. Only hoists over the full arm set, not subsets — e.g. `(g AND
a=1) OR (g AND a=2) OR (g AND a=3) OR b IS NULL` gets no benefit even
though 3 of 4 arms share `g` — never incorrect, just a smaller win.
- `fold_and`/`fold_or` rebuild the tree, short-circuiting on an
always-true/false arm.
Skipped entirely if any part of the expression is volatile
(`is_volatile`), since the identity only holds for deterministic
predicates. Recursion is capped at `MAX_FACTOR_ALTERNATION_DEPTH = 32`
operator alternations: `Arc<dyn PhysicalExpr>`'s `Eq`/`Hash` are fully
structural with no pointer-identity shortcut, so hashing a subtree of
size `S` costs `O(S)`, and recursing per alternation on a chain of depth
`N` is `O(N^2)` worst case (observed worse in practice on a synthetic
deep tree). Past the cap, the rest is left unfactored — always correct,
same fallback already used for opaque non-`BinaryExpr` leaves.
## Are these changes tested?
Yes — `cargo test -p datafusion-pruning --lib pruning_predicate` passes
115 tests (1 unrelated filtered out), including new coverage for: the
volatile-expression bailout, an 8,000-arm flatten, `OR`-hoisting with
multiple/compound common conjuncts, a 500-level alternating `AND`/`OR`
tree (depth cap, no stack overflow), and a new `i IN (11, NULL)`
equivalence case.
9 `.slt` golden files needed re-recording since the factored predicate's
`EXPLAIN` text differs (guard printed once, not twice) with no change in
returned rows: `clickbench`, `explain_analyze`, `limit_pruning`,
`parquet_filter_pushdown`, `projection_pushdown`,
`push_down_filter_parquet`, `push_down_filter_regression`,
`range_partitioning`, `sort_pushdown`.
## Are there any user-facing changes?
No behavioral changes — `EXPLAIN`/`EXPLAIN ANALYZE` text changes (guard
printed once instead of twice), which is why the `.slt` files above
needed updating. No change to query results, pruning decisions, or plan
shape.
## Measurements
### TPC-H: no measurable effect on query time
TPC-H SF=1, parquet, 8 cores, `target_partitions=8`, two binaries from
the same worktree (`cmp`-verified to differ), 12 counterbalanced rounds
x 5 iterations, at two row-group scales on `lineitem` (53 and 3,840, a
72x spread). Positive % means the change is slower; "order-dominated"
means the two counterbalanced orderings disagreed enough that no
conclusion is drawn either way, reported honestly as unresolved rather
than averaged into a false-precision number.
**No measurable effect on wall-clock query time, in either direction, at
either scale.** Control floor (q1/q13/q18, byte-identical plans on both
binaries) is ~0.8% in both runs; nothing clears 1.5x that floor
sign-consistently across both counterbalanced orderings, except one
marginal hit (default-scale q4, +1.38%) that fails to reproduce at the
other scale (-0.20%) — exactly what noise looks like across 22 queries
tested per run, not a regression.
**Run 1: default row-group size (53 row groups), control floor 0.81%**
```
query | base ms | case ms | order A,B | order B,A | pooled |
IQR | verdict
-----------------------------------------------------------------------------------------------
1 | 82.48 | 83.42 | -0.03% | +1.17% | +0.57% | [ -1.99,
+2.83] | noise floor (control)
2 | 20.42 | 20.35 | -1.16% | -0.25% | -0.70% | [ -2.27,
+0.51] | order-dominated
3 | 50.79 | 50.60 | +1.24% | -1.28% | -0.02% | [ -2.88,
+1.94] | order-dominated
4 | 25.23 | 25.34 | +1.94% | +0.81% | +1.38% | [ -0.40,
+3.05] | real regression (does not reproduce, see Run 2)
5 | 71.53 | 72.48 | +1.02% | +0.06% | +0.54% | [ -0.63,
+1.62] | order-dominated
6 | 27.97 | 28.12 | +0.73% | -0.24% | +0.24% | [ -2.02,
+2.71] | order-dominated
7 | 85.41 | 85.36 | -0.27% | +0.02% | -0.13% | [ -1.73,
+1.36] | order-dominated
8 | 63.30 | 63.80 | +0.58% | +0.29% | +0.44% | [ -1.33,
+1.50] | within noise floor
9 | 88.48 | 88.57 | +0.17% | +0.21% | +0.19% | [ -0.49,
+0.87] | within noise floor
10 | 65.28 | 65.49 | +0.64% | +0.03% | +0.33% | [ -0.53,
+1.29] | order-dominated
11 | 14.77 | 14.85 | +2.93% | -1.33% | +0.80% | [ -1.23,
+3.65] | order-dominated
12 | 39.93 | 39.64 | -0.47% | -1.21% | -0.84% | [ -2.42,
+0.87] | within noise floor
13 | 50.98 | 50.84 | -3.19% | +1.57% | -0.81% | [ -4.02,
+2.46] | noise floor (control)
14 | 36.82 | 36.81 | +0.10% | +0.36% | +0.23% | [ -0.89,
+1.27] | within noise floor
15 | 47.68 | 47.79 | +1.21% | +0.30% | +0.75% | [ -0.54,
+1.66] | order-dominated
16 | 15.31 | 15.56 | +2.57% | -0.02% | +1.27% | [ -0.69,
+3.24] | order-dominated
17 | 144.21 | 144.42 | -0.32% | +0.12% | -0.10% | [ -0.91,
+0.78] | order-dominated
18 | 129.76 | 129.53 | +0.06% | -0.58% | -0.26% | [ -0.72,
+0.88] | noise floor (control)
19 | 54.06 | 53.62 | -1.18% | +0.43% | -0.37% | [ -2.30,
+0.87] | order-dominated
20 | 49.61 | 49.67 | -0.85% | +0.78% | -0.04% | [ -0.78,
+0.78] | order-dominated
21 | 98.37 | 99.13 | -0.22% | +0.89% | +0.33% | [ -0.38,
+1.32] | order-dominated
22 | 14.27 | 14.18 | -2.11% | +1.51% | -0.30% | [ -3.24,
+1.51] | order-dominated
```
**Run 2: 3,840 row groups on `lineitem` (72x the default), independent
re-run, control floor 0.82%**
```
query | base ms | case ms | order A,B | order B,A | pooled |
IQR | verdict
-----------------------------------------------------------------------------------------------
1 | 144.93 | 146.19 | +0.74% | +0.91% | +0.82% | [ -0.75,
+2.95] | noise floor (control)
2 | 43.48 | 43.43 | +0.36% | +0.07% | +0.22% | [ -0.90,
+0.76] | order-dominated
3 | 164.20 | 163.97 | +0.84% | -0.31% | +0.27% | [ -0.48,
+0.64] | order-dominated
4 | 135.20 | 134.81 | -0.02% | -0.38% | -0.20% | [ -1.03,
+1.13] | order-dominated (Run 1's hit does not reproduce)
5 | 132.66 | 132.11 | -1.20% | -0.60% | -0.90% | [ -1.04,
+0.75] | within noise floor
6 | 73.27 | 73.35 | -1.71% | +0.79% | -0.46% | [ -0.73,
+1.33] | order-dominated
7 | 211.58 | 210.36 | +12.73% | -1.12% | +5.81% | [ -1.45,
+0.20] | order-dominated
8 | 194.01 | 193.51 | -1.32% | -0.08% | -0.70% | [ -1.12,
+0.96] | order-dominated
9 | 229.19 | 231.80 | +5.31% | -1.18% | +2.07% | [ -1.13,
+2.31] | order-dominated
10 | 177.27 | 176.67 | -1.33% | -0.40% | -0.86% | [ -1.53,
+0.39] | within noise floor
11 | 38.01 | 37.85 | -1.19% | +0.39% | -0.40% | [ -1.48,
+0.31] | order-dominated
12 | 157.96 | 159.01 | +0.90% | +0.39% | +0.64% | [ -0.05,
+1.48] | within noise floor
13 | 65.68 | 65.87 | -0.69% | +0.62% | -0.03% | [ -1.20,
+1.24] | noise floor (control)
14 | 80.45 | 80.94 | +0.23% | +0.35% | +0.29% | [ -0.47,
+1.05] | within noise floor
15 | 152.98 | 152.91 | +0.37% | -0.15% | +0.11% | [ -0.46,
+1.03] | order-dominated
16 | 27.57 | 27.68 | +0.04% | +0.55% | +0.29% | [ -0.43,
+0.91] | order-dominated
17 | 217.82 | 217.82 | +0.60% | -0.49% | +0.06% | [ -0.93,
+1.13] | order-dominated
18 | 210.28 | 210.08 | +1.48% | -1.64% | -0.08% | [ -0.82,
+1.59] | noise floor (control)
19 | 109.85 | 109.54 | -0.63% | -0.42% | -0.52% | [ -2.35,
+1.11] | within noise floor
20 | 172.17 | 171.21 | -0.04% | -0.73% | -0.38% | [ -1.15,
+0.49] | order-dominated
21 | 434.93 | 434.40 | +0.45% | -0.30% | +0.08% | [ -0.44,
+0.68] | order-dominated
22 | 25.98 | 25.94 | +0.01% | +0.10% | +0.06% | [ -0.58,
+0.42] | order-dominated
```
**Mechanical evidence** (`dfbench --debug`, q6's `lineitem` scan): the
duplicated `l_shipdate`/`l_discount` null-count guards each collapse
from 2 occurrences to 1, at both row-group scales, with row-groups-matched
and bytes-scanned byte-identical before and after — the redundant
comparisons this PR removes are real and confirmed structurally.
### Microbenchmark: a real, tiny improvement
Trying to measure the eval-time saving directly from TPC-H's own
`statistics_eval_time` metric didn't work — it's contaminated by an
unrelated timing sensitivity in hash-join dynamic-filter resolution that
swamps a signal this small (full investigation in
`.ai/plans/benchmark-writeup-final.md`). The right tool for "how much
does this one function save" is a microbenchmark, not a whole-query
measurement: `benchmarks/benches/pruning_guard_dedup.rs` (criterion)
builds the same predicate with and without `factor_common_guards`, in
one process, and calls `PruningPredicate::prune` against synthetic
container stats directly — no parquet I/O, no joins, no dynamic filters,
nothing else that could confound it.
Result, on a q6-shaped predicate (2 guards duplicated, 1 not — 5 guard
occurrences before factoring, 3 after):
```
containers | unfactored prune | factored prune | saving
--------------------------------------------------------
53 | 4.665us | 4.337us | 0.33us
768 | 8.487us | 7.915us | 0.57us
3,840 | 26.238us | 24.401us | 1.84us
```
Non-overlapping confidence intervals at every size — this is a real,
reproducible saving, and it scales up with container count exactly as
the mechanism predicts. It's also genuinely tiny: microseconds, against
individual query times of tens to hundreds of milliseconds. That's why
the TPC-H wall-clock benchmark above can't see it in either direction —
it's not that there's no effect, it's that the effect is real and far
too small to matter at query scale.
--
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]
