You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/08/14 20:14:53 UTC
(datafusion) branch gh-readonly-queue/main/pr-24361-7c079f744f32841f2166a60adfcde2ab297df725 created (now cc7565be1e)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-24361-7c079f744f32841f2166a60adfcde2ab297df725
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at cc7565be1e fix: don't report equi-key equivalence for PiecewiseMergeJoin range joins (#24361)
This branch includes the following new commits:
new cc7565be1e fix: don't report equi-key equivalence for PiecewiseMergeJoin range joins (#24361)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: fix: don't report equi-key equivalence for PiecewiseMergeJoin range joins (#24361)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-24361-7c079f744f32841f2166a60adfcde2ab297df725
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit cc7565be1ee97ba8fa2f5d6da373c5e38d81bb13
Author: Liang-Chi Hsieh <vi...@gmail.com>
AuthorDate: Fri Aug 14 20:14:31 2026 +0000
fix: don't report equi-key equivalence for PiecewiseMergeJoin range joins (#24361)
## Which issue does this PR close?
- Closes #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.
---
.../src/joins/piecewise_merge_join/exec.rs | 9 +++--
datafusion/sqllogictest/test_files/pwmj.slt | 46 +++++++++++++++++-----
2 files changed, 43 insertions(+), 12 deletions(-)
diff --git a/datafusion/physical-plan/src/joins/piecewise_merge_join/exec.rs b/datafusion/physical-plan/src/joins/piecewise_merge_join/exec.rs
index a91903934a..5183d3aa0f 100644
--- a/datafusion/physical-plan/src/joins/piecewise_merge_join/exec.rs
+++ b/datafusion/physical-plan/src/joins/piecewise_merge_join/exec.rs
@@ -363,7 +363,6 @@ impl PiecewiseMergeJoinExec {
&streamed,
Arc::clone(&schema),
join_type,
- &on,
)?;
Ok(Self {
@@ -425,7 +424,6 @@ impl PiecewiseMergeJoinExec {
streamed: &Arc<dyn ExecutionPlan>,
schema: SchemaRef,
join_type: JoinType,
- join_on: &(PhysicalExprRef, PhysicalExprRef),
) -> Result<PlanProperties> {
let eq_properties = join_equivalence_properties(
buffered.equivalence_properties().clone(),
@@ -434,7 +432,12 @@ impl PiecewiseMergeJoinExec {
schema,
&Self::maintains_input_order(join_type),
Some(Self::probe_side(&join_type)),
- std::slice::from_ref(join_on),
+ // `PiecewiseMergeJoin`'s `on` is a range predicate (e.g. `l < r`),
+ // not an equijoin key. Passing it here would register a false
+ // `left == right` output equivalence, letting the optimizer drop a
+ // required sort and return wrongly ordered results. Range joins add
+ // no column equivalences, so pass none.
+ &[],
)?;
let output_partitioning =
diff --git a/datafusion/sqllogictest/test_files/pwmj.slt b/datafusion/sqllogictest/test_files/pwmj.slt
index 42be6c6b5c..f71a1b6672 100644
--- a/datafusion/sqllogictest/test_files/pwmj.slt
+++ b/datafusion/sqllogictest/test_files/pwmj.slt
@@ -129,7 +129,7 @@ logical_plan
09)----------TableScan: join_t2 projection=[t2_id, t2_int]
physical_plan
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
-02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
+02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
03)----PiecewiseMergeJoin: operator=GtEq, join_type=Inner, on=(t1_id >= t2_id)
04)------SortExec: expr=[t1_id@0 ASC], preserve_partitioning=[false]
05)--------FilterExec: t1_id@0 >= 22
@@ -146,12 +146,12 @@ JOIN join_t2 t2
WHERE t2.t2_int >= 3
ORDER BY 1,2;
----
-11 55
11 44
-22 55
+11 55
22 44
-33 55
+22 55
33 44
+33 55
44 55
query TT
@@ -174,7 +174,7 @@ logical_plan
08)----------TableScan: join_t2 projection=[t2_id, t2_int]
physical_plan
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
-02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
+02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
03)----PiecewiseMergeJoin: operator=Lt, join_type=Inner, on=(t1_id < t2_id)
04)------SortExec: expr=[t1_id@0 DESC], preserve_partitioning=[false]
05)--------DataSourceExec: partitions=1, partition_sizes=[1]
@@ -238,11 +238,11 @@ WHERE t1.t1_id IN (11, 44)
AND t2.t2_name <> 'y'
ORDER BY 1,2;
----
-11 55
-11 44
11 11
-44 55
+11 44
+11 55
44 44
+44 55
query TT
EXPLAIN
@@ -266,7 +266,7 @@ logical_plan
09)----------TableScan: join_t2 projection=[t2_id, t2_name]
physical_plan
01)SortPreservingMergeExec: [t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST]
-02)--SortExec: expr=[t1_id@0 ASC NULLS LAST], preserve_partitioning=[true]
+02)--SortExec: expr=[t1_id@0 ASC NULLS LAST, t2_id@1 ASC NULLS LAST], preserve_partitioning=[true]
03)----PiecewiseMergeJoin: operator=LtEq, join_type=Inner, on=(t1_id <= t2_id)
04)------SortExec: expr=[t1_id@0 DESC], preserve_partitioning=[false]
05)--------FilterExec: t1_id@0 = 11 OR t1_id@0 = 44
@@ -387,6 +387,34 @@ ORDER BY 1,2;
20 100
NULL NULL
+# Regression test: a range predicate is NOT an equi-key, so an INNER
+# PiecewiseMergeJoin must not report `l.v == r.v` as an output equivalence.
+# Doing so let the optimizer treat a sort on `l.v` as also sorting `r.v` and
+# drop the `ORDER BY r.v` sort, returning wrongly ordered rows.
+statement ok
+CREATE TABLE eq_t1 (v INT);
+
+statement ok
+CREATE TABLE eq_t2 (v INT);
+
+statement ok
+INSERT INTO eq_t1 VALUES (1), (2), (3), (5), (8);
+
+statement ok
+INSERT INTO eq_t2 VALUES (4), (6), (9), (2);
+
+query II
+SELECT t1.v AS lv, t2.v AS rv
+FROM eq_t1 t1
+JOIN eq_t2 t2
+ ON t1.v < t2.v
+WHERE t1.v = 2
+ORDER BY t2.v;
+----
+2 4
+2 6
+2 9
+
# ------------------------------------------------------------------
# Existence joins (LeftSemi / LeftAnti) via PiecewiseMergeJoin
# ------------------------------------------------------------------
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org