Skip to content

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

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.

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