adriangb opened a new pull request, #22698:
URL: https://github.com/apache/datafusion/pull/22698
## Which issue does this PR close?
- Related to #11262 (predicate evaluation ordering) and complements #22343
(static cheap/expensive heuristic reordering). No single issue; happy to
file
one if useful.
## Rationale for this change
Predicate evaluation order matters: running a selective predicate first lets
it
gate the work of the predicates after it. The static cheap/expensive
heuristic
(#22343) sorts conjuncts into two cost classes and stable-sorts within each,
so
it does nothing to order multiple *similarly-expensive* predicates; and
`BinaryExpr`'s `AND` short-circuit only gates on a *leftmost* selective
conjunct.
So a conjunction of several expensive predicates whose selective member is
not
written first is evaluated with every predicate scanning ~every row — and
neither mechanism fixes it.
This PR adds **runtime, statistics-based** conjunct reordering for
`FilterExec`:
it measures each conjunct's selectivity and cost on the rows that actually
reach
it and runs the ones that discard the most rows per unit of CPU time first.
Maximising discards-per-second is exactly minimising `cost_per_row / (1 -
pass_rate)`,
the classic optimal ordering key for independent conjuncts.
It is **off by default** (`datafusion.execution.adaptive_filter_reordering`).
## What changes are included in this PR?
Split into four reviewable commits:
1. **`physical-expr-common`: adaptive selectivity-stats substrate** — a
policy-free `SelectivityStats` (online selectivity + cost with Welford
mean/variance and confidence bounds) and a concurrent
`AdaptiveStatsRegistry`.
Reusable by other consumers (e.g. a future parquet-scan integration).
2. **`common`: config flag** `execution.adaptive_filter_reordering` (default
false), plus regenerated `configs.md` / `information_schema` listing.
3. **`physical-plan`: adaptive conjunct reordering in `FilterExec`** — a
stream-local evaluator that:
- evaluates conjuncts sequentially with threshold-gated compaction
(mirroring
`BinaryExpr`'s pre-selection) and measures each marginally;
- ranks by mean discards-per-second and **freezes as soon as the ranking
is
statistically certain** (adjacent confidence intervals stop
overlapping),
or after a small sample cap if the conjuncts are indistinguishable;
- on freeze, fuses the conjuncts into a single left-deep `AND` in the
learned
order and evaluates it as an ordinary predicate (no measurement
overhead,
inherits `BinaryExpr` pre-selection);
- periodically **re-thaws with exponential backoff** to catch distribution
drift, so steady-state overhead decays toward zero.
State is stream-local; the plan, results, and `EXPLAIN` are unchanged.
4. **Tests + benchmark** — an end-to-end `.slt` asserting identical
results/plan
with the flag on and off, and a `benchmarks/adversarial_filter/`
datafusion-cli
workload demonstrating the win.
## Are these changes tested?
Yes:
- Unit tests for the substrate (`SelectivityStats`, registry) and the
`FilterExec` evaluator (gating correctness, certainty-freeze, re-thaw
backoff,
drift adaptation).
- `adaptive_filter.slt`: results and `EXPLAIN` identical with the flag
on/off.
- Benchmarks (interleaved warm, min-times):
- adversarial (5 expensive regexps, selective last): **2.85x faster**;
control
(selective first, where it can't help): **neutral**.
- TPC-H SF1: net **-0.6%** (single-predicate control ~-3% noise floor),
with a
real Q12 **-22.7%** win; TPC-DS SF1: net **+0.0%**; ClickBench: neutral
on
engaging queries (small residual only on sub-10ms queries).
## Are there any user-facing changes?
One new config option, `datafusion.execution.adaptive_filter_reordering`
(experimental, default false). When enabled, the order in which a conjunctive
filter's predicates are evaluated may change at runtime; results are
unchanged,
but observable side effects of fallible predicates could differ (predicates
containing volatile expressions are never reordered).
--
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]
