Repository navigation
Commit 1d1ec1e
Gene Bordegaray
Support co-partitioned range inner equi joins (apache#23184)
- Closes apache#23183.
- Part of apache#22395.
DataFusion can represent source-declared range partitioning, but
partitioned hash joins still required hash partitioned inputs. So an
inner join on compatible range-partitioned keys would insert unnecessary
hash repartitions, even when each left/right partition already covered
the same key domain.
This PR adds a partitioning requirement that means "equal key values are
co-located" . I was calling this "compatibility" but found we can
satisfy the requirement with looser conditions. Other systems call this
"co-location" or "co-partitioning"
([trino](https://trino.io/docs/current/admin/properties-optimizer.html#optimizer-colocated-joins-enabled),
[spark](https://spark.apache.org/docs/latest/sql-performance-tuning.html#storage-partition-join)).
Which they (and now I am proposing) define as when both sides of a join
are already partitioned so matching key values appear in corresponding
partitions, so we can join partition pairs directly without
repartitioning the sides.
This lets "co-partitioned" range inputs satisfy inner partitioned hash
joins. This will also be applicable to other join types and operators
but kept the first PR thin to keep scope more reviewable.
- Adds `Distribution::KeyPartitioned(Vec<Arc<dyn PhysicalExpr>>)` as a
public distribution requirement.
- `HashPartitioned([a])` means rows must be partitioned by hash on `a`.
- `KeyPartitioned([a])` means rows with equal `a` values must be
co-located, but the partitioning algorithm may be hash, range, or
another compatible scheme.
- Example:
```text
Hash([left.a], 3) satisfies KeyPartitioned([left.a])
Range([right.b ASC], [(10), (20)], 3) satisfies
KeyPartitioned([right.b])
```
- Adds `Partitioning::co_partitioned_with(...)` to validate that two
independently satisfying partitionings also can be paired by partition
index.
- Examples:
- Accepted: both sides satisfy their own key requirement and have
matching range boundaries.
```text
left: Range([a ASC], [(10), (20)], 3), required KeyPartitioned([a])
right: Range([b ASC], [(10), (20)], 3), required KeyPartitioned([b])
```
- Accepted: both sides satisfy their own key requirement and have
matching hash partition counts.
```text
left: Hash([a], 3), required KeyPartitioned([a])
right: Hash([b], 3), required KeyPartitioned([b])
```
- Rejected: both sides satisfy their own key requirement, but range
boundaries differ.
```text
left: Range([a ASC], [(10), (20)], 3), required KeyPartitioned([a])
right: Range([b ASC], [(15), (20)], 3), required KeyPartitioned([b])
```
- Rejected: both sides satisfy their own key requirement, but partition
counts differ.
```text
left: Hash([a], 3), required KeyPartitioned([a])
right: Hash([b], 4), required KeyPartitioned([b])
```
- Changes inner partitioned `HashJoinExec` requirements from
`HashPartitioned` to `KeyPartitioned`.
- All other hash joins still require `HashPartitioned` for now.
- Updates `EnforceDistribution` so co-partitioned range inner joins
avoid repartitioning.
- Examples:
- Compatible range partitioning: no repartition is inserted because
partitions can be joined by index.
```text
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)]
DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3)
DataSourceExec: output_partitioning=Range([b ASC], [(10), (20)], 3)
```
- Incompatible range boundaries: both sides are repartitioned by hash
because partition `i` does not represent the same key domain on both
sides.
```text
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)]
RepartitionExec: partitioning=Hash([a], target_partitions)
DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3)
RepartitionExec: partitioning=Hash([b], target_partitions)
DataSourceExec: output_partitioning=Range([b ASC], [(15), (20)], 3)
```
- Mismatched hash partition counts: both sides are forced to the target
hash partition count so partition indexes line up.
```text
HashJoinExec: mode=Partitioned, join_type=Inner, on=[(a, b)]
RepartitionExec: partitioning=Hash([a], target_partitions)
DataSourceExec: output_partitioning=Hash([a], 11)
RepartitionExec: partitioning=Hash([b], target_partitions)
DataSourceExec: output_partitioning=Hash([b], 12)
```
- Non-inner joins: range inputs still get hash repartitioning because
only inner partitioned hash joins use `KeyPartitioned` in this PR.
```text
HashJoinExec: mode=Partitioned, join_type=Left, on=[(a, b)]
RepartitionExec: partitioning=Hash([a], target_partitions)
DataSourceExec: output_partitioning=Range([a ASC], [(10), (20)], 3)
RepartitionExec: partitioning=Hash([b], target_partitions)
DataSourceExec: output_partitioning=Range([b ASC], [(10), (20)], 3)
```
- Keeps partitioned dynamic filter pushdown restricted to
hash-compatible routing.
- Compatible range partitioning can satisfy the join, but dynamic
filters still route by hash, so range/range partitioned joins disable
dynamic filters.
- Degrades range join output partitioning to `UnknownPartitioning(n)`
rather than erroring. Adding this behavior would need more tests and
careful thought about, I think its safert o just degrade for first PR.
Yes.
- `KeyPartitioned` satisfaction for hash and range partitioning.
- `co_partitioned_with` for compatible and incompatible range/hash
partitioning.
- `EnforceDistribution` behavior for:
- compatible range joins avoiding hash repartitioning
- incompatible range bounds rehashing
- mismatched hash partition counts rehashing
- non-inner range joins rehashing
- sanity checking for invalid partitioned hash joins.
- dynamic filter rejection for range partitioning, preserved file
partitions, and mismatched hash counts.
- sqllogictest coverage for range-partitioned joins avoiding hash
repartitioning and non-range joins still repartitioning.
Yes.
This PR changes public physical planning APIs:
- Adds `Distribution::KeyPartitioned`.
- Adds `Partitioning::co_partitioned_with`.
- **NOTE**: This replaces the previous partition compatibility API with
the new co-partitioning API. Since the compatibility API was never in a
release I believe this is ok to do (lesson learned to not make API
change until ew have definitive consumer).
- Affects users matching exhaustively on `Distribution`.1 parent d3a9271 commit 1d1ec1e
38 files changed
Lines changed: 1762 additions & 892 deletions
File tree
- datafusion
- catalog-listing/src
- core
- src/datasource/listing
- tests
- physical_optimizer
- user_defined
- datasource/src
- physical-expr/src
- physical-optimizer/src
- enforce_sorting
- physical-plan/src
- aggregates
- joins
- hash_join
- piecewise_merge_join
- sort_merge_join
- sorts
- windows
- proto/tests/cases
- sqllogictest
- src/test_context
- test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
802 | 802 | | |
803 | 803 | | |
804 | 804 | | |
805 | | - | |
| 805 | + | |
806 | 806 | | |
807 | 807 | | |
808 | 808 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
147 | 147 | | |
148 | 148 | | |
149 | 149 | | |
150 | | - | |
151 | 150 | | |
152 | 151 | | |
153 | 152 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
268 | 268 | | |
269 | 269 | | |
270 | 270 | | |
271 | | - | |
272 | | - | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
273 | 277 | | |
274 | 278 | | |
275 | 279 | | |
| |||
826 | 830 | | |
827 | 831 | | |
828 | 832 | | |
829 | | - | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
830 | 836 | | |
831 | 837 | | |
832 | 838 | | |
| |||
1013 | 1019 | | |
1014 | 1020 | | |
1015 | 1021 | | |
| 1022 | + | |
| 1023 | + | |
| 1024 | + | |
| 1025 | + | |
| 1026 | + | |
| 1027 | + | |
| 1028 | + | |
| 1029 | + | |
| 1030 | + | |
| 1031 | + | |
| 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 | + | |
1016 | 1065 | | |
1017 | 1066 | | |
1018 | 1067 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
800 | 800 | | |
801 | 801 | | |
802 | 802 | | |
803 | | - | |
| 803 | + | |
| 804 | + | |
| 805 | + | |
804 | 806 | | |
805 | 807 | | |
806 | 808 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
413 | 413 | | |
414 | 414 | | |
415 | 415 | | |
416 | | - | |
417 | | - | |
418 | | - | |
| 416 | + | |
419 | 417 | | |
420 | 418 | | |
421 | 419 | | |
422 | 420 | | |
423 | 421 | | |
424 | 422 | | |
425 | | - | |
426 | | - | |
| 423 | + | |
427 | 424 | | |
428 | | - | |
| 425 | + | |
| 426 | + | |
429 | 427 | | |
430 | | - | |
431 | 428 | | |
432 | 429 | | |
433 | 430 | | |
434 | 431 | | |
435 | | - | |
| 432 | + | |
436 | 433 | | |
437 | | - | |
| 434 | + | |
| 435 | + | |
438 | 436 | | |
439 | | - | |
440 | 437 | | |
441 | 438 | | |
442 | 439 | | |
443 | 440 | | |
444 | | - | |
| 441 | + | |
445 | 442 | | |
446 | 443 | | |
447 | 444 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
708 | 708 | | |
709 | 709 | | |
710 | 710 | | |
711 | | - | |
712 | | - | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
713 | 717 | | |
714 | 718 | | |
715 | 719 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
31 | 31 | | |
32 | 32 | | |
33 | 33 | | |
34 | | - | |
35 | | - | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
36 | 37 | | |
37 | 38 | | |
38 | 39 | | |
| |||
189 | 190 | | |
190 | 191 | | |
191 | 192 | | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
192 | 197 | | |
193 | 198 | | |
194 | | - | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
195 | 203 | | |
196 | 204 | | |
197 | 205 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
59 | 59 | | |
60 | 60 | | |
61 | 61 | | |
62 | | - | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
63 | 65 | | |
64 | 66 | | |
65 | 67 | | |
| |||
0 commit comments