Skip to content

PiecewiseMergeJoin reports a false equi-key equivalence for INNER range joins, dropping a required sort #24360

Closed

Description

@viirya

Describe the bug

An INNER PiecewiseMergeJoin reports a false output equivalence between the two sides of its range predicate, which can make the optimizer drop a required sort and return wrongly ordered results.

PiecewiseMergeJoinExec::compute_properties passes the join's on pair to join_equivalence_properties as if it were an equijoin key. For an INNER join, join_equivalence_properties registers left_on == right_on as an output equivalence. But PWMJ's on is a range predicate (l.v < r.v), not equality — so this equivalence is false. A downstream ORDER BY on the "other" column can then be optimized away because the planner believes it is already sorted.

To Reproduce

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 as lv, r.v as rv
from l join r on l.v < r.v
where l.v = 2
order by r.v;

Result with PiecewiseMergeJoin:

+----+----+
| lv | rv |
+----+----+
| 2  | 9  |
| 2  | 6  |
| 2  | 4  |
+----+----+

The correct result (what NestedLoopJoin returns with the flag off) is ordered by rv:

+----+----+
| lv | rv |
+----+----+
| 2  | 4  |
| 2  | 6  |
| 2  | 9  |
+----+----+

The plans show why — PWMJ sorts only on l.v, dropping the r.v sort:

PWMJ:  SortExec: expr=[v@0 ASC]                 <- only lv, rv sort elided
NLJ:   SortExec: expr=[v@0 ASC, v@1 ASC]        <- both

Expected behavior

A range join adds no column equivalences. PiecewiseMergeJoin should match NestedLoopJoin; the ORDER BY r.v sort must be preserved.

Additional context

  • Only INNER is affected — join_equivalence_properties/EquivalenceGroup::join only registers on-pair equalities for Inner.
  • PiecewiseMergeJoin is experimental (enable_piecewise_merge_join defaults to false), but this is worth fixing before default-enablement.
  • Part of the classic-join hardening for [EPIC]: Make PiecewiseMergeJoin work in Datafusion #17427. Fix + regression test coming.

Activity

  1. added a commit that references this issue on Aug 14, 2026
    cc7565b
  2. added a commit that references this issue on Aug 16, 2026
    68b8fd4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions