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/03/20 17:42:08 UTC
[PR] Cap NDV at row count in statistics estimation [datafusion]
asolimando opened a new pull request, #21081:
URL: https://github.com/apache/datafusion/pull/21081
## Which issue does this PR close?
- Part of #20766
## Rationale for this change
After a filter reduces a table from 100 to 10 rows, or a LIMIT 10 caps the output, the NDV (e.g. 80) should not exceed the new row count. Without capping, join cardinality estimation uses an inflated denominator, leading to inaccurate estimates.
## What changes are included in this PR?
Cap `distinct_count` at `num_rows` in three places to prevent NDV from exceeding the actual row count:
- `max_distinct_count` in join cardinality estimation (`joins/utils.rs`)
- `collect_new_statistics` in filter output statistics (`filter.rs`)
- `Statistics::with_fetch` (`stats.rs`), which covers `GlobalLimitExec`, `LocalLimitExec`, `SortExec` (with fetch), `CoalescePartitionsExec` (with fetch), and `CoalesceBatchesExec` (with fetch)
Note: NDV capping for `AggregateExec` is covered separately in #20926.
## Are these changes tested?
- `test_filter_statistics_ndv_capped_at_row_count` - verifies NDV capped at filtered row count
- 2 new join cardinality test cases - NDV > rows on both/one side
- Updated `test_join_cardinality` expected values for capped NDV
- `test_with_fetch_caps_ndv_at_row_count` - verifies NDV capped after LIMIT
- `test_with_fetch_ndv_below_row_count_unchanged` - verifies NDV untouched when already below row count
- All existing `with_fetch` tests pass
## Are there any user-facing changes?
No public API changes. Only internal statistics estimation is affected.
Disclaimer: I used AI to assist in the code generation, I have manually reviewed the output and it matches my intention and understanding.
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066567334
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -781,6 +782,7 @@ fn collect_new_statistics(
schema: &SchemaRef,
input_column_stats: &[ColumnStatistics],
analysis_boundaries: Vec<ExprBoundaries>,
+ filtered_num_rows: Option<usize>,
Review Comment:
Good point, addressed in 404aa131d. Since we call `distinct_count.to_inexact()`, and that `Inexact` mixed with anything else gives `Inexact`, there is no semantics change regardless of the precision of `filtered_num_rows`: this is fine, since after filtering the NDV is always an estimate, but the API looks cleaner as you suggest, 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066573862
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -708,7 +708,13 @@ fn max_distinct_count(
stats: &ColumnStatistics,
) -> Precision<usize> {
match &stats.distinct_count {
- &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => dc,
+ &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => {
+ // NDV can never exceed the number of rows
+ match num_rows {
+ Precision::Absent => dc,
+ _ => dc.min(num_rows).to_inexact(),
Review Comment:
You are right, and there is actually a case where `Exact` should be preserved: it's when we don't cap and both are `Exact` (that is `Exact(ndv/dc)` < `Exact(num_rows)`), all the rest is fine as `Inexact`, but this case was mishandled.
This made me realize that test coverage should be improved around `Exact`, so I added more tests covering all combinations (with and without capping) in 9ff12fbd1.
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4217447671
Sorry @gene-bordegaray for the force push, I rebased on main to pick up a conflict with #21077 which had just been merged.
@xudong963 since you reviewed and merged #21077 (set NDV=1 for single-value filters), you might find this PR interesting as it extends the same idea: capping NDV at the row count in joins (`max_distinct_count`), filters (`collect_new_statistics`), and `Statistics::with_fetch` (covering Limit, Sort with fetch, etc.). Would appreciate your review if you have bandwidth!
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4226563242
@gene-bordegaray @xudong963 I had to rebase and force-push due to a conflict with main (we both added tests that conflicted in their insertion point).
Before the force-push I have added the two top-most commits addressing @xudong963's comments, in case you want to 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4246884397
@xudong963, please let me know if you are OK with the latest changes or if anything else is needed before merging
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3021756638
##########
datafusion/common/src/stats.rs:
##########
@@ -551,6 +551,10 @@ impl Statistics {
}
Precision::Absent => Precision::Absent,
};
+ // NDV can never exceed the number of rows
+ if let Some(&rows) = self.num_rows.get_value() {
+ cs.distinct_count = cs.distinct_count.min(&Precision::Inexact(rows));
Review Comment:
Thanks for your comments, @gene-bordegaray!
All comments share the same concern, so I will address them together.
NDV being less than or equal the number of rows, is an invariant that must always hold, you can never have more distinct values than rows, regardless of the precision level.
`Inexact(N)` means "at most N" in DataFusion's semantics for statistics. If `num_rows` is `Inexact(10)`, there are at most 10 rows, hence at most 10 distinct values. Capping NDV at `Inexact(10)` is correct, any value higher than 10 would make the statistics incoherent.
You are correctly wondering how this interacts with `with_fetch`, and as suggested a test to clarify this point is needed, I have added it in f43b07163cd0c628721d0ed739d490ec308f67e4, showing that we don't interfere negatively with 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066573862
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -708,7 +708,13 @@ fn max_distinct_count(
stats: &ColumnStatistics,
) -> Precision<usize> {
match &stats.distinct_count {
- &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => dc,
+ &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => {
+ // NDV can never exceed the number of rows
+ match num_rows {
+ Precision::Absent => dc,
+ _ => dc.min(num_rows).to_inexact(),
Review Comment:
You are right, and there is actually a case where `Exact` should be preserved: it's when we don't cap and both are `Exact` (that is `Exact(ndv/dc)` < `Exact(num_rows)`), all the rest is fine as `Inexact`, but this case was mishandled.
This made me realize that test coverage should be improved around `Exact`, so I added more tests covering all combinations (with and without capping) in 840c6ceaa.
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4254295815
> > @xudong963, please let me know if you are OK with the latest changes or if anything else is needed before merging
>
> Okay with me, thanks as usual
Thank you for your guidance, here and in all other 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 merged PR #21081:
URL: https://github.com/apache/datafusion/pull/21081
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4100328059
cc: @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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066573862
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -708,7 +708,13 @@ fn max_distinct_count(
stats: &ColumnStatistics,
) -> Precision<usize> {
match &stats.distinct_count {
- &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => dc,
+ &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => {
+ // NDV can never exceed the number of rows
+ match num_rows {
+ Precision::Absent => dc,
+ _ => dc.min(num_rows).to_inexact(),
Review Comment:
You are right, and there is actually a case where `Exact` should be preserved: it's when we don't cap and both are `Exact` (that is `Exact(ndv/dc)` < `Exact(num_rows)`), all the rest is fine as `Inexact`, but this case was mishandled.
This made me realize that test coverage should be improved around `Exact`, so I added more tests covering all combinations (with and without capping) in f3ea230a0.
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066567334
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -781,6 +782,7 @@ fn collect_new_statistics(
schema: &SchemaRef,
input_column_stats: &[ColumnStatistics],
analysis_boundaries: Vec<ExprBoundaries>,
+ filtered_num_rows: Option<usize>,
Review Comment:
Good point, addressed in f3ea230a0. Since we call `distinct_count.to_inexact()`, and that `Inexact` mixed with anything else gives `Inexact`, there is no semantics change regardless of the precision of `filtered_num_rows`: this is fine, since after filtering the NDV is always an estimate, but the API looks cleaner as you suggest, 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#issuecomment-4249520518
> @xudong963, please let me know if you are OK with the latest changes or if anything else is needed before merging
Okay with me, thanks as usual
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "gene-bordegaray (via GitHub)" <gi...@apache.org>.
gene-bordegaray commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r2988366494
##########
datafusion/common/src/stats.rs:
##########
@@ -551,6 +551,10 @@ impl Statistics {
}
Precision::Absent => Precision::Absent,
};
+ // NDV can never exceed the number of rows
+ if let Some(&rows) = self.num_rows.get_value() {
+ cs.distinct_count = cs.distinct_count.min(&Precision::Inexact(rows));
Review Comment:
This seems like it would be fine when using this rule for a `LIMIT` since this is a hard cap.
But `with_fetch()` also seems to handle `skip` which results in estimated rows. I don't know if treating the hard cap provided form `fetch` and the estimate from `skip` is the eeet way of doing this since we could easily overestimate the NDV.
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -842,12 +844,19 @@ fn collect_new_statistics(
let is_exact = !lower.is_null() && !upper.is_null() && lower == upper;
let min_value = interval_bound_to_precision(lower, is_exact);
let max_value = interval_bound_to_precision(upper, is_exact);
+ // NDV can never exceed the number of rows after filtering
+ let capped_distinct_count = match filtered_num_rows {
+ Some(rows) => {
+ distinct_count.to_inexact().min(&Precision::Inexact(rows))
+ }
+ None => distinct_count.to_inexact(),
+ };
Review Comment:
Same thing I am wondering here. Is is safe to cap the NDV to an inexact value?
##########
datafusion/common/src/stats.rs:
##########
@@ -2075,6 +2080,46 @@ mod tests {
assert_eq!(result.total_byte_size, Precision::Inexact(800));
}
+ #[test]
Review Comment:
Adding a test here with `skip` being set would be nice to see what expecte behavior is.
Maybe ths should be not changing or downgrading its precision? Lmk your thoughts.
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -707,7 +707,13 @@ fn max_distinct_count(
stats: &ColumnStatistics,
) -> Precision<usize> {
match &stats.distinct_count {
- &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => dc,
+ &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => {
+ // NDV can never exceed the number of rows
+ match num_rows {
+ Precision::Absent => dc,
+ _ => dc.min(num_rows).to_inexact(),
+ }
+ }
Review Comment:
Ditto to other comments
--
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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3066567334
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -781,6 +782,7 @@ fn collect_new_statistics(
schema: &SchemaRef,
input_column_stats: &[ColumnStatistics],
analysis_boundaries: Vec<ExprBoundaries>,
+ filtered_num_rows: Option<usize>,
Review Comment:
Good point, addressed in 9ff12fbd1. Since we call `distinct_count.to_inexact()`, and that `Inexact` mixed with anything else gives `Inexact`, there is no semantics change regardless of the precision of `filtered_num_rows`: this is fine, since after filtering the NDV is always an estimate, but the API looks cleaner as you suggest, 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(stats): cap NDV at row count in statistics estimation [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on code in PR #21081:
URL: https://github.com/apache/datafusion/pull/21081#discussion_r3062589133
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -708,7 +708,13 @@ fn max_distinct_count(
stats: &ColumnStatistics,
) -> Precision<usize> {
match &stats.distinct_count {
- &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => dc,
+ &dc @ (Precision::Exact(_) | Precision::Inexact(_)) => {
+ // NDV can never exceed the number of rows
+ match num_rows {
+ Precision::Absent => dc,
+ _ => dc.min(num_rows).to_inexact(),
Review Comment:
do we want the unconditional `.to_inexact()`?
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -781,6 +782,7 @@ fn collect_new_statistics(
schema: &SchemaRef,
input_column_stats: &[ColumnStatistics],
analysis_boundaries: Vec<ExprBoundaries>,
+ filtered_num_rows: Option<usize>,
Review Comment:
do we need to give it a precision info? -- `Option<Precision<usize>>`
--
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