adriangb opened a new pull request, #25726: URL: https://github.com/apache/datafusion/pull/25726
feat(pruning): per-conjunct pruning statistics for `PruningPredicate` ## Which issue does this PR close? - Part of https://github.com/apache/datafusion/issues/22883. Design notes: https://claude.ai/artifact/SSz7t6hPyhFWp1MDPecVqt - Based on `main`. No dependency on the other PRs of the stack. The first production caller is the adaptive filter placement PR (E3), which depends on this PR, https://github.com/apache/datafusion/pull/25682 and https://github.com/apache/datafusion/pull/25722. - Replaces https://github.com/apache/datafusion/pull/22235 and https://github.com/apache/datafusion/pull/22498. The stale bot closed both. This PR uses the review of #22235 (thanks @asolimando). ```mermaid graph LR A1["#25673 Optional wrapper"] A3["#25674 gate"] A4["#25682 Parquet consumer"] P["#22384 post-scan filter"] F["#25722 post-scan skips optional filters"] E2["E2 per-conjunct pruning stats"] E3["E3 adaptive placement"] A1 --> A4 A3 --> A4 P --> F A1 --> F A4 --> E3 F --> E3 E2 --> E3 classDef this fill:#f6e7d6,stroke:#b25e12,stroke-width:3px class E2 this ``` ## Rationale for this change A scan that chooses where to evaluate each filter conjunct (row filter, post-scan filter or skip) must know how well each conjunct prunes with statistics. Today `PruningPredicate::prune` gives one mask for the whole predicate. It does not tell which conjunct pruned a container. ```rust // Before: one result for `a > 5 AND b < 10 AND a < 100` let keep: Vec<bool> = predicate.prune(&stats)?; // [false, false, false] // After: the same result, plus one entry for each conjunct let predicate = PruningPredicateBuilder::new() .with_file_schema(schema) .with_conjunct_stats(true) .try_build(expr)?; let (keep, per_conjunct) = predicate.prune_with_conjunct_stats(&stats)?; // keep == [false, false, false] (same as `prune`) // per_conjunct == [{pruned: 1, kept: 2}, {pruned: 1, kept: 2}, {pruned: 1, kept: 2}] ``` ## What changes are included in this PR? | Commit | Change | |---|---| | `refactor(pruning): ...` | Move the dynamic filter snapshot step and the literal guarantee loop into helpers. No change in behavior. | | `feat(pruning): ...` | Add the opt-in builder option, the new prune method and `ConjunctPruningStats`. | | `test(pruning): ...` | Unit tests. | New public API (all in `datafusion-pruning`): ```rust impl PruningPredicateBuilder<'_> { pub fn with_conjunct_stats(self, conjunct_stats: bool) -> Self; } impl PruningPredicate { pub fn prune_with_conjunct_stats<S: PruningStatistics + ?Sized>( &self, statistics: &S, ) -> Result<(Vec<bool>, Vec<ConjunctPruningStats>)>; } pub struct ConjunctPruningStats { pub containers_pruned: usize, pub containers_kept: usize, } ``` How it works: ```mermaid flowchart LR P["predicate"] --> S["split_conjunction"] S --> C1["conjunct 1: snapshot"] S --> C2["conjunct 2: snapshot"] C1 --> W["whole predicate = AND of snapshots"] C2 --> W W --> R["one RequiredColumns list"] C1 --> R C2 --> R R --> B["one statistics batch per call"] B --> M["whole mask (same as prune)"] B --> K["counts for each conjunct"] ``` - Conjuncts are the terms of `split_conjunction` on the input predicate. An `OR`, a `NOT` or a dynamic filter is one conjunct, also if it contains an `AND`. - Dynamic filters are snapshotted one time. The whole predicate and all conjuncts use that snapshot. - The whole mask uses the same steps as `prune`, so the result is the same. - Each conjunct is evaluated on all containers. There is no short circuit, so the counts of a conjunct do not depend on the other conjuncts or on their order. - A conjunct that statistics can not prune keeps all containers. - Without `with_conjunct_stats(true)`, the build and `prune` paths do the same work as before. `prune_with_conjunct_stats` returns an error for such a predicate. Changes from the review of #22235 and the design of #22498: | Concern | This PR | |---|---| | Two traversals of the leaves | One statistics batch for the whole predicate and all conjuncts. The per-conjunct expressions and literal guarantees are evaluated in addition, only when you ask for stats. | | Duplicate page-pruning method | No Parquet change. The consumer (E3) adds the call site in row group pruning. | | Placeholder `predicate_expr()` / `literal_guarantees()` / `required_columns()` | Not applicable. The predicate is the real, complete predicate. The conjunct data is extra private state. | | `AND` only? | Yes. `OR` and `NOT` stay inside one conjunct. A per-branch count under `OR` is not a sound "this term prunes" signal. | | Order-dependent stats from the short circuit | No short circuit when you ask for stats. Every conjunct sees every container. | | New types (`PruningConjunction`, builder, observer trait, `Tag`, `NoopObserver`, `ConjunctStatsObserver`) | Not added. The result is indexed by conjunct position. The caller keeps its own ids and totals. | ## What is the testing strategy for this PR? Unit tests in `datafusion/pruning/src/pruning_predicate/conjunct_stats.rs`: | Test | Checks | |---|---| | `and_of_conjuncts` | Each of three conjuncts gets its own count. | | `stats_do_not_depend_on_conjunct_order` | A conjunct that prunes all containers does not hide the other conjuncts. | | `single_conjunct` | A predicate without `AND` has one entry. | | `conjunct_that_can_not_be_rewritten_keeps_all_containers` | `a + b = 3` keeps all containers. | | `or_and_not_are_one_conjunct` | `OR` and `NOT (x AND y)` are not split. | | `dynamic_filter_is_one_conjunct` | A dynamic filter that contains an `AND` is one conjunct. | | `literal_guarantees_are_attributed_per_conjunct` | `contained` (for example Bloom filter) pruning is counted for the correct conjunct. | | `error_without_conjunct_stats` | The method returns an error if the option is not set. | Every test also checks that `prune_with_conjunct_stats` and `prune` give the same result as a predicate built without the option. The existing `datafusion-pruning`, `datafusion-datasource-parquet` and `parquet_integration` tests pass without change. ## Are there any user-facing changes? - New public API, see above. It is additive and opt-in. - No change in behavior or performance when you do not set `with_conjunct_stats(true)`. - No `api change` label is necessary. 🤖 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]
