Skip to content

Commit ebd3acd

Browse files
committed
fix: preserve null-safe join statistics
1 parent 239036d commit ebd3acd

1 file changed

Lines changed: 195 additions & 26 deletions

File tree

  • datafusion/physical-plan/src/joins

‎datafusion/physical-plan/src/joins/utils.rs‎

Lines changed: 195 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -582,8 +582,16 @@ fn estimate_join_cardinality(
582582
};
583583
let mut left_column_statistics = left_stats.column_statistics;
584584
let mut right_column_statistics = right_stats.column_statistics;
585-
let (left_keys, right_keys): (Vec<_>, Vec<_>) =
586-
on_column_indices.iter().flatten().copied().unzip();
585+
let (left_keys, right_keys): (Vec<_>, Vec<_>) = on_column_indices
586+
.iter()
587+
.flatten()
588+
.map(|&(left, right)| {
589+
(
590+
(left, right_column_statistics[right].null_count),
591+
(right, left_column_statistics[left].null_count),
592+
)
593+
})
594+
.unzip();
587595
estimate_join_null_counts(
588596
&mut left_column_statistics,
589597
&left_side,
@@ -816,6 +824,21 @@ fn estimate_join_unmatched_rows(
816824
null_equality: NullEquality,
817825
) -> Option<usize> {
818826
let rows = *input.num_rows.get_value()?;
827+
// The semi estimate uses non-NULL NDV overlap, so it can miss NULL
828+
// matches. With one null-safe key, every input NULL has a match if the
829+
// other side has any NULLs. This bounds matched input rows, not pairs.
830+
let matched_nulls = match (
831+
null_equality,
832+
input.column_statistics.as_slice(),
833+
other.column_statistics.as_slice(),
834+
) {
835+
(NullEquality::NullEqualsNull, [input], [other])
836+
if other.null_count.get_value().is_some_and(|&count| count > 0) =>
837+
{
838+
input.null_count.get_value().copied().unwrap_or(0)
839+
}
840+
_ => 0,
841+
};
819842
let matched = estimate_semi_join_cardinality(
820843
&input.num_rows,
821844
&other.num_rows,
@@ -824,6 +847,7 @@ fn estimate_join_unmatched_rows(
824847
null_equality,
825848
)
826849
.unwrap_or(inner_rows)
850+
.max(matched_nulls)
827851
.min(inner_rows);
828852
// A NULL in any key prevents a match under ordinary equality. The same
829853
// holds for null-safe equality when the other key has no NULLs.
@@ -859,39 +883,45 @@ struct JoinSideRows {
859883
/// that keeps both sides' columns. A join repeats and drops rows, so a null
860884
/// count scales with the rows that carry the column, and padding adds NULLs.
861885
/// NULL keys never match under `NullEqualsNothing`, so only the unmatched rows
862-
/// of a preserved side keep them, each once.
886+
/// of a preserved side keep them, each once. The same holds for null-safe keys
887+
/// whose opposite key has exactly zero NULLs. Each `keys` entry contains the
888+
/// column index and the opposite key's input null count.
863889
fn estimate_join_null_counts(
864890
column_statistics: &mut [ColumnStatistics],
865891
side: &JoinSideRows,
866-
keys: &[usize],
892+
keys: &[(usize, Precision<usize>)],
867893
null_equality: NullEquality,
868894
null_matches: Precision<usize>,
869895
) {
870896
for (idx, column_stats) in column_statistics.iter_mut().enumerate() {
871897
let null_count = column_stats.null_count;
872-
let own_nulls =
873-
if keys.contains(&idx) && null_equality == NullEquality::NullEqualsNothing {
874-
if side.preserved {
875-
// A single output partition can emit all unmatched rows of
876-
// a broadcast side, so the count is exact only overall.
877-
null_count.to_inexact()
878-
} else {
879-
Precision::Exact(0)
880-
}
881-
} else if null_count == Precision::Exact(0) {
882-
// A join cannot add values, so a column without nulls keeps none.
883-
null_count
884-
} else if keys.contains(&idx) {
885-
if side.preserved {
886-
null_matches.max(&null_count).to_inexact()
887-
} else {
888-
null_matches
889-
}
898+
let nulls_cannot_match = keys.iter().any(|&(key, opposite_nulls)| {
899+
key == idx
900+
&& (null_equality == NullEquality::NullEqualsNothing
901+
|| opposite_nulls == Precision::Exact(0))
902+
});
903+
let own_nulls = if nulls_cannot_match {
904+
if side.preserved && null_count != Precision::Exact(0) {
905+
// A single output partition can emit all unmatched rows of
906+
// a broadcast side, so the count is exact only overall.
907+
null_count.to_inexact()
890908
} else {
891-
side.input.map_or(Precision::Absent, |rows| {
892-
scale_subset_count(null_count, rows, side.own)
893-
})
894-
};
909+
Precision::Exact(0)
910+
}
911+
} else if null_count == Precision::Exact(0) {
912+
// A join cannot add values, so a column without nulls keeps none.
913+
null_count
914+
} else if keys.iter().any(|&(key, _)| key == idx) {
915+
if side.preserved {
916+
null_matches.max(&null_count).to_inexact()
917+
} else {
918+
null_matches
919+
}
920+
} else {
921+
side.input.map_or(Precision::Absent, |rows| {
922+
scale_subset_count(null_count, rows, side.own)
923+
})
924+
};
895925
// Padding is an estimate. An unknown contribution from matched rows
896926
// stays unknown rather than being treated as zero.
897927
column_stats.null_count = match side.padded {
@@ -3718,6 +3748,145 @@ mod tests {
37183748
}
37193749
}
37203750

3751+
#[test]
3752+
fn test_join_null_counts_null_safe_multikey() {
3753+
// The key order differs from the column order on both sides. A NULL
3754+
// can only match if the corresponding key on the other side has NULLs.
3755+
let column = |null_count| ColumnStatistics {
3756+
null_count,
3757+
distinct_count: Exact(10),
3758+
..ColumnStatistics::new_unknown()
3759+
};
3760+
let on = vec![
3761+
(
3762+
Arc::new(Column::new("a", 1)) as _,
3763+
Arc::new(Column::new("a", 1)) as _,
3764+
),
3765+
(
3766+
Arc::new(Column::new("b", 2)) as _,
3767+
Arc::new(Column::new("b", 0)) as _,
3768+
),
3769+
];
3770+
for (join_type, opposite_nulls, expected) in [
3771+
(
3772+
JoinType::Inner,
3773+
Exact(0),
3774+
[Exact(0), Exact(0), Exact(0), Exact(0)],
3775+
),
3776+
(
3777+
JoinType::Inner,
3778+
Inexact(0),
3779+
[Absent, Exact(0), Exact(0), Absent],
3780+
),
3781+
(
3782+
JoinType::Inner,
3783+
Absent,
3784+
[Absent, Exact(0), Exact(0), Absent],
3785+
),
3786+
(
3787+
JoinType::Left,
3788+
Exact(0),
3789+
[Inexact(20), Exact(0), Inexact(20), Inexact(20)],
3790+
),
3791+
(
3792+
JoinType::Right,
3793+
Exact(0),
3794+
[Inexact(20), Inexact(20), Inexact(20), Exact(0)],
3795+
),
3796+
(
3797+
JoinType::Full,
3798+
Exact(0),
3799+
[Inexact(40), Inexact(20), Inexact(40), Inexact(20)],
3800+
),
3801+
] {
3802+
let stats = estimate_join_cardinality(
3803+
&join_type,
3804+
create_stats(
3805+
Some(100),
3806+
vec![column(Exact(5)), column(Exact(20)), column(Exact(0))],
3807+
true,
3808+
),
3809+
create_stats(
3810+
Some(100),
3811+
vec![column(Exact(20)), column(opposite_nulls)],
3812+
true,
3813+
),
3814+
&on,
3815+
NullEquality::NullEqualsNull,
3816+
)
3817+
.unwrap();
3818+
let null_counts: Vec<_> = stats.column_statistics[1..]
3819+
.iter()
3820+
.map(|column| column.null_count)
3821+
.collect();
3822+
assert_eq!(null_counts, expected, "{join_type} {opposite_nulls:?}");
3823+
if join_type == JoinType::Inner {
3824+
// A non-key column is still scaled, not made null-free.
3825+
assert_eq!(stats.column_statistics[0].null_count, Inexact(50));
3826+
}
3827+
}
3828+
}
3829+
3830+
#[test]
3831+
fn test_join_null_counts_null_safe_unmatched_rows() {
3832+
let on = vec![(
3833+
Arc::new(Column::new("k", 0)) as _,
3834+
Arc::new(Column::new("k", 0)) as _,
3835+
)];
3836+
// Ninety NULL keys match every row on the other side. Only the ten
3837+
// distinct non-NULL keys are unmatched, even when matches duplicate.
3838+
for other_rows in [1, 3] {
3839+
for join_type in [JoinType::Left, JoinType::Right, JoinType::Full] {
3840+
let input = create_stats(
3841+
Some(100),
3842+
vec![create_column_stats(
3843+
Exact(1),
3844+
Exact(10),
3845+
Exact(10),
3846+
Exact(90),
3847+
)],
3848+
true,
3849+
);
3850+
let other = create_stats(
3851+
Some(other_rows),
3852+
vec![create_column_stats(
3853+
Absent,
3854+
Absent,
3855+
Exact(0),
3856+
Exact(other_rows),
3857+
)],
3858+
true,
3859+
);
3860+
let (left, right) = if join_type == JoinType::Right {
3861+
(other, input)
3862+
} else {
3863+
(input, other)
3864+
};
3865+
let stats = estimate_join_cardinality(
3866+
&join_type,
3867+
left,
3868+
right,
3869+
&on,
3870+
NullEquality::NullEqualsNull,
3871+
)
3872+
.unwrap();
3873+
let null_pairs = 90 * other_rows;
3874+
assert_eq!(stats.num_rows, null_pairs + 10, "{join_type}");
3875+
let expected = if join_type == JoinType::Right {
3876+
[Inexact(null_pairs + 10), Inexact(null_pairs)]
3877+
} else {
3878+
[Inexact(null_pairs), Inexact(null_pairs + 10)]
3879+
};
3880+
let null_counts: Vec<_> = stats
3881+
.column_statistics
3882+
.iter()
3883+
.map(|column| column.null_count)
3884+
.collect();
3885+
assert_eq!(null_counts, expected, "{join_type}");
3886+
}
3887+
}
3888+
}
3889+
37213890
#[test]
37223891
fn test_join_null_counts_unknown_padded_column() {
37233892
// All rows match. No padding does not prove that the right-hand

0 commit comments

Comments
 (0)