apache / apache/datafusion

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

Open
#24,280 3 comments 0 reactions 0 assignees View on GitHub
enhancement performance
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

## 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 `_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.

Contributor guide

Open the contributing guide

Research direction

Start in datafusion/pruning/src/pruning_predicate.rs, especially PruningPredicateBuilder::try_build, build_statistics_expr, and the boolean combination logic; review how PhysicalExprSimplifier is applied. Use the pruning_predicate outputs in datafusion/sqllogictest/test_files/clickbench.slt and related parquet or CTE files as regression cases. Done means shared guards are factored without changing pruning behavior and affected snapshots pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, databases
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.