kumarUjjawal commented on code in PR #25648:
URL: https://github.com/apache/datafusion/pull/25648#discussion_r4130061993
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -514,45 +517,99 @@ fn estimate_join_cardinality(
match join_type {
JoinType::Inner | JoinType::Left | JoinType::Right | JoinType::Full =>
{
- let ij_cardinality = estimate_inner_join_cardinality(
- Statistics {
- num_rows: left_stats.num_rows,
- total_byte_size: Precision::Absent,
- column_statistics: left_key_stats,
- },
- Statistics {
- num_rows: right_stats.num_rows,
- total_byte_size: Precision::Absent,
- column_statistics: right_key_stats,
- },
- )?;
-
- // The cardinality for inner join can also be used to estimate
- // the cardinality of left/right/full outer joins as long as it
- // it is greater than the minimum cardinality constraints of these
- // joins (so that we don't underestimate the cardinality).
- let cardinality = match join_type {
- JoinType::Inner => ij_cardinality,
- JoinType::Left => ij_cardinality.max(&left_stats.num_rows),
- JoinType::Right => ij_cardinality.max(&right_stats.num_rows),
- JoinType::Full => ij_cardinality
- .max(&left_stats.num_rows)
- .add(&ij_cardinality.max(&right_stats.num_rows))
- .sub(&ij_cardinality),
- _ => unreachable!(),
+ let left_keys_stats = Statistics {
+ num_rows: left_stats.num_rows,
+ total_byte_size: Precision::Absent,
+ column_statistics: left_key_stats,
+ };
+ let right_keys_stats = Statistics {
+ num_rows: right_stats.num_rows,
+ total_byte_size: Precision::Absent,
+ column_statistics: right_key_stats,
+ };
+ // For a single null-safe key, every left NULL matches every right
+ // NULL. With more keys their correlation is unknown.
+ let null_matches =
+ if null_equality == NullEquality::NullEqualsNull && on.len()
== 1 {
+ left_keys_stats.column_statistics[0]
+ .null_count
+
.multiply(&right_keys_stats.column_statistics[0].null_count)
+ .to_inexact()
+ } else {
+ Precision::Absent
+ };
+ let inner_rows =
+ *estimate_inner_join_cardinality(&left_keys_stats,
&right_keys_stats)?
+ .get_value()?;
+ let inner_rows =
+ inner_rows.max(null_matches.get_value().copied().unwrap_or(0));
+ let left_rows = left_stats.num_rows.get_value().copied();
+ let right_rows = right_stats.num_rows.get_value().copied();
+ let left_preserved = matches!(join_type, JoinType::Left |
JoinType::Full);
+ let right_preserved = matches!(join_type, JoinType::Right |
JoinType::Full);
+ let unmatched_left = if left_preserved {
+ estimate_join_unmatched_rows(
+ &left_keys_stats,
+ &right_keys_stats,
+ inner_rows,
+ null_equality,
+ )?
+ } else {
+ 0
+ };
+ let unmatched_right = if right_preserved {
+ estimate_join_unmatched_rows(
+ &right_keys_stats,
+ &left_keys_stats,
+ inner_rows,
+ null_equality,
+ )?
+ } else {
+ 0
};
+ let left_side = JoinSideRows {
+ input: left_rows,
+ own: inner_rows.saturating_add(unmatched_left),
+ padded: right_preserved.then_some(unmatched_right),
+ preserved: left_preserved,
+ };
+ let right_side = JoinSideRows {
+ input: right_rows,
+ own: inner_rows.saturating_add(unmatched_right),
+ padded: left_preserved.then_some(unmatched_left),
+ preserved: right_preserved,
+ };
+ let mut left_column_statistics = left_stats.column_statistics;
+ let mut right_column_statistics = right_stats.column_statistics;
+ let (left_keys, right_keys): (Vec<_>, Vec<_>) =
+ on_column_indices.iter().flatten().copied().unzip();
+ estimate_join_null_counts(
+ &mut left_column_statistics,
+ &left_side,
+ &left_keys,
+ null_equality,
+ null_matches,
+ );
+ estimate_join_null_counts(
+ &mut right_column_statistics,
+ &right_side,
+ &right_keys,
+ null_equality,
+ null_matches,
+ );
Some(PartialJoinStatistics {
- num_rows: *cardinality.get_value()?,
+ num_rows: inner_rows
Review Comment:
Split into three independent PRs against main:
- #25861: join cardinality and null counts
- #25862: filter fetch accounting
- #25863: singleton precision
The null-filter change is now a separate final commit:
78bdfbc18ac5ccf2f7ceca232152462d526df70a. I am keeping #25648 as a draft until
the supporting PRs merge, then I will rebase away their commits. Its Files
Changed tab still includes them for now because GitHub does not support native
stacks across forks.
Each independent branch passed the physical-plan tests and clippy. The
combined branch also passed both affected SQL logic test files, and the
singleton PR passed its Parquet file independently.
--
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]
