You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "buraksenn (via GitHub)" <gi...@apache.org> on 2026/04/08 14:57:17 UTC
[PR] feat: extend single ndv optimization to non-numeric types for equality predicates [datafusion]
buraksenn opened a new pull request, #21473:
URL: https://github.com/apache/datafusion/pull/21473
## Which issue does this PR close?
- Closes #21109 and #21111.
## Rationale for this change
In the case of equality we can say ndv is 1 for non-numeric types as well. Please check issues for detailed explanations
## What changes are included in this PR?
Adding a type-agnostic pattern-matching layer that inspects the predicate tree for col = literal shapes and sets NDV=Exact(1) regardless of column type
## Are these changes tested?
Yes existing and additional unit tests.
## Are there any user-facing changes?
No
--
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: extend single ndv optimization to non-numeric types for equality predicates [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4214938482
Thanks @buraksenn for tackling both #21109 and #21111 together with this type-agnostic approach, also the test consolidation over the separate per-type functions is a nice improvement.
A couple of minor notes/questions:
- Since we can't rely on interval analysis for string-based columns, I am not sure we handle correctly "contradictory" filters like `name = 'alice' AND name = 'bob'`, which should get `Exact(0)` as happening for numeric types. I don't see this as a blocker because it's not worse than before and this is an edge case, but it's good to know where we stand and file a follow-up issue, if needed.
- On a similar note, I was wondering if something like `col = NULL` gets simplified as `false` (under the unknown as false semantics for predicates in `WHERE` clauses). In case it doesn't, it would be worth adding a test making sure we don't set NDV to 1.
- Did you manage to understand why the interval analysis doesn't seem to work as expected for temporal types? It might be worth filing a separate issue for that if you have bandwidth, so we don't lose track of this 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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4216297949
> > Thanks @asolimando for the review. I've checked this again. To make it generic I've missed that I can actually make temporal types work with interval arithmetic analysis since they are `i64` backed as well.
>
> Sounds great!
>
> > Thus answering all:
> >
> > * I'm kinda afraid into getting this kind of complex behavior since I may not know what can be a side effect. Maybe I can add it to this PR and see the reviews
>
> I think it's enough to add a test to see what happens, before we would have been returning the same NDV value for the input column anyway, I don't think we are doing worse than that, let's add a test and possibly file an issue to not lose the context we built.
>
> > * I've missed this totally will push to this branch.
> > * For this, adding support for temporal types seem to be better as I've missed whiel trying to make it generic so I'll open a PR parallel to this one.
>
> No worries, making it type agnostic was a good call IMO, but what can be handled with interval arithmetic should do it as we can benefit from all the handling of edge cases like the "incoherent predicate" above and possibly others I couldn't think of.
>
> > I'm working on both changes now and will handle this in the upcoming hours
>
> No worries, feel free to ping me if you need a review, happy to take a look, thanks for working on this and helping out on so many stats-related tasks :)
Thanks @asolimando I've opened #21520 temporal types I think it is very straightforward and contained PR and only left non-arithmetic supporting changes here.
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4266442134
Thanks for the detailed review @berkaysynnada I've applied each comment and pushed the changes
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4262334608
> @buraksenn I think this is in good shape, you might want to ping a committer (ideally someone with context on this who helped merging related PRs).
Makes sense @asolimando thanks. @2010YOUY01, @xudong963 pinging you since you've taken a look to similar PRs. Can you review this PR whenever you've time to do please? (also @berkaysynnada)
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#discussion_r3098809724
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
Review Comment:
now I've only compute this once thanks
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada merged PR #21473:
URL: https://github.com/apache/datafusion/pull/21473
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on code in PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#discussion_r3098808357
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
+ (
+ selectivity,
+ collect_new_statistics(
+ schema,
+ &input_stats.column_statistics,
+ analysis_ctx.boundaries,
+ match &filtered_num_rows {
+ Precision::Absent => None,
+ p => Some(*p),
+ },
+ ),
+ )
+ };
- // Estimate (inexact) selectivity of predicate
- let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
let num_rows = num_rows.with_estimated_selectivity(selectivity);
let total_byte_size = total_byte_size.with_estimated_selectivity(selectivity);
- let column_statistics = collect_new_statistics(
- schema,
- &input_stats.column_statistics,
- analysis_ctx.boundaries,
- match &num_rows {
- Precision::Absent => None,
- p => Some(*p),
- },
- );
+ if is_infeasible {
+ for col_stat in &mut column_statistics {
+ col_stat.distinct_count = Precision::Exact(0);
+ }
+ } else {
+ for idx in eq_columns.keys() {
+ if *idx < column_statistics.len()
+ && column_statistics[*idx].distinct_count != Precision::Exact(0)
+ {
+ column_statistics[*idx].distinct_count = Precision::Exact(1);
+ }
+ }
+ }
+
Review Comment:
Thanks, makes sense I've applied this
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4262211335
@buraksenn I think this is in good shape, you might want to ping a committer (ideally someone with context on this who helped merging related PRs).
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#discussion_r3097325977
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -762,6 +787,60 @@ impl EmbeddedProjection for FilterExec {
}
}
+/// Collects column equality information from `col = literal` predicates in a
+/// conjunction.
+///
+/// Returns `(eq_columns, is_infeasible)`:
+/// - `eq_columns`: column indices constrained to a single value.
+/// - `is_infeasible`: `true` when the same column is equated to two different
+/// non-null literals (e.g. `name = 'alice' AND name = 'bob'`), which is
+/// always unsatisfiable.
+///
+/// Only AND conjunctions are traversed; OR is intentionally skipped
+/// since `a = 1 OR a = 2` does not pin NDV to 1.
+fn collect_equality_columns(
+ predicate: &Arc<dyn PhysicalExpr>,
+) -> (HashMap<usize, ScalarValue>, bool) {
Review Comment:
The returned `HashMap<usize, ScalarValue>` is only used for its keys. The `ScalarValues` are only needed internally to detect contradictions and are discarded by the caller. Could this return `(HashSet<usize>, bool)` (or even `(Vec<usize>, bool)`) to match what the caller actually needs?
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
+ (
+ selectivity,
+ collect_new_statistics(
+ schema,
+ &input_stats.column_statistics,
+ analysis_ctx.boundaries,
+ match &filtered_num_rows {
+ Precision::Absent => None,
+ p => Some(*p),
+ },
+ ),
+ )
+ };
- // Estimate (inexact) selectivity of predicate
- let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
let num_rows = num_rows.with_estimated_selectivity(selectivity);
let total_byte_size = total_byte_size.with_estimated_selectivity(selectivity);
- let column_statistics = collect_new_statistics(
- schema,
- &input_stats.column_statistics,
- analysis_ctx.boundaries,
- match &num_rows {
- Precision::Absent => None,
- p => Some(*p),
- },
- );
+ if is_infeasible {
+ for col_stat in &mut column_statistics {
+ col_stat.distinct_count = Precision::Exact(0);
+ }
+ } else {
+ for idx in eq_columns.keys() {
+ if *idx < column_statistics.len()
+ && column_statistics[*idx].distinct_count != Precision::Exact(0)
+ {
+ column_statistics[*idx].distinct_count = Precision::Exact(1);
+ }
+ }
+ }
+
Review Comment:
The function matches on `is_infeasible` twice: once to pick the selectivity/column_statistics tuple, and again here at the bottom to decide between zeroing out distinct_count vs. setting it to 1. Would it be cleaner to move each branch's distinct_count adjustment into the branch where that column_statistics is produced, so each branch is self-contained and this second match goes away? like
```
let (selectivity, column_statistics) = if is_infeasible {
let mut cs = input_stats.to_inexact().column_statistics;
for c in &mut cs { c.distinct_count = Precision::Exact(0); }
(0.0, cs)
} else if !check_support(predicate, schema) {
let mut cs = input_stats.to_inexact().column_statistics;
for &idx in eq_columns.keys() {
if idx < cs.len() && cs[idx].distinct_count != Precision::Exact(0) {
cs[idx].distinct_count = Precision::Exact(1);
}
}
(default_selectivity as f64 / 100.0, cs)
} else {
// interval-analysis path — `collect_new_statistics` already sets Exact(1)
// when the interval collapses to a single value, so no post-fix needed.
let ctx = AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
let ctx = analyze(predicate, ctx, schema)?;
let selectivity = ctx.selectivity.unwrap_or(1.0);
let filtered = num_rows.with_estimated_selectivity(selectivity);
let cs = collect_new_statistics(schema, &input_stats.column_statistics,
ctx.boundaries,
(!matches!(filtered, Precision::Absent)).then_some(filtered));
(selectivity, cs)
};
```
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
+ (
+ selectivity,
+ collect_new_statistics(
Review Comment:
For the supported-type path, `collect_new_statistics` already sets distinct_count = Exact(1) when an interval collapses to a single value (is_single_value check inside it). The bottom eq_columns loop then runs again and sets it to Exact(1) a second time. Not wrong, but redundant. If you take up the restructuring above, the override is only needed in the !check_support branch
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -762,6 +787,60 @@ impl EmbeddedProjection for FilterExec {
}
}
+/// Collects column equality information from `col = literal` predicates in a
+/// conjunction.
+///
+/// Returns `(eq_columns, is_infeasible)`:
+/// - `eq_columns`: column indices constrained to a single value.
+/// - `is_infeasible`: `true` when the same column is equated to two different
+/// non-null literals (e.g. `name = 'alice' AND name = 'bob'`), which is
+/// always unsatisfiable.
+///
+/// Only AND conjunctions are traversed; OR is intentionally skipped
+/// since `a = 1 OR a = 2` does not pin NDV to 1.
+fn collect_equality_columns(
+ predicate: &Arc<dyn PhysicalExpr>,
+) -> (HashMap<usize, ScalarValue>, bool) {
+ let mut eq_columns: HashMap<usize, ScalarValue> = HashMap::new();
+ let mut infeasible = false;
+
+ for expr in split_conjunction(predicate) {
+ let Some(binary) = expr.downcast_ref::<BinaryExpr>() else {
+ continue;
+ };
+ if *binary.op() != Operator::Eq {
+ continue;
+ }
+ let left = binary.left();
+ let right = binary.right();
+ let pair = if let Some(col) = left.downcast_ref::<Column>()
+ && let Some(lit) = right.downcast_ref::<Literal>()
+ && !lit.value().is_null()
+ {
+ Some((col.index(), lit.value().clone()))
+ } else if let Some(col) = right.downcast_ref::<Column>()
+ && let Some(lit) = left.downcast_ref::<Literal>()
+ && !lit.value().is_null()
+ {
+ Some((col.index(), lit.value().clone()))
+ } else {
+ None
+ };
+
+ if let Some((idx, value)) = pair {
+ if let Some(prev) = eq_columns.get(&idx) {
+ if *prev != value {
Review Comment:
you can use `Entry` here. And also, once infeasible is true, subsequent conjuncts don't change the outcome. A break there avoids scanning the rest of the predicate.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
Review Comment:
`num_rows.with_estimated_selectivity(selectivity)` is computed once inside the interval branch as `filtered_num_rows`, then again right after the match for the returned num_rows. Could be computed once and reused.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -308,44 +309,68 @@ impl FilterExec {
&self.projection
}
- /// Calculates `Statistics` for `FilterExec`, by applying selectivity (either default, or estimated) to input statistics.
+ /// Calculates `Statistics` for `FilterExec`, by applying selectivity
+ /// (either default, or estimated) to input statistics.
+ ///
+ /// Equality predicates (`col = literal`) set NDV to `Exact(1)`, or
+ /// `Exact(0)` when the predicate is contradictory (e.g. `a = 1 AND a = 2`).
pub(crate) fn statistics_helper(
schema: &SchemaRef,
input_stats: Statistics,
predicate: &Arc<dyn PhysicalExpr>,
default_selectivity: u8,
) -> Result<Statistics> {
- if !check_support(predicate, schema) {
- let selectivity = default_selectivity as f64 / 100.0;
- let mut stats = input_stats.to_inexact();
- stats.num_rows = stats.num_rows.with_estimated_selectivity(selectivity);
- stats.total_byte_size = stats
- .total_byte_size
- .with_estimated_selectivity(selectivity);
- return Ok(stats);
- }
+ let (eq_columns, is_infeasible) = collect_equality_columns(predicate);
let num_rows = input_stats.num_rows;
let total_byte_size = input_stats.total_byte_size;
- let input_analysis_ctx =
- AnalysisContext::try_from_statistics(schema, &input_stats.column_statistics)?;
- let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let (selectivity, mut column_statistics) = if is_infeasible {
+ (0.0, input_stats.to_inexact().column_statistics)
+ } else if !check_support(predicate, schema) {
+ (
+ default_selectivity as f64 / 100.0,
+ input_stats.to_inexact().column_statistics,
+ )
+ } else {
+ let input_analysis_ctx = AnalysisContext::try_from_statistics(
+ schema,
+ &input_stats.column_statistics,
+ )?;
+ let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
+ let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
+ let filtered_num_rows = num_rows.with_estimated_selectivity(selectivity);
+ (
+ selectivity,
+ collect_new_statistics(
+ schema,
+ &input_stats.column_statistics,
+ analysis_ctx.boundaries,
+ match &filtered_num_rows {
+ Precision::Absent => None,
+ p => Some(*p),
+ },
+ ),
+ )
+ };
- // Estimate (inexact) selectivity of predicate
- let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
let num_rows = num_rows.with_estimated_selectivity(selectivity);
let total_byte_size = total_byte_size.with_estimated_selectivity(selectivity);
- let column_statistics = collect_new_statistics(
- schema,
- &input_stats.column_statistics,
- analysis_ctx.boundaries,
- match &num_rows {
- Precision::Absent => None,
- p => Some(*p),
- },
- );
+ if is_infeasible {
Review Comment:
When the predicate is infeasible we correctly set num_rows = 0 and distinct_count = Exact(0) for every column, but min_value, max_value, and null_count carry over from the input unchanged. That leaves internally contradictory stats downstream; e.g. for` a = 1 AND a = 2` on an input with min=1, max=100, null_count=5, distinct=80, the output becomes rows=0, distinct=0, min=1, max=100, null_count=5. A reader that trusts null_count=5 on a zero-row plan would get confused.
Worth also clearing null_count to Exact(0) and min_value/max_value to Precision::Absent
--
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: extend single ndv optimization to non-arithmetic supporting types for equality predicates [datafusion]
Posted by "berkaysynnada (via GitHub)" <gi...@apache.org>.
berkaysynnada commented on code in PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#discussion_r3097388698
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -2264,78 +2343,252 @@ mod tests {
}
#[tokio::test]
- async fn test_filter_statistics_equality_sets_ndv_to_one() -> Result<()> {
- // a: min=1, max=100, ndv=80
- let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
- let input = Arc::new(StatisticsExec::new(
- Statistics {
- num_rows: Precision::Inexact(100),
- total_byte_size: Precision::Inexact(400),
- column_statistics: vec![ColumnStatistics {
- min_value: Precision::Inexact(ScalarValue::Int32(Some(1))),
- max_value: Precision::Inexact(ScalarValue::Int32(Some(100))),
- distinct_count: Precision::Inexact(80),
+ async fn test_filter_statistics_equality_ndv() -> Result<()> {
Review Comment:
I may have missed it, but is there a test for something like` a = 1 AND a = 1 AND b = 2`? Would be nice to have if not.
--
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: extend single ndv optimization to non-numeric types for equality predicates [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4215833878
> Thanks @asolimando for the review. I've checked this again. To make it generic I've missed that I can actually make temporal types work with interval arithmetic analysis since they are `i64` backed as well.
Sounds great!
> Thus answering all:
>
> * I'm kinda afraid into getting this kind of complex behavior since I may not know what can be a side effect. Maybe I can add it to this PR and see the reviews
I think it's enough to add a test to see what happens, before we would have been returning the same NDV value for the input column anyway, I don't think we are doing worse than that, let's add a test and possibly file an issue to not lose the context we built.
> * I've missed this totally will push to this branch.
> * For this, adding support for temporal types seem to be better as I've missed whiel trying to make it generic so I'll open a PR parallel to this one.
No worries, making it type agnostic was a good call IMO, but what can be handled with interval arithmetic should do it as we can benefit from all the handling of edge cases like the "incoherent predicate" above and possibly others I couldn't think of.
> I'm working on both changes now and will handle this in the upcoming hours
No worries, feel free to ping me if you need a review, happy to take a look, thanks for working on this and helping out on so many stats-related tasks :)
--
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: extend single ndv optimization to non-numeric types for equality predicates [datafusion]
Posted by "buraksenn (via GitHub)" <gi...@apache.org>.
buraksenn commented on PR #21473:
URL: https://github.com/apache/datafusion/pull/21473#issuecomment-4215402177
Thanks @asolimando for the review. I've checked this again. To make it generic I've missed that I can actually make temporal types work with interval arithmetic analysis since they are `i64` backed as well.
Thus answering all:
- I'm kinda afraid into getting this kind of complex behavior since I may not know what can be a side effect. Maybe I can add it to this PR and see the reviews
- I've missed this totally will push to this branch.
- For this, adding support for temporal types seem to be better as I've missed whiel trying to make it generic so I'll open a PR parallel to this one.
I'm working on both changes now and will handle this in the upcoming hours
--
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