gabotechs commented on code in PR #25861:
URL: https://github.com/apache/datafusion/pull/25861#discussion_r4164719785
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -750,6 +807,100 @@ fn normalize_semi_anti_join_key_null_count(
}
}
+/// Estimates input rows with no match. Inner-join rows count pairs, so they
+/// only bound the number of matching input rows when the keys repeat.
+fn estimate_join_unmatched_rows(
+ input: &Statistics,
+ other: &Statistics,
+ inner_rows: usize,
+ null_equality: NullEquality,
+) -> Option<usize> {
+ let rows = *input.num_rows.get_value()?;
+ let matched = estimate_semi_join_cardinality(
+ &input.num_rows,
+ &other.num_rows,
+ &input.column_statistics,
+ &other.column_statistics,
+ null_equality,
+ )
+ .unwrap_or(inner_rows)
Review Comment:
The semi-join estimator uses non-NULL NDV overlap for `NullEqualsNull` and
can report zero matched rows even when NULL keys match. For a left join with
100 left rows (90 NULL keys and 10 distinct non-NULL keys) and one right NULL
row, this calculation gives `inner_rows = 90`, `unmatched_left = 100`, hence
190 output rows; the actual output has 100 rows because the 90 NULL-key rows
match. I checked the case with a focused unit test: it passes at the PR base
and fails at this head (190 vs 100). Could we include the null-safe NULL
matches when estimating `matched`, or avoid treating the semi estimate as
complete in this case, and add a regression test?
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -750,6 +807,100 @@ fn normalize_semi_anti_join_key_null_count(
}
}
+/// Estimates input rows with no match. Inner-join rows count pairs, so they
+/// only bound the number of matching input rows when the keys repeat.
+fn estimate_join_unmatched_rows(
+ input: &Statistics,
+ other: &Statistics,
+ inner_rows: usize,
+ null_equality: NullEquality,
+) -> Option<usize> {
+ let rows = *input.num_rows.get_value()?;
+ let matched = estimate_semi_join_cardinality(
+ &input.num_rows,
+ &other.num_rows,
+ &input.column_statistics,
+ &other.column_statistics,
+ null_equality,
+ )
+ .unwrap_or(inner_rows)
+ .min(inner_rows);
+ // A NULL in any key prevents a match under ordinary equality. The same
+ // holds for null-safe equality when the other key has no NULLs.
+ let unmatched_nulls = input
+ .column_statistics
+ .iter()
+ .zip(&other.column_statistics)
+ .filter(|(_, other)| {
+ null_equality == NullEquality::NullEqualsNothing
+ || other.null_count == Precision::Exact(0)
+ })
+ .filter_map(|(input, _)| input.null_count.get_value().copied())
+ .max()
+ .unwrap_or(0)
+ .min(rows);
+ Some(rows.saturating_sub(matched).max(unmatched_nulls))
+}
+
+/// Row counts for one side of a join that keeps both sides' columns.
+struct JoinSideRows {
+ /// Rows of this side's input, when known.
+ input: Option<usize>,
+ /// Output rows that carry this side's values.
+ own: usize,
+ /// Estimated output rows where this side's columns are NULL padding, or
+ /// `None` when the join never pads this side.
+ padded: Option<usize>,
+ /// Whether the join keeps this side's unmatched rows.
+ preserved: bool,
+}
+
+/// Estimates the null counts of one side's columns in the output of a join
+/// that keeps both sides' columns. A join repeats and drops rows, so a null
+/// count scales with the rows that carry the column, and padding adds NULLs.
+/// NULL keys never match under `NullEqualsNothing`, so only the unmatched rows
+/// of a preserved side keep them, each once.
+fn estimate_join_null_counts(
+ column_statistics: &mut [ColumnStatistics],
+ side: &JoinSideRows,
+ keys: &[usize],
+ null_equality: NullEquality,
+ null_matches: Precision<usize>,
+) {
+ for (idx, column_stats) in column_statistics.iter_mut().enumerate() {
+ let null_count = column_stats.null_count;
+ let own_nulls =
+ if keys.contains(&idx) && null_equality ==
NullEquality::NullEqualsNothing {
+ if side.preserved {
+ // A single output partition can emit all unmatched rows of
+ // a broadcast side, so the count is exact only overall.
+ null_count.to_inexact()
+ } else {
+ Precision::Exact(0)
+ }
+ } else if null_count == Precision::Exact(0) {
+ // A join cannot add values, so a column without nulls keeps
none.
+ null_count
+ } else if keys.contains(&idx) {
+ if side.preserved {
+ null_matches.max(&null_count).to_inexact()
+ } else {
Review Comment:
For a multi-key `NullEqualsNull` inner join, `null_matches` is `Absent`, so
this branch makes a nullable key's output null count `Absent` even when the
corresponding key on the other input has `Exact(0)` nulls. For example, with
`(a, b)` join keys and right `a` null-free, no matched row can have NULL in
left `a`; its output null count is provably `Exact(0)`. Could we derive that
per-key zero from the opposite key's null count and add a regression test? This
keeps a usable statistic for a downstream `IS NULL` filter.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
