Skip to content

Commit 1465d6f

Browse files
author
Gene Bordegaray
authored
Add partitioning compatibility API (apache#22590)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> - Closes apache#22589 - EPIC: apache#22395 - Relevant thread apache#21992 ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. --> Follow-up range partitioning work needs a way to ask whether two physical partitionings describe the same partition map. This is distinct from distribution satisfaction and is needed before optimizer rules can safely use partition-local behavior. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR. --> - Adds `Partitioning::compatible_with`. - Adds `RangePartitioning::compatible_with`. - Adds tests for hash, range, round-robin, and unknown partitioning compatibility. ## Are these changes tested? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> Yes added unit tests for all compatibility ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> Yes. This adds public compatibility helper API on physical partitioning types. <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent 5073db1 commit 1465d6f

1 file changed

Lines changed: 276 additions & 23 deletions

File tree

‎datafusion/physical-expr/src/partitioning.rs‎

Lines changed: 276 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -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)]
421500
pub 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

Comments
 (0)