You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "2010YOUY01 (via GitHub)" <gi...@apache.org> on 2026/01/02 14:25:15 UTC
[PR] feat: Predicate pruning via statistics propagation [datafusion]
2010YOUY01 opened a new pull request, #19609:
URL: https://github.com/apache/datafusion/pull/19609
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
The initial work of https://github.com/apache/datafusion/issues/19487
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
See the issue for the rationale, and design considerations.
For PR structure, start with datafusion/physical-expr-common/src/physical_expr/pruning.rs 's module-level comment, and follow along.
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
The core change in this PR is around a small few hundreds from estimation, the PR diff is mainly tests and docs.
- Defined core APIs/data structures for stat-propagation-based predicate pruning
- Implemented statistics pruning on:
- Literals (like 3)
- Column references (like c1)
- Comparison operators >, <, =, >=, <=
And we now support pruning for expressions like
- c1 > 1
- c1 >= c2
The issue also includes some thoughts on future implementation plans.
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
UTs
## Are there any user-facing changes?
No
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681669528
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
Review Comment:
I changed it to `evaluate_statistics_vectorized` in [9d256a5](https://github.com/apache/datafusion/pull/19609/commits/9d256a58320bf915335591c0c741dfb7993e369f), it makes sense to make it more general, and potentially unify those APIs.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-5288631226
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681663554
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
Review Comment:
`datafusion-pruning` is a parent module for `physicl-expr`, so it might not be possible.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3737870110
All review feedback has been addressed (except for https://github.com/apache/datafusion/pull/19609#discussion_r2681634077, which might need further discussion).
It’s ready for another look.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3729712558
> > If we do want to proceed, I think the first thing we should do is figure out how we will eventually unify the existing APIs that have overlap (specifically `PruningPredicate` and `PhysicalExpr::evalute_bounds`, possibly the propagate statistics code too)
>
> Regarding `PruningPredicate`, I think its major API can eventually remain the same, while its implementation should be replaced with this statistics-propagation-based pruning. Some minor API changes are inevitable.
Yes this sounds like a great plan
I still really feel that we can unify these APIs somehow. Starting with `vectorized_evaluate_bounds` as sugggested by @ozankabak seems like a good step in that direction
Also I shoudl be clear my concern isn't just the multiple implementations are harder to maintain, it is also that we already have significant code and test coverage for single row range analysis -- so replicating it again in vectorized fashion entirely separately won't leverage the past experience, and may result in different behaviors between the two paths
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681642190
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
Review Comment:
We don't have a usage for it yet, would be great to add in the future when needed.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2658117712
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
Review Comment:
I think it's important to point out that if null stats or missing (`NullPresence::UnknownOrMixed`) we cannot make any inferences from the min/max values, they should be treated as missing as well.
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
Review Comment:
Maybe an `iter_results(&self) -> impl Iterator<Item = PruningOutcome>`?
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
Review Comment:
A comment here explaining the meaning of each one of the 3 boolean states would be helpful, maybe linking to `PruningOutcome`
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
Review Comment:
This seems like it might be a bit magic and an explicit constructor is better
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
Review Comment:
When would this be called with `(None, 123)`? It seems like that usage is only ever internal from `pub fn none()`. I would make the public constructor `new(array: BooleanArrray)` and make `none()` initialize the struct itself.
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -746,6 +968,106 @@ fn check_short_circuit<'a>(
ShortCircuitStrategy::None
}
+/// For expressions like `left OP right`, calculate the `PruningOutcome` given child
+/// expression's range statistics, and operator type.
+///
+/// The supported operators are: >, <, =, >=, <=
+///
+/// Bounds encoding: each bound uses an `Option` to encode a NULL range value;
+/// `None` means the bound is NULL, and `Some` must contain a non-null `ScalarValue`.
+/// This is due to the existing ScalarValue comparison having unexpected null behavior:
+/// <https://github.com/apache/datafusion/issues/19579>
+///
+/// Type compatibility: if all bound data types are not equal, return
+/// `PruningOutcome::UnknownOrMixed` as a safe fallback. For different but
+/// compatible types (e.g., lhs is Int32, rhs is Int64), the type coercion
+/// optimizer rule should already handle them before evaluating pruning.
+///
+/// # Errors
+/// Returns Internal Error if unsupported operator is provided.
+fn compare_ranges(
Review Comment:
Some unit tests for this method specifically that ensure 100% coverage would be great
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2658692767
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
Review Comment:
I put them all in the struct comment of `PruningResults`, will also add links in the fields and other related structs
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3725386509
My suggested next step is to Decide if we have the effort / motivation to see it through (I am willing to help review, organized, and build consensus, as I think it is a foundational piece of DataFusion)
If we do want to proceed, I think the first thing we should do is figure out how we will eventually unify the existing APIs that have overlap (specifically `PruningPredicate` and `PhysicalExpr::evalute_bounds`, possibly the propagate statistics code too)
I think as long as there is a realistic way towards a unified framework we can then start pounding out the 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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681644634
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
Review Comment:
removed in [04f1697](https://github.com/apache/datafusion/pull/19609/commits/04f16979bb335afe6d0f4447ee9a013bd92f48d3)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681638163
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
Review Comment:
updated in [6741a2a](https://github.com/apache/datafusion/pull/19609/commits/6741a2abd1466eaf25f9799d052345a6c6753976)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2674838237
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
Review Comment:
How about `propagate_pruning_statistics()`? Since its covering a rich set of statistics more than just range, and we can use `_pruning_` to make it less ambiguous.
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
Review Comment:
I realized they're the same. `Unknown` means not `SkipAll` or `KeepAll`.
I will change it to `Unknown` to avoid confusion.
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
Review Comment:
If we want to do so, it should be add additional precision masks next to each statistics type like `min/max`, but in order to implement such propagation with precision variants, all the stat propagation logics should be adding a new path, there should be little code we can reuse for this case.
So technically it's feasible, but probably we should re-evaluate this idea when we want to support complex expressions for `ColumnStatistics` 🤔
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
+ /// docs for background.
+ ///
+ /// This default implementation is for `PhysicalExpr`s that have not yet
+ /// implemented pruning; returning `None` signals that no pruning statistics
+ /// are available.
+ ///
+ /// In the future, propagation may expose dedicated APIs such as:
Review Comment:
This is an excellent idea, we should do this in the future.
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
Review Comment:
Good point, will do it.
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+impl RangeStats {
+ pub fn new(
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ ) -> Result<Self> {
+ if let Some(ref mins) = mins {
+ assert_eq_or_internal_err!(
+ mins.len(),
+ length,
+ "Range mins length mismatch for pruning statistics"
+ );
+ }
+ if let Some(ref maxs) = maxs {
+ assert_eq_or_internal_err!(
+ maxs.len(),
+ length,
+ "Range maxs length mismatch for pruning statistics"
+ );
+ }
+ Ok(Self::Array { mins, maxs, length })
+ }
+
+ /// Create range stats for a constant literal across all containers.
+ pub fn new_scalar(value: ScalarValue, length: usize) -> Result<Self> {
+ Ok(Self::Scalar { value, length })
+ }
+
+ pub fn len(&self) -> usize {
+ match self {
+ RangeStats::Array { length, .. } | RangeStats::Scalar { length, .. } => {
+ *length
+ }
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// Normalize into concrete min/max arrays.
+ ///
+ /// For `Array`, returns cloned mins/maxs (which may be `None`).
+ /// For `Scalar`, expands the scalar to arrays of length `length`.
+ pub fn normalize_to_arrays(&self) -> Result<(Option<ArrayRef>, Option<ArrayRef>)> {
+ match self {
+ RangeStats::Array { mins, maxs, .. } => Ok((mins.clone(), maxs.clone())),
+ RangeStats::Scalar { value, length } => {
+ let mins = value.to_array_of_size(*length)?;
+ let maxs = value.to_array_of_size(*length)?;
+ Ok((Some(mins), Some(maxs)))
+ }
+ }
+ }
+}
+
+pub struct PruningContext {
+ stats: Arc<dyn PruningStatistics + Send + Sync>,
+}
+
+impl PruningContext {
+ pub fn new(stats: Arc<dyn PruningStatistics + Send + Sync>) -> Self {
+ Self { stats }
+ }
+
+ pub fn statistics(&self) -> &Arc<dyn PruningStatistics + Send + Sync> {
+ &self.stats
+ }
+}
+
+impl NullStats {
+ /// Build `NullStats` from per-container null and row counts.
+ ///
+ /// # Arguments
+ /// - `null_counts`: All containers' null counts in a single `Array`, or `None` if missing.
+ /// - `row_counts`: All containers' row counts in a single `Array`, or `None` if missing.
+ ///
+ /// # Return
+ /// `Some(NullStats)` when both inputs are present and aligned; `None` when either input is missing/unknown.
+ ///
+ /// # Examples (per-container outcomes)
+ /// - `null_counts=[3, 0, 1]`, `row_counts=[3, 5, 10]` →
+ /// presence = [false, true, null] (AllNull, NoNull, Mixed).
+ ///
+ /// # Errors
+ /// - Internal error if inputs have inconsistent lengths.
+ pub fn new(
+ null_counts: Option<&UInt64Array>,
+ row_counts: Option<&UInt64Array>,
+ ) -> Result<Option<Self>> {
+ // If either input is absent, we can't derive null stats for all containers.
+ let (Some(null_counts), Some(row_counts)) = (null_counts, row_counts) else {
+ return Ok(None);
+ };
+
+ let length = null_counts.len();
+ assert_eq_or_internal_err!(
+ row_counts.len(),
+ length,
+ "Row counts length mismatch for pruning statistics"
+ );
+
+ let mut presence = BooleanBuilder::with_capacity(length);
+ for idx in 0..length {
+ let nulls = (!null_counts.is_null(idx)).then(|| null_counts.value(idx));
+ let rows = (!row_counts.is_null(idx)).then(|| row_counts.value(idx));
+
+ // See `NullStats` for encoding semantics
+ match (nulls, rows) {
+ (Some(0), Some(_)) | (Some(0), None) => presence.append_value(true),
+ (Some(n), Some(r)) if n == r => presence.append_value(false),
+ _ => presence.append_null(),
+ }
+ }
+
+ Ok(Some(Self {
+ presence: presence.finish(),
+ }))
+ }
+
+ /// Create a `NullStats` with a uniform `presence` repeated `num_containers` times.
+ /// See `NullStats` docs for `presence` semantics.
+ ///
+ /// Used to create pruning statistics literal/scalar values.
+ pub fn from_uniform_presence(presence: NullPresence, num_containers: usize) -> Self {
+ let presence_item = match presence {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ };
+ NullStats {
+ presence: BooleanArray::from_iter(repeat_n(presence_item, num_containers)),
+ }
+ }
+
+ /// Combine two null-stat arrays for a comparison (`=, !=, <, >, <=, >=`).
+ ///
+ /// None means all containers' null stats are missing, otherwise for each container:
+ /// - If either side is `AllNull` → result is `AllNull` (all comparisons are null).
+ /// - If both sides are `NoNull` → result is `NoNull`.
+ /// - Otherwise → result is `UnknownOrMixed`.
+ ///
+ /// # Errors
+ /// Returns internal error if left and right side has inconsistent container length
+ pub fn combine_for_cmp(
+ left: Option<&Self>,
+ right: Option<&Self>,
+ ) -> Result<Option<Self>> {
+ let (left, right) = match (left, right) {
+ (Some(l), Some(r)) => (l, r),
+ (_, _) => {
+ return Ok(None);
+ }
+ };
+
+ let len = left.len();
+ assert_eq_or_internal_err!(
+ len,
+ right.len(),
+ "Null stats length mismatch for comparison pruning"
+ );
+
+ // The function comments specified the semantics behavior, and given the
+ // physical encoding:
+ // `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+ // The implementation can be simplified to a kleene(null-aware) 'AND'
+ Ok(Some(NullStats {
+ presence: and_kleene(left.presence(), right.presence())?,
+ }))
+ }
+
+ pub fn len(&self) -> usize {
+ self.presence.len()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.presence.is_empty()
+ }
+
+ pub fn presence(&self) -> &BooleanArray {
+ &self.presence
+ }
+}
+
+impl ColumnStats {
+ pub fn new(
+ range_stats: Option<RangeStats>,
+ null_stats: Option<NullStats>,
+ num_containers: usize,
+ ) -> Self {
+ debug_assert_eq!(
+ range_stats
+ .as_ref()
+ .map(|r| r.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ debug_assert_eq!(
+ null_stats
+ .as_ref()
+ .map(|n| n.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ range_stats,
+ null_stats,
+ num_containers,
+ }
+ }
+
+ pub fn range_stats(&self) -> Option<&RangeStats> {
+ self.range_stats.as_ref()
+ }
+
+ pub fn null_stats(&self) -> Option<&NullStats> {
+ self.null_stats.as_ref()
+ }
+
+ pub fn len(&self) -> usize {
+ self.num_containers
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.num_containers == 0
+ }
+}
+
+/// Pruning intermediate type propagated through `PhysicalExpr` nodes.
Review Comment:
Yes, this is doable. To encode `PruningResult`, we only need a single inner `Option<BooleanArray>`. The key consideration, I think, is which approach leads to a simpler implementation.
The answer is not clear to me yet; I will build a small prototype to confirm.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3727237478
> If we do want to proceed, I think the first thing we should do is figure out how we will eventually unify the existing APIs that have overlap (specifically `PruningPredicate` and `PhysicalExpr::evalute_bounds`, possibly the propagate statistics code too)
Regarding `PruningPredicate`, I think its major API can eventually remain the same, while its implementation should be replaced with this statistics-propagation-based pruning. Some minor API changes are inevitable.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-4701511864
> Apologies for the slightly ignorant comment, I am wandering in from the outside, but has any consideration been given to how this will perform for very wide/generated plans of the kind you might see in ML pipelines, etc? It might be appreciated for such cases to have this behaviour be controllable via a config toggle for users.
In practice, partitioned storage is usually clustered by a small number of columns: often a single sort/order column, or sometimes 2–3 Z-order columns.
So for complex-expression pruning, we want to only evaluate expressions with those clustering columns. Evaluating expressions involving unrelated columns on very wide tables could be wasteful, most of the time those columns are unlikely to contribute useful pruning power.
For that reason, making this behavior configurable is definitely desirable, and also it's doable.
This is just my guess about ML workloads and very wide tables concerns, so I might not get it correctly. I'd be interested to learn more if that's the case!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681639742
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
Review Comment:
updated in [04f1697](https://github.com/apache/datafusion/pull/19609/commits/04f16979bb335afe6d0f4447ee9a013bd92f48d3)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681657664
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
Review Comment:
fixed in [6741a2a](https://github.com/apache/datafusion/pull/19609/commits/6741a2abd1466eaf25f9799d052345a6c6753976)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2673504185
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
Review Comment:
we can likely lift some / all of the documentation from PruningPredicate here
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
Review Comment:
Is there any fundamental reason they need to be separate interfaces?
Like I am thinking, is there some potential future where we are able to rewrite [`PhysicalExpr::evaluate_bounds`] to use the new API in this PR?
That way having multiple APIs would be only a temporary, intermediate state as we worked to fill out the rest of the functionality 🤔
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
Review Comment:
```suggestion
//! `evaluate_bounds()` derives per-column statistics for a single expression, aimed at
```
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
Review Comment:
A minor suggestion is these look like they could be `impl From` / other methods on `PruningOutcome` -- for example, like `PruningOutcome::from(Some(true))`
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
Review Comment:
what does "mixed" predicate mean?
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
Review Comment:
I realize the primary usecase for this evaluation is pruning, but I think it is a more general concept -- basically propagating statistical information through this expression
What would you think of calling this more like `propagate_ranges`? (I realize it is getting very similar to `evalute_ranges` and `propagate_constraints`...)
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
Review Comment:
maybe they could be ColumnarValue? That would allow efficient representation of literals...
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
Review Comment:
After reading this code more, I don't think there is any fundamental difference (other than being vectorized) with evaluate_bounds
##########
datafusion/physical-expr/src/expressions/is_null.rs:
##########
@@ -92,6 +96,42 @@ impl PhysicalExpr for IsNullExpr {
}
}
+ fn evaluate_pruning(
+ &self,
+ ctx: Arc<PruningContext>,
+ ) -> Result<Option<PruningIntermediate>> {
+ let Some(child) = self.arg.evaluate_pruning(ctx)? else {
+ return Ok(None);
+ };
+ match child {
+ PruningIntermediate::IntermediateStats(stats) => {
+ if let Some(null_stats) = stats.null_stats() {
Review Comment:
I swear that @pepijnve recently implemented very similar logic (for the bounds evaluation of IsNull, albiet one row at a time) but now I can't find it...
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
Review Comment:
I think this shares some, but not all, similarities with the `ColumnStatistics` https://github.com/apache/datafusion/blob/c1aa1b530ab2fa73efcdeb8896dbb50c30c492f0/datafusion/common/src/stats.rs#L721-L720
The major difference is that ColumnStatistics also has some notion of precision (and is a row wise structure)
I am not sure if there is some way to unify them
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+impl RangeStats {
+ pub fn new(
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ ) -> Result<Self> {
+ if let Some(ref mins) = mins {
+ assert_eq_or_internal_err!(
+ mins.len(),
+ length,
+ "Range mins length mismatch for pruning statistics"
+ );
+ }
+ if let Some(ref maxs) = maxs {
+ assert_eq_or_internal_err!(
+ maxs.len(),
+ length,
+ "Range maxs length mismatch for pruning statistics"
+ );
+ }
+ Ok(Self::Array { mins, maxs, length })
+ }
+
+ /// Create range stats for a constant literal across all containers.
+ pub fn new_scalar(value: ScalarValue, length: usize) -> Result<Self> {
+ Ok(Self::Scalar { value, length })
+ }
+
+ pub fn len(&self) -> usize {
+ match self {
+ RangeStats::Array { length, .. } | RangeStats::Scalar { length, .. } => {
+ *length
+ }
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// Normalize into concrete min/max arrays.
+ ///
+ /// For `Array`, returns cloned mins/maxs (which may be `None`).
+ /// For `Scalar`, expands the scalar to arrays of length `length`.
+ pub fn normalize_to_arrays(&self) -> Result<(Option<ArrayRef>, Option<ArrayRef>)> {
+ match self {
+ RangeStats::Array { mins, maxs, .. } => Ok((mins.clone(), maxs.clone())),
+ RangeStats::Scalar { value, length } => {
+ let mins = value.to_array_of_size(*length)?;
+ let maxs = value.to_array_of_size(*length)?;
+ Ok((Some(mins), Some(maxs)))
+ }
+ }
+ }
+}
+
+pub struct PruningContext {
+ stats: Arc<dyn PruningStatistics + Send + Sync>,
+}
+
+impl PruningContext {
+ pub fn new(stats: Arc<dyn PruningStatistics + Send + Sync>) -> Self {
+ Self { stats }
+ }
+
+ pub fn statistics(&self) -> &Arc<dyn PruningStatistics + Send + Sync> {
+ &self.stats
+ }
+}
+
+impl NullStats {
+ /// Build `NullStats` from per-container null and row counts.
+ ///
+ /// # Arguments
+ /// - `null_counts`: All containers' null counts in a single `Array`, or `None` if missing.
+ /// - `row_counts`: All containers' row counts in a single `Array`, or `None` if missing.
+ ///
+ /// # Return
+ /// `Some(NullStats)` when both inputs are present and aligned; `None` when either input is missing/unknown.
+ ///
+ /// # Examples (per-container outcomes)
+ /// - `null_counts=[3, 0, 1]`, `row_counts=[3, 5, 10]` →
+ /// presence = [false, true, null] (AllNull, NoNull, Mixed).
+ ///
+ /// # Errors
+ /// - Internal error if inputs have inconsistent lengths.
+ pub fn new(
+ null_counts: Option<&UInt64Array>,
+ row_counts: Option<&UInt64Array>,
+ ) -> Result<Option<Self>> {
+ // If either input is absent, we can't derive null stats for all containers.
+ let (Some(null_counts), Some(row_counts)) = (null_counts, row_counts) else {
+ return Ok(None);
+ };
+
+ let length = null_counts.len();
+ assert_eq_or_internal_err!(
+ row_counts.len(),
+ length,
+ "Row counts length mismatch for pruning statistics"
+ );
+
+ let mut presence = BooleanBuilder::with_capacity(length);
+ for idx in 0..length {
+ let nulls = (!null_counts.is_null(idx)).then(|| null_counts.value(idx));
+ let rows = (!row_counts.is_null(idx)).then(|| row_counts.value(idx));
+
+ // See `NullStats` for encoding semantics
+ match (nulls, rows) {
+ (Some(0), Some(_)) | (Some(0), None) => presence.append_value(true),
+ (Some(n), Some(r)) if n == r => presence.append_value(false),
+ _ => presence.append_null(),
+ }
+ }
+
+ Ok(Some(Self {
+ presence: presence.finish(),
+ }))
+ }
+
+ /// Create a `NullStats` with a uniform `presence` repeated `num_containers` times.
+ /// See `NullStats` docs for `presence` semantics.
+ ///
+ /// Used to create pruning statistics literal/scalar values.
+ pub fn from_uniform_presence(presence: NullPresence, num_containers: usize) -> Self {
+ let presence_item = match presence {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ };
+ NullStats {
+ presence: BooleanArray::from_iter(repeat_n(presence_item, num_containers)),
+ }
+ }
+
+ /// Combine two null-stat arrays for a comparison (`=, !=, <, >, <=, >=`).
+ ///
+ /// None means all containers' null stats are missing, otherwise for each container:
+ /// - If either side is `AllNull` → result is `AllNull` (all comparisons are null).
+ /// - If both sides are `NoNull` → result is `NoNull`.
+ /// - Otherwise → result is `UnknownOrMixed`.
+ ///
+ /// # Errors
+ /// Returns internal error if left and right side has inconsistent container length
+ pub fn combine_for_cmp(
+ left: Option<&Self>,
+ right: Option<&Self>,
+ ) -> Result<Option<Self>> {
+ let (left, right) = match (left, right) {
+ (Some(l), Some(r)) => (l, r),
+ (_, _) => {
+ return Ok(None);
+ }
+ };
+
+ let len = left.len();
+ assert_eq_or_internal_err!(
+ len,
+ right.len(),
+ "Null stats length mismatch for comparison pruning"
+ );
+
+ // The function comments specified the semantics behavior, and given the
+ // physical encoding:
+ // `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+ // The implementation can be simplified to a kleene(null-aware) 'AND'
+ Ok(Some(NullStats {
+ presence: and_kleene(left.presence(), right.presence())?,
+ }))
+ }
+
+ pub fn len(&self) -> usize {
+ self.presence.len()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.presence.is_empty()
+ }
+
+ pub fn presence(&self) -> &BooleanArray {
+ &self.presence
+ }
+}
+
+impl ColumnStats {
+ pub fn new(
+ range_stats: Option<RangeStats>,
+ null_stats: Option<NullStats>,
+ num_containers: usize,
+ ) -> Self {
+ debug_assert_eq!(
+ range_stats
+ .as_ref()
+ .map(|r| r.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ debug_assert_eq!(
+ null_stats
+ .as_ref()
+ .map(|n| n.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ range_stats,
+ null_stats,
+ num_containers,
+ }
+ }
+
+ pub fn range_stats(&self) -> Option<&RangeStats> {
+ self.range_stats.as_ref()
+ }
+
+ pub fn null_stats(&self) -> Option<&NullStats> {
+ self.null_stats.as_ref()
+ }
+
+ pub fn len(&self) -> usize {
+ self.num_containers
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.num_containers == 0
+ }
+}
+
+/// Pruning intermediate type propagated through `PhysicalExpr` nodes.
Review Comment:
I am not sure we need to distinguish between intermediate statistics and intermediate results
Specifically, I think ColumnStats for boolean expressions will be trivially convertible to `PruningResults` (if the min/max are both `true` then we know the boolean value is always `true`. If the min/max are both `false` then we know the value is always `false`, etc)
This is similar to how Interval works: https://github.com/apache/datafusion/blob/81512da2b0aaa474f6c4ba205b05eea7b3095176/datafusion/expr-common/src/interval_arithmetic.rs#L182-L181
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
Review Comment:
It probably makes sense to put these into `datafuison-pruning` rather than `physical-expr`:
https://github.com/apache/datafusion/blob/7900cd6e98c11d4eaa7ac7d7db17dbd676315333/datafusion/pruning/
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
+ /// docs for background.
+ ///
+ /// This default implementation is for `PhysicalExpr`s that have not yet
+ /// implemented pruning; returning `None` signals that no pruning statistics
+ /// are available.
+ ///
+ /// In the future, propagation may expose dedicated APIs such as:
Review Comment:
Rather than different APIs, I would recommend a single API `propagate_ranges` and add the different types of information in the object that is propagated
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
Review Comment:
maybe just a comment here pointing to the definitions would be helpful
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "jordantgh (via GitHub)" <gi...@apache.org>.
jordantgh commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-4701085836
Apologies for the slightly ignorant comment, I am wandering in from the outside, but has any consideration been given to how this will perform for very wide/generated plans of the kind you might see in ML pipelines, etc? It might be appreciated for such cases to have this behaviour be controllable via a config toggle for users.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-6158979299
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3727520370
> If `evaluate_statistics()` and `propagate_statistics()` are intended to replace `evaluate_bounds()` and `propagate_constraints()`, and the latter two are no longer used inside the DataFusion core, should we simply deprecate them?
They are not. The latter are the simplest building blocks that calculate ranges, the former are designed to use them to generate richer statistical information. The former are not used yet in the codebase, because we unfortunately didn't have time to work on it over the last 6 months or so, but have an intention to come back and finish the job.
I didn't have time yet to look at this big PR, but I looked at the issue and design. As a general thought I think replacing the `evaluate_bounds`/`propagate_constraints` duo will not be easy. The `Interval` library makes very careful calculations w.r.t. things like rounding (with floats etc.), because their results are used to take branches. Support for such rounding-aware calculations were not present in `arrow-rs` at the time when we created these APIs (and still not here AFAICT).
However, we have two things:
1. Rigor (w.r.t. containment) in bounds is a real need in some use cases (like join pruning).
2. Vectorization is a real need in other use cases (like Parquet pruning).
A good first step is to add `evaluate_bounds_vectorized`, and note these nuances in the docs. Then, if you think it is possible to somehow achieve containment rigor w.r.t. rounding in the vectorized version too, we can try our hand at that, and then implement its `propagate_constraints` counterpart. Only at that stage we can remove the `evaluate_bounds`/`propagate_constraints` duo. Then, `evaluate_statistics()` and `propagate_statistics()` can migrate to the new API.
However, my hunch is that this won't be possible for the time being, and we will need to a new API that does vectorized bounds, and make it clear in the docs that we need the two APIs to cater to 1 and 2.
I hope this context helps @2010YOUY01 and @alamb
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3727206400
Let's work through the API design first. After we agree to move forward, I'll apply all minor code review suggestions.
> My suggested next step is to Decide if we have the effort / motivation to see it through (I am willing to help review, organized, and build consensus, as I think it is a foundational piece of DataFusion)
I do plan to spend significant effort on the future implementation, as I believe this is a very important optimization feature. Thank you for your help, @alamb!
> I have a bunch of API suggestions I think we can iterate on and make the code better / cleaner.
>
> The biggest challenge in this project, in my mind, is that it proposes to adds (yet) another API for some sort of range/statistics propagation.
>
> Even before this PR, we already have 4 APIs on the PhysicalExpr
>
> * https://docs.rs/datafusion/latest/datafusion/physical_expr/trait.PhysicalExpr.html#method.evaluate_bounds
> * https://docs.rs/datafusion/latest/datafusion/physical_expr/trait.PhysicalExpr.html#method.evaluate_statistics
> * https://docs.rs/datafusion/latest/datafusion/physical_expr/trait.PhysicalExpr.html#method.propagate_constraints
> * https://docs.rs/datafusion/latest/datafusion/physical_expr/trait.PhysicalExpr.html#method.propagate_statistics
>
> Some of these methods seem to be unused in the core codebase (e.g. the "propagate" variants, and some of the new V2 statistics API added in #14699 by @Fly-Style, but I don't see any uses of it in the code (https://github.com/apache/datafusion/blob/998f534aafbf55c83daaa6fd4985ba143954b0e0/datafusion/physical-expr/src/statistics/stats_solver.rs#L39-L38). It also has provisions for various statistical distributions for which I still don't understand the usecase
>
> If we are going to add a new API, I think we should deprecate some/all of the others.
I took a quick look at those APIs; their high-level ideas are:
- `evaluate_bounds()` propagates bounds using the `Interval` type.
- `propagate_constraints()` performs inverse propagation on `Interval`s. For example, given the output range of an expression and the original input ranges for its child expressions, it performs inverse propagation to refine the children’s ranges (its comment includes a specific example).
- `evaluate_statistics()` is similar to `evaluate_bounds()`, but operates on `Distribution` inputs to capture richer statistical distribution information.
- `propagate_statistics()` is similar to `propagate_constraints()`, but operates on `Distribution` inputs.
The API proposed in this PR can replace `evaluate_bounds()`, because it covers the full functionality of `evaluate_bounds()`. The only difference is that it is vectorized; we can use a simple adaptor for conversion, and `evaluate_bounds()` can be deprecated in the future.
`propagate_constraints()` cannot be replaced, since the statistics propagation for pruning (this PR) does not require inverse propagation.
`evaluate_statistics()` and `propagate_statistics()` cannot be replaced by this PR, because their representations do not overlap. Even more advanced pruning will not need the statistical information inside the `Distribution` struct.
I did some archaeology, but I am not very sure. If `evaluate_statistics()` and `propagate_statistics()` are intended to replace `evaluate_bounds()` and `propagate_constraints()`, and the latter two are no longer used inside the DataFusion core, should we simply deprecate them?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681659090
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
Review Comment:
Refactored in [04f1697](https://github.com/apache/datafusion/pull/19609/commits/04f16979bb335afe6d0f4447ee9a013bd92f48d3)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2658689968
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
Review Comment:
The actual inference logic is more aggressive than the algorithm you have described, it's implemented in https://github.com/apache/datafusion/pull/19609/changes#diff-32f7f18dcd86a268e7e1e0134eae6ae002bd42e61180cfabd60944566b10f6d8R660
I'll add more comments here also.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3706665874
Thank you for the review, those feedbacks make sense to me, I'll batch them later
> Some initial comments. Need to read a couple more times to actually wrap my had around how it's working.
unclear. I’m trying to make both the implementation and the documentation clearer, but the logic and edge cases for this feature are admittedly quite tricky.
> Is the plan to make multiple subsequent PRs to add more handling e.g. for `Like` expressions, UDFs, etc. and then eventually once we reach feature parity replace the current system?
Yes — the initial milestone should be reaching coverage equivalent to the existing `PruningPredicate` implementation, so we can reuse the existing tests and gain more confidence.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3716472557
I plan to review this PR carefully tomorrow. I am sorry for the delay but I have been out for a few days and I am quite backed up
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-4331888745
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3727914980
As an example, when one implements a join on an ordered table with a "sliding window" condition, the `propagate_constraints` becomes instrumental in finding the upper (or lower) bounds to prune the join hash map.
IMO [this blog post](https://synnada.medium.com/general-purpose-stream-joins-via-pruning-symmetric-hash-joins-94cc69a4847) explains the ideas well.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2676839541
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+impl RangeStats {
+ pub fn new(
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ ) -> Result<Self> {
+ if let Some(ref mins) = mins {
+ assert_eq_or_internal_err!(
+ mins.len(),
+ length,
+ "Range mins length mismatch for pruning statistics"
+ );
+ }
+ if let Some(ref maxs) = maxs {
+ assert_eq_or_internal_err!(
+ maxs.len(),
+ length,
+ "Range maxs length mismatch for pruning statistics"
+ );
+ }
+ Ok(Self::Array { mins, maxs, length })
+ }
+
+ /// Create range stats for a constant literal across all containers.
+ pub fn new_scalar(value: ScalarValue, length: usize) -> Result<Self> {
+ Ok(Self::Scalar { value, length })
+ }
+
+ pub fn len(&self) -> usize {
+ match self {
+ RangeStats::Array { length, .. } | RangeStats::Scalar { length, .. } => {
+ *length
+ }
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// Normalize into concrete min/max arrays.
+ ///
+ /// For `Array`, returns cloned mins/maxs (which may be `None`).
+ /// For `Scalar`, expands the scalar to arrays of length `length`.
+ pub fn normalize_to_arrays(&self) -> Result<(Option<ArrayRef>, Option<ArrayRef>)> {
+ match self {
+ RangeStats::Array { mins, maxs, .. } => Ok((mins.clone(), maxs.clone())),
+ RangeStats::Scalar { value, length } => {
+ let mins = value.to_array_of_size(*length)?;
+ let maxs = value.to_array_of_size(*length)?;
+ Ok((Some(mins), Some(maxs)))
+ }
+ }
+ }
+}
+
+pub struct PruningContext {
+ stats: Arc<dyn PruningStatistics + Send + Sync>,
+}
+
+impl PruningContext {
+ pub fn new(stats: Arc<dyn PruningStatistics + Send + Sync>) -> Self {
+ Self { stats }
+ }
+
+ pub fn statistics(&self) -> &Arc<dyn PruningStatistics + Send + Sync> {
+ &self.stats
+ }
+}
+
+impl NullStats {
+ /// Build `NullStats` from per-container null and row counts.
+ ///
+ /// # Arguments
+ /// - `null_counts`: All containers' null counts in a single `Array`, or `None` if missing.
+ /// - `row_counts`: All containers' row counts in a single `Array`, or `None` if missing.
+ ///
+ /// # Return
+ /// `Some(NullStats)` when both inputs are present and aligned; `None` when either input is missing/unknown.
+ ///
+ /// # Examples (per-container outcomes)
+ /// - `null_counts=[3, 0, 1]`, `row_counts=[3, 5, 10]` →
+ /// presence = [false, true, null] (AllNull, NoNull, Mixed).
+ ///
+ /// # Errors
+ /// - Internal error if inputs have inconsistent lengths.
+ pub fn new(
+ null_counts: Option<&UInt64Array>,
+ row_counts: Option<&UInt64Array>,
+ ) -> Result<Option<Self>> {
+ // If either input is absent, we can't derive null stats for all containers.
+ let (Some(null_counts), Some(row_counts)) = (null_counts, row_counts) else {
+ return Ok(None);
+ };
+
+ let length = null_counts.len();
+ assert_eq_or_internal_err!(
+ row_counts.len(),
+ length,
+ "Row counts length mismatch for pruning statistics"
+ );
+
+ let mut presence = BooleanBuilder::with_capacity(length);
+ for idx in 0..length {
+ let nulls = (!null_counts.is_null(idx)).then(|| null_counts.value(idx));
+ let rows = (!row_counts.is_null(idx)).then(|| row_counts.value(idx));
+
+ // See `NullStats` for encoding semantics
+ match (nulls, rows) {
+ (Some(0), Some(_)) | (Some(0), None) => presence.append_value(true),
+ (Some(n), Some(r)) if n == r => presence.append_value(false),
+ _ => presence.append_null(),
+ }
+ }
+
+ Ok(Some(Self {
+ presence: presence.finish(),
+ }))
+ }
+
+ /// Create a `NullStats` with a uniform `presence` repeated `num_containers` times.
+ /// See `NullStats` docs for `presence` semantics.
+ ///
+ /// Used to create pruning statistics literal/scalar values.
+ pub fn from_uniform_presence(presence: NullPresence, num_containers: usize) -> Self {
+ let presence_item = match presence {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ };
+ NullStats {
+ presence: BooleanArray::from_iter(repeat_n(presence_item, num_containers)),
+ }
+ }
+
+ /// Combine two null-stat arrays for a comparison (`=, !=, <, >, <=, >=`).
+ ///
+ /// None means all containers' null stats are missing, otherwise for each container:
+ /// - If either side is `AllNull` → result is `AllNull` (all comparisons are null).
+ /// - If both sides are `NoNull` → result is `NoNull`.
+ /// - Otherwise → result is `UnknownOrMixed`.
+ ///
+ /// # Errors
+ /// Returns internal error if left and right side has inconsistent container length
+ pub fn combine_for_cmp(
+ left: Option<&Self>,
+ right: Option<&Self>,
+ ) -> Result<Option<Self>> {
+ let (left, right) = match (left, right) {
+ (Some(l), Some(r)) => (l, r),
+ (_, _) => {
+ return Ok(None);
+ }
+ };
+
+ let len = left.len();
+ assert_eq_or_internal_err!(
+ len,
+ right.len(),
+ "Null stats length mismatch for comparison pruning"
+ );
+
+ // The function comments specified the semantics behavior, and given the
+ // physical encoding:
+ // `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+ // The implementation can be simplified to a kleene(null-aware) 'AND'
+ Ok(Some(NullStats {
+ presence: and_kleene(left.presence(), right.presence())?,
+ }))
+ }
+
+ pub fn len(&self) -> usize {
+ self.presence.len()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.presence.is_empty()
+ }
+
+ pub fn presence(&self) -> &BooleanArray {
+ &self.presence
+ }
+}
+
+impl ColumnStats {
+ pub fn new(
+ range_stats: Option<RangeStats>,
+ null_stats: Option<NullStats>,
+ num_containers: usize,
+ ) -> Self {
+ debug_assert_eq!(
+ range_stats
+ .as_ref()
+ .map(|r| r.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ debug_assert_eq!(
+ null_stats
+ .as_ref()
+ .map(|n| n.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ range_stats,
+ null_stats,
+ num_containers,
+ }
+ }
+
+ pub fn range_stats(&self) -> Option<&RangeStats> {
+ self.range_stats.as_ref()
+ }
+
+ pub fn null_stats(&self) -> Option<&NullStats> {
+ self.null_stats.as_ref()
+ }
+
+ pub fn len(&self) -> usize {
+ self.num_containers
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.num_containers == 0
+ }
+}
+
+/// Pruning intermediate type propagated through `PhysicalExpr` nodes.
Review Comment:
Using `BooleanArray` I think will make handling all other expressions easier -- implementations of each expression will not have to pick between results or ranges, they will all use statistics
With some wrappers to interpret BooleanArray I think the APis could be quite nice
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681656047
##########
datafusion/physical-expr-common/src/physical_expr/statistics_vectorized.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
Review Comment:
Added a link in [6741a2a](https://github.com/apache/datafusion/pull/19609/commits/6741a2abd1466eaf25f9799d052345a6c6753976)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #19609: feat: Prune complex/nested predicates via statistics propagation
URL: https://github.com/apache/datafusion/pull/19609
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #19609: feat: Prune complex/nested predicates via statistics propagation
URL: https://github.com/apache/datafusion/pull/19609
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681634077
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ },
+ /// Represents a uniform literal value across all containers.
+ /// This variant make it easy to compare between literals and normal ranges representing
+ /// each containers' value range.
+ Scalar { value: ScalarValue, length: usize },
+}
+
+/// Null-related statistics for each container stored as a BooleanArray:
+/// `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+/// `NullPresence` provides utility to convert between its semantics representation
+/// and physical encoding.
+#[derive(Debug, Clone)]
+pub struct NullStats {
+ presence: BooleanArray,
+}
+
+/// Semantic representation for items inside `NullStats::presence`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum NullPresence {
+ NoNull,
+ AllNull,
+ UnknownOrMixed,
+}
+
+impl NullPresence {
+ /// Convert to/from the tri-state boolean encoding stored in `NullStats.presence`
+ /// - Some(true)=NoNull
+ /// - Some(false)=AllNull
+ /// - None=(Unknown/mixed)
+ pub fn from_presence_item(presence_item: Option<bool>) -> Self {
+ match presence_item {
+ Some(true) => NullPresence::NoNull,
+ Some(false) => NullPresence::AllNull,
+ None => NullPresence::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_presence_item(&self) -> Option<bool> {
+ match self {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ }
+ }
+}
+
+/// Column statistics that propagate through the `PhysicalExpr` tree nodes
+///
+/// # Important invariants
+/// Non-null stats (e.g., ranges) describe only the value bounds for non-null
+/// rows; they DO NOT include nulls. For example, a partition with `min=0,
+/// max=10` may still contain nulls outside that range. Predicate pruning must
+/// combine decisions from non-null stats with null stats to derive the final
+/// outcome.
+#[derive(Debug, Clone)]
+pub struct ColumnStats {
+ pub range_stats: Option<RangeStats>,
+ pub null_stats: Option<NullStats>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+impl RangeStats {
+ pub fn new(
+ mins: Option<ArrayRef>,
+ maxs: Option<ArrayRef>,
+ length: usize,
+ ) -> Result<Self> {
+ if let Some(ref mins) = mins {
+ assert_eq_or_internal_err!(
+ mins.len(),
+ length,
+ "Range mins length mismatch for pruning statistics"
+ );
+ }
+ if let Some(ref maxs) = maxs {
+ assert_eq_or_internal_err!(
+ maxs.len(),
+ length,
+ "Range maxs length mismatch for pruning statistics"
+ );
+ }
+ Ok(Self::Array { mins, maxs, length })
+ }
+
+ /// Create range stats for a constant literal across all containers.
+ pub fn new_scalar(value: ScalarValue, length: usize) -> Result<Self> {
+ Ok(Self::Scalar { value, length })
+ }
+
+ pub fn len(&self) -> usize {
+ match self {
+ RangeStats::Array { length, .. } | RangeStats::Scalar { length, .. } => {
+ *length
+ }
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// Normalize into concrete min/max arrays.
+ ///
+ /// For `Array`, returns cloned mins/maxs (which may be `None`).
+ /// For `Scalar`, expands the scalar to arrays of length `length`.
+ pub fn normalize_to_arrays(&self) -> Result<(Option<ArrayRef>, Option<ArrayRef>)> {
+ match self {
+ RangeStats::Array { mins, maxs, .. } => Ok((mins.clone(), maxs.clone())),
+ RangeStats::Scalar { value, length } => {
+ let mins = value.to_array_of_size(*length)?;
+ let maxs = value.to_array_of_size(*length)?;
+ Ok((Some(mins), Some(maxs)))
+ }
+ }
+ }
+}
+
+pub struct PruningContext {
+ stats: Arc<dyn PruningStatistics + Send + Sync>,
+}
+
+impl PruningContext {
+ pub fn new(stats: Arc<dyn PruningStatistics + Send + Sync>) -> Self {
+ Self { stats }
+ }
+
+ pub fn statistics(&self) -> &Arc<dyn PruningStatistics + Send + Sync> {
+ &self.stats
+ }
+}
+
+impl NullStats {
+ /// Build `NullStats` from per-container null and row counts.
+ ///
+ /// # Arguments
+ /// - `null_counts`: All containers' null counts in a single `Array`, or `None` if missing.
+ /// - `row_counts`: All containers' row counts in a single `Array`, or `None` if missing.
+ ///
+ /// # Return
+ /// `Some(NullStats)` when both inputs are present and aligned; `None` when either input is missing/unknown.
+ ///
+ /// # Examples (per-container outcomes)
+ /// - `null_counts=[3, 0, 1]`, `row_counts=[3, 5, 10]` →
+ /// presence = [false, true, null] (AllNull, NoNull, Mixed).
+ ///
+ /// # Errors
+ /// - Internal error if inputs have inconsistent lengths.
+ pub fn new(
+ null_counts: Option<&UInt64Array>,
+ row_counts: Option<&UInt64Array>,
+ ) -> Result<Option<Self>> {
+ // If either input is absent, we can't derive null stats for all containers.
+ let (Some(null_counts), Some(row_counts)) = (null_counts, row_counts) else {
+ return Ok(None);
+ };
+
+ let length = null_counts.len();
+ assert_eq_or_internal_err!(
+ row_counts.len(),
+ length,
+ "Row counts length mismatch for pruning statistics"
+ );
+
+ let mut presence = BooleanBuilder::with_capacity(length);
+ for idx in 0..length {
+ let nulls = (!null_counts.is_null(idx)).then(|| null_counts.value(idx));
+ let rows = (!row_counts.is_null(idx)).then(|| row_counts.value(idx));
+
+ // See `NullStats` for encoding semantics
+ match (nulls, rows) {
+ (Some(0), Some(_)) | (Some(0), None) => presence.append_value(true),
+ (Some(n), Some(r)) if n == r => presence.append_value(false),
+ _ => presence.append_null(),
+ }
+ }
+
+ Ok(Some(Self {
+ presence: presence.finish(),
+ }))
+ }
+
+ /// Create a `NullStats` with a uniform `presence` repeated `num_containers` times.
+ /// See `NullStats` docs for `presence` semantics.
+ ///
+ /// Used to create pruning statistics literal/scalar values.
+ pub fn from_uniform_presence(presence: NullPresence, num_containers: usize) -> Self {
+ let presence_item = match presence {
+ NullPresence::NoNull => Some(true),
+ NullPresence::AllNull => Some(false),
+ NullPresence::UnknownOrMixed => None,
+ };
+ NullStats {
+ presence: BooleanArray::from_iter(repeat_n(presence_item, num_containers)),
+ }
+ }
+
+ /// Combine two null-stat arrays for a comparison (`=, !=, <, >, <=, >=`).
+ ///
+ /// None means all containers' null stats are missing, otherwise for each container:
+ /// - If either side is `AllNull` → result is `AllNull` (all comparisons are null).
+ /// - If both sides are `NoNull` → result is `NoNull`.
+ /// - Otherwise → result is `UnknownOrMixed`.
+ ///
+ /// # Errors
+ /// Returns internal error if left and right side has inconsistent container length
+ pub fn combine_for_cmp(
+ left: Option<&Self>,
+ right: Option<&Self>,
+ ) -> Result<Option<Self>> {
+ let (left, right) = match (left, right) {
+ (Some(l), Some(r)) => (l, r),
+ (_, _) => {
+ return Ok(None);
+ }
+ };
+
+ let len = left.len();
+ assert_eq_or_internal_err!(
+ len,
+ right.len(),
+ "Null stats length mismatch for comparison pruning"
+ );
+
+ // The function comments specified the semantics behavior, and given the
+ // physical encoding:
+ // `true` = NoNull, `false` = AllNull, `null` = Unknown/mixed.
+ // The implementation can be simplified to a kleene(null-aware) 'AND'
+ Ok(Some(NullStats {
+ presence: and_kleene(left.presence(), right.presence())?,
+ }))
+ }
+
+ pub fn len(&self) -> usize {
+ self.presence.len()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.presence.is_empty()
+ }
+
+ pub fn presence(&self) -> &BooleanArray {
+ &self.presence
+ }
+}
+
+impl ColumnStats {
+ pub fn new(
+ range_stats: Option<RangeStats>,
+ null_stats: Option<NullStats>,
+ num_containers: usize,
+ ) -> Self {
+ debug_assert_eq!(
+ range_stats
+ .as_ref()
+ .map(|r| r.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ debug_assert_eq!(
+ null_stats
+ .as_ref()
+ .map(|n| n.len())
+ .unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ range_stats,
+ null_stats,
+ num_containers,
+ }
+ }
+
+ pub fn range_stats(&self) -> Option<&RangeStats> {
+ self.range_stats.as_ref()
+ }
+
+ pub fn null_stats(&self) -> Option<&NullStats> {
+ self.null_stats.as_ref()
+ }
+
+ pub fn len(&self) -> usize {
+ self.num_containers
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.num_containers == 0
+ }
+}
+
+/// Pruning intermediate type propagated through `PhysicalExpr` nodes.
Review Comment:
I thought about it carefully again, and I don’t think it is actually simpler.
It does reduce the number of lines of code for most arithmetic expressions. However, for predicate expressions, we still have to inspect the semantic meaning inside column statistics. This is not really “eliminating a special case by definition”; rather, it is trying to encode multiple concepts into a single struct. I think the downside of this approach is that it weakens type safety and also makes predicate nodes harder to reason about.
To simplify implementation and avoid repetitive checking enum variant, probably we can add some utility functions.
```rust
#[derive(Debug, Clone)]
pub struct ColumnStats {
pub range_stats: Option<RangeStats>,
pub null_stats: Option<NullStats>,
pub evaluate_results: Option<BooleanArray>, // <--- Change here. We are adding an implicit constraint that
// if this is Some, then this node no longer represents
// statistics, and all other stat fields must be None.
/// Number of containers. Needed to infer result if all stats types are `None`.
pub num_containers: usize,
}
```
Another consideration is that we might want a parent `enum` in the future for extensibility. It could be used to pass control information if we want to implement certain optimizations, or if we want to unify this PR’s stat propagation API with the existing ones, where additional intermediate stat variants may be needed.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681671408
##########
datafusion/physical-expr-common/src/physical_expr/pruning.rs:
##########
@@ -0,0 +1,539 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Pruner Common Structs/Utilities
+
+//! This is the top-level comment for pruning via statistics propagation.
+//!
+//! TODO: This is a concise draft; it should be polished for readers with less
+//! prior background.
+//!
+//! # Introduction
+//!
+//! This module helps skip scanning data micro-partitions by evaluating predicates
+//! against container-level statistics.
+//!
+//! It supports pruning for complex and nested predicates through statistics
+//! propagation.
+//!
+//! For examples of pruning nested predicates via statistics propagation, see:
+//! <https://github.com/apache/datafusion/issues/19487>
+//!
+//!
+//!
+//! # Vectorized pruning intermediate representation
+//!
+//! Source statistics and intermediate pruning results are stored in Arrow arrays,
+//! enabling vectorized evaluation across many containers.
+//!
+//!
+//!
+//! # Difference from [`super::PhysicalExpr::evaluate_bounds`]
+//!
+//! `evaluate_bounds()` derives per-column statistics for a single plan, aimed at
+//! tasks like cardinality estimation and other planner fast paths. It reasons
+//! about one container and may track richer distribution details.
+//! Pruning must reason about *all* containers (potentially thousands) to decide
+//! which to skip, so it favors a vectorized, array-backed representation with
+//! lighter-weight stats. These are intentionally separate interfaces.
+//!
+//!
+//!
+//! # Core API/Data Structures
+//!
+//! The key structures involved in pruning are:
+//! - [`PruningStatistics`]: the input source statistics for all containers
+//! - [`super::PhysicalExpr::evaluate_pruning()`]: evaluates pruning behavior for predicates
+//! - [`PruningIntermediate`]: the intermediate result produced during statistics propagation for pruning. Its internal representation uses Arrow Arrays, enabling vectorized evaluation for performance.
+
+use std::{iter::repeat_n, sync::Arc};
+
+use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBuilder, UInt64Array};
+use arrow::compute::kernels::boolean::and_kleene;
+use datafusion_common::pruning::PruningStatistics;
+use datafusion_common::{Result, ScalarValue, assert_eq_or_internal_err};
+
+/// Physical representation of pruning outcomes for each container:
+/// `true` = KeepAll, `false` = SkipAll, `null` = Unknown.
+///
+/// Use `BooleanArray` so the propagation steps can use existing Arrow kernels for
+/// both simplicity and performance.
+///
+/// # Pruning results
+/// - KeepAll: The pruning predicate evaluates to true for all rows within a micro
+/// partition. Future filter evaluation can be skipped for that partition.
+/// - SkipAll: The pruning predicate evaluates to false for all rows within a micro
+/// partition. The partition can be skipped at scan time.
+/// - UnknownOrMixed: The statistics are insufficient to prove KeepAll/SkipAll, or
+/// the predicate is mixed. The predicate must be evaluated row-wise.
+///
+/// Example (`SELECT * FROM t WHERE x >= 0`):
+/// - micro_partition_a(min=0, max=10): KeepAll — can pass through `FilterExec`
+/// without re-evaluating `x >= 0`.
+/// - micro_partition_b(min=-10, max=-1): SkipAll — skip the partition entirely.
+/// - micro_partition_c(min=-5, max=5): Unknown — must evaluate the predicate on rows.
+///
+/// `PruningOutcome` provides utilities to convert between this semantic
+/// representation and its tri-state boolean encoding.
+///
+/// # Important invariants
+/// Pruning results must be sound, but need not be complete:
+/// - If a container is labeled `KeepAll` or `SkipAll`, that label must be correct.
+/// - If a container is labeled `Unknown` but is actually `KeepAll`/`SkipAll`,
+/// correctness is still preserved; it just means pruning was conservative.
+///
+/// Propagation implementation can be refined to reduce `Unknown` cases to improve
+/// pruning effectiveness.
+#[derive(Debug, Clone)]
+pub struct PruningResults {
+ results: Option<BooleanArray>,
+ /// Number of containers. Needed to infer result if all stats types are `None`.
+ pub num_containers: usize,
+}
+
+/// Semantic representation for items inside `PruningResults::results`.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum PruningOutcome {
+ KeepAll,
+ SkipAll,
+ UnknownOrMixed,
+}
+
+impl PruningResults {
+ pub fn new(array: Option<BooleanArray>, num_containers: usize) -> Self {
+ debug_assert_eq!(
+ array.as_ref().map(|a| a.len()).unwrap_or(num_containers),
+ num_containers
+ );
+ Self {
+ results: array,
+ num_containers,
+ }
+ }
+
+ pub fn none(num_containers: usize) -> Self {
+ Self::new(None, num_containers)
+ }
+
+ pub fn as_ref(&self) -> Option<&BooleanArray> {
+ self.results.as_ref()
+ }
+
+ pub fn into_inner(self) -> Option<BooleanArray> {
+ self.results
+ }
+
+ pub fn len(&self) -> usize {
+ self.results
+ .as_ref()
+ .map(|a| a.len())
+ .unwrap_or(self.num_containers)
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+}
+
+impl PruningOutcome {
+ /// Convert to/from the tri-state boolean encoding stored in `PruningResults`.
+ /// - Some(true)=KeepAll
+ /// - Some(false)=SkipAll
+ /// - None=(Unknown/mixed)
+ pub fn from_result_item(result_item: Option<bool>) -> Self {
+ match result_item {
+ Some(true) => PruningOutcome::KeepAll,
+ Some(false) => PruningOutcome::SkipAll,
+ None => PruningOutcome::UnknownOrMixed,
+ }
+ }
+
+ pub fn to_result_item(&self) -> Option<bool> {
+ match self {
+ PruningOutcome::KeepAll => Some(true),
+ PruningOutcome::SkipAll => Some(false),
+ PruningOutcome::UnknownOrMixed => None,
+ }
+ }
+}
+
+impl From<BooleanArray> for PruningResults {
+ fn from(array: BooleanArray) -> Self {
+ let len = array.len();
+ PruningResults::new(Some(array), len)
+ }
+}
+
+#[derive(Debug, Clone)]
+pub enum RangeStats {
+ /// Ranges for all containers in array form.
+ /// - If `mins`/`maxs` are `None`, all containers have unknown statistics.
+ /// - Each entry (per-container) may be a bound or null. Null means missing or
+ /// unbounded (null in `mins` = -inf; treating missing/unbounded the same
+ /// does not change pruning results).
+ Array {
+ mins: Option<ArrayRef>,
Review Comment:
refactored in [5140c98](https://github.com/apache/datafusion/pull/19609/commits/5140c98e1ee50336fb4a109dcf64c0ebd13dfdf0)
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2681652778
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -746,6 +968,106 @@ fn check_short_circuit<'a>(
ShortCircuitStrategy::None
}
+/// For expressions like `left OP right`, calculate the `PruningOutcome` given child
+/// expression's range statistics, and operator type.
+///
+/// The supported operators are: >, <, =, >=, <=
+///
+/// Bounds encoding: each bound uses an `Option` to encode a NULL range value;
+/// `None` means the bound is NULL, and `Some` must contain a non-null `ScalarValue`.
+/// This is due to the existing ScalarValue comparison having unexpected null behavior:
+/// <https://github.com/apache/datafusion/issues/19579>
+///
+/// Type compatibility: if all bound data types are not equal, return
+/// `PruningOutcome::UnknownOrMixed` as a safe fallback. For different but
+/// compatible types (e.g., lhs is Int32, rhs is Int64), the type coercion
+/// optimizer rule should already handle them before evaluating pruning.
+///
+/// # Errors
+/// Returns Internal Error if unsupported operator is provided.
+fn compare_ranges(
Review Comment:
I have checked, it has reached 100% test line coverage by
```
cargo +nightly llvm-cov \
--package datafusion-physical-expr \
--test pruning \
--all-features \
--html \
--open \
-- --nocapture
```
Though it's covered by higher-level pruning API tests, not the UT directly on it. The benefit is the test coverage won't be lost when we change the implementation to a vectorized `compare_ranges_vectorized`
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#discussion_r2676834118
##########
datafusion/physical-expr-common/src/physical_expr.rs:
##########
@@ -430,6 +437,36 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
fn is_volatile_node(&self) -> bool {
false
}
+
+ /// Evaluates pruning statistics via propagation. See the pruning module
Review Comment:
If the only thing it will ever be used for is pruning then putting pruning in the name makes sense
I still have (not so) secret hopes, that we can somehow unify these range / expression analysis APIs as they all seem so similar in theory
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3727624481
> I didn't have time yet to look at this big PR, but I looked at the issue and design. As a general thought I think replacing the `evaluate_bounds`/`propagate_constraints` duo will not be easy. The `Interval` library makes very careful calculations w.r.t. things like rounding (with floats etc.), because their results are used to take branches in contexts like pruning join hash tables that may operate on data like floats. Support for such rounding-aware calculations were not present in `arrow-rs` at the time when we created these APIs (and still not here if I'm not missing something).
This is a really good point. I didn't consider rounding safety so far, I'll make sure to include them in the vectorized version also.
By the way, do you have any references on the high-level ideas behind “join pruning,” and why we need the inverse path (`propagate_constraints()`)? @ozankabak Just out of my curiosity.
Thanks for the context. For now, I think we shouldn’t touch the existing statistics propagation APIs and should introduce a vectorized one in this work. I’ll add more documentation to explain the rationale.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: Prune complex/nested predicates via statistics propagation [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #19609:
URL: https://github.com/apache/datafusion/pull/19609#issuecomment-3725389839
FYI @ozankabak and @berkaysynnada as you have been instrumental in previous versions of statistics and range analysis
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org