You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "asolimando (via GitHub)" <gi...@apache.org> on 2026/01/23 17:55:26 UTC
[PR] feat: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
asolimando opened a new pull request, #19957:
URL: https://github.com/apache/datafusion/pull/19957
## Which issue does this PR close?
- Part of #15265
Related: #18628, #8227
(I am not sure if an new issue specifically for the scope of the PR is needed, happy to create it if needed)
<!--
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.
-->
## 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.
-->
This work originates from a discussion in datafusion-distributed about improving the `TaskEstimator` API:
https://github.com/datafusion-contrib/datafusion-distributed/issues/296#issuecomment-3777726928
We agreed that improved statistics support in DataFusion would benefit both projects. For distributed-datafusion, better cardinality estimation helps decide how to split computation across network boundaries.
This also benefits DataFusion directly, as CBO is already in place, for example, join cardinality estimation ([`joins/utils.rs:586-646`](https://github.com/apache/datafusion/blob/main/datafusion/physical-plan/src/joins/utils.rs#L586-L646)) uses `distinct_count` via `max_distinct_count` to compute join selectivity.
Currently this field is always `Absent` when reading from Parquet, so this PR fills that gap.
## 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.
-->
Commit 1 - Reading NDV from Parquet files:
- Extract `distinct_count` from Parquet row group column statistics
- Single row group with NDV -> `Precision::Exact(ndv)`
- Multiple row groups with NDV -> `Precision::Inexact(max)` as conservative lower bound
- No NDV available -> `Precision::Absent`
Commit 2 - Statistics propagation (can be split to a separate PR, if preferred):
- `Statistics::try_merge()`: use max as conservative lower bound instead of discarding NDV
- `Projection`: preserve NDV for single-column expressions as upper bound
I'm including the second commit to showcase how I intend to use the statistics, but these changes can be split to a follow-up PR to keep review scope limited.
## 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)?
-->
Yes, 7 unit tests are added for NDV extraction:
- Single/multiple row groups with NDV
- Partial NDV availability across row groups
- Multiple columns with different NDV values
- Integration test reading a real Parquet file with distinct_count statistics (following the pattern in
[`row_filter.rs:685-696`](https://github.com/apache/datafusion/blob/main/datafusion/datasource-parquet/src/row_filter.rs#L685-L696), using `parquet_to_arrow_schema` to derive the schema from the file)
## Are there any user-facing changes?
<!--
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.
-->
No breaking changes. Statistics consumers will now see populated `distinct_count` values when available in Parquet metadata.
Disclaimer: I used AI (Claude Code) to assist translating my ideas into code as I am still ramping up with the codebase and especially with Rust (guidance on both aspects is highly appreciated). I have a good understanding of the core concepts (statistics, CBO etc.) and have carefully double-checked that the PR matches my intentions and understanding.
cc: @gabotechs @jayshrivastava @NGA-TRAN @gene-bordegaray
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2728830062
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Good question! I have an idea of how this could evolve, based on my experience with Apache Calcite.
The idea is to make statistics propagation pluggable, with each relational operator having a default but configurable logic for how statistics propagate through it.
The default implementation would follow classic Selinger-style estimation (selectivity factors, independence assumptions), as seen in this PR. A nice intro to this can be found [here](https://15799.courses.cs.cmu.edu/spring2025/slides/13-cardinalities1.pdf). That's what most OSS databases implement by default.
Following DataFusion's philosophy as a customizable framework, users should be able to override and complement this logic when needed.
Proposed architecture:
- `StatisticsProvider`: chain element that computes statistics for specific operators (returns `Computed` or `Delegate`)
- `StatisticsRegistry`: chains providers, would live in `SessionState`
- `CardinalityEstimator`: unified interface for metadata queries (row count, selectivity, NDV, ...) - similar to Calcite's [RelMetadataProvider](https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/metadata/RelMetadataProvider.html)/[RelMetadataQuery](https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/metadata/RelMetadataQuery.html)
- `ExtendedStatistics`: `Statistics` with type-safe custom extensions for histograms, sketches, etc. (I am looking at type-erased maps for that but I am not sure that's the best way to implement it)
- `ExpressionAnalyzerRegistry`+`ExpressionAnalyzer`: similar concept of chain for expression analyzers, equivalent to what detailed above for the operators, so that built-in and UDF can be covered
This follows the same chain-of-responsibility pattern that the https://datafusion.apache.org/blog/2026/01/12/extending-sql/ solved for custom syntax/relations. Built-in operators get default handling, custom `ExecutionPlan` nodes can plug in their own logic, and unknown cases delegate down the chain. To override the default estimation (e.g., with histogram-based approaches), you register your provider before the default one.
StatisticsV2 and Distribution-based are very advanced and interesting statistics, but I see them more as an extension via `ExtendedStatistics` than taking over the default implementation. What you are wondering about NDVs, for instance, is correct, it deals with distributions but as-is it can't answer question around number of distinct values.
If this sounds interesting and aligns with community interest, I can provide a more detailed design doc and an epic to break down the work.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2736292455
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
The new constructs are an extensibility layer that builds on top of the existing methods rather than replacing them.
For instance, the `DefaultStatisticsProvider` will simply delegate to `partition_statistics()`.
The key difference is that by adopting `StatisticsProvider`/`StatisticsRegistry` pattern, the user can:
- Register custom providers for custom operators without trait changes
- Override default estimation for specific (even built-in) operators
- Carry extended statistics (histograms, sketches) through `ExtendedStatistics`
Similarly, `PhysicalExpr::evaluate_statistics()` will be the default for `ExpressionAnalyzer`, but it will allow to override the behavior for built-in expressions, and it will easily provide an extension point for user-defined functions.
I totally understand the concern about the blast radius, but if there is consensus on doubling down on statistics and CBO (by making them more effective in driving planning decisions, when stats are available), it will become necessary to provide flexibility to override and extend for people implementing on top of DataFusion, to steer planning decisions as the user sees fit.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2897571210
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
Review Comment:
nit: When called in projection.rs this is doing vec + 4 arc allocations. I think we can pass this in through sessioncontext to avoid initializing for every expression
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -541,6 +541,36 @@ fn summarize_min_max_null_counts(
)
.map(|(idx, _)| idx);
+ // Extract distinct counts from row group column statistics
+ accumulators.distinct_counts_array[logical_schema_index] =
+ if let Some(parquet_idx) = parquet_index {
+ let distinct_counts: Vec<u64> = row_groups_metadata
+ .iter()
+ .filter_map(|rg| {
+ rg.columns()
+ .get(parquet_idx)
+ .and_then(|col| col.statistics())
+ .and_then(|stats| stats.distinct_count_opt())
+ })
+ .collect();
+
+ if distinct_counts.is_empty() {
+ Precision::Absent
+ } else if distinct_counts.len() == 1 {
Review Comment:
If we are merging multiple row groups and only one of them have NDV, then it will trigger this path and assign that distinct_count to statistics despite having many unknown NDVs.
There are two scenarios here:
large fraction of ndvs missing from row groups -> return Absent
only a small fraction NDVs missing from row groups -> return inexact
What the fraction should be is debatable, maybe like 1/4 or something
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
+ Self {
+ analyzers: vec![
+ Arc::new(StringFunctionAnalyzer),
+ Arc::new(MathFunctionAnalyzer),
+ Arc::new(DateTimeFunctionAnalyzer),
+ Arc::new(DefaultExpressionAnalyzer),
+ ],
+ }
+ }
+
+ /// Create a registry with custom analyzers (no default).
+ pub fn with_analyzers(analyzers: Vec<Arc<dyn ExpressionAnalyzer>>) -> Self {
+ Self { analyzers }
+ }
+
+ /// Create a registry with custom analyzers plus default as fallback.
+ pub fn with_analyzers_and_default(
+ analyzers: impl IntoIterator<Item = Arc<dyn ExpressionAnalyzer>>,
+ ) -> Self {
+ let mut all: Vec<Arc<dyn ExpressionAnalyzer>> = analyzers.into_iter().collect();
+ all.push(Arc::new(DefaultExpressionAnalyzer));
+ Self { analyzers: all }
+ }
+
+ /// Register an analyzer at the front of the chain (higher priority).
+ pub fn register(&mut self, analyzer: Arc<dyn ExpressionAnalyzer>) {
+ self.analyzers.insert(0, analyzer);
+ }
+
+ /// Get selectivity through the analyzer chain.
+ pub fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(sel) =
+ analyzer.get_selectivity(expr, input_stats)
+ {
+ return Some(sel);
+ }
+ }
+ None
+ }
+
+ /// Get distinct count through the analyzer chain.
+ pub fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<usize> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(ndv) =
+ analyzer.get_distinct_count(expr, input_stats)
+ {
+ return Some(ndv);
+ }
+ }
+ None
+ }
+
+ /// Get min/max bounds through the analyzer chain.
+ pub fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<(ScalarValue, ScalarValue)> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(bounds) =
+ analyzer.get_min_max(expr, input_stats)
+ {
+ return Some(bounds);
+ }
+ }
+ None
+ }
+
+ /// Get null fraction through the analyzer chain.
+ pub fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(frac) =
+ analyzer.get_null_fraction(expr, input_stats)
+ {
+ return Some(frac);
+ }
+ }
+ None
+ }
+}
+
+// ============================================================================
+// DefaultExpressionAnalyzer
+// ============================================================================
+
+/// Default expression analyzer with Selinger-style estimation.
+///
+/// Handles common expression types:
+/// - Column references (uses column statistics)
+/// - Binary expressions (AND, OR, comparison operators)
+/// - Literals (constant selectivity/NDV)
+/// - NOT expressions (1 - child selectivity)
+#[derive(Debug, Default, Clone)]
+pub struct DefaultExpressionAnalyzer;
+
+impl DefaultExpressionAnalyzer {
+ /// Get column index from a Column expression
+ fn get_column_index(expr: &Arc<dyn PhysicalExpr>) -> Option<usize> {
+ expr.as_any().downcast_ref::<Column>().map(|c| c.index())
+ }
+
+ /// Get column statistics for an expression if it's a column reference
+ fn get_column_stats<'a>(
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &'a Statistics,
+ ) -> Option<&'a ColumnStatistics> {
+ Self::get_column_index(expr)
+ .and_then(|idx| input_stats.column_statistics.get(idx))
+ }
+
+ /// Recursive selectivity estimation
+ fn estimate_selectivity_recursive(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> f64 {
+ if let AnalysisResult::Computed(sel) = self.get_selectivity(expr, input_stats) {
+ return sel;
+ }
+ 0.5 // Default fallback
+ }
+}
+
+impl ExpressionAnalyzer for DefaultExpressionAnalyzer {
+ fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Binary expressions: AND, OR, comparisons
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let left_sel =
+ self.estimate_selectivity_recursive(binary.left(), input_stats);
+ let right_sel =
+ self.estimate_selectivity_recursive(binary.right(), input_stats);
+
+ let sel = match binary.op() {
+ // Logical operators
+ Operator::And => left_sel * right_sel,
+ Operator::Or => left_sel + right_sel - (left_sel * right_sel),
+
+ // Equality: selectivity = 1/NDV
+ Operator::Eq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 / (*ndv as f64));
+ }
+ 0.1 // Default equality selectivity
+ }
+
+ // Inequality: selectivity = 1 - 1/NDV
+ Operator::NotEq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 - (1.0 / (*ndv as f64)));
+ }
+ 0.9
+ }
+
+ // Range predicates: classic 1/3 estimate
+ Operator::Lt | Operator::LtEq | Operator::Gt | Operator::GtEq => 0.33,
+
+ // LIKE: depends on pattern, use conservative estimate
+ Operator::LikeMatch | Operator::ILikeMatch => 0.25,
+ Operator::NotLikeMatch | Operator::NotILikeMatch => 0.75,
+
+ // Other operators: default
+ _ => 0.5,
+ };
+
+ return AnalysisResult::Computed(sel);
+ }
+
+ // NOT expression: 1 - child selectivity
+ if let Some(not_expr) = expr.as_any().downcast_ref::<NotExpr>() {
+ let child_sel =
+ self.estimate_selectivity_recursive(not_expr.arg(), input_stats);
+ return AnalysisResult::Computed(1.0 - child_sel);
+ }
+
+ // Literal boolean: 0.0 or 1.0
+ if let Some(b) = expr
+ .as_any()
+ .downcast_ref::<Literal>()
+ .and_then(|lit| match lit.value() {
+ ScalarValue::Boolean(Some(b)) => Some(*b),
+ _ => None,
+ })
+ {
+ return AnalysisResult::Computed(if b { 1.0 } else { 0.0 });
+ }
+
+ // Column reference as predicate (boolean column)
+ if expr.as_any().downcast_ref::<Column>().is_some() {
+ return AnalysisResult::Computed(0.5);
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ // Column reference: use column NDV
+ if let Some(ndv) = Self::get_column_stats(expr, input_stats)
+ .and_then(|col_stats| col_stats.distinct_count.get_value().copied())
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+
+ // Literal: NDV = 1
+ if expr.as_any().downcast_ref::<Literal>().is_some() {
+ return AnalysisResult::Computed(1);
+ }
+
+ // BinaryExpr: for injective operations (arithmetic with literal), preserve NDV
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let is_arithmetic = matches!(
+ binary.op(),
+ Operator::Plus
+ | Operator::Minus
+ | Operator::Multiply
+ | Operator::Divide
+ | Operator::Modulo
+ );
+
+ if is_arithmetic {
+ // If one side is a literal, the operation is injective on the other side
+ let left_is_literal = binary.left().as_any().is::<Literal>();
+ let right_is_literal = binary.right().as_any().is::<Literal>();
+
+ if left_is_literal {
+ // NDV comes from right side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.right(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ } else if right_is_literal {
+ // NDV comes from left side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.left(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ }
+ // Both sides are non-literals: could combine, but delegate for now
+ }
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ // Column reference: use column min/max
+ if let Some((min, max)) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ match (
+ col_stats.min_value.get_value(),
+ col_stats.max_value.get_value(),
+ ) {
+ (Some(min), Some(max)) => Some((min.clone(), max.clone())),
+ _ => None,
+ }
+ })
+ {
+ return AnalysisResult::Computed((min, max));
+ }
+
+ // Literal: min = max = value
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let val = lit_expr.value().clone();
+ return AnalysisResult::Computed((val.clone(), val));
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Column reference: null_count / num_rows
+ if let Some(fraction) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ let null_count = col_stats.null_count.get_value().copied()?;
+ let num_rows = input_stats.num_rows.get_value().copied()?;
+ if num_rows > 0 {
+ Some(null_count as f64 / num_rows as f64)
+ } else {
+ None
+ }
+ })
+ {
+ return AnalysisResult::Computed(fraction);
+ }
+
+ // Literal: null fraction depends on whether it's null
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let is_null = lit_expr.value().is_null();
+ return AnalysisResult::Computed(if is_null { 1.0 } else { 0.0 });
+ }
+
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// StringFunctionAnalyzer
+// ============================================================================
+
+/// Analyzer for string functions.
+///
+/// - Injective (preserve NDV): UPPER, LOWER, TRIM, LTRIM, RTRIM, REVERSE
+/// - Non-injective (reduce NDV): SUBSTRING, LEFT, RIGHT, REPLACE
+#[derive(Debug, Default, Clone)]
+pub struct StringFunctionAnalyzer;
+
+impl StringFunctionAnalyzer {
+ /// Check if a function is injective (one-to-one)
+ pub fn is_injective(func_name: &str) -> bool {
+ matches!(
+ func_name.to_uppercase().as_str(),
+ "UPPER" | "LOWER" | "TRIM" | "LTRIM" | "RTRIM" | "REVERSE" | "INITCAP"
+ )
+ }
+
+ /// Get NDV reduction factor for non-injective functions
+ pub fn ndv_reduction_factor(func_name: &str) -> Option<f64> {
+ match func_name.to_uppercase().as_str() {
+ "SUBSTRING" | "LEFT" | "RIGHT" => Some(0.5),
+ "REPLACE" => Some(0.8),
+ _ => None,
+ }
+ }
+}
+
+impl ExpressionAnalyzer for StringFunctionAnalyzer {
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ let Some(func) = expr.as_any().downcast_ref::<ScalarFunctionExpr>() else {
+ return AnalysisResult::Delegate;
+ };
+
+ let func_name = func.name();
+ let Some(first_arg) = func.args().first() else {
+ return AnalysisResult::Delegate;
+ };
+
+ // Get input NDV
+ let Some(input_ndv) = DefaultExpressionAnalyzer
Review Comment:
For this API using DefaultExpressionAnalyzer here might not be what we want
If i had `impl ExpressionAnalyzer for InsertNewNDV` the problem is that I would have to handle all the cases with different column functions (ex. UPPER, LOWER, etc.), leading to a lot of duplicate functionality. Instead what if we pass in the list of analyzers here is that instead of `DefaultExpressionAnalyzer.get_distinct_count` we can call `analyzer_list[0].get_distinct_count` or something.
So if we add a custom analyzer to change the input NDV with our own statistics (ex. histogram), we do not need to reimplement the other functionality
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
+ Self {
+ analyzers: vec![
+ Arc::new(StringFunctionAnalyzer),
+ Arc::new(MathFunctionAnalyzer),
+ Arc::new(DateTimeFunctionAnalyzer),
+ Arc::new(DefaultExpressionAnalyzer),
+ ],
+ }
+ }
+
+ /// Create a registry with custom analyzers (no default).
+ pub fn with_analyzers(analyzers: Vec<Arc<dyn ExpressionAnalyzer>>) -> Self {
+ Self { analyzers }
+ }
+
+ /// Create a registry with custom analyzers plus default as fallback.
+ pub fn with_analyzers_and_default(
+ analyzers: impl IntoIterator<Item = Arc<dyn ExpressionAnalyzer>>,
+ ) -> Self {
+ let mut all: Vec<Arc<dyn ExpressionAnalyzer>> = analyzers.into_iter().collect();
+ all.push(Arc::new(DefaultExpressionAnalyzer));
+ Self { analyzers: all }
+ }
+
+ /// Register an analyzer at the front of the chain (higher priority).
+ pub fn register(&mut self, analyzer: Arc<dyn ExpressionAnalyzer>) {
+ self.analyzers.insert(0, analyzer);
+ }
+
+ /// Get selectivity through the analyzer chain.
+ pub fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(sel) =
+ analyzer.get_selectivity(expr, input_stats)
+ {
+ return Some(sel);
+ }
+ }
+ None
+ }
+
+ /// Get distinct count through the analyzer chain.
+ pub fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<usize> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(ndv) =
+ analyzer.get_distinct_count(expr, input_stats)
+ {
+ return Some(ndv);
+ }
+ }
+ None
+ }
+
+ /// Get min/max bounds through the analyzer chain.
+ pub fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<(ScalarValue, ScalarValue)> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(bounds) =
+ analyzer.get_min_max(expr, input_stats)
+ {
+ return Some(bounds);
+ }
+ }
+ None
+ }
+
+ /// Get null fraction through the analyzer chain.
+ pub fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(frac) =
+ analyzer.get_null_fraction(expr, input_stats)
+ {
+ return Some(frac);
+ }
+ }
+ None
+ }
+}
+
+// ============================================================================
+// DefaultExpressionAnalyzer
+// ============================================================================
+
+/// Default expression analyzer with Selinger-style estimation.
+///
+/// Handles common expression types:
+/// - Column references (uses column statistics)
+/// - Binary expressions (AND, OR, comparison operators)
+/// - Literals (constant selectivity/NDV)
+/// - NOT expressions (1 - child selectivity)
+#[derive(Debug, Default, Clone)]
+pub struct DefaultExpressionAnalyzer;
+
+impl DefaultExpressionAnalyzer {
+ /// Get column index from a Column expression
+ fn get_column_index(expr: &Arc<dyn PhysicalExpr>) -> Option<usize> {
+ expr.as_any().downcast_ref::<Column>().map(|c| c.index())
+ }
+
+ /// Get column statistics for an expression if it's a column reference
+ fn get_column_stats<'a>(
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &'a Statistics,
+ ) -> Option<&'a ColumnStatistics> {
+ Self::get_column_index(expr)
+ .and_then(|idx| input_stats.column_statistics.get(idx))
+ }
+
+ /// Recursive selectivity estimation
+ fn estimate_selectivity_recursive(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> f64 {
+ if let AnalysisResult::Computed(sel) = self.get_selectivity(expr, input_stats) {
+ return sel;
+ }
+ 0.5 // Default fallback
+ }
+}
+
+impl ExpressionAnalyzer for DefaultExpressionAnalyzer {
Review Comment:
Maybe we could move all of this to its own folder later on to declutter.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910711598
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
I'm concerned that the conservative lower-bound estimation could cause huge inaccuracy.
For example, we have 100 parts, and each part has 100 rows, and they are linearly increasing. The reality is that the ndv should be 100 * 100, but now we evaluate it as 100. The result could cause inaccuracies to propagate throughout subsequent cost estimation algorithms.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910806525
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
+ Self {
+ analyzers: vec![
+ Arc::new(StringFunctionAnalyzer),
+ Arc::new(MathFunctionAnalyzer),
+ Arc::new(DateTimeFunctionAnalyzer),
+ Arc::new(DefaultExpressionAnalyzer),
+ ],
+ }
+ }
+
+ /// Create a registry with custom analyzers (no default).
+ pub fn with_analyzers(analyzers: Vec<Arc<dyn ExpressionAnalyzer>>) -> Self {
+ Self { analyzers }
+ }
+
+ /// Create a registry with custom analyzers plus default as fallback.
+ pub fn with_analyzers_and_default(
+ analyzers: impl IntoIterator<Item = Arc<dyn ExpressionAnalyzer>>,
+ ) -> Self {
+ let mut all: Vec<Arc<dyn ExpressionAnalyzer>> = analyzers.into_iter().collect();
+ all.push(Arc::new(DefaultExpressionAnalyzer));
+ Self { analyzers: all }
+ }
+
+ /// Register an analyzer at the front of the chain (higher priority).
+ pub fn register(&mut self, analyzer: Arc<dyn ExpressionAnalyzer>) {
+ self.analyzers.insert(0, analyzer);
+ }
+
+ /// Get selectivity through the analyzer chain.
+ pub fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(sel) =
+ analyzer.get_selectivity(expr, input_stats)
+ {
+ return Some(sel);
+ }
+ }
+ None
+ }
+
+ /// Get distinct count through the analyzer chain.
+ pub fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<usize> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(ndv) =
+ analyzer.get_distinct_count(expr, input_stats)
+ {
+ return Some(ndv);
+ }
+ }
+ None
+ }
+
+ /// Get min/max bounds through the analyzer chain.
+ pub fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<(ScalarValue, ScalarValue)> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(bounds) =
+ analyzer.get_min_max(expr, input_stats)
+ {
+ return Some(bounds);
+ }
+ }
+ None
+ }
+
+ /// Get null fraction through the analyzer chain.
+ pub fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(frac) =
+ analyzer.get_null_fraction(expr, input_stats)
+ {
+ return Some(frac);
+ }
+ }
+ None
+ }
+}
+
+// ============================================================================
+// DefaultExpressionAnalyzer
+// ============================================================================
+
+/// Default expression analyzer with Selinger-style estimation.
+///
+/// Handles common expression types:
+/// - Column references (uses column statistics)
+/// - Binary expressions (AND, OR, comparison operators)
+/// - Literals (constant selectivity/NDV)
+/// - NOT expressions (1 - child selectivity)
+#[derive(Debug, Default, Clone)]
+pub struct DefaultExpressionAnalyzer;
+
+impl DefaultExpressionAnalyzer {
+ /// Get column index from a Column expression
+ fn get_column_index(expr: &Arc<dyn PhysicalExpr>) -> Option<usize> {
+ expr.as_any().downcast_ref::<Column>().map(|c| c.index())
+ }
+
+ /// Get column statistics for an expression if it's a column reference
+ fn get_column_stats<'a>(
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &'a Statistics,
+ ) -> Option<&'a ColumnStatistics> {
+ Self::get_column_index(expr)
+ .and_then(|idx| input_stats.column_statistics.get(idx))
+ }
+
+ /// Recursive selectivity estimation
+ fn estimate_selectivity_recursive(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> f64 {
+ if let AnalysisResult::Computed(sel) = self.get_selectivity(expr, input_stats) {
+ return sel;
+ }
+ 0.5 // Default fallback
+ }
+}
+
+impl ExpressionAnalyzer for DefaultExpressionAnalyzer {
Review Comment:
Makes sense, will do in the follow-up PR for the `ExpressionAnalyzer`
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4046213633
Rebased on latest `main` (includes #20846) and addressed all pending review comments (new changes are in the 4 topmost commits only, the rest is untouched modulo SHA changes for the rebase).
@xudong963: replaced the `max(left, right)` merge heuristic with the overlap-based formula from #20846 ([comment with details](https://github.com/apache/datafusion/pull/19957#discussion_r2924005097))
@gene-bordegaray:
- Reverted NDV propagation in projections as suggested, will address in a follow-up with proper expression statistics design ([comment with details](https://github.com/apache/datafusion/pull/19957#discussion_r2923949231))
- Added 75% threshold for partial NDV extraction from Parquet: if fewer than 75% of row groups report NDV, return `Absent` ([comment with details](https://github.com/apache/datafusion/pull/19957#discussion_r2923969032))
- The `max()` merge rule concern is also addressed by the overlap formula above
@jonathanc-n: partial NDV threshold addresses your [comment with details](https://github.com/apache/datafusion/pull/19957#discussion_r2897575666) as well.
Looking forward to hearing your thoughts!
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722738030
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -419,6 +424,7 @@ fn get_col_stats(
is_max_value_exact: &mut [Option<bool>],
is_min_value_exact: &mut [Option<bool>],
column_byte_sizes: &[Precision<usize>],
+ distinct_counts: &[Precision<usize>],
Review Comment:
Adopted `StatisticsAccumulators` as suggested, it feels better and I got rid of the "too many arguments" warning suppression, addressed in 4833ef5cfe1928ab9bafdde1b510131a2f17a211
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2917174928
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
Since you approved https://github.com/apache/datafusion/pull/20846 already, and the code in `union.rs::col_stats_union` is exactly what we want here too, I plan to wait for that PR to get merged, then turn `estimate_ndv_with_overlap` into a utility function in `datafusion-common/src/stats.rs` for reuse (all the types it needs already live there).
The formula is binary, but `try_merge` folds over many row groups, iterative pairwise application works naturally. No extra heap allocations: `distance()` returns a stack `usize`, the rest is `f64` arithmetic on top of the min/max comparisons `try_merge` already does.
Note: in #20846 the fallback when min/max are absent is `sum` (sensible for Union). For row group merging I'll keep `max` as fallback, since row groups from the same file are more likely to have overlapping values. I will make sure to generalize the current code to handle both cases.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2923487862
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -541,6 +541,36 @@ fn summarize_min_max_null_counts(
)
.map(|(idx, _)| idx);
+ // Extract distinct counts from row group column statistics
+ accumulators.distinct_counts_array[logical_schema_index] =
+ if let Some(parquet_idx) = parquet_index {
+ let distinct_counts: Vec<u64> = row_groups_metadata
+ .iter()
+ .filter_map(|rg| {
+ rg.columns()
+ .get(parquet_idx)
+ .and_then(|col| col.statistics())
+ .and_then(|stats| stats.distinct_count_opt())
+ })
+ .collect();
+
+ if distinct_counts.is_empty() {
+ Precision::Absent
+ } else if distinct_counts.len() == 1 {
Review Comment:
I think the partial-coverage case still needs tightening.
If we merge multiple row groups and only some of them expose NDV returning NDV as Exact for the whole file doesn't seem accurrate to me. Could we return make it Inexact?
The test `test_distinct_count_partial_ndv_in_row_groups` seems wrong asserting `Exact(15)` for a file where another row group has unknown NDV.
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
If we keep max() as the merge rule, I think we should document that merged NDV is treated as a lower-bound-ish estimate in public facing comments.
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Following up on this thread for my review:
I’d prefer to drop the new NDV propagation in projections from this PR. The heuristic “expression references a single column” is too broad to be correct for NDV. The thread already suggests handling this in a separate expression statistics design. For this PR I think derived expressions should stay unknown, then address the rest in a follow-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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4089125785
> @xudong963, is there anything missing to get this merged? (sorry for the direct ping but you are the only committer among approvers)
Oh! I forgot to merge it. Feel free to ping me directly, then I can notice it.
THanks for your work
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2911488857
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
>I'm concerned that the conservative lower-bound estimation could cause huge inaccuracy.
>
> For example, we have 100 parts, and each part has 100 rows, and they are linearly increasing. The reality is that the ndv should be 100 * 100, but now we evaluate it as 100. The result could cause inaccuracies to propagate throughout subsequent cost estimation algorithms.
You raise a good point, the true NDV across partitions lies in `[max(partition NDVs), sum(partition NDVs)]`: `max` when values fully overlap (e.g., a `status` column), `sum` when completely disjoint (e.g., `order_id`), no single strategy is optimal.
This is how different major OSS systems deal with the problem:
- Trino: `max` across partitions ([source](https://github.com/trinodb/trino/blob/9c1abc44e162ae8c63fcc07d072c56a16def1ed6/plugin/trino-hive/src/main/java/io/trino/plugin/hive/statistics/AbstractHiveStatisticsProvider.java#L678-L688)). Known to be problematic with disjoint domains: [trinodb/trino#50](https://github.com/trinodb/trino/issues/50) shows 62K estimated vs 150M actual. This is what I considered in the current proposal.
- Spark: `ANALYZE TABLE` runs a full-table `HyperLogLogPlusPlus` aggregation ([source](https://github.com/apache/spark/blob/5932f11fb91606606234f486f289be1358b1d829/sql/core/src/main/scala/org/apache/spark/sql/execution/command/CommandUtils.scala#L392)), so there are no per-partition NDVs to merge. But this strategy doesn't seem to be fitting here.
- Hive: stores HLL bitvector sketches per partition in the metastore, merges them at planning time ([HLL merge](https://github.com/apache/hive/blob/925df927248c1be11b84df3e8a0c3e43955e133e/standalone-metastore/metastore-server/src/main/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLog.java#L443-L485), [aggregator merge](https://github.com/apache/hive/blob/925df927248c1be11b84df3e8a0c3e43955e133e/standalone-metastore/metastore-server/src/main/java/org/apache/hadoop/hive/metastore/columnstats/aggr/StringColumnStatsAggregator.java#L88-L100)), and [interpolates](https://github.com/apache/hive/blob/925df927248c1be11b84df3e8a0c3e43955e133e/standalone-metastore/metastore-server/src/main/java/org/apache/hadoop/hive/metastore/columnstats/aggr/StringColumnStatsAggregator.java#L200-L201) for missing partitions by merging adjacent bitvectors and extrapolating. Note that this is exactly what [trinodb/trino#50](https://github.com/trinodb/trino/issues/50) suggests, but in this first PR I a
imed for simplicity.
- DuckDB: HLL merge with Good-Turing sampling correction ([merge](https://github.com/duckdb/duckdb/blob/19a12e9b74386a9e212811ef0c04014b04baede5/src/storage/statistics/distinct_statistics.cpp#L19-L23), [Good-Turing](https://github.com/duckdb/duckdb/blob/19a12e9b74386a9e212811ef0c04014b04baede5/src/storage/statistics/distinct_statistics.cpp#L53-L68)), but only for its native format. No HLL data available when reading Parquet. Good-Turing won't help here but it could be used for https://github.com/apache/datafusion/pull/19957#discussion_r2897575666, to extrapolate NDVs from a sample of the whole population, even if sampling should be random (cc: @jonathanc-n, as a complement to the threshold strategy?).
> HyperLogLog is a classic way to process this, but for a large dataset, it takes a long time to process.
The core constraint is that Parquet stores NDV as a single `optional i64` ([spec](https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift#L301)), not a sketch, and most writers don't even set it (see [apache/arrow-rs#8608](https://github.com/apache/arrow-rs/issues/8608)). So when merging row groups, we're interpolating from scalar values.
Regarding HLL cost: sketches are compact (~1.6KB for 2% error), merge is `O(registers)`, so it's cheap at planning time. The cost is at ingestion. Data sketches are standard practice at scale: Hive uses HLL for NDV and KLL for histograms/quantiles (e.g., [HIVE-26243](https://issues.apache.org/jira/browse/HIVE-26243), [HIVE-26221](https://issues.apache.org/jira/browse/HIVE-26221)). In extreme cases sketch size might be a concern, but it's not the general case in my experience.
> IIRC, the merge method may be called during query execution, so using HyperLogLog here isn't ideal.
To clarify: `try_merge` is only called at planning time (by `partition_statistics(None)` in optimizer rules like `JoinSelection`, and during file group metadata collection), not during query execution. This is orthogonal to statistics-based pruning work like [#19609](https://github.com/apache/datafusion/pull/19609).
I mentioned `JoinSelection` as a concrete use of NDV, but NDV can be used to drive other planning decisions (https://github.com/apache/datafusion/issues/20766 covers many of them). Some examples:
- Aggregation pushdown: NDV estimates the grouping reduction ratio: overestimating NDV makes the optimizer skip beneficial pushdowns, underestimating makes it push down aggregation expecting good compression that doesn't materialize.
- Hash table sizing via NDV: underestimate causes resizing/spilling, overestimate wastes memory.
- Filters (NDV for IN/equality): underestimating makes a filter push-down look more appealing than it is, overestimating might make us not push the filter down.
Bottom line is: there's no universally "safe" direction, the impact depends on how the statistic is consumed/used, since the consumers of NDV aren't fully defined yet, there is no strong guidance available.
Longer term, if we invest in CBO and statistics (as [#8227](https://github.com/apache/datafusion/issues/8227) and [#20766](https://github.com/apache/datafusion/issues/20766) suggest), the "one size fits all" problem will be exacerbated for downstream projects. Systems like Hive, Spark, or DuckDB, being end-user databases/warehouses, can make hard choices (e.g., Hive mandating HLL in the metastore). DataFusion is a framework, so we can't take one single route with no way to override. Decision points need to be tunable: what and how you read stats, how to propagate them through operators and expressions, and how to use them for planning decisions, for both built-in and custom stats, expressions, and operators.
I'm working on this via a `StatisticsProvider`/`StatisticsRegistry` pattern ([WIP branch](https://github.com/asolimando/datafusion/tree/asolimando/statistics-planner-prototype)), including `ExtendedStatistics` for custom data (histograms, sketches, etc.). For reading custom stats from Parquet, [user-defined Parquet indexes](https://datafusion.apache.org/blog/2025/07/14/user-defined-parquet-indexes/) could provide the ingestion mechanism: embed HLL sketches alongside Parquet data and read them at planning time through the provider chain.
Until we have that, maybe we should gate this novel propagation mechanism with a configuration property, so we are free to experiment without causing unexpected changes in existing planning? For NDV I haven't done it because, as discussed, it's not usually set by standard writers, so I don't expect any impact unless you make a conscious effort to write them and use them, but if we feel unsure I can add that safeguard.
Apologies for the wall of text! This discussion deserves its own space, but I wanted to address your concern here, happy to take the discussion to an RFC or issue, as you see fit.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910781304
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
> I do think it would be better to split into two pull requests.
Agreed, I have created a separate branch ([asolimando/ndv-expression-analyzer](https://github.com/asolimando/datafusion/tree/asolimando/ndv-expression-analyzer)), I will open a second PR for the `ExpressionAnalyzer` where I will "port" and discuss in details your comments, so they don't slip through the cracks.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "timsaucer (via GitHub)" <gi...@apache.org>.
timsaucer commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4089539781
It looks like this PR has caused CI to fail on `main` now: https://github.com/apache/datafusion/actions/runs/23290394969/job/67724593860
From reading the description of the PR it looks like this is a case where we have better performance with the PR and we just need to update the test files.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2900762554
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
I do think it would be better to split into two pull requests.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910772163
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -541,6 +541,36 @@ fn summarize_min_max_null_counts(
)
.map(|(idx, _)| idx);
+ // Extract distinct counts from row group column statistics
+ accumulators.distinct_counts_array[logical_schema_index] =
+ if let Some(parquet_idx) = parquet_index {
+ let distinct_counts: Vec<u64> = row_groups_metadata
+ .iter()
+ .filter_map(|rg| {
+ rg.columns()
+ .get(parquet_idx)
+ .and_then(|col| col.statistics())
+ .and_then(|stats| stats.distinct_count_opt())
+ })
+ .collect();
+
+ if distinct_counts.is_empty() {
+ Precision::Absent
+ } else if distinct_counts.len() == 1 {
Review Comment:
Good point. As a first step I agree on a threshold + configuration for this.
That said, since DataFusion is a framework, how to propagate statistics is really dependent on the system, data, etc. I'm working towards a fully customizable solution for statistics propagation, not just at the expression level (as shown with ExpressionAnalyzer in this PR), but also at the operator level.
The WIP branch is here:
https://github.com/asolimando/datafusion/tree/asolimando/statistics-planner-prototype - it introduces a `StatisticsProvider`/`StatisticsRegistry` chain-of-responsibility pattern for operator-level stats, similar in spirit to `ExpressionAnalyzer` but for `ExecutionPlan` nodes. I will open PRs for it, but any feedback on the general approach is welcome. For instance, the shortcoming you highlighted for `ExpressionAnalyzer` (hard-coded delegation instead of going through the chain) does not affect the operator-level design, but there might be other limitations I'm not seeing.
A few things are still pending as I'd like to make use of https://github.com/apache/datafusion/issues/20184 (unmerged) and https://github.com/apache/datafusion/pull/20570 (that just got merged).
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722323190
##########
datafusion/common/src/stats.rs:
##########
@@ -632,7 +632,24 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
+ col_stats.distinct_count =
+ match (&col_stats.distinct_count, &item_col_stats.distinct_count) {
+ (Precision::Exact(a), Precision::Exact(b))
+ | (Precision::Inexact(a), Precision::Exact(b))
+ | (Precision::Exact(a), Precision::Inexact(b))
+ | (Precision::Inexact(a), Precision::Inexact(b)) => {
+ Precision::Inexact(if a >= b { *a } else { *b })
+ }
+ (Precision::Exact(v), Precision::Absent)
+ | (Precision::Inexact(v), Precision::Absent)
+ | (Precision::Absent, Precision::Exact(v))
+ | (Precision::Absent, Precision::Inexact(v)) => {
+ Precision::Inexact(*v)
+ }
+ (Precision::Absent, Precision::Absent) => Precision::Absent,
+ };
Review Comment:
I think this verbosity could be reduced to something like:
```rust
col_stats.distinct_count = col_stats.distinct_count.get_value()
.max(item_col_stats.distinct_count.get_value())
.map(|&v| Precision::Inexact(v))
.unwrap_or(Precision::Absent);
```
or we could introduce some method like `max_inexact()` on Precision.
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
noice, this is useful thanks 😄
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -778,4 +815,354 @@ mod tests {
assert_eq!(result, Some(false));
}
}
+
+ mod ndv_tests {
+ use super::*;
+ use arrow::datatypes::Field;
+ use parquet::basic::Type as PhysicalType;
+ use parquet::file::metadata::{ColumnChunkMetaData, RowGroupMetaData};
+ use parquet::file::statistics::Statistics as ParquetStatistics;
+ use parquet::schema::types::{SchemaDescriptor, Type as SchemaType};
+
+ fn create_schema_descr(num_columns: usize) -> Arc<SchemaDescriptor> {
+ let fields: Vec<Arc<SchemaType>> = (0..num_columns)
+ .map(|i| {
+ Arc::new(
+ SchemaType::primitive_type_builder(
+ &format!("col_{i}"),
+ PhysicalType::INT32,
+ )
+ .build()
+ .unwrap(),
+ )
+ })
+ .collect();
+
+ let schema = SchemaType::group_type_builder("schema")
+ .with_fields(fields)
+ .build()
+ .unwrap();
+
+ Arc::new(SchemaDescriptor::new(Arc::new(schema)))
+ }
+
+ fn create_arrow_schema(num_columns: usize) -> SchemaRef {
+ let fields: Vec<Field> = (0..num_columns)
+ .map(|i| Field::new(format!("col_{i}"), DataType::Int32, true))
+ .collect();
+ Arc::new(Schema::new(fields))
+ }
+
+ fn create_row_group_with_stats(
+ schema_descr: &Arc<SchemaDescriptor>,
+ column_stats: Vec<Option<ParquetStatistics>>,
+ num_rows: i64,
+ ) -> RowGroupMetaData {
+ let columns: Vec<ColumnChunkMetaData> = column_stats
+ .into_iter()
+ .enumerate()
+ .map(|(i, stats)| {
+ let mut builder =
+ ColumnChunkMetaData::builder(schema_descr.column(i));
+ if let Some(s) = stats {
+ builder = builder.set_statistics(s);
+ }
+ builder.set_num_values(num_rows).build().unwrap()
+ })
+ .collect();
+
+ RowGroupMetaData::builder(schema_descr.clone())
+ .set_num_rows(num_rows)
+ .set_total_byte_size(1000)
+ .set_column_metadata(columns)
+ .build()
+ .unwrap()
+ }
+
+ fn create_parquet_metadata(
+ schema_descr: Arc<SchemaDescriptor>,
+ row_groups: Vec<RowGroupMetaData>,
+ ) -> ParquetMetaData {
+ use parquet::file::metadata::FileMetaData;
+
+ let num_rows: i64 = row_groups.iter().map(|rg| rg.num_rows()).sum();
+ let file_meta = FileMetaData::new(
+ 1, // version
+ num_rows, // num_rows
+ None, // created_by
+ None, // key_value_metadata
+ schema_descr, // schema_descr
+ None, // column_orders
+ );
+
+ ParquetMetaData::new(file_meta, row_groups)
+ }
+
+ #[test]
+ fn test_distinct_count_single_row_group_with_ndv() {
+ // Single row group with distinct count should return Exact
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create statistics with distinct_count = 42
+ let stats = ParquetStatistics::int32(
+ Some(1), // min
+ Some(100), // max
+ Some(42), // distinct_count
+ Some(0), // null_count
+ false, // is_deprecated
+ );
+
+ let row_group =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats)], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(42)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_multiple_row_groups_with_ndv() {
+ // Multiple row groups with distinct counts should return Inexact (sum)
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Row group 1: distinct_count = 10
+ let stats1 = ParquetStatistics::int32(
+ Some(1),
+ Some(50),
+ Some(10), // distinct_count
+ Some(0),
+ false,
+ );
+
+ // Row group 2: distinct_count = 20
+ let stats2 = ParquetStatistics::int32(
+ Some(51),
+ Some(100),
+ Some(20), // distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group1 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats1)], 500);
+ let row_group2 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats2)], 500);
+ let metadata =
+ create_parquet_metadata(schema_descr, vec![row_group1, row_group2]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ // Max of distinct counts (lower bound since we can't accurately merge NDV)
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Inexact(20)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_no_ndv_available() {
+ // No distinct count in statistics should return Absent
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create statistics without distinct_count (None)
+ let stats = ParquetStatistics::int32(
+ Some(1),
+ Some(100),
+ None, // no distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats)], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Absent
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_partial_ndv_in_row_groups() {
+ // Some row groups have NDV, some don't - should use only those that have it
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Row group 1: has distinct_count = 15
+ let stats1 =
+ ParquetStatistics::int32(Some(1), Some(50), Some(15), Some(0), false);
+
+ // Row group 2: no distinct_count
+ let stats2 = ParquetStatistics::int32(
+ Some(51),
+ Some(100),
+ None, // no distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group1 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats1)], 500);
+ let row_group2 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats2)], 500);
+ let metadata =
+ create_parquet_metadata(schema_descr, vec![row_group1, row_group2]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ // Only one row group has NDV, so it's Exact(15)
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(15)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_multiple_columns() {
+ // Test with multiple columns, each with different NDV
+ let schema_descr = create_schema_descr(3);
+ let arrow_schema = create_arrow_schema(3);
+
+ // col_0: distinct_count = 5
+ let stats0 =
+ ParquetStatistics::int32(Some(1), Some(10), Some(5), Some(0), false);
+ // col_1: no distinct_count
+ let stats1 =
+ ParquetStatistics::int32(Some(1), Some(100), None, Some(0), false);
+ // col_2: distinct_count = 100
+ let stats2 =
+ ParquetStatistics::int32(Some(1), Some(1000), Some(100), Some(0), false);
+
+ let row_group = create_row_group_with_stats(
+ &schema_descr,
+ vec![Some(stats0), Some(stats1), Some(stats2)],
+ 1000,
+ );
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(5)
+ );
+ assert_eq!(
+ result.column_statistics[1].distinct_count,
+ Precision::Absent
+ );
+ assert_eq!(
+ result.column_statistics[2].distinct_count,
+ Precision::Exact(100)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_no_statistics_at_all() {
+ // No statistics in row group should return Absent for all stats
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create row group without any statistics
+ let row_group = create_row_group_with_stats(&schema_descr, vec![None], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Absent
+ );
+ }
+
+ /// Integration test that reads a real Parquet file with distinct_count statistics.
+ /// The test file was created with DuckDB and has known NDV values:
+ /// - id: NULL (high cardinality, not tracked)
+ /// - category: 10 distinct values
+ /// - name: 5 distinct values
+ #[test]
+ fn test_distinct_count_from_real_parquet_file() {
+ use parquet::arrow::parquet_to_arrow_schema;
+ use parquet::file::reader::{FileReader, SerializedFileReader};
+ use std::fs::File;
+ use std::path::PathBuf;
Review Comment:
nit: since these tests are in their own module, I think moving these to the ndv_test module level would be ok
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -419,6 +424,7 @@ fn get_col_stats(
is_max_value_exact: &mut [Option<bool>],
is_min_value_exact: &mut [Option<bool>],
column_byte_sizes: &[Precision<usize>],
+ distinct_counts: &[Precision<usize>],
Review Comment:
A nit but maybe these could be extracted into a struct that encapsulates these parameters as fields - say extend `StatisticsAccumulators` and use this or create a new struct
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2764844890
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
There are also APIs being proposed in 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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gabotechs (via GitHub)" <gi...@apache.org>.
gabotechs commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2732799159
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
For `StatisticsProvider`, `StatisticsRegistry` and `CardinalityEstimator`. Do you think there is some overlap with the existing `ExecutionPlan::partition_statistics()` and `PhysicalExpr::evaluate_statistics()`? would it be appropriate to extend the functionality shipped in both methods? or are you considering `StatisticsProvider`, `StatisticsRegistry` and `CardinalityEstimator` to be a separate mechanism for providing statistics?
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2873011310
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Sorry for the late reply @adriangb, I have been off for a little while.
I have been following https://github.com/apache/datafusion/pull/19609 with lots of interest, and in my understanding it's dealing with statistics for what concerns filtering and predicate pruning, so the two approaches are orthogonal and complement each other.
This PR focuses on NDV, laying the foundation of improved cardinality estimation (which we will soon be able to precisely measure thanks to https://github.com/apache/datafusion/pull/20292).
For DataFusion, the benefit is for improving some existing configuration options, when statistics are available, a few examples for NDV:
- [prefer_hash_join](https://github.com/apache/datafusion/blob/1f37a33ce530bdedcaf3aba65295703874cd7d09/datafusion/common/src/config.rs#L1073): with NDV the optimizer could compare `HashJoin` vs `SortMergeJoin` cost, especially when downstream ordering is needed, enabling per-join cost-based decisions
- [default_filter_selectivity](https://github.com/apache/datafusion/blob/1f37a33ce530bdedcaf3aba65295703874cd7d09/datafusion/common/src/config.rs#L1121) (20% hardcoded value): with NDV, equality filters become `1/NDV(col)`, IN-lists become `list_size/NDV(col)`, etc.
This is also relevant for distributed DataFusion, where cardinality estimation plays an even larger role in physical planning (many planning choices can't be corrected via adaptive query processing in a distributed setup).
The PR got stale and I will need to rebase on current main branch, so interested reviewers can take a 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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910809049
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
Review Comment:
Agreed, will move it to `SessionContext`/`SessionState` in the follow-up PR, thanks for your suggestion
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2923949231
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Resolving as it seems the comments have been considered, and the discussion will continue in the follow-up PR for `ExpressionAnalyzer`, feel free to unresolve if you think otherwise.
EDIT: sorry the page didn't refresh and I missed your message. I agree, I have reverted it in 0e23ef17d, expression-level statistics will be addressed in a follow-up, this was there just to show-case how one could use it, but not worth keeping here, thanks again for the reminder!
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2739145784
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
I have done a POC for ExpressionAnalyzer, commit [3d229b6f5](https://github.com/asolimando/datafusion/commit/3d229b6f5) introduces it, it is a pluggable chain-of-responsibility for expression-level statistics (selectivity, NDV, min/max). It includes default Selinger-style estimation and built-in analyzers for string/math/datetime functions (that's just an example to see how you could do it in practice, but it's also sound).
Commit [d725cc08c](https://github.com/asolimando/datafusion/commit/d725cc08c) demonstrates its use by integrating it into projection NDV estimation (where the present discussion started, basically).
This is a non-breaking change, purely additive. The `StatisticsRegistry` approach for operator-level statistics would require modifying `partition_statistics` signatures and that would be breaking.
As I was saying, I think it's inevitable to adopt something similar in the long run, but at what time and under what form can be discussed, if the community is interested in exploring this direction.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2915363185
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
Looks great to me, thanks for the sweet reply.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2923949231
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Resolving as it seems the comments have been considered, and the discussion will continue in the follow-up PR for `ExpressionAnalyzer`, feel free to unresolve if you think otherwise
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4089785743
> It looks like this PR has caused CI to fail on `main` now: https://github.com/apache/datafusion/actions/runs/23290394969/job/67724593860
>
> From reading the description of the PR it looks like this is a case where we have better performance with the PR and we just need to update the test files.
Thanks for the heads up @timsaucer and apologies for the inconvenience, I am checking and will prepare a PR to fix this shortly
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4069364165
Force-pushing to resolve conflicts with main after changes from https://github.com/apache/datafusion/pull/20768
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2924005097
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
Addressed in 72d3be325. Thanks for the heads up on #20846!
I have finally replaced `max(left, right)` with the overlap-based formula from that PR, now extracted into a shared `estimate_ndv_with_overlap` in `stats.rs` used by both `try_merge` and Union, as agreed with @xudong963.
I have added tests covering disjoint, identical, partial overlap, missing min/max, non-numeric, and constant column cases. No Union tests changed, as expected from a pure extraction/refactoring.
Is this matching your expectations, @gene-bordegaray?
Apologies again for the force push but building on #20846 seemed really worth it, apart from SHAs, the only changes are the two topmost, addressing pending points.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2942020180
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
Thanks to you and to all other reviewers, great discussions!
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2941408937
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
I have filed #20966 as it's indeed a nice improvement and I think this can be made associative if working with lists of column statistics, rather than merging pair-wise.
I wouldn't consider this a problem for the current PR as the error is still reasonably bounded due to the uniform distribution of NDVs that our formulas rely on anyway.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2941451971
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
nice nice, this makes sense.
I will also have a peak and some thoughts on that issue. Thank you for all the thoughtful responses and explanations 💯
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4088981708
@xudong963, is there anything missing to get this merged? (sorry for the direct ping but you are the only committer among approvers)
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2935277064
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
This being moved from union.rs makes me wonder if this should be generalized to all operators.
Say rather than just merging two columns we were to merge three: A, B, C. This can result in different outcomes with the same columns being merged since the columns stats are smeared after the first merge.
Example:
```
- A = [0,100], NDV=80
- B = [50,150], NDV=60
- C = [100,200], NDV=50
Scenarios:
- (A+B)+C = 135
- A+(B+C) = 137
```
I know that while in union.rs this problem still existed but it was more tightly scoped.
Is there a way we could make this more explicit in the documentation / plan follow up work to handle merging?
I would think that preserving the shape of the distinct values in some way after merging is what we want. This might require more plumbing and could come back to this.
Let me know your thoughts.
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
This being moved from union.rs makes me wonder if this should be generalized to all operators.
Say rather than just merging two columns we were to merge three: A, B, C. This can result in different outcomes with the same columns being merged since the columns stats are smeared after the first merge.
Example:
```
- A = [0,100], NDV=80
- B = [50,150], NDV=60
- C = [100,200], NDV=50
Scenarios:
- (A+B)+C = 135
- A+(B+C) = 137
```
I know that while in union.rs this problem still existed but it was more tightly scoped.
Is there a way we could make this more explicit in the documentation / plan follow up work to handle merging?
I would think that preserving the shape of the distinct values in some way after merging is what we want. This might require more plumbing and could come back to this.
Let me know your thoughts.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722735298
##########
datafusion/common/src/stats.rs:
##########
@@ -632,7 +632,24 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
+ col_stats.distinct_count =
+ match (&col_stats.distinct_count, &item_col_stats.distinct_count) {
+ (Precision::Exact(a), Precision::Exact(b))
+ | (Precision::Inexact(a), Precision::Exact(b))
+ | (Precision::Exact(a), Precision::Inexact(b))
+ | (Precision::Inexact(a), Precision::Inexact(b)) => {
+ Precision::Inexact(if a >= b { *a } else { *b })
+ }
+ (Precision::Exact(v), Precision::Absent)
+ | (Precision::Inexact(v), Precision::Absent)
+ | (Precision::Absent, Precision::Exact(v))
+ | (Precision::Absent, Precision::Inexact(v)) => {
+ Precision::Inexact(*v)
+ }
+ (Precision::Absent, Precision::Absent) => Precision::Absent,
+ };
Review Comment:
Thanks a lot, this is very neat, addressed in db182e50dc2b920e2da03380729b70cb4ec58c39!
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2727672710
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -411,53 +415,6 @@ fn create_max_min_accs(
(max_values, min_values)
}
-fn get_col_stats(
Review Comment:
Yes, the `get_col_stats` -> `StatisticsAccumulators::build_column_statistics()` change is purely a no-op refactor keeping the same logic, it just encapsulates it as a method on the struct instead of a standalone function due to the grown number of parameters
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722739028
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -778,4 +815,354 @@ mod tests {
assert_eq!(result, Some(false));
}
}
+
+ mod ndv_tests {
+ use super::*;
+ use arrow::datatypes::Field;
+ use parquet::basic::Type as PhysicalType;
+ use parquet::file::metadata::{ColumnChunkMetaData, RowGroupMetaData};
+ use parquet::file::statistics::Statistics as ParquetStatistics;
+ use parquet::schema::types::{SchemaDescriptor, Type as SchemaType};
+
+ fn create_schema_descr(num_columns: usize) -> Arc<SchemaDescriptor> {
+ let fields: Vec<Arc<SchemaType>> = (0..num_columns)
+ .map(|i| {
+ Arc::new(
+ SchemaType::primitive_type_builder(
+ &format!("col_{i}"),
+ PhysicalType::INT32,
+ )
+ .build()
+ .unwrap(),
+ )
+ })
+ .collect();
+
+ let schema = SchemaType::group_type_builder("schema")
+ .with_fields(fields)
+ .build()
+ .unwrap();
+
+ Arc::new(SchemaDescriptor::new(Arc::new(schema)))
+ }
+
+ fn create_arrow_schema(num_columns: usize) -> SchemaRef {
+ let fields: Vec<Field> = (0..num_columns)
+ .map(|i| Field::new(format!("col_{i}"), DataType::Int32, true))
+ .collect();
+ Arc::new(Schema::new(fields))
+ }
+
+ fn create_row_group_with_stats(
+ schema_descr: &Arc<SchemaDescriptor>,
+ column_stats: Vec<Option<ParquetStatistics>>,
+ num_rows: i64,
+ ) -> RowGroupMetaData {
+ let columns: Vec<ColumnChunkMetaData> = column_stats
+ .into_iter()
+ .enumerate()
+ .map(|(i, stats)| {
+ let mut builder =
+ ColumnChunkMetaData::builder(schema_descr.column(i));
+ if let Some(s) = stats {
+ builder = builder.set_statistics(s);
+ }
+ builder.set_num_values(num_rows).build().unwrap()
+ })
+ .collect();
+
+ RowGroupMetaData::builder(schema_descr.clone())
+ .set_num_rows(num_rows)
+ .set_total_byte_size(1000)
+ .set_column_metadata(columns)
+ .build()
+ .unwrap()
+ }
+
+ fn create_parquet_metadata(
+ schema_descr: Arc<SchemaDescriptor>,
+ row_groups: Vec<RowGroupMetaData>,
+ ) -> ParquetMetaData {
+ use parquet::file::metadata::FileMetaData;
+
+ let num_rows: i64 = row_groups.iter().map(|rg| rg.num_rows()).sum();
+ let file_meta = FileMetaData::new(
+ 1, // version
+ num_rows, // num_rows
+ None, // created_by
+ None, // key_value_metadata
+ schema_descr, // schema_descr
+ None, // column_orders
+ );
+
+ ParquetMetaData::new(file_meta, row_groups)
+ }
+
+ #[test]
+ fn test_distinct_count_single_row_group_with_ndv() {
+ // Single row group with distinct count should return Exact
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create statistics with distinct_count = 42
+ let stats = ParquetStatistics::int32(
+ Some(1), // min
+ Some(100), // max
+ Some(42), // distinct_count
+ Some(0), // null_count
+ false, // is_deprecated
+ );
+
+ let row_group =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats)], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(42)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_multiple_row_groups_with_ndv() {
+ // Multiple row groups with distinct counts should return Inexact (sum)
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Row group 1: distinct_count = 10
+ let stats1 = ParquetStatistics::int32(
+ Some(1),
+ Some(50),
+ Some(10), // distinct_count
+ Some(0),
+ false,
+ );
+
+ // Row group 2: distinct_count = 20
+ let stats2 = ParquetStatistics::int32(
+ Some(51),
+ Some(100),
+ Some(20), // distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group1 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats1)], 500);
+ let row_group2 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats2)], 500);
+ let metadata =
+ create_parquet_metadata(schema_descr, vec![row_group1, row_group2]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ // Max of distinct counts (lower bound since we can't accurately merge NDV)
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Inexact(20)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_no_ndv_available() {
+ // No distinct count in statistics should return Absent
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create statistics without distinct_count (None)
+ let stats = ParquetStatistics::int32(
+ Some(1),
+ Some(100),
+ None, // no distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats)], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Absent
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_partial_ndv_in_row_groups() {
+ // Some row groups have NDV, some don't - should use only those that have it
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Row group 1: has distinct_count = 15
+ let stats1 =
+ ParquetStatistics::int32(Some(1), Some(50), Some(15), Some(0), false);
+
+ // Row group 2: no distinct_count
+ let stats2 = ParquetStatistics::int32(
+ Some(51),
+ Some(100),
+ None, // no distinct_count
+ Some(0),
+ false,
+ );
+
+ let row_group1 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats1)], 500);
+ let row_group2 =
+ create_row_group_with_stats(&schema_descr, vec![Some(stats2)], 500);
+ let metadata =
+ create_parquet_metadata(schema_descr, vec![row_group1, row_group2]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ // Only one row group has NDV, so it's Exact(15)
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(15)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_multiple_columns() {
+ // Test with multiple columns, each with different NDV
+ let schema_descr = create_schema_descr(3);
+ let arrow_schema = create_arrow_schema(3);
+
+ // col_0: distinct_count = 5
+ let stats0 =
+ ParquetStatistics::int32(Some(1), Some(10), Some(5), Some(0), false);
+ // col_1: no distinct_count
+ let stats1 =
+ ParquetStatistics::int32(Some(1), Some(100), None, Some(0), false);
+ // col_2: distinct_count = 100
+ let stats2 =
+ ParquetStatistics::int32(Some(1), Some(1000), Some(100), Some(0), false);
+
+ let row_group = create_row_group_with_stats(
+ &schema_descr,
+ vec![Some(stats0), Some(stats1), Some(stats2)],
+ 1000,
+ );
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Exact(5)
+ );
+ assert_eq!(
+ result.column_statistics[1].distinct_count,
+ Precision::Absent
+ );
+ assert_eq!(
+ result.column_statistics[2].distinct_count,
+ Precision::Exact(100)
+ );
+ }
+
+ #[test]
+ fn test_distinct_count_no_statistics_at_all() {
+ // No statistics in row group should return Absent for all stats
+ let schema_descr = create_schema_descr(1);
+ let arrow_schema = create_arrow_schema(1);
+
+ // Create row group without any statistics
+ let row_group = create_row_group_with_stats(&schema_descr, vec![None], 1000);
+ let metadata = create_parquet_metadata(schema_descr, vec![row_group]);
+
+ let result = DFParquetMetadata::statistics_from_parquet_metadata(
+ &metadata,
+ &arrow_schema,
+ )
+ .unwrap();
+
+ assert_eq!(
+ result.column_statistics[0].distinct_count,
+ Precision::Absent
+ );
+ }
+
+ /// Integration test that reads a real Parquet file with distinct_count statistics.
+ /// The test file was created with DuckDB and has known NDV values:
+ /// - id: NULL (high cardinality, not tracked)
+ /// - category: 10 distinct values
+ /// - name: 5 distinct values
+ #[test]
+ fn test_distinct_count_from_real_parquet_file() {
+ use parquet::arrow::parquet_to_arrow_schema;
+ use parquet::file::reader::{FileReader, SerializedFileReader};
+ use std::fs::File;
+ use std::path::PathBuf;
Review Comment:
Thanks for the suggestion, adopted in e36c46ae036d62bd680ac89d7dc639dceab9b8d2
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2917421807
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
+ Self {
+ analyzers: vec![
+ Arc::new(StringFunctionAnalyzer),
+ Arc::new(MathFunctionAnalyzer),
+ Arc::new(DateTimeFunctionAnalyzer),
+ Arc::new(DefaultExpressionAnalyzer),
+ ],
+ }
+ }
+
+ /// Create a registry with custom analyzers (no default).
+ pub fn with_analyzers(analyzers: Vec<Arc<dyn ExpressionAnalyzer>>) -> Self {
+ Self { analyzers }
+ }
+
+ /// Create a registry with custom analyzers plus default as fallback.
+ pub fn with_analyzers_and_default(
+ analyzers: impl IntoIterator<Item = Arc<dyn ExpressionAnalyzer>>,
+ ) -> Self {
+ let mut all: Vec<Arc<dyn ExpressionAnalyzer>> = analyzers.into_iter().collect();
+ all.push(Arc::new(DefaultExpressionAnalyzer));
+ Self { analyzers: all }
+ }
+
+ /// Register an analyzer at the front of the chain (higher priority).
+ pub fn register(&mut self, analyzer: Arc<dyn ExpressionAnalyzer>) {
+ self.analyzers.insert(0, analyzer);
+ }
+
+ /// Get selectivity through the analyzer chain.
+ pub fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(sel) =
+ analyzer.get_selectivity(expr, input_stats)
+ {
+ return Some(sel);
+ }
+ }
+ None
+ }
+
+ /// Get distinct count through the analyzer chain.
+ pub fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<usize> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(ndv) =
+ analyzer.get_distinct_count(expr, input_stats)
+ {
+ return Some(ndv);
+ }
+ }
+ None
+ }
+
+ /// Get min/max bounds through the analyzer chain.
+ pub fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<(ScalarValue, ScalarValue)> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(bounds) =
+ analyzer.get_min_max(expr, input_stats)
+ {
+ return Some(bounds);
+ }
+ }
+ None
+ }
+
+ /// Get null fraction through the analyzer chain.
+ pub fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(frac) =
+ analyzer.get_null_fraction(expr, input_stats)
+ {
+ return Some(frac);
+ }
+ }
+ None
+ }
+}
+
+// ============================================================================
+// DefaultExpressionAnalyzer
+// ============================================================================
+
+/// Default expression analyzer with Selinger-style estimation.
+///
+/// Handles common expression types:
+/// - Column references (uses column statistics)
+/// - Binary expressions (AND, OR, comparison operators)
+/// - Literals (constant selectivity/NDV)
+/// - NOT expressions (1 - child selectivity)
+#[derive(Debug, Default, Clone)]
+pub struct DefaultExpressionAnalyzer;
+
+impl DefaultExpressionAnalyzer {
+ /// Get column index from a Column expression
+ fn get_column_index(expr: &Arc<dyn PhysicalExpr>) -> Option<usize> {
+ expr.as_any().downcast_ref::<Column>().map(|c| c.index())
+ }
+
+ /// Get column statistics for an expression if it's a column reference
+ fn get_column_stats<'a>(
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &'a Statistics,
+ ) -> Option<&'a ColumnStatistics> {
+ Self::get_column_index(expr)
+ .and_then(|idx| input_stats.column_statistics.get(idx))
+ }
+
+ /// Recursive selectivity estimation
+ fn estimate_selectivity_recursive(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> f64 {
+ if let AnalysisResult::Computed(sel) = self.get_selectivity(expr, input_stats) {
+ return sel;
+ }
+ 0.5 // Default fallback
+ }
+}
+
+impl ExpressionAnalyzer for DefaultExpressionAnalyzer {
+ fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Binary expressions: AND, OR, comparisons
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let left_sel =
+ self.estimate_selectivity_recursive(binary.left(), input_stats);
+ let right_sel =
+ self.estimate_selectivity_recursive(binary.right(), input_stats);
+
+ let sel = match binary.op() {
+ // Logical operators
+ Operator::And => left_sel * right_sel,
+ Operator::Or => left_sel + right_sel - (left_sel * right_sel),
+
+ // Equality: selectivity = 1/NDV
+ Operator::Eq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 / (*ndv as f64));
+ }
+ 0.1 // Default equality selectivity
+ }
+
+ // Inequality: selectivity = 1 - 1/NDV
+ Operator::NotEq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 - (1.0 / (*ndv as f64)));
+ }
+ 0.9
+ }
+
+ // Range predicates: classic 1/3 estimate
+ Operator::Lt | Operator::LtEq | Operator::Gt | Operator::GtEq => 0.33,
+
+ // LIKE: depends on pattern, use conservative estimate
+ Operator::LikeMatch | Operator::ILikeMatch => 0.25,
+ Operator::NotLikeMatch | Operator::NotILikeMatch => 0.75,
+
+ // Other operators: default
+ _ => 0.5,
+ };
+
+ return AnalysisResult::Computed(sel);
+ }
+
+ // NOT expression: 1 - child selectivity
+ if let Some(not_expr) = expr.as_any().downcast_ref::<NotExpr>() {
+ let child_sel =
+ self.estimate_selectivity_recursive(not_expr.arg(), input_stats);
+ return AnalysisResult::Computed(1.0 - child_sel);
+ }
+
+ // Literal boolean: 0.0 or 1.0
+ if let Some(b) = expr
+ .as_any()
+ .downcast_ref::<Literal>()
+ .and_then(|lit| match lit.value() {
+ ScalarValue::Boolean(Some(b)) => Some(*b),
+ _ => None,
+ })
+ {
+ return AnalysisResult::Computed(if b { 1.0 } else { 0.0 });
+ }
+
+ // Column reference as predicate (boolean column)
+ if expr.as_any().downcast_ref::<Column>().is_some() {
+ return AnalysisResult::Computed(0.5);
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ // Column reference: use column NDV
+ if let Some(ndv) = Self::get_column_stats(expr, input_stats)
+ .and_then(|col_stats| col_stats.distinct_count.get_value().copied())
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+
+ // Literal: NDV = 1
+ if expr.as_any().downcast_ref::<Literal>().is_some() {
+ return AnalysisResult::Computed(1);
+ }
+
+ // BinaryExpr: for injective operations (arithmetic with literal), preserve NDV
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let is_arithmetic = matches!(
+ binary.op(),
+ Operator::Plus
+ | Operator::Minus
+ | Operator::Multiply
+ | Operator::Divide
+ | Operator::Modulo
+ );
+
+ if is_arithmetic {
+ // If one side is a literal, the operation is injective on the other side
+ let left_is_literal = binary.left().as_any().is::<Literal>();
+ let right_is_literal = binary.right().as_any().is::<Literal>();
+
+ if left_is_literal {
+ // NDV comes from right side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.right(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ } else if right_is_literal {
+ // NDV comes from left side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.left(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ }
+ // Both sides are non-literals: could combine, but delegate for now
+ }
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ // Column reference: use column min/max
+ if let Some((min, max)) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ match (
+ col_stats.min_value.get_value(),
+ col_stats.max_value.get_value(),
+ ) {
+ (Some(min), Some(max)) => Some((min.clone(), max.clone())),
+ _ => None,
+ }
+ })
+ {
+ return AnalysisResult::Computed((min, max));
+ }
+
+ // Literal: min = max = value
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let val = lit_expr.value().clone();
+ return AnalysisResult::Computed((val.clone(), val));
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Column reference: null_count / num_rows
+ if let Some(fraction) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ let null_count = col_stats.null_count.get_value().copied()?;
+ let num_rows = input_stats.num_rows.get_value().copied()?;
+ if num_rows > 0 {
+ Some(null_count as f64 / num_rows as f64)
+ } else {
+ None
+ }
+ })
+ {
+ return AnalysisResult::Computed(fraction);
+ }
+
+ // Literal: null fraction depends on whether it's null
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let is_null = lit_expr.value().is_null();
+ return AnalysisResult::Computed(if is_null { 1.0 } else { 0.0 });
+ }
+
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// StringFunctionAnalyzer
+// ============================================================================
+
+/// Analyzer for string functions.
+///
+/// - Injective (preserve NDV): UPPER, LOWER, TRIM, LTRIM, RTRIM, REVERSE
+/// - Non-injective (reduce NDV): SUBSTRING, LEFT, RIGHT, REPLACE
+#[derive(Debug, Default, Clone)]
+pub struct StringFunctionAnalyzer;
+
+impl StringFunctionAnalyzer {
+ /// Check if a function is injective (one-to-one)
+ pub fn is_injective(func_name: &str) -> bool {
+ matches!(
+ func_name.to_uppercase().as_str(),
+ "UPPER" | "LOWER" | "TRIM" | "LTRIM" | "RTRIM" | "REVERSE" | "INITCAP"
+ )
+ }
+
+ /// Get NDV reduction factor for non-injective functions
+ pub fn ndv_reduction_factor(func_name: &str) -> Option<f64> {
+ match func_name.to_uppercase().as_str() {
+ "SUBSTRING" | "LEFT" | "RIGHT" => Some(0.5),
+ "REPLACE" => Some(0.8),
+ _ => None,
+ }
+ }
+}
+
+impl ExpressionAnalyzer for StringFunctionAnalyzer {
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ let Some(func) = expr.as_any().downcast_ref::<ScalarFunctionExpr>() else {
+ return AnalysisResult::Delegate;
+ };
+
+ let func_name = func.name();
+ let Some(first_arg) = func.args().first() else {
+ return AnalysisResult::Delegate;
+ };
+
+ // Get input NDV
+ let Some(input_ndv) = DefaultExpressionAnalyzer
Review Comment:
Note to self for `ExpressionAnalyzer`: it addresses https://github.com/apache/datafusion/issues/992 which got closed recently as non-actionable, a new issue will be needed but the old one should be referenced
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2923969032
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -541,6 +541,36 @@ fn summarize_min_max_null_counts(
)
.map(|(idx, _)| idx);
+ // Extract distinct counts from row group column statistics
+ accumulators.distinct_counts_array[logical_schema_index] =
+ if let Some(parquet_idx) = parquet_index {
+ let distinct_counts: Vec<u64> = row_groups_metadata
+ .iter()
+ .filter_map(|rg| {
+ rg.columns()
+ .get(parquet_idx)
+ .and_then(|col| col.statistics())
+ .and_then(|stats| stats.distinct_count_opt())
+ })
+ .collect();
+
+ if distinct_counts.is_empty() {
+ Precision::Absent
+ } else if distinct_counts.len() == 1 {
Review Comment:
Thanks for the reminder @gene-bordegaray, I have followed the advise of @jonathanc-n in faf521161.
Added a `PARTIAL_NDV_THRESHOLD` constant (0.75): if fewer than 75% of row groups report NDV, return `Absent`. Kept as a constant rather than a config option since the statistics extraction path has no config access today. It would require updating a lot of signatures, we can consider that for later.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910786609
##########
datafusion/physical-expr/src/expression_analyzer.rs:
##########
@@ -0,0 +1,1222 @@
+// 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.
+
+//! Pluggable expression-level statistics analysis.
+//!
+//! This module provides an extensible mechanism for computing expression-level
+//! statistics metadata (selectivity, NDV, min/max bounds) following the chain
+//! of responsibility pattern.
+//!
+//! # Overview
+//!
+//! Different expressions have different statistical properties:
+//!
+//! - **Injective functions** (UPPER, LOWER, ABS on non-negative): preserve NDV
+//! - **Non-injective functions** (FLOOR, YEAR, SUBSTRING): reduce NDV
+//! - **Monotonic functions**: allow min/max bound propagation
+//! - **Constants**: NDV = 1, selectivity depends on value
+//!
+//! The default implementation uses classic Selinger-style estimation. Users can
+//! register custom [`ExpressionAnalyzer`] implementations to:
+//!
+//! 1. Provide statistics for custom UDFs
+//! 2. Override default estimation with domain-specific knowledge
+//! 3. Plug in advanced approaches (e.g., histogram-based estimation)
+//!
+//! # Example
+//!
+//! ```ignore
+//! use datafusion_physical_plan::expression_analyzer::*;
+//!
+//! // Create registry with default analyzer
+//! let mut registry = ExpressionAnalyzerRegistry::new();
+//!
+//! // Register custom analyzer (higher priority)
+//! registry.register(Arc::new(MyCustomAnalyzer));
+//!
+//! // Query expression statistics
+//! let selectivity = registry.get_selectivity(&predicate, &input_stats);
+//! ```
+
+use std::fmt::Debug;
+use std::sync::Arc;
+
+use datafusion_common::{ColumnStatistics, ScalarValue, Statistics};
+use datafusion_expr::Operator;
+
+use crate::expressions::{BinaryExpr, Column, Literal, NotExpr};
+use crate::{PhysicalExpr, ScalarFunctionExpr};
+
+// ============================================================================
+// AnalysisResult: Chain of responsibility result type
+// ============================================================================
+
+/// Result of expression analysis - either computed or delegate to next analyzer.
+#[derive(Debug, Clone)]
+pub enum AnalysisResult<T> {
+ /// Analysis was performed, here's the result
+ Computed(T),
+ /// This analyzer doesn't handle this expression; delegate to next
+ Delegate,
+}
+
+impl<T> AnalysisResult<T> {
+ /// Convert to Option, returning None for Delegate
+ pub fn into_option(self) -> Option<T> {
+ match self {
+ AnalysisResult::Computed(v) => Some(v),
+ AnalysisResult::Delegate => None,
+ }
+ }
+
+ /// Returns true if this is a Computed result
+ pub fn is_computed(&self) -> bool {
+ matches!(self, AnalysisResult::Computed(_))
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzer trait
+// ============================================================================
+
+/// Expression-level metadata analysis.
+///
+/// Implementations can handle specific expression types or provide domain
+/// knowledge for custom UDFs. The chain of analyzers is traversed until one
+/// returns [`AnalysisResult::Computed`].
+///
+/// # Implementing a Custom Analyzer
+///
+/// ```ignore
+/// #[derive(Debug)]
+/// struct MyUdfAnalyzer;
+///
+/// impl ExpressionAnalyzer for MyUdfAnalyzer {
+/// fn get_selectivity(
+/// &self,
+/// expr: &Arc<dyn PhysicalExpr>,
+/// input_stats: &Statistics,
+/// ) -> AnalysisResult<f64> {
+/// // Recognize my custom is_valid_email() UDF
+/// if is_my_email_validator(expr) {
+/// return AnalysisResult::Computed(0.8); // ~80% valid
+/// }
+/// AnalysisResult::Delegate
+/// }
+/// }
+/// ```
+pub trait ExpressionAnalyzer: Debug + Send + Sync {
+ /// Estimate selectivity when this expression is used as a predicate.
+ ///
+ /// Returns a value in [0.0, 1.0] representing the fraction of rows
+ /// that satisfy the predicate.
+ fn get_selectivity(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the number of distinct values in the expression's output.
+ ///
+ /// Properties:
+ /// - Injective functions preserve input NDV
+ /// - Non-injective functions reduce NDV (e.g., FLOOR, YEAR)
+ /// - Constants have NDV = 1
+ fn get_distinct_count(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate min/max bounds of the expression's output.
+ ///
+ /// Monotonic functions can transform input bounds:
+ /// - Increasing: (f(min), f(max))
+ /// - Decreasing: (f(max), f(min))
+ /// - Non-monotonic: may need wider bounds or return Delegate
+ fn get_min_max(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ AnalysisResult::Delegate
+ }
+
+ /// Estimate the fraction of null values in the expression's output.
+ ///
+ /// Returns a value in [0.0, 1.0].
+ fn get_null_fraction(
+ &self,
+ _expr: &Arc<dyn PhysicalExpr>,
+ _input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// ExpressionAnalyzerRegistry
+// ============================================================================
+
+/// Registry that chains [`ExpressionAnalyzer`] implementations.
+///
+/// Analyzers are tried in order; the first to return [`AnalysisResult::Computed`]
+/// wins. Register domain-specific analyzers before the default for override.
+#[derive(Debug, Clone)]
+pub struct ExpressionAnalyzerRegistry {
+ analyzers: Vec<Arc<dyn ExpressionAnalyzer>>,
+}
+
+impl Default for ExpressionAnalyzerRegistry {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+impl ExpressionAnalyzerRegistry {
+ /// Create a new registry with the default expression analyzer.
+ pub fn new() -> Self {
+ Self {
+ analyzers: vec![Arc::new(DefaultExpressionAnalyzer)],
+ }
+ }
+
+ /// Create a registry with all built-in analyzers (string, math, datetime, default).
+ pub fn with_builtin_analyzers() -> Self {
+ Self {
+ analyzers: vec![
+ Arc::new(StringFunctionAnalyzer),
+ Arc::new(MathFunctionAnalyzer),
+ Arc::new(DateTimeFunctionAnalyzer),
+ Arc::new(DefaultExpressionAnalyzer),
+ ],
+ }
+ }
+
+ /// Create a registry with custom analyzers (no default).
+ pub fn with_analyzers(analyzers: Vec<Arc<dyn ExpressionAnalyzer>>) -> Self {
+ Self { analyzers }
+ }
+
+ /// Create a registry with custom analyzers plus default as fallback.
+ pub fn with_analyzers_and_default(
+ analyzers: impl IntoIterator<Item = Arc<dyn ExpressionAnalyzer>>,
+ ) -> Self {
+ let mut all: Vec<Arc<dyn ExpressionAnalyzer>> = analyzers.into_iter().collect();
+ all.push(Arc::new(DefaultExpressionAnalyzer));
+ Self { analyzers: all }
+ }
+
+ /// Register an analyzer at the front of the chain (higher priority).
+ pub fn register(&mut self, analyzer: Arc<dyn ExpressionAnalyzer>) {
+ self.analyzers.insert(0, analyzer);
+ }
+
+ /// Get selectivity through the analyzer chain.
+ pub fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(sel) =
+ analyzer.get_selectivity(expr, input_stats)
+ {
+ return Some(sel);
+ }
+ }
+ None
+ }
+
+ /// Get distinct count through the analyzer chain.
+ pub fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<usize> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(ndv) =
+ analyzer.get_distinct_count(expr, input_stats)
+ {
+ return Some(ndv);
+ }
+ }
+ None
+ }
+
+ /// Get min/max bounds through the analyzer chain.
+ pub fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<(ScalarValue, ScalarValue)> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(bounds) =
+ analyzer.get_min_max(expr, input_stats)
+ {
+ return Some(bounds);
+ }
+ }
+ None
+ }
+
+ /// Get null fraction through the analyzer chain.
+ pub fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> Option<f64> {
+ for analyzer in &self.analyzers {
+ if let AnalysisResult::Computed(frac) =
+ analyzer.get_null_fraction(expr, input_stats)
+ {
+ return Some(frac);
+ }
+ }
+ None
+ }
+}
+
+// ============================================================================
+// DefaultExpressionAnalyzer
+// ============================================================================
+
+/// Default expression analyzer with Selinger-style estimation.
+///
+/// Handles common expression types:
+/// - Column references (uses column statistics)
+/// - Binary expressions (AND, OR, comparison operators)
+/// - Literals (constant selectivity/NDV)
+/// - NOT expressions (1 - child selectivity)
+#[derive(Debug, Default, Clone)]
+pub struct DefaultExpressionAnalyzer;
+
+impl DefaultExpressionAnalyzer {
+ /// Get column index from a Column expression
+ fn get_column_index(expr: &Arc<dyn PhysicalExpr>) -> Option<usize> {
+ expr.as_any().downcast_ref::<Column>().map(|c| c.index())
+ }
+
+ /// Get column statistics for an expression if it's a column reference
+ fn get_column_stats<'a>(
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &'a Statistics,
+ ) -> Option<&'a ColumnStatistics> {
+ Self::get_column_index(expr)
+ .and_then(|idx| input_stats.column_statistics.get(idx))
+ }
+
+ /// Recursive selectivity estimation
+ fn estimate_selectivity_recursive(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> f64 {
+ if let AnalysisResult::Computed(sel) = self.get_selectivity(expr, input_stats) {
+ return sel;
+ }
+ 0.5 // Default fallback
+ }
+}
+
+impl ExpressionAnalyzer for DefaultExpressionAnalyzer {
+ fn get_selectivity(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Binary expressions: AND, OR, comparisons
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let left_sel =
+ self.estimate_selectivity_recursive(binary.left(), input_stats);
+ let right_sel =
+ self.estimate_selectivity_recursive(binary.right(), input_stats);
+
+ let sel = match binary.op() {
+ // Logical operators
+ Operator::And => left_sel * right_sel,
+ Operator::Or => left_sel + right_sel - (left_sel * right_sel),
+
+ // Equality: selectivity = 1/NDV
+ Operator::Eq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 / (*ndv as f64));
+ }
+ 0.1 // Default equality selectivity
+ }
+
+ // Inequality: selectivity = 1 - 1/NDV
+ Operator::NotEq => {
+ if let Some(ndv) = Self::get_column_stats(binary.left(), input_stats)
+ .and_then(|s| s.distinct_count.get_value())
+ .filter(|&&ndv| ndv > 0)
+ {
+ return AnalysisResult::Computed(1.0 - (1.0 / (*ndv as f64)));
+ }
+ 0.9
+ }
+
+ // Range predicates: classic 1/3 estimate
+ Operator::Lt | Operator::LtEq | Operator::Gt | Operator::GtEq => 0.33,
+
+ // LIKE: depends on pattern, use conservative estimate
+ Operator::LikeMatch | Operator::ILikeMatch => 0.25,
+ Operator::NotLikeMatch | Operator::NotILikeMatch => 0.75,
+
+ // Other operators: default
+ _ => 0.5,
+ };
+
+ return AnalysisResult::Computed(sel);
+ }
+
+ // NOT expression: 1 - child selectivity
+ if let Some(not_expr) = expr.as_any().downcast_ref::<NotExpr>() {
+ let child_sel =
+ self.estimate_selectivity_recursive(not_expr.arg(), input_stats);
+ return AnalysisResult::Computed(1.0 - child_sel);
+ }
+
+ // Literal boolean: 0.0 or 1.0
+ if let Some(b) = expr
+ .as_any()
+ .downcast_ref::<Literal>()
+ .and_then(|lit| match lit.value() {
+ ScalarValue::Boolean(Some(b)) => Some(*b),
+ _ => None,
+ })
+ {
+ return AnalysisResult::Computed(if b { 1.0 } else { 0.0 });
+ }
+
+ // Column reference as predicate (boolean column)
+ if expr.as_any().downcast_ref::<Column>().is_some() {
+ return AnalysisResult::Computed(0.5);
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ // Column reference: use column NDV
+ if let Some(ndv) = Self::get_column_stats(expr, input_stats)
+ .and_then(|col_stats| col_stats.distinct_count.get_value().copied())
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+
+ // Literal: NDV = 1
+ if expr.as_any().downcast_ref::<Literal>().is_some() {
+ return AnalysisResult::Computed(1);
+ }
+
+ // BinaryExpr: for injective operations (arithmetic with literal), preserve NDV
+ if let Some(binary) = expr.as_any().downcast_ref::<BinaryExpr>() {
+ let is_arithmetic = matches!(
+ binary.op(),
+ Operator::Plus
+ | Operator::Minus
+ | Operator::Multiply
+ | Operator::Divide
+ | Operator::Modulo
+ );
+
+ if is_arithmetic {
+ // If one side is a literal, the operation is injective on the other side
+ let left_is_literal = binary.left().as_any().is::<Literal>();
+ let right_is_literal = binary.right().as_any().is::<Literal>();
+
+ if left_is_literal {
+ // NDV comes from right side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.right(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ } else if right_is_literal {
+ // NDV comes from left side
+ if let AnalysisResult::Computed(ndv) =
+ self.get_distinct_count(binary.left(), input_stats)
+ {
+ return AnalysisResult::Computed(ndv);
+ }
+ }
+ // Both sides are non-literals: could combine, but delegate for now
+ }
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_min_max(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<(ScalarValue, ScalarValue)> {
+ // Column reference: use column min/max
+ if let Some((min, max)) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ match (
+ col_stats.min_value.get_value(),
+ col_stats.max_value.get_value(),
+ ) {
+ (Some(min), Some(max)) => Some((min.clone(), max.clone())),
+ _ => None,
+ }
+ })
+ {
+ return AnalysisResult::Computed((min, max));
+ }
+
+ // Literal: min = max = value
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let val = lit_expr.value().clone();
+ return AnalysisResult::Computed((val.clone(), val));
+ }
+
+ AnalysisResult::Delegate
+ }
+
+ fn get_null_fraction(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<f64> {
+ // Column reference: null_count / num_rows
+ if let Some(fraction) =
+ Self::get_column_stats(expr, input_stats).and_then(|col_stats| {
+ let null_count = col_stats.null_count.get_value().copied()?;
+ let num_rows = input_stats.num_rows.get_value().copied()?;
+ if num_rows > 0 {
+ Some(null_count as f64 / num_rows as f64)
+ } else {
+ None
+ }
+ })
+ {
+ return AnalysisResult::Computed(fraction);
+ }
+
+ // Literal: null fraction depends on whether it's null
+ if let Some(lit_expr) = expr.as_any().downcast_ref::<Literal>() {
+ let is_null = lit_expr.value().is_null();
+ return AnalysisResult::Computed(if is_null { 1.0 } else { 0.0 });
+ }
+
+ AnalysisResult::Delegate
+ }
+}
+
+// ============================================================================
+// StringFunctionAnalyzer
+// ============================================================================
+
+/// Analyzer for string functions.
+///
+/// - Injective (preserve NDV): UPPER, LOWER, TRIM, LTRIM, RTRIM, REVERSE
+/// - Non-injective (reduce NDV): SUBSTRING, LEFT, RIGHT, REPLACE
+#[derive(Debug, Default, Clone)]
+pub struct StringFunctionAnalyzer;
+
+impl StringFunctionAnalyzer {
+ /// Check if a function is injective (one-to-one)
+ pub fn is_injective(func_name: &str) -> bool {
+ matches!(
+ func_name.to_uppercase().as_str(),
+ "UPPER" | "LOWER" | "TRIM" | "LTRIM" | "RTRIM" | "REVERSE" | "INITCAP"
+ )
+ }
+
+ /// Get NDV reduction factor for non-injective functions
+ pub fn ndv_reduction_factor(func_name: &str) -> Option<f64> {
+ match func_name.to_uppercase().as_str() {
+ "SUBSTRING" | "LEFT" | "RIGHT" => Some(0.5),
+ "REPLACE" => Some(0.8),
+ _ => None,
+ }
+ }
+}
+
+impl ExpressionAnalyzer for StringFunctionAnalyzer {
+ fn get_distinct_count(
+ &self,
+ expr: &Arc<dyn PhysicalExpr>,
+ input_stats: &Statistics,
+ ) -> AnalysisResult<usize> {
+ let Some(func) = expr.as_any().downcast_ref::<ScalarFunctionExpr>() else {
+ return AnalysisResult::Delegate;
+ };
+
+ let func_name = func.name();
+ let Some(first_arg) = func.args().first() else {
+ return AnalysisResult::Delegate;
+ };
+
+ // Get input NDV
+ let Some(input_ndv) = DefaultExpressionAnalyzer
Review Comment:
Good catch, will address in the follow-up PR. The function analyzers should delegate through the chain rather than hard-coding `DefaultExpressionAnalyzer`.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#issuecomment-4032216072
Rebased on latest `main` to fix the branch drift. No code changes, just new SHAs from the rebase.
@gene-bordegaray: the code you reviewed is unchanged. The only addition since your approval is commit [`e352c28`](https://github.com/apache/datafusion/pull/19957/commits/e352c2839), which updates test expectations in `test_hash_join_partition_statistics` (added by [#20711](https://github.com/apache/datafusion/pull/20711)) to account for NDV propagation through merges. No new logic was added.
@jonathanc-n: as you suggested, the `ExpressionAnalyzer` commits have been removed from this PR and will come in a [follow-up](https://github.com/asolimando/datafusion/tree/asolimando/ndv-expression-analyzer).
@xudong963: I replied to your [comments on NDV merge strategy](https://github.com/apache/datafusion/pull/19957#discussion_r2897501498), let me know if you have further concerns or if we should take the discussion to an RFC/issue.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2912728465
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -541,6 +541,36 @@ fn summarize_min_max_null_counts(
)
.map(|(idx, _)| idx);
+ // Extract distinct counts from row group column statistics
+ accumulators.distinct_counts_array[logical_schema_index] =
+ if let Some(parquet_idx) = parquet_index {
+ let distinct_counts: Vec<u64> = row_groups_metadata
+ .iter()
+ .filter_map(|rg| {
+ rg.columns()
+ .get(parquet_idx)
+ .and_then(|col| col.statistics())
+ .and_then(|stats| stats.distinct_count_opt())
+ })
+ .collect();
+
+ if distinct_counts.is_empty() {
+ Precision::Absent
+ } else if distinct_counts.len() == 1 {
Review Comment:
yes I will try to get #20184 out today ot tomorrow now that #20570 is out
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2935277064
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
This being moved from union.rs makes me wonder if this should be generalized to all operators.
Say rather than just merging two columns we were to merge three: A, B, C. This can result in different outcomes with the same columns being merged since the columns stats are smeared after the first merge.
Example:
```
- A = [0,100], NDV=80
- B = [50,150], NDV=60
- C = [100,200], NDV=50
Scenarios:
- (A+B)+C = 135
- A+(B+C) = 137
```
I know that while in union.rs this problem still existed but it was more tightly scoped.
Is there a way we could make this more explicit in the documentation / plan follow up work to handle merging?
I would think that preserving the shape of the distinct values in some way after merging is what we want. This might require more plumbing and could come back to this.
Let me know your thoughts.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 merged PR #19957:
URL: https://github.com/apache/datafusion/pull/19957
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2728830062
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Good question! I have an idea of how this could evolve, based on my experience with Apache Calcite.
The idea is to make statistics propagation pluggable, with each relational operator having a default but configurable logic for how statistics propagate through it.
The default implementation would follow classic Selinger-style estimation (selectivity factors, independence assumptions), as seen in this PR. A nice intro to this can be found [here](https://15799.courses.cs.cmu.edu/spring2025/slides/13-cardinalities1.pdf). That's what most OSS databases implement by default.
Following DataFusion's philosophy as a customizable framework, users should be able to override and complement this logic when needed.
Proposed architecture:
- `StatisticsProvider`: chain element that computes statistics for specific operators (returns `Computed` or `Delegate`)
- `StatisticsRegistry`: chains providers, would live in `SessionState`
- `CardinalityEstimator`: unified interface for metadata queries (row count, selectivity, NDV, ...) - similar to Calcite's [RelMetadataProvider](https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/metadata/RelMetadataProvider.html)/[RelMetadataQuery](https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/metadata/RelMetadataQuery.html)
- `ExtendedStatistics`: `Statistics` with type-safe custom extensions for histograms, sketches, etc. (I am looking at type-erased maps for that but I am not sure that's the best way to implement it)
- `ExpressionAnalyzerRegistry`+`ExpressionAnalyzer`: similar concept of chain for expression analyzers, equivalent to what detailed above for the operators, so that built-in and UDF can be covered
This follows the same chain-of-responsibility pattern that the https://datafusion.apache.org/blog/2026/01/12/extending-sql/ solved for custom syntax/relations. Built-in operators get default handling, custom `ExecutionPlan` nodes can plug in their own logic, and unknown cases delegate down the chain. To override the default estimation (e.g., with histogram-based approaches), you register your provider before the default one.
StatisticsV2 and Distribution-based are very advanced and interesting statistics, but I see them more as an extension via `ExtendedStatistics` than taking over the default implementation.
If this sounds interesting and aligns with community interest, I can provide a more detailed design doc and an epic to break down the work.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gabotechs (via GitHub)" <gi...@apache.org>.
gabotechs commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2726962898
##########
datafusion/common/src/stats.rs:
##########
@@ -632,7 +632,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
+ col_stats.distinct_count = col_stats
+ .distinct_count
+ .get_value()
+ .max(item_col_stats.distinct_count.get_value())
+ .map(|&v| Precision::Inexact(v))
+ .unwrap_or(Precision::Absent);
Review Comment:
👍 thinks sounds pretty reasonable to me
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
I think this TODO comment is right on point: if we wanted to compute statistics for all expressions here, it would become unmanageable pretty soon.
Even if the estimation about expressions referencing single columns here is an improvement, it would be awesome if we could try to be one step ahead and think how proper stats propagation across expressions would look like. That way, this PR, instead of special-handling one particular case, it could be setting the foundation on top of which more people can start contributing smarter stats calculation.
I see that some prior work has been done in order to improve stats propagation in expressions. Some context here:
- https://github.com/apache/datafusion/pull/14699
- https://github.com/apache/datafusion/issues/14896
By looking at the API for handling statistics in expressions shipped in https://github.com/apache/datafusion/pull/14699... I would not know how to use it in order to properly calculate NDV values. I get the impression that 1) we do not want to introduce yet another API for propagating stats across expressions and 2) the current "new" API shipped in https://github.com/apache/datafusion/pull/14699 is not suitable for propagating NDV values.
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -411,53 +415,6 @@ fn create_max_min_accs(
(max_values, min_values)
}
-fn get_col_stats(
Review Comment:
Correct me if I'm wrong but the `get_col_stats()` changes look more like a noop refactor right? I think it looks good 👍 but just double checking that
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2913413380
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
Actually @jonathanc-n in https://github.com/apache/datafusion/pull/20846#discussion_r2913027707 proposes to use what Trino has for updating NDV when min and max are available, which is quite elegant (quoting from his message):
```text
// for merging A + B when min/max are available
overlap_a = (overlap range) / (A's range) // fraction of A's range that overlaps with B
overlap_b = (overlap range) / (B's range) // fraction of B's range that overlaps with A
new_ndv = max(overlap_a * NDV_a, overlap_b * NDV_b) // NDV in the overlapping range
+ (1 - overlap_a) * NDV_a // NDV unique to A's range
+ (1 - overlap_b) * NDV_b // NDV unique to B's range
```
The formula ranges between `[max(ndvs), sum(ndvs)]`, from full overlap to no overlap (under the uniform distribution of NDV values in the `[min, max]` range, which is classic for scalar-based statistics propagation).
When min/max are not available, we can fall back to `max`, as currently implemented.
I can update `try_merge` accordingly, if you agree, @xudong963 @jonathanc-n.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2922215441
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
fyi, the #20846 is merged
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2910738802
##########
datafusion/common/src/stats.rs:
##########
@@ -660,7 +637,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
Review Comment:
HyperLogLog is a classic way to process this, but for a large dataset, it takes a long time to process.
IIRC, the merge method may be called during query execution, so using `HyperLogLog` here isn't ideal.
So I'm looking forward to hearing some other thoughts!
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2936704265
##########
datafusion/common/src/stats.rs:
##########
@@ -672,6 +684,96 @@ impl Statistics {
}
}
+/// Estimates the combined number of distinct values (NDV) when merging two
+/// column statistics, using range overlap to avoid double-counting shared values.
+///
+/// Assumes values are distributed uniformly within each input's
+/// `[min, max]` range (the standard assumption when only summary
+/// statistics are available). Under uniformity the fraction of an input's
+/// distinct values that land in a sub-range equals the fraction of
+/// the range that sub-range covers.
+///
+/// The combined value space is split into three disjoint regions:
+///
+/// ```text
+/// |-- only A --|-- overlap --|-- only B --|
+/// ```
+///
+/// * **Only in A/B** - values outside the other input's range
+/// contribute `(1 - overlap_a) * NDV_a` and `(1 - overlap_b) * NDV_b`.
+/// * **Overlap** - both inputs may produce values here. We take
+/// `max(overlap_a * NDV_a, overlap_b * NDV_b)` rather than the
+/// sum because values in the same sub-range are likely shared
+/// (the smaller set is assumed to be a subset of the larger).
+///
+/// The formula ranges between `[max(NDV_a, NDV_b), NDV_a + NDV_b]`,
+/// from full overlap to no overlap.
+///
+/// ```text
+/// NDV = max(overlap_a * NDV_a, overlap_b * NDV_b) [intersection]
+/// + (1 - overlap_a) * NDV_a [only in A]
+/// + (1 - overlap_b) * NDV_b [only in B]
+/// ```
+///
+/// Returns `None` when min/max are absent or distance is unsupported
+/// (e.g. strings), in which case the caller should fall back to a simpler
+/// estimate.
+pub fn estimate_ndv_with_overlap(
Review Comment:
This being moved from union.rs makes me wonder if this should be generalized to all operators.
Say rather than just merging two columns we were to merge three: A, B, C. This can result in different outcomes with the same columns being merged since the columns stats are smeared after the first merge.
Example:
```
- A = [0,100], NDV=80
- B = [50,150], NDV=60
- C = [100,200], NDV=50
Scenarios:
- (A+B)+C = 135
- A+(B+C) = 137
```
I know that while in union.rs this problem still existed but it was more tightly scoped.
Is there a way we could make this more explicit in the documentation / plan follow up work to handle merging?
I would think that preserving the shape of the distinct values in some way after merging is what we want. This might require more plumbing and could come back to this.
Let me know your thoughts.
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722857543
##########
datafusion/datasource-parquet/src/metadata.rs:
##########
@@ -466,9 +423,52 @@ struct StatisticsAccumulators<'a> {
is_min_value_exact: &'a mut [Option<bool>],
is_max_value_exact: &'a mut [Option<bool>],
column_byte_sizes: &'a mut [Precision<usize>],
+ distinct_counts_array: &'a mut [Precision<usize>],
}
-fn summarize_min_max_null_counts(
+impl StatisticsAccumulators<'_> {
Review Comment:
didn't know about this notation, an anonymous lifetime. cool 😄
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722383532
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
noice, this is useful thanks for understanding implications with using and propagating distincts. thank you 😄
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2722383532
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
noice, this is useful thanks for understanding more implications with this metadata usage thank you 😄
--
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: Extract NDV (distinct_count) statistics from Parquet metadata [datafusion]
Posted by "gabotechs (via GitHub)" <gi...@apache.org>.
gabotechs commented on code in PR #19957:
URL: https://github.com/apache/datafusion/pull/19957#discussion_r2726984397
##########
datafusion/physical-expr/src/projection.rs:
##########
@@ -660,9 +660,25 @@ impl ProjectionExprs {
}
}
} else {
- // TODO stats: estimate more statistics from expressions
- // (expressions should compute their statistics themselves)
- ColumnStatistics::new_unknown()
+ // TODO: expressions should compute their own statistics
Review Comment:
Do you have any thoughts about how the current `Distribution`-based API could be used for propagating NDV stats across expressions?
##########
datafusion/common/src/stats.rs:
##########
@@ -632,7 +632,14 @@ impl Statistics {
col_stats.max_value = col_stats.max_value.max(&item_col_stats.max_value);
col_stats.min_value = col_stats.min_value.min(&item_col_stats.min_value);
col_stats.sum_value = col_stats.sum_value.add(&item_col_stats.sum_value);
- col_stats.distinct_count = Precision::Absent;
+ // Use max as a conservative lower bound for distinct count
+ // (can't accurately merge NDV since duplicates may exist across partitions)
+ col_stats.distinct_count = col_stats
+ .distinct_count
+ .get_value()
+ .max(item_col_stats.distinct_count.get_value())
+ .map(|&v| Precision::Inexact(v))
+ .unwrap_or(Precision::Absent);
Review Comment:
👍 this sounds pretty reasonable to me
--
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