You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "neilconway (via GitHub)" <gi...@apache.org> on 2026/06/04 15:04:25 UTC
[PR] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
neilconway opened a new pull request, #22762:
URL: https://github.com/apache/datafusion/pull/22762
## Which issue does this PR close?
- Closes #22743
## Rationale for this change
This PR makes several related improvements/fixes to the stats code for semi- and anti-joins:
1. Scale per-column stats using the estimated output row count, rather than just reusing the preserved side of the join.
2. Compute `total_byte_size` for semi/anti-join results, based on summing per-column `byte_size`, instead of always emitting `Absent`. We still emit absent for other join types and if any of the per-column `byte_size` values are `Absent`
3. Pass in the join's `NullEquality` semantics, and use those for stats: under `NullEqualsNothing`, null join keys will never match (so we can return `Exact(0)`), whereas under `NullEqualsNull` we consider nulls just like any other value.
## What changes are included in this PR?
* Stats improvements described above
* Some refactoring and cleanup
* New unit tests
* Update test expectations where needed
## Are these changes tested?
Yes; new tests added.
## Are there any user-facing changes?
Some queries might get different plans.
--
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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on code in PR #22762:
URL: https://github.com/apache/datafusion/pull/22762#discussion_r3357913305
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -806,11 +978,21 @@ fn estimate_semi_join_cardinality(
if let (Some(&o), Some(&i)) = (outer_ndv.get_value(), inner_ndv.get_value())
&& o > 0
{
- let null_frac = outer_stat
- .null_count
- .get_value()
- .map(|&nc| nc as f64 / outer_rows as f64)
- .unwrap_or(0.0);
+ let null_frac = if null_equality == NullEquality::NullEqualsNothing {
Review Comment:
Nice catch
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -610,12 +654,132 @@ fn estimate_join_cardinality(
column_statistics.push(ColumnStatistics::new_unknown());
Some(PartialJoinStatistics {
num_rows,
+ total_byte_size: Precision::Absent,
column_statistics,
})
}
}
}
+fn equijoin_column_indices(
+ left: &PhysicalExprRef,
+ right: &PhysicalExprRef,
+) -> Option<(usize, usize)> {
+ Some((
+ left.downcast_ref::<Column>()?.index(),
+ right.downcast_ref::<Column>()?.index(),
+ ))
+}
+
+/// Adjusts the preserved input's column statistics to describe the subset of
+/// rows a semi or anti join emits. Most values become estimates (marked
+/// inexact) bounded by the smaller output row count:
+///
+/// - `null_count` and `byte_size` are scaled by the output/input row ratio.
+/// - `distinct_count` is capped at the number of non-null output rows.
+/// - `sum_value` is dropped, since the input sum does not apply to the subset.
+///
+/// Join-key columns are the exception for `null_count`: under regular SQL
+/// equality, null keys never match, so a semi join keeps none of those rows and
+/// an anti join keeps all of them. Under null-equal joins, null keys can match
+/// and are treated like the rest of the subset.
+fn normalize_semi_anti_join_column_statistics(
+ column_statistics: Vec<ColumnStatistics>,
+ input_num_rows: &Precision<usize>,
+ output_num_rows: usize,
+ join_key_indices: &[usize],
+ is_anti: bool,
+ null_equality: NullEquality,
+) -> Vec<ColumnStatistics> {
+ let input_num_rows = input_num_rows.get_value().copied().unwrap_or(0);
+
+ column_statistics
+ .into_iter()
+ .enumerate()
+ .map(|(idx, stats)| {
+ let mut stats = stats.to_inexact();
+ stats.null_count = if join_key_indices.contains(&idx) {
Review Comment:
Nit: Not a big problem as there won't be many items, but maybe we can use a `HashSet` here as it seems we are just using containment test.
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -446,24 +449,34 @@ struct PartialJoinStatistics {
/// - Does not account for selectivity of arbitrary join filter expressions
/// (e.g., `(t1.v1 + t2.v1) % 2 = 0`). Such filters, common in NestedLoopJoinExec,
/// are not factored into the cardinality estimation.
-/// - Column statistics for the output are simply combined from inputs without
-/// adjusting for join selectivity (acknowledged in the code as needing
-/// "filter selectivity analysis").
+/// - Column statistics for inner/outer joins are simply combined from inputs
+/// without adjusting for join selectivity (acknowledged in the code as
+/// needing "filter selectivity analysis").
Review Comment:
Q: is there an issue filed already? It's easier to discover pending issues in GitHub rather than code 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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #22762:
URL: https://github.com/apache/datafusion/pull/22762#issuecomment-4637603283
🚀
--
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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on PR #22762:
URL: https://github.com/apache/datafusion/pull/22762#issuecomment-4623396471
FYI @asolimando
--
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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22762:
URL: https://github.com/apache/datafusion/pull/22762#discussion_r3358534846
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -610,12 +654,132 @@ fn estimate_join_cardinality(
column_statistics.push(ColumnStatistics::new_unknown());
Some(PartialJoinStatistics {
num_rows,
+ total_byte_size: Precision::Absent,
column_statistics,
})
}
}
}
+fn equijoin_column_indices(
+ left: &PhysicalExprRef,
+ right: &PhysicalExprRef,
+) -> Option<(usize, usize)> {
+ Some((
+ left.downcast_ref::<Column>()?.index(),
+ right.downcast_ref::<Column>()?.index(),
+ ))
+}
+
+/// Adjusts the preserved input's column statistics to describe the subset of
+/// rows a semi or anti join emits. Most values become estimates (marked
+/// inexact) bounded by the smaller output row count:
+///
+/// - `null_count` and `byte_size` are scaled by the output/input row ratio.
+/// - `distinct_count` is capped at the number of non-null output rows.
+/// - `sum_value` is dropped, since the input sum does not apply to the subset.
+///
+/// Join-key columns are the exception for `null_count`: under regular SQL
+/// equality, null keys never match, so a semi join keeps none of those rows and
+/// an anti join keeps all of them. Under null-equal joins, null keys can match
+/// and are treated like the rest of the subset.
+fn normalize_semi_anti_join_column_statistics(
+ column_statistics: Vec<ColumnStatistics>,
+ input_num_rows: &Precision<usize>,
+ output_num_rows: usize,
+ join_key_indices: &[usize],
+ is_anti: bool,
+ null_equality: NullEquality,
+) -> Vec<ColumnStatistics> {
+ let input_num_rows = input_num_rows.get_value().copied().unwrap_or(0);
+
+ column_statistics
+ .into_iter()
+ .enumerate()
+ .map(|(idx, stats)| {
+ let mut stats = stats.to_inexact();
+ stats.null_count = if join_key_indices.contains(&idx) {
Review Comment:
`HashSet` would make the set-containment usage more clear, but since it will be small in practice, I'm inclined to leave this as-is.
--
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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "neilconway (via GitHub)" <gi...@apache.org>.
neilconway commented on code in PR #22762:
URL: https://github.com/apache/datafusion/pull/22762#discussion_r3357966718
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -446,24 +449,34 @@ struct PartialJoinStatistics {
/// - Does not account for selectivity of arbitrary join filter expressions
/// (e.g., `(t1.v1 + t2.v1) % 2 = 0`). Such filters, common in NestedLoopJoinExec,
/// are not factored into the cardinality estimation.
-/// - Column statistics for the output are simply combined from inputs without
-/// adjusting for join selectivity (acknowledged in the code as needing
-/// "filter selectivity analysis").
+/// - Column statistics for inner/outer joins are simply combined from inputs
+/// without adjusting for join selectivity (acknowledged in the code as
+/// needing "filter selectivity analysis").
Review Comment:
https://github.com/apache/datafusion/issues/22761 covers this, I think.
--
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] fix: Scale semi/anti-join column stats by estimated row count [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #22762:
URL: https://github.com/apache/datafusion/pull/22762
--
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