gabotechs commented on code in PR #25648:
URL: https://github.com/apache/datafusion/pull/25648#discussion_r4122769097
##########
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:
Thanks for working on this! Could we split this into smaller PRs? The
original issue is about using null counts for bare IS NULL / IS NOT NULL
filters, but this also changes outer-join cardinality estimation, fetch-limit
accounting, and singleton-statistics precision.
Some join null-count fixes may be prerequisites; those could go first,
followed by the focused null-filter change. The independent fetch and precision
changes could be separate PRs. That would make the assumptions and tests much
easier to review.
--
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]
