Skip to content

Commit d109f1b

Browse files
authored
Adapt existing partitioning for unsatisfied inputs in co-partitioned joins (#24600)
## Which issue does this PR close? - Closes #24599. ## Rationale for this change When multi-child operators (such as `HashJoinExec` or `SortMergeJoinExec`) declare co-partitioning requirements via `InputDistributionRequirements`, all children must share a compatible partitioning scheme on their respective join keys. Prior to this change, joining an unpartitioned stream with an input that was already partitioned (such as `Partitioning::Range` or `Partitioning::Hash` from a pre-sorted/partitioned data source scan): 1. During per-child requirement enforcement in [`ensure_distribution`](https://github.com/apache/datafusion/blob/d5552342012888b7d1a3ab88d92e3d292fc0cde0/datafusion/physical-optimizer/src/ensure_requirements/enforce_distribution.rs#L1285-L1552), the unpartitioned input failed its `Distribution::KeyPartitioned` requirement and was wrapped in `RepartitionExec: Hash(keys, target_partitions)`. 2. When [`enforce_distribution_relationships`](https://github.com/apache/datafusion/blob/d5552342012888b7d1a3ab88d92e3d292fc0cde0/datafusion/physical-optimizer/src/ensure_requirements/enforce_distribution.rs#L1078-L1271) inspected both children, it saw a layout mismatch between `Hash` and `Range`. The code would only create `Hash` partitionings, and so it discarded the existing native `Range` partitioning on the second child and wrapped both children in `RepartitionExec: Hash`, forcing a double shuffle. ## What changes are included in this PR? This PR adjusts `enforce_distribution_relationships` to recognize when one of the children in a co-partitioned group already satisfies its distribution requirement, selecting it as a reference partitioning and adapting unsatisfied peer inputs to match: * Candidate Identification & Tie-Breaking: - Inspect co-partitioned children to find those that satisfy [`input_distributions.child_satisfaction()`](https://github.com/apache/datafusion/blob/d5552342012888b7d1a3ab88d92e3d292fc0cde0/datafusion/physical-plan/src/distribution_requirements.rs#L164-L181). - Prefer native partitioned inputs (e.g. data source scans) over newly injected `RepartitionExec` exchange nodes (since their statistics and partition balance are more likely to be accurate). - For tie-breaking among multiple satisfied candidates, rank candidates using `PlanSize` (`total_byte_size`, then `num_rows` computed via `StatisticsContext`) and select the strictly largest input. * Partitioning Adaptation: - `RangePartitioning`: If the satisfied reference child has `Partitioning::Range(ref_range)`, adapt `ref_range`'s `split_points` and sort options to the unsatisfied child's join expressions after verifying that expression data types match split point scalar values via `split_points_match_expr_types`. - `HashPartitioning`: If the reference child has `Partitioning::Hash(_, count)`, adapt to `Partitioning::Hash(exprs, count)`. - Validate that the reference candidate can be adapted across all unsatisfied children in the co-partitioned group; if any child is incompatible, safely fall back to standard two-sided hash repartitioning. * In-Place Repartition Rewiring: - If the unsatisfied child was already wrapped in an eager `RepartitionExec` during Phase 1, replace its input directly rather than nesting redundant `RepartitionExec` nodes. ## Are these changes tested? Yes, integration tests in `datafusion/core/tests/physical_optimizer/enforce_distribution.rs`: - `range_hash_join_repartitions_unsatisfied_side_to_match_range`: verifies unsatisfied range input adapts to peer reference range partitioning. - `range_hash_join_repartitions_unpartitioned_side_to_match_range`: verifies unpartitioned scan input adapts directly to peer range partitioning without modifying the partitioned side. - `range_hash_join_rehashes_incompatible_data_type`: verifies type mismatch (`Int32` vs `Int64`) safely falls back to two-sided hash repartitioning. ## Are there any user-facing changes? No API changes.
1 parent 7776266 commit d109f1b

5 files changed

Lines changed: 514 additions & 41 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_distribution.rs‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1030,6 +1030,104 @@ fn range_right_mark_hash_join_reuses_range_partitioning() -> Result<()> {
10301030
Ok(())
10311031
}
10321032

1033+
#[test]
1034+
fn range_hash_join_repartitions_unsatisfied_side_to_match_range() -> Result<()> {
1035+
let left = parquet_exec_with_output_partitioning(range_partitioning(
1036+
"b",
1037+
[100, 200, 300],
1038+
SortOptions::default(),
1039+
)?);
1040+
let right = parquet_exec_with_output_partitioning(range_partitioning(
1041+
"a",
1042+
[10, 20, 30],
1043+
SortOptions::default(),
1044+
)?);
1045+
let join_on = vec![(
1046+
Arc::new(Column::new_with_schema("a", &left.schema())?) as _,
1047+
Arc::new(Column::new_with_schema("a", &right.schema())?) as _,
1048+
)];
1049+
let join = hash_join_exec(left, right, &join_on, &JoinType::Inner);
1050+
1051+
let plan = TestConfig::default()
1052+
.with_query_execution_partitions(4)
1053+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1054+
1055+
assert_plan!(
1056+
plan,
1057+
@r"
1058+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a@0, a@0)]
1059+
RepartitionExec: partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), input_partitions=4
1060+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([b@1 ASC], [(100), (200), (300)], 4), file_type=parquet
1061+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), file_type=parquet
1062+
"
1063+
);
1064+
1065+
Ok(())
1066+
}
1067+
1068+
#[test]
1069+
fn range_hash_join_repartitions_unpartitioned_side_to_match_range() -> Result<()> {
1070+
let left = parquet_exec();
1071+
let right = parquet_exec_with_output_partitioning(range_partitioning(
1072+
"a",
1073+
[10, 20, 30],
1074+
SortOptions::default(),
1075+
)?);
1076+
let join_on = vec![(
1077+
Arc::new(Column::new_with_schema("a", &left.schema())?) as _,
1078+
Arc::new(Column::new_with_schema("a", &right.schema())?) as _,
1079+
)];
1080+
let join = hash_join_exec(left, right, &join_on, &JoinType::Inner);
1081+
1082+
let plan = TestConfig::default()
1083+
.with_query_execution_partitions(4)
1084+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1085+
1086+
assert_plan!(
1087+
plan,
1088+
@r"
1089+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a@0, a@0)]
1090+
RepartitionExec: partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), input_partitions=1
1091+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
1092+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), file_type=parquet
1093+
"
1094+
);
1095+
1096+
Ok(())
1097+
}
1098+
1099+
#[test]
1100+
fn range_hash_join_rehashes_incompatible_data_type() -> Result<()> {
1101+
let left = parquet_exec();
1102+
let right = parquet_exec_with_output_partitioning(range_partitioning(
1103+
"a",
1104+
[10, 20, 30],
1105+
SortOptions::default(),
1106+
)?);
1107+
let join_on = vec![(
1108+
Arc::new(Column::new_with_schema("d", &left.schema())?) as _,
1109+
Arc::new(Column::new_with_schema("a", &right.schema())?) as _,
1110+
)];
1111+
let join = hash_join_exec(left, right, &join_on, &JoinType::Inner);
1112+
1113+
let plan = TestConfig::default()
1114+
.with_query_execution_partitions(4)
1115+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1116+
1117+
assert_plan!(
1118+
plan,
1119+
@r"
1120+
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(d@3, a@0)]
1121+
RepartitionExec: partitioning=Hash([d@3], 4), input_partitions=1
1122+
DataSourceExec: file_groups={1 group: [[x]]}, projection=[a, b, c, d, e], file_type=parquet
1123+
RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=4
1124+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (20), (30)], 4), file_type=parquet
1125+
"
1126+
);
1127+
1128+
Ok(())
1129+
}
1130+
10331131
#[test]
10341132
fn range_right_semi_hash_join_rehashes_incompatible_sort_options() -> Result<()> {
10351133
let left = parquet_exec_with_output_partitioning(range_partitioning(

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

Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ use crate::{
2121
EquivalenceProperties, PhysicalExpr, equivalence::ProjectionMapping,
2222
expressions::UnKnownColumn, physical_exprs_contains, physical_exprs_equal,
2323
};
24+
use arrow::datatypes::Schema;
2425
pub use datafusion_common::SplitPoint;
2526
use datafusion_common::{Result, validate_range_split_points};
2627
use datafusion_physical_expr_common::physical_expr::format_physical_expr_list;
@@ -281,6 +282,49 @@ impl RangePartitioning {
281282
split_points: self.split_points.clone(),
282283
})
283284
}
285+
286+
/// Checks whether the types of the given expressions match the data types of the split points in this range partitioning.
287+
pub fn is_compatible_with_expressions(
288+
&self,
289+
exprs: &[Arc<dyn PhysicalExpr>],
290+
schema: &Schema,
291+
) -> bool {
292+
if self.ordering.len() != exprs.len() {
293+
return false;
294+
}
295+
if let Some(first_split) = self.split_points.first() {
296+
exprs.iter().zip(first_split.values()).all(|(expr, val)| {
297+
expr.data_type(schema)
298+
.map(|dt| dt == val.data_type())
299+
.unwrap_or(false)
300+
})
301+
} else {
302+
true
303+
}
304+
}
305+
306+
/// Adapts this range partitioning to the given expressions, preserving split points and sort options.
307+
/// Returns `None` if `exprs` count doesn't match ordering length or expression types don't match split points.
308+
pub fn adapt(
309+
&self,
310+
exprs: &[Arc<dyn PhysicalExpr>],
311+
schema: &Schema,
312+
) -> Option<Self> {
313+
if !self.is_compatible_with_expressions(exprs, schema) {
314+
return None;
315+
}
316+
let new_ordering = LexOrdering::new(
317+
exprs
318+
.iter()
319+
.zip(&self.ordering)
320+
.map(|(expr, sort_expr)| PhysicalSortExpr {
321+
expr: Arc::clone(expr),
322+
options: sort_expr.options,
323+
})
324+
.collect::<Vec<_>>(),
325+
)?;
326+
Self::try_new(new_ordering, self.split_points.clone()).ok()
327+
}
284328
}
285329

286330
impl Display for RangePartitioning {
@@ -517,6 +561,37 @@ impl Partitioning {
517561
}
518562
}
519563
}
564+
565+
/// Adapts this partitioning scheme to satisfy a required [`Distribution`] on the given schema.
566+
///
567+
/// - For `Partitioning::Hash`: creates `Partitioning::Hash(exprs, partition_count)`.
568+
/// - For `Partitioning::Range`: adapts the range partitioning to the requirement's expressions using [`RangePartitioning::adapt`].
569+
/// - For other partitioning schemes: returns `None`.
570+
#[expect(
571+
deprecated,
572+
reason = "HashPartitioned is accepted during the KeyPartitioned migration"
573+
)]
574+
pub fn adapt(
575+
&self,
576+
child_requirement: &Distribution,
577+
child_schema: &Schema,
578+
) -> Option<Self> {
579+
let (Distribution::HashPartitioned(exprs) | Distribution::KeyPartitioned(exprs)) =
580+
child_requirement
581+
else {
582+
return None;
583+
};
584+
585+
match self {
586+
Partitioning::Range(ref_range) => ref_range
587+
.adapt(exprs, child_schema)
588+
.map(Partitioning::Range),
589+
Partitioning::Hash(_, ref_count) => {
590+
Some(Partitioning::Hash(exprs.to_vec(), *ref_count))
591+
}
592+
_ => None,
593+
}
594+
}
520595
}
521596

522597
/// Protobuf conversions for [`Partitioning`].
@@ -1270,6 +1345,117 @@ mod tests {
12701345

12711346
Ok(())
12721347
}
1348+
1349+
#[test]
1350+
fn test_range_partitioning_adapt() -> Result<()> {
1351+
let fixture = PartitioningTestFixture::new(vec![
1352+
("a", DataType::Int32),
1353+
("b", DataType::Int64),
1354+
("c", DataType::Int32),
1355+
])?;
1356+
1357+
let range = fixture.range(
1358+
[0],
1359+
vec![
1360+
SplitPoint::new(vec![ScalarValue::Int32(Some(10))]),
1361+
SplitPoint::new(vec![ScalarValue::Int32(Some(20))]),
1362+
],
1363+
);
1364+
1365+
// Adapting to col_c (same type Int32) succeeds
1366+
let adapted = range.adapt(&[fixture.col(2)], &fixture.schema).unwrap();
1367+
assert_eq!(adapted.ordering().len(), 1);
1368+
assert!(adapted.ordering()[0].expr.eq(&fixture.col(2)));
1369+
assert_eq!(adapted.partition_count(), 3);
1370+
1371+
// Adapting to col_b (different type Int64) fails
1372+
assert!(range.adapt(&[fixture.col(1)], &fixture.schema).is_none());
1373+
1374+
// Adapting to empty or mismatch count fails
1375+
assert!(range.adapt(&[], &fixture.schema).is_none());
1376+
assert!(
1377+
range
1378+
.adapt(&fixture.cols([0, 2]), &fixture.schema)
1379+
.is_none()
1380+
);
1381+
1382+
// Partitioning::adapt works with Distribution::KeyPartitioned
1383+
let part = Partitioning::Range(range);
1384+
assert!(
1385+
part.adapt(&fixture.key_distribution([1]), &fixture.schema)
1386+
.is_none()
1387+
);
1388+
1389+
let adapted_part = part
1390+
.adapt(&fixture.key_distribution([2]), &fixture.schema)
1391+
.unwrap();
1392+
match adapted_part {
1393+
Partitioning::Range(r) => assert!(r.ordering()[0].expr.eq(&fixture.col(2))),
1394+
_ => panic!("expected Range partitioning"),
1395+
}
1396+
1397+
// Partitioning::Hash adaptation
1398+
let hash_part = fixture.hash_partitioning([1], 4);
1399+
let adapted_hash = hash_part
1400+
.adapt(&fixture.key_distribution([2]), &fixture.schema)
1401+
.unwrap();
1402+
match adapted_hash {
1403+
Partitioning::Hash(exprs, count) => {
1404+
assert_eq!(count, 4);
1405+
assert_eq!(exprs.len(), 1);
1406+
assert!(exprs[0].eq(&fixture.col(2)));
1407+
}
1408+
_ => panic!("expected Hash partitioning"),
1409+
}
1410+
1411+
Ok(())
1412+
}
1413+
1414+
#[test]
1415+
fn test_range_partitioning_adapt_multi_key() -> Result<()> {
1416+
let fixture = PartitioningTestFixture::new(vec![
1417+
("k1", DataType::Int32),
1418+
("k2", DataType::Utf8),
1419+
("t1", DataType::Int32),
1420+
("t2", DataType::Utf8),
1421+
])?;
1422+
1423+
let opt_k1 = SortOptions {
1424+
descending: true,
1425+
nulls_first: false,
1426+
};
1427+
let opt_k2 = SortOptions {
1428+
descending: false,
1429+
nulls_first: true,
1430+
};
1431+
1432+
let ordering = LexOrdering::new(vec![
1433+
fixture.range_sort_expr(0, opt_k1),
1434+
fixture.range_sort_expr(1, opt_k2),
1435+
])
1436+
.unwrap();
1437+
1438+
let split_points = vec![
1439+
SplitPoint::new(vec![ScalarValue::Int32(Some(20)), ScalarValue::Utf8(None)]),
1440+
SplitPoint::new(vec![
1441+
ScalarValue::Int32(Some(10)),
1442+
ScalarValue::Utf8(Some("foo".to_string())),
1443+
]),
1444+
];
1445+
1446+
let range = RangePartitioning::try_new(ordering, split_points.clone())?;
1447+
let adapted = range.adapt(&fixture.cols([2, 3]), &fixture.schema).unwrap();
1448+
1449+
assert_eq!(adapted.ordering().len(), 2);
1450+
assert!(adapted.ordering()[0].expr.eq(&fixture.col(2)));
1451+
assert_eq!(adapted.ordering()[0].options, opt_k1);
1452+
assert!(adapted.ordering()[1].expr.eq(&fixture.col(3)));
1453+
assert_eq!(adapted.ordering()[1].options, opt_k2);
1454+
assert_eq!(adapted.split_points(), &split_points);
1455+
assert_eq!(adapted.partition_count(), 3);
1456+
1457+
Ok(())
1458+
}
12731459
}
12741460

12751461
#[cfg(all(test, feature = "proto"))]

0 commit comments

Comments
 (0)