@@ -19,10 +19,11 @@ use std::sync::Arc;
1919
2020use super :: EquivalenceProperties ;
2121use crate :: expressions:: Column ;
22- use crate :: { PhysicalExprRef , equivalence:: OrderingEquivalenceClass } ;
22+ use crate :: { ConstExpr , PhysicalExprRef , equivalence:: OrderingEquivalenceClass } ;
2323
2424use arrow:: datatypes:: SchemaRef ;
25- use datafusion_common:: { Constraint , JoinSide , JoinType , Result } ;
25+ use datafusion_common:: { Constraint , JoinSide , JoinType , NullEquality , Result } ;
26+ use datafusion_physical_expr_common:: physical_expr:: is_volatile;
2627
2728/// Calculate ordering equivalence properties for the given join operation.
2829#[ expect( clippy:: too_many_arguments) ]
@@ -35,6 +36,7 @@ pub fn join_equivalence_properties(
3536 probe_side : Option < JoinSide > ,
3637 on : & [ ( PhysicalExprRef , PhysicalExprRef ) ] ,
3738 has_filter : bool ,
39+ null_equality : NullEquality ,
3840) -> Result < EquivalenceProperties > {
3941 let left_size = left. schema . fields . len ( ) ;
4042 let mut result = EquivalenceProperties :: new ( join_schema) ;
@@ -59,6 +61,7 @@ pub fn join_equivalence_properties(
5961 on,
6062 JoinSide :: Left ,
6163 * join_type != JoinType :: Inner ,
64+ null_equality,
6265 ) ?) ;
6366 }
6467 result. add_orderings ( left. oeq_class ) ;
@@ -74,6 +77,7 @@ pub fn join_equivalence_properties(
7477 on,
7578 JoinSide :: Right ,
7679 * join_type != JoinType :: Inner ,
80+ null_equality,
7781 ) ?) ;
7882 }
7983 let mut right_oeq_class = right. oeq_class ;
@@ -102,6 +106,7 @@ fn unique_build_join_orderings(
102106 on : & [ ( PhysicalExprRef , PhysicalExprRef ) ] ,
103107 probe_side : JoinSide ,
104108 preserves_unmatched_probe : bool ,
109+ null_equality : NullEquality ,
105110) -> Result < OrderingEquivalenceClass > {
106111 if build. constraints ( ) . is_empty ( ) || build. oeq_class ( ) . is_empty ( ) {
107112 return Ok ( OrderingEquivalenceClass :: default ( ) ) ;
@@ -122,20 +127,31 @@ fn unique_build_join_orderings(
122127 . collect :: < Vec < _ > > ( ) ;
123128 let mut valid_orderings = Vec :: new ( ) ;
124129 for ordering in probe. oeq_class ( ) . iter ( ) {
125- let probe_exprs = ordering
126- . iter ( )
127- . map ( |sort| probe. eq_group ( ) . normalize_expr ( Arc :: clone ( & sort. expr ) ) )
128- . collect :: < Vec < _ > > ( ) ;
130+ // Within a group of equal ordering values, these expressions are
131+ // constant. Keep this assumption local to the ordering proof.
132+ let mut group = probe. eq_group ( ) . clone ( ) ;
133+ for sort in ordering {
134+ let expr = probe. eq_group ( ) . normalize_expr ( Arc :: clone ( & sort. expr ) ) ;
135+ group. add_constant ( ConstExpr :: from ( expr) ) ;
136+ }
137+ let probe_key_is_fixed = |key : & PhysicalExprRef | {
138+ !is_volatile ( key) && group. is_expr_constant ( key) . is_some ( )
139+ } ;
129140
130141 // Outer joins must have the same match status throughout the group.
131142 if preserves_unmatched_probe
132143 && !on
133144 . iter ( )
134- . all ( |( probe_key, _) | probe_exprs . contains ( probe_key) )
145+ . all ( |( probe_key, _) | probe_key_is_fixed ( probe_key) )
135146 {
136147 continue ;
137148 }
138- if !ordering_covers_unique_build_key ( build, & on, & probe_exprs) {
149+ if !ordering_covers_unique_build_key (
150+ build,
151+ & on,
152+ probe_key_is_fixed,
153+ null_equality,
154+ ) {
139155 continue ;
140156 }
141157 valid_orderings. push ( ordering. clone ( ) ) ;
@@ -154,11 +170,12 @@ fn unique_build_join_orderings(
154170}
155171
156172/// Check whether the probe ordering determines a unique build key.
157- /// Join keys and probe ordering expressions must already be normalized.
173+ /// Join keys must already be normalized against their input equivalence groups .
158174fn ordering_covers_unique_build_key (
159175 build : & EquivalenceProperties ,
160176 on : & [ ( PhysicalExprRef , PhysicalExprRef ) ] ,
161- probe_exprs : & [ PhysicalExprRef ] ,
177+ probe_key_is_fixed : impl Fn ( & PhysicalExprRef ) -> bool ,
178+ null_equality : NullEquality ,
162179) -> bool {
163180 build. constraints ( ) . iter ( ) . any ( |constraint| {
164181 let ( Constraint :: PrimaryKey ( indices) | Constraint :: Unique ( indices) ) = constraint;
@@ -167,15 +184,18 @@ fn ordering_covers_unique_build_key(
167184 let Some ( field) = build. schema . fields ( ) . get ( index) else {
168185 return false ;
169186 } ;
170- // UNIQUE can contain repeated NULLs. Without null-equality
171- // information, only non-null UNIQUE columns prove uniqueness.
172- if matches ! ( constraint, Constraint :: Unique ( _) ) && field. is_nullable ( ) {
187+ // UNIQUE permits repeated NULLs, which only invalidate the
188+ // uniqueness proof when NULL join keys can match each other.
189+ if matches ! ( constraint, Constraint :: Unique ( _) )
190+ && field. is_nullable ( )
191+ && null_equality == NullEquality :: NullEqualsNull
192+ {
173193 return false ;
174194 }
175195 let column: PhysicalExprRef = Arc :: new ( Column :: new ( field. name ( ) , index) ) ;
176196 let column = build. eq_group ( ) . normalize_expr ( column) ;
177197 on. iter ( ) . any ( |( probe_key, build_key) | {
178- build_key. eq ( & column) && probe_exprs . contains ( probe_key)
198+ build_key. eq ( & column) && probe_key_is_fixed ( probe_key)
179199 } )
180200 } )
181201 } )
@@ -209,9 +229,10 @@ mod tests {
209229 use super :: * ;
210230 use crate :: equivalence:: convert_to_orderings;
211231 use crate :: equivalence:: tests:: create_test_schema;
212- use crate :: expressions:: { Column , col} ;
232+ use crate :: expressions:: { BinaryExpr , Column , col, lit } ;
213233 use crate :: { LexOrdering , PhysicalSortExpr } ;
214234 use datafusion_common:: { Constraint , Constraints } ;
235+ use datafusion_expr:: Operator ;
215236
216237 use arrow:: compute:: SortOptions ;
217238 use arrow:: datatypes:: { DataType , Field , Fields , Schema } ;
@@ -273,6 +294,7 @@ mod tests {
273294 Some ( JoinSide :: Left ) ,
274295 & [ ] ,
275296 false ,
297+ NullEquality :: NullEqualsNothing ,
276298 ) ?;
277299 let err_msg =
278300 format ! ( "expected: {:?}, actual:{:?}" , expected, join_eq. oeq_class) ;
@@ -326,6 +348,7 @@ mod tests {
326348 Some ( JoinSide :: Left ) ,
327349 on,
328350 false ,
351+ NullEquality :: NullEqualsNothing ,
329352 )
330353 } ;
331354 let required = |prefix| {
@@ -348,7 +371,34 @@ mod tests {
348371 let inner = join_properties ( JoinType :: Inner , & on) ?;
349372 let outer = join_properties ( JoinType :: Left , & on) ?;
350373 assert ! ( inner. ordering_satisfy( required( Arc :: clone( & a) ) ) ?) ;
351- assert ! ( !outer. ordering_satisfy( required( a) ) ?) ;
374+ assert ! ( !outer. ordering_satisfy( required( Arc :: clone( & a) ) ) ?) ;
375+
376+ let plus_one = |expr| -> PhysicalExprRef {
377+ Arc :: new ( BinaryExpr :: new ( expr, Operator :: Plus , lit ( 1_i32 ) ) )
378+ } ;
379+ let a_plus_one = plus_one ( Arc :: clone ( & a) ) ;
380+ let b_plus_one = plus_one ( Arc :: clone ( & b) ) ;
381+ // Record the ordering before adding equivalence, so the proof must
382+ // normalize both the ordering expression and the join key consistently.
383+ let mut probe = EquivalenceProperties :: new_with_orderings (
384+ Arc :: clone ( & schema) ,
385+ [ ordering ( Arc :: clone ( & b_plus_one) ) ] ,
386+ ) ;
387+ probe. add_equal_conditions ( Arc :: clone ( & a) , b) ?;
388+ for join_type in [ JoinType :: Inner , JoinType :: Left ] {
389+ let output = join_equivalence_properties (
390+ probe. clone ( ) ,
391+ build. clone ( ) ,
392+ & join_type,
393+ Arc :: clone ( & output_schema) ,
394+ & [ true , false ] ,
395+ Some ( JoinSide :: Left ) ,
396+ & [ ( Arc :: clone ( & a_plus_one) , Arc :: clone ( & a) ) ] ,
397+ false ,
398+ NullEquality :: NullEqualsNothing ,
399+ ) ?;
400+ assert ! ( output. ordering_satisfy( required( Arc :: clone( & b_plus_one) ) ) ?) ;
401+ }
352402 Ok ( ( ) )
353403 }
354404
0 commit comments