Repository navigation
Commit 63e25c1
Gene Bordegaray
Support co-partitioned range inner equi joins (apache#23184)
## Which issue does this PR close?
- Closes apache#23183.
- Part of apache#22395.
## Rationale for this change
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.
## What changes are included in this PR?
- 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.
## Are these changes tested?
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.
## Are there any user-facing changes?
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 24d8957 commit 63e25c1
37 files changed
Lines changed: 1635 additions & 473 deletions
File tree
- datafusion
- core/tests
- physical_optimizer
- user_defined
- datasource/src
- physical-expr/src
- physical-optimizer/src
- ensure_requirements
- enforce_sorting
- physical-plan/src
- aggregates
- joins
- hash_join
- piecewise_merge_join
- sort_merge_join
- sorts
- windows
- sqllogictest
- src/test_context
- test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
265 | 265 | | |
266 | 266 | | |
267 | 267 | | |
268 | | - | |
269 | | - | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
270 | 274 | | |
271 | 275 | | |
272 | 276 | | |
| |||
823 | 827 | | |
824 | 828 | | |
825 | 829 | | |
| 830 | + | |
| 831 | + | |
| 832 | + | |
| 833 | + | |
| 834 | + | |
| 835 | + | |
| 836 | + | |
| 837 | + | |
| 838 | + | |
| 839 | + | |
| 840 | + | |
| 841 | + | |
| 842 | + | |
| 843 | + | |
| 844 | + | |
| 845 | + | |
| 846 | + | |
| 847 | + | |
| 848 | + | |
| 849 | + | |
| 850 | + | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
| 855 | + | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
826 | 873 | | |
827 | 874 | | |
828 | 875 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
974 | 974 | | |
975 | 975 | | |
976 | 976 | | |
977 | | - | |
978 | | - | |
| 977 | + | |
| 978 | + | |
| 979 | + | |
| 980 | + | |
| 981 | + | |
| 982 | + | |
979 | 983 | | |
980 | 984 | | |
981 | 985 | | |
| |||
| 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 | |
|---|---|---|---|
| |||
19 | 19 | | |
20 | 20 | | |
21 | 21 | | |
22 | | - | |
23 | | - | |
24 | | - | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
25 | 25 | | |
26 | 26 | | |
27 | 27 | | |
| |||
30 | 30 | | |
31 | 31 | | |
32 | 32 | | |
33 | | - | |
34 | 33 | | |
| 34 | + | |
35 | 35 | | |
36 | 36 | | |
37 | 37 | | |
| |||
400 | 400 | | |
401 | 401 | | |
402 | 402 | | |
| 403 | + | |
| 404 | + | |
| 405 | + | |
| 406 | + | |
| 407 | + | |
| 408 | + | |
| 409 | + | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
| 413 | + | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
| 419 | + | |
| 420 | + | |
| 421 | + | |
| 422 | + | |
| 423 | + | |
| 424 | + | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
403 | 446 | | |
404 | 447 | | |
405 | 448 | | |
| |||
| 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 | |
|---|---|---|---|
| |||
63 | 63 | | |
64 | 64 | | |
65 | 65 | | |
66 | | - | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
67 | 69 | | |
68 | 70 | | |
69 | 71 | | |
| |||
0 commit comments