Pruning predicates repeat the `null_count != row_count` guard once per comparison

[adriangb]

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. feat(pruning): prune containers through CASE predicates #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.