Skip to content

Commit cc7565b

Browse files
authored
fix: don't report equi-key equivalence for PiecewiseMergeJoin range joins (apache#24361)
## Which issue does this PR close? - Closes apache#24360. ## Rationale for this change `PiecewiseMergeJoinExec::compute_properties` passed the join's `on` pair to `join_equivalence_properties` as if it were an equijoin key. For an `INNER` join that registers `left_on == right_on` as an output equivalence — but PWMJ's `on` is a **range** predicate (`l.v < r.v`), not equality, so the equivalence is false. It let the optimizer treat a sort on the left key as also sorting the right key and drop a required `ORDER BY`, returning wrongly ordered rows. ```sql set datafusion.optimizer.enable_piecewise_merge_join = true; create table l(v int) as values (1),(2),(3),(5),(8); create table r(v int) as values (4),(6),(9),(2); select l.v, r.v from l join r on l.v < r.v where l.v = 2 order by r.v; -- PWMJ: 2,9 / 2,6 / 2,4 (wrong order) -- NLJ: 2,4 / 2,6 / 2,9 (correct) ``` The plans differ: PWMJ sorts only on `l.v` (`SortExec: expr=[v@0 ASC]`); NLJ sorts on both (`[v@0 ASC, v@1 ASC]`). ## What changes are included in this PR? - `compute_properties` no longer passes the range `on` pair to `join_equivalence_properties` (a range join adds no column equivalences). The now-unused `join_on` parameter is dropped. - Existing `pwmj.slt` plans/results updated to the corrected (fully sorted) output — they previously encoded the wrong ordering — and a regression test is added. ## Are these changes tested? Yes. - New regression test in `pwmj.slt` (INNER `l.v < r.v`, `WHERE l.v = 2`, `ORDER BY r.v`) asserting the correctly ordered result. - The existing `pwmj.slt` cases that asserted the wrong ordering / a single-column sort plan are updated to the correct values (verified against `NestedLoopJoin`). - `piecewise` unit tests and `joins.slt` still pass. Only `INNER` is affected. ## Are there any user-facing changes? `INNER` range joins via `PiecewiseMergeJoin` (behind `enable_piecewise_merge_join`, default off) no longer drop a required sort, matching `NestedLoopJoin`. No API changes.
1 parent 7c079f7 commit cc7565b

2 files changed

Lines changed: 43 additions & 12 deletions

File tree

  • datafusion
    • physical-plan/src/joins/piecewise_merge_join
    • sqllogictest/test_files

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

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -363,7 +363,6 @@ impl PiecewiseMergeJoinExec {
363363
&streamed,
364364
Arc::clone(&schema),
365365
join_type,
366-
&on,
367366
)?;
368367

369368
Ok(Self {
@@ -425,7 +424,6 @@ impl PiecewiseMergeJoinExec {
425424
streamed: &Arc<dyn ExecutionPlan>,
426425
schema: SchemaRef,
427426
join_type: JoinType,
428-
join_on: &(PhysicalExprRef, PhysicalExprRef),
429427
) -> Result<PlanProperties> {
430428
let eq_properties = join_equivalence_properties(
431429
buffered.equivalence_properties().clone(),
@@ -434,7 +432,12 @@ impl PiecewiseMergeJoinExec {
434432
schema,
435433
&Self::maintains_input_order(join_type),
436434
Some(Self::probe_side(&join_type)),
437-
std::slice::from_ref(join_on),
435+
// `PiecewiseMergeJoin`'s `on` is a range predicate (e.g. `l < r`),
436+
// not an equijoin key. Passing it here would register a false
437+
// `left == right` output equivalence, letting the optimizer drop a
438+
// required sort and return wrongly ordered results. Range joins add
439+
// no column equivalences, so pass none.
440+
&[],
438441
)?;
439442

440443
let output_partitioning =

‎datafusion/sqllogictest/test_files/pwmj.slt‎

Lines changed: 37 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -129,7 +129,7 @@ logical_plan
129129
09)----------TableScan: join_t2 projection=[t2_id, t2_int]
130130
physical_plan
131131
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
132-
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
132+
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
133133
03)----PiecewiseMergeJoin: operator=GtEq, join_type=Inner, on=(t1_id >= t2_id)
134134
04)------SortExec: expr=[t1_id@0 ASC], preserve_partitioning=[false]
135135
05)--------FilterExec: t1_id@0 >= 22
@@ -146,12 +146,12 @@ JOIN join_t2 t2
146146
WHERE t2.t2_int >= 3
147147
ORDER BY 1,2;
148148
----
149-
11 55
150149
11 44
151-
22 55
150+
11 55
152151
22 44
153-
33 55
152+
22 55
154153
33 44
154+
33 55
155155
44 55
156156

157157
query TT
@@ -174,7 +174,7 @@ logical_plan
174174
08)----------TableScan: join_t2 projection=[t2_id, t2_int]
175175
physical_plan
176176
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
177-
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
177+
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
178178
03)----PiecewiseMergeJoin: operator=Lt, join_type=Inner, on=(t1_id < t2_id)
179179
04)------SortExec: expr=[t1_id@0 DESC], preserve_partitioning=[false]
180180
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
@@ -238,11 +238,11 @@ WHERE t1.t1_id IN (11, 44)
238238
AND t2.t2_name <> 'y'
239239
ORDER BY 1,2;
240240
----
241-
11 55
242-
11 44
243241
11 11
244-
44 55
242+
11 44
243+
11 55
245244
44 44
245+
44 55
246246

247247
query TT
248248
EXPLAIN
@@ -266,7 +266,7 @@ logical_plan
266266
09)----------TableScan: join_t2 projection=[t2_id, t2_name]
267267
physical_plan
268268
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
269-
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
269+
02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
270270
03)----PiecewiseMergeJoin: operator=LtEq, join_type=Inner, on=(t1_id <= t2_id)
271271
04)------SortExec: expr=[t1_id@0 DESC], preserve_partitioning=[false]
272272
05)--------FilterExec: t1_id@0 = 11 OR t1_id@0 = 44
@@ -387,6 +387,34 @@ ORDER BY 1,2;
387387
20 100
388388
NULL NULL
389389

390+
# Regression test: a range predicate is NOT an equi-key, so an INNER
391+
# PiecewiseMergeJoin must not report `l.v == r.v` as an output equivalence.
392+
# Doing so let the optimizer treat a sort on `l.v` as also sorting `r.v` and
393+
# drop the `ORDER BY r.v` sort, returning wrongly ordered rows.
394+
statement ok
395+
CREATE TABLE eq_t1 (v INT);
396+
397+
statement ok
398+
CREATE TABLE eq_t2 (v INT);
399+
400+
statement ok
401+
INSERT INTO eq_t1 VALUES (1), (2), (3), (5), (8);
402+
403+
statement ok
404+
INSERT INTO eq_t2 VALUES (4), (6), (9), (2);
405+
406+
query II
407+
SELECT t1.v AS lv, t2.v AS rv
408+
FROM eq_t1 t1
409+
JOIN eq_t2 t2
410+
ON t1.v < t2.v
411+
WHERE t1.v = 2
412+
ORDER BY t2.v;
413+
----
414+
2 4
415+
2 6
416+
2 9
417+
390418
# ------------------------------------------------------------------
391419
# Existence joins (LeftSemi / LeftAnti) via PiecewiseMergeJoin
392420
# ------------------------------------------------------------------

0 commit comments

Comments
 (0)