adriangb opened a new pull request, #25721: URL: https://github.com/apache/datafusion/pull/25721
# feat: adaptive conjunct reordering in FilterExec ## Which issue does this PR close? - Part of #22883. Design notes: https://claude.ai/artifact/SSz7t6hPyhFWp1MDPecVqt - Replaces #22698 in spirit: a smaller re-implementation on the shared `filter_stats` primitives. #22698 stays open for its review history. - Based on `main`. Two commits. The first commit (`filter_stats`) is also the first commit of #25674. When one of the two PRs merges, the copy in the other PR becomes empty on rebase. ```mermaid graph LR FS["filter_stats commit"] A1["#25673 Optional wrapper"] A2["#25681 producers mark filters"] A3["#25674 gate"] A4["#25682 Parquet consumer"] B1["#25683 FilterExec consumer"] B2["FilterExec reordering (new)"] C2["#25713 split join filter"] P["#22384 post-scan filter"] F["post-scan skips optional filters (new)"] FS --> A3 FS --> B2 A1 --> A2 C2 --> A2 A1 --> A4 A3 --> A4 A1 --> B1 A3 --> B1 A1 --> F P --> F classDef this fill:#f6e7d6,stroke:#b25e12,stroke-width:3px class B2 this ``` ## Rationale for this change The order of the conjuncts of an `AND` predicate is important. `BinaryExpr` evaluates the right side only on the rows that the left side keeps, if the left side keeps few rows. A selective, cheap conjunct written last makes the other conjuncts run on all rows. ```sql -- regexp_like(s, 'rare') removes most rows, but it is written last SELECT * FROM t WHERE regexp_like(s, 'a') AND regexp_like(s, 'rare'); ``` This PR starts from the review of #22698: | #22698 review point | This PR | |---|---| | One AND evaluator, not a second engine | the result is a plain `BinaryExpr` AND chain | | The cost model must match `BinaryExpr` pre-selection | uses `PRE_SELECTION_THRESHOLD` (now `pub`, `#[doc(hidden)]`) | | State must not leak across executions | the state is per stream | | Deterministic tests | injectable `Clock` (`ManualClock` in tests) | | No unsafe `unwrap`, no `UInt32Array` downcast | removed | ## What changes are included in this PR? `datafusion.execution.adaptive_filter_reordering` (experimental, default `false`): ```mermaid graph LR W["8 warm-up batches:<br/>measure each conjunct"] --> R["rank by rows removed per ns"] R --> D{"estimated cost ≥ 5% lower?"} D -- yes --> N["new BinaryExpr AND chain"] D -- no --> O["keep the original predicate"] ``` | Item | Purpose | |---|---| | `filter_stats::{FilterCost, Clock, SystemClock, ManualClock}` (first commit) | rows in, rows out, time; injectable clock | | `filter/conjunct_order.rs` | `ConjunctOrder`: warm-up measurement, ranking, cost estimate with the `BinaryExpr` pre-selection rule | | `FilterExec` | uses `ConjunctOrder` for each stream when the option is on | | Metric `adaptive_reorders` | number of streams that changed the order | Volatile predicates are never reordered. A fallible conjunct can see different rows after a reorder (for example `b <> 0 AND 1 / b > 2`); the config documentation says so. There are no optional-filter concepts in this PR. ## What is the testing strategy for this PR? | Area | Tests | |---|---| | `conjunct_order.rs` | 9 scenario tests with a manual clock: a selective conjunct moves first, the best written order is kept, a cheap conjunct stays before an expensive selective one, no reorder when `AND` cannot pre-select, nulls prevent a reorder, right-nested result, empty batches are not measured, volatile predicates are not reordered, the pre-selection model matches `BinaryExpr` | | `FilterExec` | `adaptive_filter_reordering_returns_same_rows` (same rows, metric present only with two or more conjuncts) | | `adaptive_filter_reordering.slt` | same results with the option on and off | | `filter_stats` | cost derivations, manual clock, system clock | ## Are there any user-facing changes? One new config option (default off) and one new metric. The default behavior does not change. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
