@@ -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.
863889fn 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