Skip to content

Commit ce077f6

Browse files
mattp5657Matthew Patton
authored andcommitted
feat: allow Full joins to reuse range co-partitioning in HashJoinExec (apache#23583)
## Which issue does this PR close? - Closes apache#23454. ## Rationale for this change apache#23184 let compatible range-partitioned inputs satisfy inner partitioned hash joins without repartitioning. Full partitioned equi joins still always went through the conservative hash-repartition path, even when both inputs were already co-partitioned by range on the join key(s). The per-partition unmatched-row tracking in `HashJoinExec` is already partition-local under `PartitionMode::Partitioned` (not shared globally like in `CollectLeft`), so Full-join semantics generalize cleanly to range co-partitioning with no additional bookkeeping required. ## What changes are included in this PR? - Extend `HashJoinExec::input_distribution_requirements()` to opt `JoinType::Full` in to `allow_range_satisfaction_for_key_partitioning()`, alongside the existing `JoinType::Inner` case. The underlying `co_partitioned` / `compatible_co_partitioning_layout` / `co_partitioning_satisfied` logic in `distribution_requirements.rs` was already join-type-agnostic, so no changes were needed there. - Add planner unit tests in `enforce_distribution.rs` covering both the compatible-layout case (no repartition inserted) and the incompatible-split-points case (repartition still inserted) for `JoinType::Full`. - Add a `range_partitioned_sparse` sqllogictest fixture table with the same partition layout as `range_partitioned` but only partially overlapping keys, and add sqllogictest coverage in `range_partitioning.slt` for: a compatible Full join avoiding repartition, an incompatible Full join still repartitioning, and matched/left-only/right-only unmatched rows produced correctly by a co-partitioned Full join. ## Are these changes tested? Yes: - Two new Rust unit tests in `datafusion/core/tests/physical_optimizer/enforce_distribution.rs` assert on the physical plan shape (repartition inserted or not) for compatible and incompatible range layouts. - Three new sqllogictest cases in `datafusion/sqllogictest/test_files/range_partitioning.slt` exercise the feature end-to-end against real data, including matched rows, left-only unmatched rows, and right-only unmatched rows for a Full outer join. - Existing `enforce_distribution` tests, `range_partitioning.slt`, and proto roundtrip tests all continue to pass. ## Are there any user-facing changes? Yes: `EXPLAIN` output for `Full` joins over compatible range-partitioned inputs will no longer show a `RepartitionExec`, and such queries will avoid the associated hash-shuffle cost at execution time. No public API changes. --------- Co-authored-by: Matthew Patton <[email protected]>
1 parent 5bcb1b9 commit ce077f6

4 files changed

Lines changed: 230 additions & 17 deletions

File tree

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

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1125,6 +1125,90 @@ fn range_window_rehashes_incompatible_range_partitioning() -> Result<()> {
11251125
Ok(())
11261126
}
11271127

1128+
#[test]
1129+
fn range_full_hash_join_reuses_compatible_range_partitioning() -> Result<()> {
1130+
let left = parquet_exec_with_output_partitioning(range_partitioning(
1131+
"a",
1132+
[10, 20, 30],
1133+
SortOptions::default(),
1134+
)?);
1135+
let right = projection_exec_with_alias(
1136+
parquet_exec_with_output_partitioning(range_partitioning(
1137+
"a",
1138+
[10, 20, 30],
1139+
SortOptions::default(),
1140+
)?),
1141+
vec![
1142+
("a".to_string(), "a1".to_string()),
1143+
("b".to_string(), "b1".to_string()),
1144+
],
1145+
);
1146+
let join_on = vec![(
1147+
Arc::new(Column::new_with_schema("a", &left.schema())?) as _,
1148+
Arc::new(Column::new_with_schema("a1", &right.schema())?) as _,
1149+
)];
1150+
let join = hash_join_exec(left, right, &join_on, &JoinType::Full);
1151+
1152+
let plan = TestConfig::default()
1153+
.with_query_execution_partitions(4)
1154+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1155+
1156+
assert_plan!(
1157+
plan,
1158+
@r"
1159+
HashJoinExec: mode=Partitioned, join_type=Full, on=[(a@0, a1@0)]
1160+
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
1161+
ProjectionExec: expr=[a@0 as a1, b@1 as b1]
1162+
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
1163+
"
1164+
);
1165+
1166+
Ok(())
1167+
}
1168+
1169+
#[test]
1170+
fn range_full_hash_join_rehashes_incompatible_range_partitioning() -> Result<()> {
1171+
let left = parquet_exec_with_output_partitioning(range_partitioning(
1172+
"a",
1173+
[10, 20, 30],
1174+
SortOptions::default(),
1175+
)?);
1176+
let right = projection_exec_with_alias(
1177+
parquet_exec_with_output_partitioning(range_partitioning(
1178+
"a",
1179+
[10, 30, 40],
1180+
SortOptions::default(),
1181+
)?),
1182+
vec![
1183+
("a".to_string(), "a1".to_string()),
1184+
("b".to_string(), "b1".to_string()),
1185+
],
1186+
);
1187+
let join_on = vec![(
1188+
Arc::new(Column::new_with_schema("a", &left.schema())?) as _,
1189+
Arc::new(Column::new_with_schema("a1", &right.schema())?) as _,
1190+
)];
1191+
let join = hash_join_exec(left, right, &join_on, &JoinType::Full);
1192+
1193+
let plan = TestConfig::default()
1194+
.with_query_execution_partitions(4)
1195+
.to_plan(join, &DISTRIB_DISTRIB_SORT);
1196+
1197+
assert_plan!(
1198+
plan,
1199+
@r"
1200+
HashJoinExec: mode=Partitioned, join_type=Full, on=[(a@0, a1@0)]
1201+
RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=4
1202+
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
1203+
RepartitionExec: partitioning=Hash([a1@0], 4), input_partitions=4
1204+
ProjectionExec: expr=[a@0 as a1, b@1 as b1]
1205+
DataSourceExec: file_groups={4 groups: [[p0], [p1], [p2], [p3]]}, projection=[a, b, c, d, e], output_partitioning=Range([a@0 ASC], [(10), (30), (40)], 4), file_type=parquet
1206+
"
1207+
);
1208+
1209+
Ok(())
1210+
}
1211+
11281212
#[test]
11291213
fn multi_hash_joins() -> Result<()> {
11301214
let left = parquet_exec();

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1274,7 +1274,9 @@ impl ExecutionPlan for HashJoinExec {
12741274
]),
12751275
};
12761276

1277-
if self.mode == PartitionMode::Partitioned && self.join_type == JoinType::Inner {
1277+
if self.mode == PartitionMode::Partitioned
1278+
&& matches!(self.join_type, JoinType::Inner | JoinType::Full)
1279+
{
12781280
requirements.allow_range_satisfaction_for_key_partitioning()
12791281
} else {
12801282
requirements

‎datafusion/sqllogictest/src/test_context/range_partitioning.rs‎

Lines changed: 28 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,7 @@ pub(super) fn register_range_partitioned_table(ctx: &SessionContext) {
121121
"range_partitioned_shifted",
122122
Path::new(env!("CARGO_MANIFEST_DIR"))
123123
.join("test_files/scratch_range_partitioning/range_partitioned_shifted"),
124-
schema,
124+
Arc::clone(&schema),
125125
[
126126
"1,1,10\n5,2,50\n10,1,100\n",
127127
"15,2,150\n",
@@ -130,6 +130,33 @@ pub(super) fn register_range_partitioned_table(ctx: &SessionContext) {
130130
],
131131
Some(shifted_output_partitioning),
132132
);
133+
134+
let sparse_output_partitioning = Partitioning::Range(
135+
RangePartitioning::try_new(
136+
vec![col("range_key").sort(true, true)],
137+
vec![
138+
SplitPoint::new(vec![ScalarValue::Int32(Some(10))]),
139+
SplitPoint::new(vec![ScalarValue::Int32(Some(20))]),
140+
SplitPoint::new(vec![ScalarValue::Int32(Some(30))]),
141+
],
142+
)
143+
.expect("range partitioning should be valid"),
144+
);
145+
146+
register_csv_listing_table(
147+
ctx,
148+
"range_partitioned_sparse",
149+
Path::new(env!("CARGO_MANIFEST_DIR"))
150+
.join("test_files/scratch_range_partitioning/range_partitioned_sparse"),
151+
schema,
152+
[
153+
"5,2,50\n8,3,80\n",
154+
"10,1,100\n",
155+
"20,1,200\n",
156+
"30,1,300\n40,4,400\n",
157+
],
158+
Some(sparse_output_partitioning),
159+
);
133160
}
134161

135162
fn register_csv_listing_table(

‎datafusion/sqllogictest/test_files/range_partitioning.slt‎

Lines changed: 115 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -385,9 +385,9 @@ ORDER BY l.non_range_key, l.value, r.value;
385385
2 350 350
386386

387387
##########
388-
# TEST 12: Non-Inner Range Join Repartitions
389-
# Only inner partitioned hash joins opt in to Range satisfying KeyPartitioned
390-
# requirements. Non-inner joins keep using Hash repartitioning.
388+
# TEST 12: Unsupported
389+
# Only Inner and Full partitioned hash joins opt in to Range satisfying
390+
# KeyPartitioned requirements. Other join types keep using Hash repartitioning.
391391
##########
392392

393393
query TT
@@ -761,6 +761,106 @@ FULL JOIN unbounded_range_like_shifted r ON l.range_key = r.range_key;
761761
35 350 350
762762
5 50 50
763763

764+
##########
765+
# TEST 22: Full Outer Join on Range Partition Column
766+
# Full partitioned hash joins also opt in to Range satisfying KeyPartitioned
767+
# requirements, so compatible Range layouts avoid Hash repartitioning here too.
768+
##########
769+
770+
query TT
771+
EXPLAIN SELECT l.range_key, l.value, r.value
772+
FROM range_partitioned l
773+
FULL JOIN range_partitioned r ON l.range_key = r.range_key;
774+
----
775+
physical_plan
776+
01)HashJoinExec: mode=Partitioned, join_type=Full, on=[(range_key@0, range_key@0)], projection=[range_key@0, value@1, value@3]
777+
02)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
778+
03)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
779+
780+
query III
781+
SELECT l.range_key, l.value, r.value
782+
FROM range_partitioned l
783+
FULL JOIN range_partitioned r ON l.range_key = r.range_key
784+
ORDER BY l.range_key;
785+
----
786+
1 10 10
787+
5 50 50
788+
10 100 100
789+
15 150 150
790+
20 200 200
791+
25 250 250
792+
30 300 300
793+
35 350 350
794+
795+
##########
796+
# TEST 23: Full Outer Join Incompatible Range Repartitions
797+
# Same as TEST 10, but for Full: differing split points between the two
798+
# Range-partitioned inputs still require Hash repartitioning to co-partition.
799+
##########
800+
801+
query TT
802+
EXPLAIN SELECT l.range_key, l.value, r.value
803+
FROM range_partitioned l
804+
FULL JOIN range_partitioned_shifted r ON l.range_key = r.range_key;
805+
----
806+
physical_plan
807+
01)HashJoinExec: mode=Partitioned, join_type=Full, on=[(range_key@0, range_key@0)], projection=[range_key@0, value@1, value@3]
808+
02)--RepartitionExec: partitioning=Hash([range_key@0], 4), input_partitions=4
809+
03)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
810+
04)--RepartitionExec: partitioning=Hash([range_key@0], 4), input_partitions=4
811+
05)----DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(15), (20), (30)], 4), file_type=csv, has_header=false
812+
813+
query III
814+
SELECT l.range_key, l.value, r.value
815+
FROM range_partitioned l
816+
FULL JOIN range_partitioned_shifted r ON l.range_key = r.range_key
817+
ORDER BY l.range_key;
818+
----
819+
1 10 10
820+
5 50 50
821+
10 100 100
822+
15 150 150
823+
20 200 200
824+
25 250 250
825+
30 300 300
826+
35 350 350
827+
828+
##########
829+
# TEST 24: Full Outer Join Produces Matched and Unmatched Rows
830+
# `range_partitioned` and `range_partitioned_sparse` share the same Range
831+
# split points/partition count but only partially overlapping range_key
832+
# values, so this exercises matched rows, left-only unmatched rows (NULLs on
833+
# the right), and right-only unmatched rows (NULLs on the left) while still
834+
# avoiding Hash repartitioning.
835+
##########
836+
837+
query TT
838+
EXPLAIN SELECT l.range_key, r.range_key, l.value, r.value
839+
FROM range_partitioned l
840+
FULL JOIN range_partitioned_sparse r ON l.range_key = r.range_key;
841+
----
842+
physical_plan
843+
01)HashJoinExec: mode=Partitioned, join_type=Full, on=[(range_key@0, range_key@0)], projection=[range_key@0, range_key@2, value@1, value@3]
844+
02)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
845+
03)--DataSourceExec: file_groups=<slt:ignore>, projection=[range_key, value], output_partitioning=Range([range_key@0 ASC], [(10), (20), (30)], 4), file_type=csv, has_header=false
846+
847+
query IIII
848+
SELECT l.range_key, r.range_key, l.value, r.value
849+
FROM range_partitioned l
850+
FULL JOIN range_partitioned_sparse r ON l.range_key = r.range_key
851+
ORDER BY l.range_key, r.range_key;
852+
----
853+
1 NULL 10 NULL
854+
5 5 50 50
855+
10 10 100 100
856+
15 NULL 150 NULL
857+
20 20 200 200
858+
25 NULL 250 NULL
859+
30 30 300 300
860+
35 NULL 350 NULL
861+
NULL 8 NULL 80
862+
NULL 40 NULL 400
863+
764864
statement ok
765865
reset datafusion.optimizer.prefer_hash_join;
766866

@@ -771,7 +871,7 @@ statement ok
771871
reset datafusion.optimizer.preserve_file_partitions;
772872

773873
##########
774-
# TEST 22: Union of Range Partitioned Inputs
874+
# TEST 25: Union of Range Partitioned Inputs
775875
# Each input exposes the same Range partitioning on range_key, so the optimizer
776876
# converts UnionExec to InterleaveExec to avoid redundant repartitioning.
777877
##########
@@ -820,7 +920,7 @@ set datafusion.optimizer.preserve_file_partitions = 0;
820920

821921

822922
##########
823-
# TEST 23: Window on Range Partition Column
923+
# TEST 26: Window on Range Partition Column
824924
# Range([range_key]) colocates equal range_key values, so
825925
# PARTITION BY range_key is satisfied without a hash repartition.
826926
##########
@@ -848,7 +948,7 @@ SELECT range_key, SUM(value) OVER (PARTITION BY range_key ORDER BY value) FROM r
848948

849949

850950
##########
851-
# TEST 24: Unbounded-Frame Window on Range Partition Column
951+
# TEST 27: Unbounded-Frame Window on Range Partition Column
852952
# The unbounded frame makes DataFusion use WindowAggExec instead of
853953
# BoundedWindowAggExec, which likewise reuses Range partitioning without a
854954
# hash repartition.
@@ -877,7 +977,7 @@ SELECT range_key, SUM(value) OVER (PARTITION BY range_key ORDER BY value ROWS BE
877977

878978

879979
##########
880-
# TEST 25: Window on Non-Range Column Rehashes
980+
# TEST 28: Window on Non-Range Column Rehashes
881981
# Range([range_key]) does not colocate non_range_key values, so
882982
# PARTITION BY non_range_key still requires a hash repartition.
883983
##########
@@ -906,7 +1006,7 @@ SELECT non_range_key, value, SUM(value) OVER (PARTITION BY non_range_key ORDER B
9061006

9071007

9081008
##########
909-
# TEST 26: Unbounded-Frame Window on Non-Range Column Rehashes
1009+
# TEST 29: Unbounded-Frame Window on Non-Range Column Rehashes
9101010
# The unbounded frame makes DataFusion use WindowAggExec; Range([range_key])
9111011
# does not colocate non_range_key values, so PARTITION BY non_range_key
9121012
# still requires a hash repartition.
@@ -936,7 +1036,7 @@ SELECT non_range_key, value, SUM(value) OVER (PARTITION BY non_range_key ORDER B
9361036

9371037

9381038
##########
939-
# TEST 27: Window Subset Satisfaction on Range Partition Column
1039+
# TEST 30: Window Subset Satisfaction on Range Partition Column
9401040
# With the subset threshold met, Range([range_key]) satisfies
9411041
# PARTITION BY (range_key, non_range_key): equal composite keys share the
9421042
# same range_key, so they are already colocated.
@@ -968,7 +1068,7 @@ SELECT range_key, SUM(value) OVER (PARTITION BY range_key, non_range_key ORDER B
9681068

9691069

9701070
##########
971-
# TEST 28: Window Subset Rehashes Below Subset Threshold
1071+
# TEST 31: Window Subset Rehashes Below Subset Threshold
9721072
# Range([range_key]) is only a subset of PARTITION BY
9731073
# (range_key, non_range_key), so it should not satisfy the window key when
9741074
# subset satisfaction is disabled.
@@ -1007,7 +1107,7 @@ reset datafusion.optimizer.preserve_file_partitions;
10071107

10081108

10091109
##########
1010-
# TEST 29: Window Without Partition Keys Uses a Single Partition
1110+
# TEST 32: Window Without Partition Keys Uses a Single Partition
10111111
# A window with no PARTITION BY requires a single partition; range
10121112
# partitioning is not applicable.
10131113
##########
@@ -1037,7 +1137,7 @@ SELECT range_key, SUM(value) OVER (ORDER BY value) FROM range_partitioned ORDER
10371137

10381138

10391139
##########
1040-
# TEST 30: PartitionedTopK on Range Partition Column
1140+
# TEST 33: PartitionedTopK on Range Partition Column
10411141
# Exact Range([range_key]) satisfies the TopK partition key and avoids repartitioning.
10421142
##########
10431143

@@ -1080,7 +1180,7 @@ ORDER BY range_key;
10801180

10811181

10821182
##########
1083-
# TEST 31: PartitionedTopK on Non-Range Column
1183+
# TEST 34: PartitionedTopK on Non-Range Column
10841184
# Partitioning on a non-range key cannot reuse Range([range_key]) and
10851185
# requires hash repartitioning.
10861186
##########
@@ -1116,7 +1216,7 @@ ORDER BY non_range_key;
11161216

11171217

11181218
##########
1119-
# TEST 32: PartitionedTopK Reuses Range Subset Partitioning
1219+
# TEST 35: PartitionedTopK Reuses Range Subset Partitioning
11201220
# With subset threshold met and preserve-file disabled, Range([range_key])
11211221
# satisfies partitioning by (range_key, non_range_key).
11221222
##########
@@ -1157,7 +1257,7 @@ ORDER BY range_key, non_range_key;
11571257

11581258

11591259
##########
1160-
# TEST 33: Range Subset PartitionedTopK Rehashes Below Subset Threshold
1260+
# TEST 36: Range Subset PartitionedTopK Rehashes Below Subset Threshold
11611261
# Range([range_key]) is only a subset of PARTITION BY (range_key, non_range_key),
11621262
# so it should not satisfy the TopK partition key when subset satisfaction is
11631263
# disabled.

0 commit comments

Comments
 (0)