You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "adriangb (via GitHub)" <gi...@apache.org> on 2026/09/07 17:01:32 UTC
[I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
adriangb opened a new issue, #25035:
URL: https://github.com/apache/datafusion/issues/25035
### Is your feature request related to a problem or challenge?
`BinaryExpr::evaluate` (`datafusion/physical-expr/src/expressions/binary.rs:542`)
evaluates its LHS, then `check_short_circuit` (`binary.rs:1188`) returns
`PreSelection` for `AND` when the LHS boolean array has no nulls and
`true_count / len <= PRE_SELECTION_THRESHOLD` (0.2, `binary.rs:1167`). Pre-selection
does `filter_record_batch(batch, &mask)` on the original batch (`binary.rs:562`),
evaluates the RHS on the survivors, and `pre_selection_scatter`s back to full length
(`binary.rs:1307`).
Conjunctions are built **left-deep** — `datafusion_expr::utils::conjunction` is
`reduce(Expr::and)` (`datafusion/expr/src/utils.rs:1296`),
`datafusion_physical_expr::utils::conjunction_opt` is a left fold
(`datafusion/physical-expr/src/utils/mod.rs:122`), and SQL's `AND` is
left-associative. So at each level the LHS is the **accumulated prefix**, not a
single conjunct. Two consequences:
1. **The threshold is tested against the wrong quantity.** With several
individually unselective conjuncts, no single conjunct is selective, but the
prefix multiplies below 20% partway down the chain. Pre-selection then fires to
save evaluating a couple of cheap comparisons on the remaining rows — a losing
trade.
2. **Left-nesting repeats the work.** Every level that trips the threshold
re-filters the *original* batch and scatters back to full length, instead of
compacting once and keeping survivors compacted. And `filter_record_batch` copies
**every column of the batch**, not just the ones the RHS reads, so the cost
scales with batch width.
Measured on `BinaryExpr` directly at `262936eef5` (8192-row batches, k conjuncts
`ci < cutoff` on independent Int32 columns, left-deep vs right-deep, median of 7
interleaved rounds). `fires` counts prefix levels below the threshold:
| k | per-conjunct pass rate | left-deep | right-deep | right/left | fires |
|---|---|---|---|---|---|
| 4 | 0.50 | 13.3 us | 5.0 us | 0.376 | 1 |
| 8 | 0.50 | 31.8 us | 10.9 us | 0.344 | 5 |
| 8 | 0.70 | 41.0 us | 10.8 us | 0.263 | 3 |
| 8 | 0.90 | 11.0 us | 10.8 us | 0.988 | 0 |
| 16 | 0.70 | 95.8 us | 24.4 us | 0.254 | 11 |
| 16 | 0.90 | 25.5 us | 24.6 us | 0.967 | 0 |
Every `fires = 0` row is within 4% of parity, so the two shapes are equivalent when
the threshold never trips.
Width amplifies it. Same 8 conjuncts, with unreferenced payload columns added to the
batch:
| extra columns | pass rate | left-deep | right-deep | right/left |
|---|---|---|---|---|
| 0 | 0.70 | 40.3 us | 11.1 us | 0.277 |
| 8 | 0.70 | 50.7 us | 11.0 us | 0.218 |
| 32 | 0.70 | 81.9 us | 11.3 us | 0.138 |
End to end this costs TPC-H Q06 — the canonical 4-conjunct `lineitem` scan filter —
about 17%.
(Noticed while working on runtime conjunct reordering in #22698; the problem above
is in stock DataFusion and independent of that PR.)
### Describe the solution you'd like
**Option A: build conjunctions right-deep.** Recommend against. Besides ~180
expected-output lines across ~30 `.slt` files, the InList merge rules at
`datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs:1888-1975` require
the two InLists to be direct siblings and would silently stop firing; proto's
linearized `operands` form reconstructs left-deep (`binary.rs:973`), so the shape
does not survive serialization; and it changes which rows a fallible conjunct sees
(`b <> 0 AND 1/b > 2`), a user-visible semantic change. (`split_conjunction` itself
is shape-agnostic in both crates, so that part would have been fine.)
**Option B: evaluate `AND` chains n-ary.** Keep the tree shape, but when evaluating
an `AND`, flatten the chain, evaluate conjuncts against a working batch, and compact
only when the accumulated mask crosses the threshold — what a right-deep tree would
give without changing the tree. EXPLAIN, proto and the simplifier rules are all
untouched. Three-valued logic is preserved by refusing to compact while the
accumulated mask has nulls, matching today's behaviour. `OR` is left alone.
This is how Velox evaluates conjunctions, and the point is worth making explicitly
because Velox is where the `time / (1 + n_in - n_out)` conjunct-ordering metric
comes from: that metric is applied to a *flat list* of conjuncts evaluated against a
*narrowing* row set, not to a binary tree. Verified against the paper and the
current source:
- **One n-ary node, flattened at compile time.** Pedreira et al., *Velox: Meta's
Unified Execution Engine*, PVLDB 15(12), 2022, §4.3.1 "Adaptive Conjunct
Reordering" (p. 3377): "AND(AND(AND(a, b), c), AND(d, e)) is flattened to a single
AND(a, b, c, d, e) node during compilation". In source, `ConjunctExpr`
(`velox/expression/ConjunctExpr.h`) takes a `std::vector<ExprPtr>&& inputs`;
`ExprCompiler.cpp` treats `and`/`or` as flattenable in `shouldFlatten` and calls
`expression::utils::flattenInput` (`velox/expression/ExprUtils.cpp`), which
recursively folds nested same-name calls into one input list.
- **Later conjuncts only see surviving rows.**
`ConjunctExpr::evalSpecialForm` (`ConjunctExpr.cpp`) evaluates each input with
`inputs_[inputOrder_[i]]->eval(*activeRows, ...)`, then `updateResult` removes
decided rows from `activeRows` and the loop exits when `countSelected()` reaches 0.
Velox passes the shrinking `SelectivityVector` *down* into the child rather than
copying the batch, so there is no filter-and-scatter at all; DataFusion's kernels
take whole arrays, so compacting once and keeping the survivors compacted is the
closest equivalent.
- **Three-valued logic is handled per row, without stopping evaluation on null.**
In `updateAnd` the drop set is `testFalse = ~testValue & testPresent` and only
`active &= ~testFalse` — a definite `false` retires the row; a `null` input flips a
so-far-`true` result to null but the row stays active, so a later `false` can
still decide it. That is the same rule option B needs (a null in the accumulated
mask must not be treated as eliminated).
- **Reordering is a separate concern layered on top.** `maybeReorderInputs` sorts
`inputOrder_` by `SelectivityInfo::timeToDropValue()`
(`velox/common/base/SelectivityInfo.h`: `timeClocks_ / (numIn_ - numOut_)`, with a
guard when nothing was dropped — the paper writes it as
`time / (1 + n_in - n_out)`), gated by `adaptiveFilterReorderingEnabled()`. The
n-ary, narrowing evaluation works with reordering off; it is the shape that makes
reordering meaningful, not the other way round.
DuckDB does the same thing: `ExpressionExecutor::Select` on a
`BoundConjunctionExpression` (`src/execution/expression_executor/execute_conjunction.cpp`)
walks the children in `permutation` order and, once rows are filtered out, switches
`current_sel = true_sel` so each subsequent child evaluates only the passing tuples;
its `AdaptiveFilter` (`src/execution/adaptive_filter.cpp`) reorders by randomized
adjacent swaps kept or reverted on measured runtime. I did not check ClickHouse.
**Option C: make the compaction decision cost-aware.** Option B alone is necessary
but not sufficient. With B, shape stops mattering (left/right parity within 0.4%),
but at 40 columns / 0.70 pass rate it still lands at 36.9 us against 11.3 us for a
tree that never compacts — B removes the *repeated* filtering but still performs one
unprofitable compaction, because the threshold cannot see that the remaining
conjuncts are cheap and the batch is wide. A complete fix needs B plus a decision
that weighs the filter and scatter against the RHS's actual cost and the batch
width.
### Reproducing
Micro-benchmark: an integration test in `datafusion/physical-expr/tests/` that builds
the same conjuncts as left-deep and right-deep `BinaryExpr` trees and times both
interleaved. Sweep k in {2,4,8,16}, per-conjunct pass rate in {0.5,0.7,0.9,0.99},
batch sizes {1024,8192}, plus unreferenced payload columns. The existing
`datafusion/physical-expr/benches/binary_op.rs` (`cargo bench --bench binary_op`,
`benchmark_binary_op_in_short_circuit`) already exercises this code path and would
be the natural home for a regression benchmark.
End to end:
```
cd benchmarks
../target/release/benchmark_runner tpch -i 5
../target/release/benchmark_runner predicate_eval -i 5
```
### Measured results
Prototype of option B behind an env switch so one binary runs both configurations;
6-8 interleaved A/B/A' rounds x 5 iterations, AC power, medians, warm-up iteration
dropped.
| suite | query | baseline | prototype | ratio | rounds faster | A/A drift |
|---|---|---|---|---|---|---|
| TPC-H SF1 | Q06 | 14.80 ms | 12.23 ms | 0.826 | 6/6 | 0.980 |
| TPC-H SF1 | all other 21 | | | 0.95-1.04 | coin flip | median 1.4% |
| predicate_eval 1M | cardinality_q33_k16 | 2.724 ms | 2.157 ms | 0.792 | 7/8 | 1.014 |
| predicate_eval 1M | all other 25 | | | 0.95-1.12 | coin flip | median 2.6% |
Q06 and cardinality_q33_k16 are the only results outside the noise floor. Both are
exactly the predicted shape: several conjuncts whose prefix crosses the threshold
partway down. Only queries whose runtime is dominated by a multi-conjunct filter move
at all; the micro-benchmark ratios are filter-evaluation-only numbers.
Correctness of the prototype: all 510 sqllogictest files pass, all
`datafusion-physical-expr` unit tests pass, and all 26 `predicate_eval` queries
validate against result CSVs persisted from unmodified main.
### Describe alternatives you've considered
Options A and C above.
### Additional context
Related but distinct: #15631 optimizes the short-circuit *check* itself
(`count_ones` versus testing for any set bit), not the quantity being tested.
Separately: `predicate_eval.benchmark.template` has no `result` directive, so
`--result-mode validate` currently verifies nothing for that suite.
Sources for the prior-art section: https://www.vldb.org/pvldb/vol15/p3372-pedreira.pdf
(§4.3.1), https://github.com/facebookincubator/velox (`velox/expression/ConjunctExpr.{h,cpp}`,
`velox/expression/ExprCompiler.cpp`, `velox/expression/ExprUtils.cpp`,
`velox/common/base/SelectivityInfo.h`), https://github.com/duckdb/duckdb
(`src/execution/expression_executor/execute_conjunction.cpp`,
`src/execution/adaptive_filter.cpp`); all read at `main` on 2026-09-07.
--
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: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
Posted by "Abhisheklearn12 (via GitHub)" <gi...@apache.org>.
Abhisheklearn12 commented on issue #25035:
URL: https://github.com/apache/datafusion/issues/25035#issuecomment-5844585930
@adriangb I opened a draft for this: #25771
It evaluates `AND` chains as one n-ary conjunction and only pre-selects before conjuncts that are expensive or can fail, so left- and right-deep trees now cost the same. TPC-H Q6, Q12 and Q19 are 9 to 17% faster at SF1 and SF10, and `cardinality_q33_k16` in `predicate_eval` is 2.4× faster. The full numbers are in the PR.
Two things I'd like your take on before marking it ready:
1. It removes the `AND` branch of `check_short_circuit` that #22698 edits and models with `and_rhs_evaluation`. Would you rather this land first, or #22698?
2. The contract is that an expensive or fallible conjunct never sees a row that nested evaluation would have skipped. Does that match what you'd expect?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
Posted by "Abhisheklearn12 (via GitHub)" <gi...@apache.org>.
Abhisheklearn12 commented on issue #25035:
URL: https://github.com/apache/datafusion/issues/25035#issuecomment-5580009917
take
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
Posted by "Abhisheklearn12 (via GitHub)" <gi...@apache.org>.
Abhisheklearn12 commented on issue #25035:
URL: https://github.com/apache/datafusion/issues/25035#issuecomment-5669281208
Sorry for the delayed follow-up, @adriangb, I was tied up with other work. I independently reproduced and traced the current evaluator at [`9082d6b10`](https://github.com/apache/datafusion/commit/9082d6b10c29b72d56bede3d8e353d9d61fde542).
The association-sensitive slowdown is real. Accumulated-prefix selectivity is useful, but insufficient as the sole trigger. Evidence points to node-local state plus policy: binary parents discard compact state, while the 20% rule omits bytes copied and remaining work. My measurements reproduce the qualitative result; absolute timings and ratios differ. I have not selected A/B/C, implemented B/C, or reproduced the reported TPC-H, `predicate_eval`, prototype, or 510-SLT results.
Benchmark: [immutable commit](https://github.com/Abhisheklearn12/datafusion/commit/290f57d24efe9cd3cb75bb78570cc68cd03cf988), SHA-256 `2f0338362241221bc8fbdf3f0cf96c913feb4307513ba167e80a0a6152fbd29c`. This benchmark commit is a reproducibility artifact only, not a proposed production change or PR.
### Reproduction and mechanism
The target evaluates eight ordered SplitMix64-salted `Int32 > 0` conjuncts over 8,192 rows at roughly 70%, with 32 unreferenced `Int64` payload columns. Both use the same leaf definitions and order. Criterion used 1-second warmup, 3-second measurement, and 40 samples on an Intel i7-11700F, Linux 6.1, rustc 1.97.0, and Arrow 59.3.0. Criterion's slope point estimates were **172.681 µs** [95% CI: 172.151, 173.214] and **31.965 µs** [95% CI: 31.915, 32.017], a **5.40x** ratio. Three invocations gave 5.39x to 5.41x. Frequency was unpinned and targets sequential, so small differences are not meaningful.
The mixed-RHS path is [`BinaryExpr::evaluate`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L542-L611) -> [`check_short_circuit`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L1188-L1272) -> Arrow [`filter_record_batch`](https://github.com/apache/arrow-rs/blob/59.3.0/arrow-select/src/filter.rs#L441-L463) -> RHS evaluation -> [`pre_selection_scatter`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr/src/expressions/binary.rs#L1307-L1354). Each trigger filters the full batch and restores a full-length Boolean array because the selected RHS is mixed. The uniform-RHS shortcut does not apply, and compact state is not propagated upward.
Exact prefix survivors: `5742 -> 3946 -> 2749 -> 1905 -> 1338 -> 889 -> 617 -> 425`. At 8,192 rows, mixed non-null arrays with 1 to 1,638 true rows qualify, so the last three left-deep parents trigger. Right-deep LHS values are individual approximately 70%-passing leaves and do not. Arrow `filter_record_batch` filters every column, including unreferenced payload.
### Controlled experiments
| Control | Left | Right | L/R |
|---|---:|---:|---:|
| k=2, p=.70, width=32 | 7.356 µs | 7.349 µs | 1.00x |
| k=8, p=.70, width=0 | 73.062 µs | 31.878 µs | 2.29x |
| k=8, p=.70, width=32 | 172.681 µs | 31.965 µs | 5.40x |
| k=8, p=.70, width=64 | 282.648 µs | 31.899 µs | 8.86x |
| k=8, p=.90, no firing | 31.900 µs | 31.872 µs | 1.00x |
| k=16, p=.70, width=32 | 380.918 µs | 68.728 µs | 5.54x |
| k=8, p=.70, regex suffix | 146.079 µs | 375.879 µs | 0.39x |
Width amplifies only the preselecting path; the no-fire control removes the gap. Regex reverses it, making left-deep 2.57x faster. This strongly argues against disabling preselection globally or treating right-deep as the fix.
These Samply stack counts are inclusive and may overlap:
| Profile | Samples | `filter_record_batch` | `pre_selection_scatter` |
|---|---:|---:|---:|
| Left | 7,948 | 4,937 (62.12%) | 1,263 (15.89%) |
| Right | 8,031 | 1 (0.01%) | 2 (0.02%) |
| Left p=.90 | 7,898 | 4 (0.05%) | 0 |
#### Right-deep: `pre_selection_scatter`
<img width="1455" height="486" alt="Image" src="https://github.com/user-attachments/assets/fc4b5d52-f47b-4acc-a258-7ce897f3886c" />
#### Right-deep: `filter_record_batch`
<img width="1454" height="497" alt="Image" src="https://github.com/user-attachments/assets/e6b2096a-c097-4dbf-b09c-e6e90ceb2900" />
#### Left-deep: `filter_record_batch`
<img width="1454" height="491" alt="Image" src="https://github.com/user-attachments/assets/294373f1-5802-46aa-821d-4301ca588bc6" />
#### Left-deep: `pre_selection_scatter`
<img width="1457" height="499" alt="Image" src="https://github.com/user-attachments/assets/5443fba4-7b4f-4632-93a9-6f216481235f" />
### Correctness constraints and next decision
All 11 generated comparisons and 22 Criterion targets passed, alongside the targeted nullable/scalar association, short-circuit/scatter, physical-expression library (1,643 passed, 2 ignored), logical right-deep protobuf round-trip, and `simplify_inlist` tests. These validate current cases, not candidates.
For Kleene value semantics, definite `FALSE` rows can retire, but `NULL` must remain active because `NULL AND FALSE = FALSE`. [`evaluate_selection`](https://github.com/apache/datafusion/blob/9082d6b10c29b72d56bede3d8e353d9d61fde542/datafusion/physical-expr-common/src/physical_expr.rs#L97-L180) guarantees that skipped rows cannot trigger errors. A changed active set can therefore alter rows evaluated, first observable error, and rows on which volatile expressions run.
Git history points to [`4818966fa0` / #15694](https://github.com/apache/datafusion/commit/4818966fa0950a6a471d1ea9e4b8c5808878207e) as introducing partial-row filtering/scatter. Protobuf preserves an explicitly right-deep logical tree, while fully mergeable `InList` chains can simplify bottom-up. These findings narrow the serialization and `InList` objections to A, but A still changes global shape and does not address the evaluator’s state or cost policy.
This motivates testing A as a control. B would carry one active-row mapping through the `AND` chain and restore full length once; C would gate compaction using its predicted benefit. I would test B, C, then B+C independently. Before prototyping, I would value alignment on:
1. Is evaluator-local `AND` flattening the right initial boundary, preserving stored shape, leaf order, serialization, display, optimizer behavior, and public API?
2. What observable contract must hold for fallible and volatile leaves: rows evaluated, evaluation count, and/or first observable error?
3. Should B and C remain independently switchable, and which cheap signals may C use: survivor ratio, estimated bytes, remaining conjuncts, or coarse expression cost?
4. What correctness and performance criteria should define acceptance? Should `OR` remain unchanged, and should selection-aware `FilterExec` integration be considered only if the `BinaryExpr` boundary is insufficient?
After alignment, I will establish correctness, then compare baseline, B, C, and B+C with interleaved same-binary runs and profiles. Only then would I run 31 `predicate_eval` cases with validation, TPC-H Q06 and the full suite with A/A drift controls, and repository-wide checks before proposing a production fix. I would genuinely appreciate your feedback on the semantic contract and evaluator boundary :)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
Posted by "Abhisheklearn12 (via GitHub)" <gi...@apache.org>.
Abhisheklearn12 commented on issue #25035:
URL: https://github.com/apache/datafusion/issues/25035#issuecomment-5575254240
Hi @adriangb, are you currently working on this issue? If not, I’d like to work on it. Could you assign it to me?
I’d like to do some research and understand the problem thoroughly before implementing it. I’ll share a rough design/sketch in the next 5-6 days.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb closed issue #25035: `AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct
URL: https://github.com/apache/datafusion/issues/25035
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org