Repository navigation
Commit d109f1b
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
- physical-expr/src
- physical-optimizer/src/ensure_requirements
- physical-plan/src
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1030 | 1030 | | |
1031 | 1031 | | |
1032 | 1032 | | |
| 1033 | + | |
| 1034 | + | |
| 1035 | + | |
| 1036 | + | |
| 1037 | + | |
| 1038 | + | |
| 1039 | + | |
| 1040 | + | |
| 1041 | + | |
| 1042 | + | |
| 1043 | + | |
| 1044 | + | |
| 1045 | + | |
| 1046 | + | |
| 1047 | + | |
| 1048 | + | |
| 1049 | + | |
| 1050 | + | |
| 1051 | + | |
| 1052 | + | |
| 1053 | + | |
| 1054 | + | |
| 1055 | + | |
| 1056 | + | |
| 1057 | + | |
| 1058 | + | |
| 1059 | + | |
| 1060 | + | |
| 1061 | + | |
| 1062 | + | |
| 1063 | + | |
| 1064 | + | |
| 1065 | + | |
| 1066 | + | |
| 1067 | + | |
| 1068 | + | |
| 1069 | + | |
| 1070 | + | |
| 1071 | + | |
| 1072 | + | |
| 1073 | + | |
| 1074 | + | |
| 1075 | + | |
| 1076 | + | |
| 1077 | + | |
| 1078 | + | |
| 1079 | + | |
| 1080 | + | |
| 1081 | + | |
| 1082 | + | |
| 1083 | + | |
| 1084 | + | |
| 1085 | + | |
| 1086 | + | |
| 1087 | + | |
| 1088 | + | |
| 1089 | + | |
| 1090 | + | |
| 1091 | + | |
| 1092 | + | |
| 1093 | + | |
| 1094 | + | |
| 1095 | + | |
| 1096 | + | |
| 1097 | + | |
| 1098 | + | |
| 1099 | + | |
| 1100 | + | |
| 1101 | + | |
| 1102 | + | |
| 1103 | + | |
| 1104 | + | |
| 1105 | + | |
| 1106 | + | |
| 1107 | + | |
| 1108 | + | |
| 1109 | + | |
| 1110 | + | |
| 1111 | + | |
| 1112 | + | |
| 1113 | + | |
| 1114 | + | |
| 1115 | + | |
| 1116 | + | |
| 1117 | + | |
| 1118 | + | |
| 1119 | + | |
| 1120 | + | |
| 1121 | + | |
| 1122 | + | |
| 1123 | + | |
| 1124 | + | |
| 1125 | + | |
| 1126 | + | |
| 1127 | + | |
| 1128 | + | |
| 1129 | + | |
| 1130 | + | |
1033 | 1131 | | |
1034 | 1132 | | |
1035 | 1133 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
21 | 21 | | |
22 | 22 | | |
23 | 23 | | |
| 24 | + | |
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
| |||
281 | 282 | | |
282 | 283 | | |
283 | 284 | | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
284 | 328 | | |
285 | 329 | | |
286 | 330 | | |
| |||
517 | 561 | | |
518 | 562 | | |
519 | 563 | | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
| 578 | + | |
| 579 | + | |
| 580 | + | |
| 581 | + | |
| 582 | + | |
| 583 | + | |
| 584 | + | |
| 585 | + | |
| 586 | + | |
| 587 | + | |
| 588 | + | |
| 589 | + | |
| 590 | + | |
| 591 | + | |
| 592 | + | |
| 593 | + | |
| 594 | + | |
520 | 595 | | |
521 | 596 | | |
522 | 597 | | |
| |||
1270 | 1345 | | |
1271 | 1346 | | |
1272 | 1347 | | |
| 1348 | + | |
| 1349 | + | |
| 1350 | + | |
| 1351 | + | |
| 1352 | + | |
| 1353 | + | |
| 1354 | + | |
| 1355 | + | |
| 1356 | + | |
| 1357 | + | |
| 1358 | + | |
| 1359 | + | |
| 1360 | + | |
| 1361 | + | |
| 1362 | + | |
| 1363 | + | |
| 1364 | + | |
| 1365 | + | |
| 1366 | + | |
| 1367 | + | |
| 1368 | + | |
| 1369 | + | |
| 1370 | + | |
| 1371 | + | |
| 1372 | + | |
| 1373 | + | |
| 1374 | + | |
| 1375 | + | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
| 1380 | + | |
| 1381 | + | |
| 1382 | + | |
| 1383 | + | |
| 1384 | + | |
| 1385 | + | |
| 1386 | + | |
| 1387 | + | |
| 1388 | + | |
| 1389 | + | |
| 1390 | + | |
| 1391 | + | |
| 1392 | + | |
| 1393 | + | |
| 1394 | + | |
| 1395 | + | |
| 1396 | + | |
| 1397 | + | |
| 1398 | + | |
| 1399 | + | |
| 1400 | + | |
| 1401 | + | |
| 1402 | + | |
| 1403 | + | |
| 1404 | + | |
| 1405 | + | |
| 1406 | + | |
| 1407 | + | |
| 1408 | + | |
| 1409 | + | |
| 1410 | + | |
| 1411 | + | |
| 1412 | + | |
| 1413 | + | |
| 1414 | + | |
| 1415 | + | |
| 1416 | + | |
| 1417 | + | |
| 1418 | + | |
| 1419 | + | |
| 1420 | + | |
| 1421 | + | |
| 1422 | + | |
| 1423 | + | |
| 1424 | + | |
| 1425 | + | |
| 1426 | + | |
| 1427 | + | |
| 1428 | + | |
| 1429 | + | |
| 1430 | + | |
| 1431 | + | |
| 1432 | + | |
| 1433 | + | |
| 1434 | + | |
| 1435 | + | |
| 1436 | + | |
| 1437 | + | |
| 1438 | + | |
| 1439 | + | |
| 1440 | + | |
| 1441 | + | |
| 1442 | + | |
| 1443 | + | |
| 1444 | + | |
| 1445 | + | |
| 1446 | + | |
| 1447 | + | |
| 1448 | + | |
| 1449 | + | |
| 1450 | + | |
| 1451 | + | |
| 1452 | + | |
| 1453 | + | |
| 1454 | + | |
| 1455 | + | |
| 1456 | + | |
| 1457 | + | |
| 1458 | + | |
1273 | 1459 | | |
1274 | 1460 | | |
1275 | 1461 | | |
| |||
0 commit comments