@@ -284,6 +284,54 @@ impl RangePartitioning {
284284 self . split_points . len ( ) + 1
285285 }
286286
287+ /// Returns true when `self` and `other` describe the same range partition
288+ /// map.
289+ ///
290+ /// Single-partition range partitionings are always compatible. Otherwise,
291+ /// the two partitionings must have identical split points and equivalent
292+ /// ordering expressions with the same sort options.
293+ pub fn compatible_with (
294+ & self ,
295+ other : & Self ,
296+ eq_properties : & EquivalenceProperties ,
297+ ) -> bool {
298+ if self . partition_count ( ) == 1 && other. partition_count ( ) == 1 {
299+ return true ;
300+ }
301+
302+ if self . split_points != other. split_points
303+ || self . ordering . len ( ) != other. ordering . len ( )
304+ {
305+ return false ;
306+ }
307+
308+ if !self
309+ . ordering
310+ . iter ( )
311+ . zip ( other. ordering . iter ( ) )
312+ . all ( |( left, right) | left. options == right. options )
313+ {
314+ return false ;
315+ }
316+
317+ let left_exprs = self
318+ . ordering
319+ . iter ( )
320+ . map ( |sort_expr| Arc :: clone ( & sort_expr. expr ) )
321+ . collect :: < Vec < _ > > ( ) ;
322+ let right_exprs = other
323+ . ordering
324+ . iter ( )
325+ . map ( |sort_expr| Arc :: clone ( & sort_expr. expr ) )
326+ . collect :: < Vec < _ > > ( ) ;
327+
328+ equivalent_exprs ( & left_exprs, & right_exprs, eq_properties)
329+ }
330+
331+ /// Calculates the range partitioning after applying the given projection.
332+ ///
333+ /// Returns `None` if any range key cannot be projected or if projection
334+ /// collapses distinct range keys into duplicate output expressions.
287335 fn project (
288336 & self ,
289337 mapping : & ProjectionMapping ,
@@ -416,6 +464,37 @@ fn compare_scalar_values_for_sort(
416464 }
417465}
418466
467+ fn equivalent_exprs (
468+ left : & [ Arc < dyn PhysicalExpr > ] ,
469+ right : & [ Arc < dyn PhysicalExpr > ] ,
470+ eq_properties : & EquivalenceProperties ,
471+ ) -> bool {
472+ if physical_exprs_equal ( left, right) {
473+ return true ;
474+ }
475+
476+ let eq_groups = eq_properties. eq_group ( ) ;
477+ if eq_groups. is_empty ( ) {
478+ return false ;
479+ }
480+
481+ let normalized_left = normalize_exprs ( left, eq_properties) ;
482+ let normalized_right = normalize_exprs ( right, eq_properties) ;
483+
484+ physical_exprs_equal ( & normalized_left, & normalized_right)
485+ }
486+
487+ fn normalize_exprs (
488+ exprs : & [ Arc < dyn PhysicalExpr > ] ,
489+ eq_properties : & EquivalenceProperties ,
490+ ) -> Vec < Arc < dyn PhysicalExpr > > {
491+ let eq_groups = eq_properties. eq_group ( ) ;
492+ exprs
493+ . iter ( )
494+ . map ( |expr| eq_groups. normalize_expr ( Arc :: clone ( expr) ) )
495+ . collect ( )
496+ }
497+
419498/// Represents how a [`Partitioning`] satisfies a [`Distribution`] requirement.
420499#[ derive( Debug , Clone , Copy , PartialEq , Eq ) ]
421500pub enum PartitioningSatisfaction {
@@ -447,6 +526,42 @@ impl Partitioning {
447526 }
448527 }
449528
529+ /// Returns true when `self` and `other` describe compatible partition maps.
530+ ///
531+ /// Compatible partition maps can be used for partition-local behavior: if
532+ /// this returns true, partition `i` from both partitionings can be treated
533+ /// as covering the same partition domain. This is stricter than
534+ /// [`Self::satisfaction`], which only answers whether this partitioning can
535+ /// satisfy a required distribution.
536+ pub fn compatible_with (
537+ & self ,
538+ other : & Self ,
539+ eq_properties : & EquivalenceProperties ,
540+ ) -> bool {
541+ if self . partition_count ( ) == 1 && other. partition_count ( ) == 1 {
542+ return true ;
543+ }
544+
545+ match ( self , other) {
546+ (
547+ Partitioning :: Hash ( left_exprs, left_count) ,
548+ Partitioning :: Hash ( right_exprs, right_count) ,
549+ ) => {
550+ if left_count != right_count {
551+ return false ;
552+ }
553+ if left_exprs. is_empty ( ) || right_exprs. is_empty ( ) {
554+ return false ;
555+ }
556+ equivalent_exprs ( left_exprs, right_exprs, eq_properties)
557+ }
558+ ( Partitioning :: Range ( left) , Partitioning :: Range ( right) ) => {
559+ left. compatible_with ( right, eq_properties)
560+ }
561+ _ => false ,
562+ }
563+ }
564+
450565 /// Returns true if `subset_exprs` is a subset of `exprs`.
451566 /// For example: Hash(a, b) is subset of Hash(a) since a partition with all occurrences of
452567 /// a distinct (a) must also contain all occurrences of a distinct (a, b) with the same (a).
@@ -503,36 +618,23 @@ impl Partitioning {
503618 return PartitioningSatisfaction :: NotSatisfied ;
504619 }
505620
506- // Fast path: exact match
507- if physical_exprs_equal ( required_exprs, partition_exprs) {
621+ if equivalent_exprs ( required_exprs, partition_exprs, eq_properties) {
508622 return PartitioningSatisfaction :: Exact ;
509623 }
510624
511- // Normalization path using equivalence groups
512625 let eq_groups = eq_properties. eq_group ( ) ;
513626 if !eq_groups. is_empty ( ) {
514- let normalized_required_exprs = required_exprs
515- . iter ( )
516- . map ( |e| eq_groups. normalize_expr ( Arc :: clone ( e) ) )
517- . collect :: < Vec < _ > > ( ) ;
518- let normalized_partition_exprs = partition_exprs
519- . iter ( )
520- . map ( |e| eq_groups. normalize_expr ( Arc :: clone ( e) ) )
521- . collect :: < Vec < _ > > ( ) ;
522- if physical_exprs_equal (
523- & normalized_required_exprs,
524- & normalized_partition_exprs,
525- ) {
526- return PartitioningSatisfaction :: Exact ;
527- }
528-
529- if allow_subset
530- && Self :: is_subset_partitioning (
627+ if allow_subset {
628+ let normalized_partition_exprs =
629+ normalize_exprs ( partition_exprs, eq_properties) ;
630+ let normalized_required_exprs =
631+ normalize_exprs ( required_exprs, eq_properties) ;
632+ if Self :: is_subset_partitioning (
531633 & normalized_partition_exprs,
532634 & normalized_required_exprs,
533- )
534- {
535- return PartitioningSatisfaction :: Subset ;
635+ ) {
636+ return PartitioningSatisfaction :: Subset ;
637+ }
536638 }
537639 } else if allow_subset
538640 && Self :: is_subset_partitioning ( partition_exprs, required_exprs)
@@ -1272,6 +1374,157 @@ mod tests {
12721374 Ok ( ( ) )
12731375 }
12741376
1377+ #[ test]
1378+ fn test_range_partitioning_compatible_with ( ) -> Result < ( ) > {
1379+ let fixture = PartitioningTestFixture :: int64 ( & [ "a" , "b" ] ) ?;
1380+ let mut eq_properties = fixture. eq_properties . clone ( ) ;
1381+ eq_properties. add_equal_conditions ( fixture. col ( 0 ) , fixture. col ( 1 ) ) ?;
1382+
1383+ let split_points = vec ! [ int_split_point( [ 10 ] ) , int_split_point( [ 20 ] ) ] ;
1384+ let range_a = fixture. range ( [ 0 ] , split_points. clone ( ) ) ;
1385+ let range_a_same = fixture. range ( [ 0 ] , split_points. clone ( ) ) ;
1386+ let range_b_equivalent = fixture. range ( [ 1 ] , split_points. clone ( ) ) ;
1387+ let range_b_different_split = fixture. range ( [ 1 ] , vec ! [ int_split_point( [ 30 ] ) ] ) ;
1388+ let range_a_desc = RangePartitioning :: try_new (
1389+ [ fixture. range_sort_expr ( 0 , SortOptions :: new ( true , false ) ) ] . into ( ) ,
1390+ vec ! [ int_split_point( [ 10 ] ) ] ,
1391+ ) ?;
1392+ let single_partition_range_a = fixture. range ( [ 0 ] , vec ! [ ] ) ;
1393+ let single_partition_range_b = fixture. range ( [ 1 ] , vec ! [ ] ) ;
1394+
1395+ assert ! ( range_a. compatible_with( & range_a_same, & fixture. eq_properties) ) ;
1396+ assert ! ( range_a. compatible_with( & range_b_equivalent, & eq_properties) ) ;
1397+ assert ! ( !range_a. compatible_with( & range_b_equivalent, & fixture. eq_properties) ) ;
1398+ assert ! ( !range_a. compatible_with( & range_b_different_split, & eq_properties) ) ;
1399+ assert ! ( !range_a. compatible_with( & range_a_desc, & eq_properties) ) ;
1400+ assert ! (
1401+ single_partition_range_a
1402+ . compatible_with( & single_partition_range_b, & fixture. eq_properties)
1403+ ) ;
1404+
1405+ assert ! (
1406+ fixture
1407+ . range_partitioning( [ 0 ] , vec![ int_split_point( [ 10 ] ) ] )
1408+ . compatible_with(
1409+ & fixture. range_partitioning( [ 1 ] , vec![ int_split_point( [ 10 ] ) ] ) ,
1410+ & eq_properties
1411+ )
1412+ ) ;
1413+ assert ! (
1414+ !fixture
1415+ . range_partitioning( [ 0 ] , vec![ int_split_point( [ 10 ] ) ] )
1416+ . compatible_with(
1417+ & fixture. range_partitioning( [ 0 ] , vec![ int_split_point( [ 20 ] ) ] ) ,
1418+ & fixture. eq_properties
1419+ )
1420+ ) ;
1421+ assert ! (
1422+ !fixture
1423+ . range_partitioning( [ 0 ] , vec![ int_split_point( [ 10 ] ) ] )
1424+ . compatible_with(
1425+ & fixture. hash_partitioning( [ 0 ] , 2 ) ,
1426+ & fixture. eq_properties
1427+ )
1428+ ) ;
1429+
1430+ Ok ( ( ) )
1431+ }
1432+
1433+ #[ test]
1434+ fn test_hash_partitioning_compatible_with ( ) -> Result < ( ) > {
1435+ let fixture = PartitioningTestFixture :: int64 ( & [ "a" , "b" ] ) ?;
1436+ let mut eq_properties = fixture. eq_properties . clone ( ) ;
1437+ eq_properties. add_equal_conditions ( fixture. col ( 0 ) , fixture. col ( 1 ) ) ?;
1438+
1439+ assert ! (
1440+ fixture. hash_partitioning( [ 0 ] , 2 ) . compatible_with(
1441+ & fixture. hash_partitioning( [ 0 ] , 2 ) ,
1442+ & fixture. eq_properties
1443+ )
1444+ ) ;
1445+ assert ! (
1446+ fixture
1447+ . hash_partitioning( [ 0 ] , 2 )
1448+ . compatible_with( & fixture. hash_partitioning( [ 1 ] , 2 ) , & eq_properties)
1449+ ) ;
1450+ assert ! (
1451+ !fixture. hash_partitioning( [ 0 ] , 2 ) . compatible_with(
1452+ & fixture. hash_partitioning( [ 1 ] , 2 ) ,
1453+ & fixture. eq_properties
1454+ )
1455+ ) ;
1456+ assert ! (
1457+ !fixture. hash_partitioning( [ 0 ] , 2 ) . compatible_with(
1458+ & fixture. hash_partitioning( [ 0 ] , 3 ) ,
1459+ & fixture. eq_properties
1460+ )
1461+ ) ;
1462+ assert ! ( !fixture. hash_partitioning( [ 0 ] , 2 ) . compatible_with(
1463+ & fixture. hash_partitioning( [ 0 , 1 ] , 2 ) ,
1464+ & fixture. eq_properties
1465+ ) ) ;
1466+ assert ! (
1467+ !Partitioning :: Hash ( vec![ ] , 2 )
1468+ . compatible_with( & Partitioning :: Hash ( vec![ ] , 2 ) , & fixture. eq_properties)
1469+ ) ;
1470+ assert ! ( !fixture. hash_partitioning( [ 0 ] , 2 ) . compatible_with(
1471+ & fixture. range_partitioning( [ 0 ] , vec![ int_split_point( [ 10 ] ) ] ) ,
1472+ & fixture. eq_properties
1473+ ) ) ;
1474+ assert ! (
1475+ fixture. hash_partitioning( [ 0 ] , 1 ) . compatible_with(
1476+ & Partitioning :: RoundRobinBatch ( 1 ) ,
1477+ & fixture. eq_properties
1478+ )
1479+ ) ;
1480+
1481+ Ok ( ( ) )
1482+ }
1483+
1484+ #[ test]
1485+ fn test_round_robin_partitioning_compatible_with ( ) {
1486+ let eq_properties = EquivalenceProperties :: new ( Arc :: new ( Schema :: empty ( ) ) ) ;
1487+
1488+ assert ! (
1489+ Partitioning :: RoundRobinBatch ( 1 )
1490+ . compatible_with( & Partitioning :: RoundRobinBatch ( 1 ) , & eq_properties)
1491+ ) ;
1492+ assert ! (
1493+ !Partitioning :: RoundRobinBatch ( 2 )
1494+ . compatible_with( & Partitioning :: RoundRobinBatch ( 2 ) , & eq_properties)
1495+ ) ;
1496+ assert ! (
1497+ Partitioning :: RoundRobinBatch ( 1 )
1498+ . compatible_with( & Partitioning :: UnknownPartitioning ( 1 ) , & eq_properties)
1499+ ) ;
1500+ assert ! (
1501+ !Partitioning :: RoundRobinBatch ( 2 )
1502+ . compatible_with( & Partitioning :: UnknownPartitioning ( 2 ) , & eq_properties)
1503+ ) ;
1504+ }
1505+
1506+ #[ test]
1507+ fn test_unknown_partitioning_compatible_with ( ) {
1508+ let eq_properties = EquivalenceProperties :: new ( Arc :: new ( Schema :: empty ( ) ) ) ;
1509+
1510+ assert ! (
1511+ Partitioning :: UnknownPartitioning ( 1 )
1512+ . compatible_with( & Partitioning :: UnknownPartitioning ( 1 ) , & eq_properties)
1513+ ) ;
1514+ assert ! (
1515+ !Partitioning :: UnknownPartitioning ( 2 )
1516+ . compatible_with( & Partitioning :: UnknownPartitioning ( 2 ) , & eq_properties)
1517+ ) ;
1518+ assert ! (
1519+ Partitioning :: UnknownPartitioning ( 1 )
1520+ . compatible_with( & Partitioning :: RoundRobinBatch ( 1 ) , & eq_properties)
1521+ ) ;
1522+ assert ! (
1523+ !Partitioning :: UnknownPartitioning ( 2 )
1524+ . compatible_with( & Partitioning :: RoundRobinBatch ( 2 ) , & eq_properties)
1525+ ) ;
1526+ }
1527+
12751528 #[ test]
12761529 fn test_multi_partition_range_does_not_satisfy_hash_distribution ( ) -> Result < ( ) > {
12771530 let fixture = PartitioningTestFixture :: int64 ( & [ "a" , "b" ] ) ?;
0 commit comments