Proposal: Prune complex predicates by propagating column statistics

# TL;DR

This proposal introduces **expression-aware predicate pruning** via **statistics propagation**. By propagating available micro-partition statistics bottom-up through the physical expression tree, we can prune **complex / nested predicates** that are not prunable with the current implementation.

This approach leads to clean solutions to several existing pruning-related challenges, including:

* [https://github.com/apache/datafusion/issues/19028](https://github.com/apache/datafusion/issues/19028)
* [https://github.com/apache/datafusion/issues/18320](https://github.com/apache/datafusion/issues/18320)
* [https://github.com/apache/datafusion/issues/1692](https://github.com/apache/datafusion/issues/1692)

*Example 1 (motivating workload)*

```sql
SELECT *
FROM t
WHERE
((a * 7) > 100)
OR (b IS NULL)
OR (UPPER(c) IN ('ELECTRONIC', 'BOOK'))
OR (ST_INTERSECTS(d, MBR_EUROPE))
```

Micro-partition statistics:

```text
a: min=0, max=10
b: AllNotNull
c: values ⊆ {'toy', 'clothing'}
d: geometries ⊆ MBR_CHINA (assume MBR_CHINA ∩ MBR_EUROPE = ∅)
```

The micro-partition in this example can be safely pruned by the predicate.

Later sections walk through this example step by step to introduce the core ideas behind statistics-propagation-based predicate pruning. They also include additional background on partition pruning for readers who may not already be familiar with the topic.

The issue is organized as follows:

* Section 1: Background on partition pruning
* Section 2: The core idea of statistics propagation, with a walkthrough of the example above
* Section 3: Limitations of the existing implementation
* Section 4: Engineering challenges / open questions
* Section 5: Implementation details

* Key data structures / APIs
* Algorithm
* Section 6: Implementation plan (initial PR scope, future milestones, etc.)

---

# 1. Background on partition pruning

In Parquet, data is physically organized and encoded into micro-partitions, each with statistics summarizing the entire micro-partition. The query engine can use these statistics to perform predicate pruning: it evaluates the predicate against the statistics to decide whether it can skip decoding and scanning the micro-partition entirely.

Suppose we have a filter predicate `x > 5`:

```sql
SELECT * FROM t WHERE x > 5
```

Assume the table is stored with the following micro-partition statistics:

* partition 1: `min=0, max=3`
* partition 2: `min=2, max=12`
* partition 3: `min=8, max=20`

Then for `x > 5`:

* `x > 5` on `[0,3]` → **SkipAll** (always false)

* safely skip scanning this micro-partition
* `x > 5` on `[2,12]` → **Unknown** (mixed)

* still need to scan it
* `x > 5` on `[8,20]` → **KeepAll** (always true)

* no need to evaluate the predicate again during the filter phase; all rows can pass through

In summary, predicate pruning makes query execution more efficient by avoiding unnecessary I/O and computation.

## Terms

The following terminology is used throughout this proposal:

* **Micro-partition**: the smallest unit of storage-level pruning (e.g., partitioned files, Parquet row groups, or pages). These are prunable because they have partition-level statistics that the pruning engine can evaluate.
* **Zone map / range stats**: per–micro-partition `min/max` statistics (and potentially richer summaries) for a column.
* **Null stats**: summaries such as `null_count`, `row_count`, or derived states like `AllNull`, `AllNotNull`, and `Unknown`.
* **Set stats**: a summary of distinct values (exact sets or bounded dictionaries) within a micro-partition, e.g., `{'toy', 'clothing'}`.
* **Geo stats**: spatial summaries such as an MBR (minimum bounding rectangle) containing all geometries in a micro-partition.
* **Pruning result (tri-state)**:

* **SkipAll**: the predicate is always false on the micro-partition → safe to prune.
* **KeepAll**: the predicate is always true on the micro-partition → scanning can skip predicate evaluation.
* **Unknown**: the predicate is mixed → must scan and evaluate the predicate.
* **Statistics propagation**: evaluating an expression by transforming and combining statistics bottom-up along the expression tree.

## Issue: making this work on real workloads is hard

Realistic filter predicates are often nested and include functions or UDFs. Column statistics can also be diverse (min/max, null summaries, sets/dictionaries, geospatial summaries, etc.). Designing a pruning framework that composes all of these cleanly is challenging.

---

# 2. Example demo: the idea behind statistics propagation

Let's start with a simpler example for the idea, then walk through the above `Example 1`.

**Core idea**: propagate and evaluate different kinds of statistics independently, and only combine them at the predicate expression nodes (like `>`)

Note: this section is only meant for a rough intuition; the later `Implementation` section explains the algorithm and the benefits of this design in more detail.

## Simpler example walkthrough
```text
Example 2: A simpler example to demonstrate separated stat propagation for different stat types

Expression:
((abs(a)) * 7) > 100

Column statistics for `a`:
- Range: min = 0, max = 10
- Set: {0, 3, 10}
- Nulls: AllNotNull
```

The following figure visualize the idea of 'propagating different kinds of statistics independently', and next it walkthrough each steps in detail.

*Figure 0. Separated Stats Propagation for Example 2*

```text
Example 2 walkthrough

1) Propagate through abs(a)

- Range: [0, 10] -> [0, 10]
- Set: {0, 3, 10} -> {0, 3, 10}
- Nulls: AllNotNull -> AllNotNull

2) Propagate through abs(a) * 7

- Range: [0, 10] combined with [7, 7] -> [0, 70]
- Set: {0, 3, 10} combined with {7} -> {0, 21, 70}
- Nulls: AllNotNull combined with AllNotNull -> AllNotNull

3) Evaluate (abs(a) * 7) > 100

- Range: evaluate([0, 70] > [100, 100]) -> SkipAll
(partial result derived from range stats only)

- Set: evaluate({0, 21, 70} > {100}) -> SkipAll
(partial result derived from set stats only)

- Nulls: evaluate(AllNotNull > AllNotNull) -> AllNotNull
(combined null stats)

4) Combine the results

1. Combine partial results:
SkipAll + SkipAll -> SkipAll

2. Fold the combined final result with the combined null stats:
SkipAll + AllNotNull -> SkipAll
```

## Example 1 walkthrough
Comparing with the above simpler example, here the 'Example 1' includes more complex expressions, and with some statistics types not available on some columns, it can still try to evaluate an useful pruning result with only the available statistics.

Using the statistics shown earlier in `Example 1`, the entire predicate can be evaluated as **SkipAll**, meaning the micro-partition can be safely pruned:

* Sub-expr 1: `(a * 7) > 100`

* `a` in `[0, 10]` ⇒ `a * 7` in `[0, 70]` ⇒ always false ⇒ **SkipAll**
* Sub-expr 2: `b IS NULL`

* `b` is `AllNotNull` ⇒ always false ⇒ **SkipAll**
* Sub-expr 3: `UPPER(c) IN ('ELECTRONIC', 'BOOK')`

* `c` in `{'toy', 'clothing'}` ⇒ `UPPER(c)` in `{'TOY', 'CLOTHING'}` ⇒ always false ⇒ **SkipAll**
* Sub-expr 4: `ST_INTERSECTS(d, MBR_EUROPE)`

* `d` within `MBR_CHINA` and `MBR_CHINA ∩ MBR_EUROPE = ∅` ⇒ always false ⇒ **SkipAll**

For an `OR` expression, if **all branches are SkipAll**, the entire predicate is **SkipAll**, and the micro-partition can be pruned.

The figures below illustrate the propagation of statistics and pruning results through the expression tree. The geospatial sub-expression is omitted for brevity.

Note that these figures show a **conceptual** view for a single micro-partition. In the actual implementation, statistics propagation is vectorized: each node propagates pruning intermediates for many micro-partitions at once, with statistics stored in arrays. This is described in more detail in later sections.

*Figure 1. Stats Propagation for sub-expression `(a*7)>100`*

*Figure 2. Stats Propagation for sub-expression `b IS NULL`*

*Figure 3. Stats Propagation for sub-expression `UPPER(c) in ('ELECTRONIC', 'BOOK')`*

*Figure 4. Stats Propagation for final evaluation on `OR`s*

---

# 3. Limitations of the existing implementation

`PruningPredicate` is currently the main mechanism for predicate pruning. It supports basic range and null-summary arithmetic for a subset of expressions, but effectively produces only two outcomes: `SkipAll` or `Other`.

Current implementation:
[https://github.com/apache/datafusion/blob/main/datafusion/pruning/src/pruning_predicate.rs](https://github.com/apache/datafusion/blob/main/datafusion/pruning/src/pruning_predicate.rs)

The core idea is to rewrite the original predicate into a new predicate over partition statistics, which can then be evaluated to a boolean value indicating whether to prune.

For example:

* predicate: `x < 5`
* statistics: min/max/nulls for column `x`

The pruning predicate rewrites `x < 5` into something like:
`x_null_count != row_count AND x_min < 5`

The rewritten expression is interpreted as:

* `true` → **SkipAll**
* `false` or `null` → **Unknown**

You can experiment with the current pruning API via `datafusion-examples`:
[https://github.com/apache/datafusion/blob/main/datafusion-examples/examples/query_planning/pruning.rs](https://github.com/apache/datafusion/blob/main/datafusion-examples/examples/query_planning/pruning.rs)

### Limitations

* **No tri-state output**: **KeepAll** is missing, which prevents skipping redundant filtering.
* **Hard to extend**: Supporting new functions or UDFs often requires invasive changes to the optimizer.

As a workaround, tri-state logic and set/geo pruning can be implemented as special cases or extensions, so for the cases that can't be covered by `PruningPredicate`, we're now adding new standalone modules to handle them separately. This increases complexity and makes pruning nested expressions even harder.

---

# 4. Engineering challenges / open questions

There are several challenges in implementing statistics-propagation-based predicate pruning.

Most of these considerations are compatible with the initial design, but are intended to be addressed incrementally in future extensions rather than the initial PR.

## Performance

Optimization time matters. Otherwise, we risk queries that take seconds to optimize but only milliseconds to execute.

Key scenarios to consider:

1. **Many micro-partitions**
In real workloads, pruning may need to evaluate thousands of micro-partitions.

2. **Expensive statistics**
Some statistics (e.g., set stats) are expensive to compute. Often, an effective pruning decision can be derived from partial propagation.

```text
Example: short-circuit evaluation using set statistics

Query:
SELECT *
FROM t
WHERE tag IN ('a', 'b')

Stats:
partition1: tag ⊆ S1, |S1| = 1000
partition2: tag ⊆ S2, |S2| = 1
```

For partition 1, evaluating set stats is expensive and unlikely to yield pruning.
For partition 2, set stats are cheap and potentially useful.
Short-circuiting should avoid unnecessary work.

3. **Useless sub-expressions**

```text
Example: runtime feedback refinement

Query:
SELECT *
FROM t
WHERE (c1 > 1) AND expensive_func(c2)
```

If runtime feedback shows:

* `c1 > 1` frequently evaluates to false (helpful for pruning)
* `expensive_func(c2)` rarely evaluates to false (wasted optimization effort)

Then `expensive_func(c2)` can be dropped from pruning consideration.

## Implementation complexity

Supporting statistics propagation across all commonly used expressions requires a large amount of code. While the logic is mostly straightforward, identifying common patterns and providing reusable utilities is critical to avoid repetitive implementations.

## Propagation may lose precision

The below example may not reflect real workloads; it is intended only for demonstration, and we can brainstorm real-world cases that should be considered.

```text
Query:
SELECT *
FROM t
WHERE ((x - 3) * (3 - x)) > 1

Statistics:
partition1: x_min = 0, x_max = 10
```

Naive propagation yields:

```
x - 3 -> [-3, 7]
3 - x -> [-7, 3]
product -> [-49, 21]
```

This leads to `Unknown`.

However, algebraically:

```
((x - 3) * (3 - x)) > 1
-> (x - 3)^2 < -1
-> false
```

The partition can be safely pruned.

The example shows that we still want a set of optimizer rules to rewrite the predicate to make it easier for the statistics-propagation-based pruner to work—either by making pruning more effective or cheaper to evaluate. This technique is called **pre-image rewrite**.

We have an existing issue tracking pre-image rewrites (https://github.com/apache/datafusion/issues/18320).
While the motivating examples in that issue can be handled directly by the statistics-propagation approach proposed here—without requiring pre-image rewrites—the idea remains relevant for cases where naive statistics propagation loses precision or is too expensive to evaluate.

## Supporting more statistics

Beyond min/max, additional statistics types could further improve pruning effectiveness. The design should make it easy to extend support for new statistics.

---

# 5. Implementation

## Overview

This proposal enables pruning of complex and nested expressions by propagating and combining column statistics, with the following properties:

* A unified pruning framework across multiple statistics types
* Easy extensibility for new or externally defined functions
* Natural support for nested expressions
* Extensible to address the challenges described above

The idea is inspired by [Pruning in Snowflake: Working Smarter, Not Harder](https://arxiv.org/abs/2504.11540)

Section 3 in the paper describes the statistics propagation approach at a high level, while it didn't provide any implementation detail. This document and the accompanying POC PR develop a concrete implementation and seek feedback.

## Key data structures / APIs

See PR: https://github.com/apache/datafusion/pull/19609

## Considerations

### `PruningIntermediate` is vectorized

`PruningIntermediate` is a vectorized data structure holding statistics for all source containers, using Arrow `Array`s as the low-level physical representation.

Vectorization is critical because pruning may involve thousands of containers. Evaluating them one by one would be too slow. With Arrow arrays, existing Arrow kernels can be reused for efficient propagation.

The existing `PruningPredicate` already uses a vectorized design:
[https://github.com/apache/datafusion/blob/6ce237492d9f75477c594ba132b2575932122dd6/datafusion/pruning/src/pruning_predicate.rs#L77-L78](https://github.com/apache/datafusion/blob/6ce237492d9f75477c594ba132b2575932122dd6/datafusion/pruning/src/pruning_predicate.rs#L77-L78)

### Existing `evaluate_bounds()` API

There is an existing statistics propagation API:
[https://github.com/apache/datafusion/blob/4960284541a8394034fd7f82833571fd601633bf/datafusion/physical-expr-common/src/physical_expr.rs#L190](https://github.com/apache/datafusion/blob/4960284541a8394034fd7f82833571fd601633bf/datafusion/physical-expr-common/src/physical_expr.rs#L190)

This API serves a different purpose. It derives statistics for the *current plan* and is primarily used for cardinality estimation (e.g., join ordering). It:

* Considers only one logical container per column
* Tracks richer distribution information
* Is not vectorized

In contrast, pruning statistics:

* Must represent **all input containers**
* Benefit from vectorized evaluation
* Do not require rich distribution modeling

Therefore, these are intentionally separate interfaces:

* **Pruning statistics propagation (this proposal)**: vectorized
* **Cardinality-estimation propagation**: non-vectorized, richer distributions

## Algorithm

The core idea behind the algorithm is propagating different types of statistics independently, see `Section 2` for visualization and example. There are two types of expression nodes to implement:

### 1) Arithmetic nodes (`+`, `-`, `abs()`, `upper()`, UDFs)

Each statistics type is propagated independently via optional hooks:

```rust
pub trait PhysicalExpr {
fn propagate_range_stats(
&self,
_child_range_stats: &[RangeStats],
) -> Result> {
Ok(None)
}

fn propagate_null_stats(
&self,
_child_null_stats: &[NullStats],
) -> Result> {
Ok(None)
}

fn propagate_set_stats(
&self,
_child_set_stats: &[SetStats],
) -> Result> {
Ok(None)
}
}
```

A default `evaluate_pruning()` implementation can:

1. Evaluate children
2. Collect child statistics by type
3. Invoke each `propagate_*` hook
4. Combine outputs into a `PruningIntermediate`

### 2) Predicate nodes (`>`, `<`, `=`, `IN`, spatial predicates)

1. Evaluate predicates using available **non-null statistics** (range/set/geo), producing partial tri-state results.
2. Combine partial results:

* **SkipAll** short-circuits immediately
* **KeepAll** may short-circuit if safe
* Conflicts indicate bugs or incompatible semantics

For Null handling, the assumption is all stat types only include non-null items, and all nulls are excluded from the stat. For example for a range stat `min=0, max=10`, it's unknown if there are any `Null`s in the partition, that's why we have to check the null stats for the final pruning result.

3. Combine with `NullStats` to produce the final pruning result.

The PR explains the combination rules in detail, see https://github.com/apache/datafusion/pull/19609.
Here is a simple example for some high-level idea for the above rules:

**Example: predicate `expr1 > expr2`**

- If `expr1` has range stats `[0, 10]` and `expr2` has `[-20, -10]`, then using **only** range stats we can derive a partial pruning result of **SkipAll**. At this point, we can short-circuit evaluation of other statistics for efficiency. The intermediate result may look like `range: SkipAll, set: Unknown`, but the combined result is still **SkipAll**.
Null stats also do not change this decision: for all non-null values, the predicate always evaluates to false; for any remaining null values, `>` evaluates to `NULL`, and the row is still filtered out. Therefore, it is safe to skip the partition entirely.

- Since all statistics are semantically consistent, it is impossible for different stat types to yield conflicting pruning results. For example, it cannot happen that range stats evaluate to **SkipAll** while set stats evaluate to **KeepAll**. The **Unknown** result, however, is compatible with other pruning outcomes.

- If `expr1` has range `[20, 30]` and `expr2` has `[0, 10]`, then using **only** range stats the predicate evaluates to **KeepAll**. Because range stats summarize only non-null values, we know all non-null rows satisfy the predicate, but possible null rows cannot be guaranteed to pass. Therefore, the final result is **KeepAll** only if both `expr1` and `expr2` have null stats `AllNonNull`; otherwise, **KeepAll** must be downgraded to **Unknown**.

### Tradeoff
With this separated propagation, the benefits are
- Conceptually simpler implementation for arithmetic nodes, they only have to consider how to propagate each stat type individually, and the trickier combination step can be handled in a common utility function.
- Easy to extend for additional new statistics types
- Easy to implement the short-circuit optimization described in `Section 4`
- For instance, range and null stats are usually faster to evaluate, if we can derive useful output like `SkipAll`, we don't have to evaluate the expensive set stats. This can be implemented with passing some control info in the per-PhysicalExpr `evaluate_pruning()` API, so the first pass of traversal, we can skip evaluating set stats, and only trigger a second pass to evaluate them when necessary.

---

# 6. Implementation plan

The initial PR is intentionally limited in scope and is primarily focused on establishing a flexible API that can accommodate future extensions and challenges.

A subsequent milestone would be to implement statistics propagation for additional PhysicalExpr types, so that the new propagation-based pruning utility achieves feature parity with the existing PruningPredicate and can eventually replace it.

It would also be valuable to design an advanced pruning benchmark that captures a diverse set of real-world pruning scenarios and explicitly exercises the performance challenges discussed above, helping to guide and validate the implementation.

Start by reading datafusion/pruning/src/pruning_predicate.rs and the datafusion-examples/examples/query_planning/pruning.rs example to understand the current pruning API and its limitations. Before coding, confirm the initial PR scope and acceptance criteria in the proposal's implementation-plan section; the issue describes a broad design rather than a self-contained change.

Written by the indexing model from the issue text.