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

### 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&& 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.