`AND` chain pre-selection tests its threshold against the accumulated prefix, not the next conjunct

[adriangb]

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_scatters 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.

[Abhisheklearn12]

Hi @adriangb, are you currently working on this issue? If not, I’d like to work on it.

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.

[Abhisheklearn12]

take