adriangb opened a new issue, #24280: URL: https://github.com/apache/datafusion/issues/24280
## Is your feature request related to a problem or challenge? `build_statistics_expr` finishes every rewritten leaf comparison with an unconditional `wrap_null_count_check_expr`: https://github.com/apache/datafusion/blob/main/datafusion/pruning/src/pruning_predicate.rs#L1815 so the guard `<col>_null_count != row_count` is emitted **once per comparison** rather than once per column per boolean group. Because `find_stat_column` reuses one `row_count` column and one `null_count` column per source column, every copy of the guard for a given column is *structurally identical* — the duplicates are pure redundancy in an expression that is then evaluated against every container (file, row group, data page). This is independent of any one predicate shape and is already visible on `main`. The examples below are all real `pruning_predicate=` strings from `EXPLAIN`. ### 1. A range on one column — 4 comparisons where 3 suffice `WHERE v >= 10 AND v <= 20`: ``` v_null_count@1 != row_count@2 AND v_max@0 >= 10 AND v_null_count@1 != row_count@2 AND v_min@3 <= 20 ``` Equivalent: ``` v_null_count@1 != row_count@2 AND v_max@0 >= 10 AND v_min@3 <= 20 ``` A committed instance is in `datafusion/sqllogictest/test_files/clickbench.slt` (line 1001, the `EventDate BETWEEN` conjunct), where `EventDate_null_count@5 != row_count@3` appears twice in one predicate. ### 2. `IN` list at the default `max_in_list_size` — 20 identical guards `WHERE v IN (1, ..., 20)` produces 20 disjuncts, each re-testing the same guard: ``` v_null_count@2 != row_count@3 AND v_min@0 <= 1 AND 1 <= v_max@1 OR v_null_count@2 != row_count@3 AND v_min@0 <= 2 AND 2 <= v_max@1 OR ... 18 more ... v_null_count@2 != row_count@3 AND v_min@0 <= 20 AND 20 <= v_max@1 ``` **60 comparisons.** Equivalent: ``` v_null_count@2 != row_count@3 AND ( v_min@0 <= 1 AND 1 <= v_max@1 OR ... OR v_min@0 <= 20 AND 20 <= v_max@1 ) ``` **41 comparisons — 32% fewer.** The redundancy grows linearly with the list length, up to `datafusion.execution.parquet.max_in_list_size`. ### 3. `CASE` predicates — worst case, and it scales with `target_partitions` With #24238, a `CASE` used as a predicate is pruned on as the disjunction of its arms. A two-arm range `CASE`: ``` v_null_count@1 != row_count@2 AND v_max@0 >= 0 AND v_null_count@1 != row_count@2 AND v_min@3 <= 10 OR v_null_count@1 != row_count@2 AND v_max@0 >= 100 AND v_null_count@1 != row_count@2 AND v_min@3 <= 110 ``` **8 comparisons.** Equivalent: ``` v_null_count@1 != row_count@2 AND ( v_max@0 >= 0 AND v_min@3 <= 10 OR v_max@0 >= 100 AND v_min@3 <= 110 ) ``` **5 comparisons.** In general `4N -> 2N + 1` for `N` range arms. This matters because the motivating source of such predicates is a dynamic filter pushed down from a hash-partitioned join, which carries **one arm per partition** — so at `target_partitions=12` that is 48 comparisons vs 25, a 48% reduction, and the gap widens with core count. All arms of such a filter are on the same join key, so the guard factors down to exactly one copy. ## Describe the solution you'd like Factor the shared guard out. Two identities, applied to the generated statistics predicate: * conjunction: `(G AND P) AND (G AND Q)` == `G AND P AND Q` * disjunction: `(G AND P) OR (G AND Q)` == `G AND (P OR Q)` Generalised: dedup conjuncts within each term, then hoist the intersection of the terms' conjunct sets out of a disjunction. **This is exact, not an approximation.** The statistics predicate is evaluated in three-valued logic (`null_count`/`row_count`/`min`/`max` are all nullable — missing statistics come back as NULL arrays from `build_statistics_record_batch`), and both identities are theorems of Kleene logic: `AND`/`OR` are `min`/`max` over `F < N < T`, which is a distributive lattice, so idempotence, associativity and distributivity all hold. I checked both identities and the full four-arm shape exhaustively over every assignment in `{F, N, T}` — zero counterexamples. The bar is in fact lower than exact equivalence. `BoolVecBuilder::combine_value` prunes only on a definite `false`; `true` and `NULL` both keep the container. So only the "evaluates to false" set has to be preserved, and factoring preserves the entire three-valued value. **No pruning power is given up.** What cannot be factored: guards for *different* columns. `(a_null_count != row_count AND ...) OR (b_null_count != row_count AND ...)` has no common factor, and those two guards are genuinely different tests. So the achievable shape is "one guard per column per boolean group", which is exactly what examples 1–3 collapse to. ### Where it could live `PruningPredicateBuilder::try_build` already runs `PhysicalExprSimplifier` over the freshly built predicate: https://github.com/apache/datafusion/blob/main/datafusion/pruning/src/pruning_predicate.rs#L521-L523 but that simplifier currently only does constant folding, `NOT` normalisation and cast unwrapping — it has no conjunct dedup or common-factor extraction. Options, roughly in increasing blast radius: 1. Factor locally where the disjunction is built (the `IN` rewrite and the `CASE` rewrite), leaving `build_statistics_expr` alone. 2. Factor in the `AND`/`OR` combining step of `build_predicate_expression`, which covers every shape including example 1. 3. Add a general "dedup conjuncts / factor common conjuncts out of a disjunction" rule to `PhysicalExprSimplifier`, benefiting any consumer, not just pruning. ### Expected benefit The term-count reductions above are exact and measured. The runtime effect is **not** measured yet: the predicate is built once per file but evaluated once per container, so the saving should scale with row-group count and with the width of the disjunction. #24238 reports a ~5% TPC-H q20 regression attributed to the added per-container evaluation of a wide `CASE` disjunction, which suggests this cost is observable and is the natural thing to measure against. A secondary benefit is much more readable `EXPLAIN` output. ### Cost Implementing 2 or 3 will churn `pruning_predicate=` snapshots across a number of `.slt` files (`clickbench.slt`, `cte.slt`, `parquet*.slt`, ...). That churn is the main cost and is the reason this is filed separately rather than folded into #24238. ## Describe alternatives you've considered * **Dropping the guard entirely.** Not viable: when a container is all-NULL, parquet reports `min`/`max` as NULL, so `v_max >= 10` evaluates to NULL and the container is *kept*. The guard is what turns that into a prune, so it is a pruning enabler, not dead weight — one copy of it is needed. * **Capping the number of terms** instead of shrinking them. #24238 adds `datafusion.execution.parquet.max_case_arms` for exactly that, but a cap trades away pruning power, whereas factoring does not. They are complementary. ## Additional context Found while reviewing #24238. The duplication itself predates that PR and is reproducible on `main` with example 1. -- 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]
