SanityCheckPlan error when ordering by a literal column from the probe side of a hash join #26283

Describe the bug

Ordering by a column that is a literal in a subquery (-2 AS k below) fails at planning time when that subquery is the probe (right) input of a HashJoinExec:

SanityCheckPlan
caused by
Error during planning: Plan: ["SortPreservingMergeExec: [k@0 DESC]", "  HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[k@2, a@1]", ...] does not satisfy order requirements: [k@0 DESC]. Child-0 order: []

No sort is planned for k because k is constant in the probe input, but the join's output no longer knows that k is constant, so the sanity check rejects the plan.

To Reproduce

In datafusion-cli with default settings:

CREATE TABLE t(a INT, b INT) AS VALUES (1, 1), (2, 2), (3, 3), (4, 4);
CREATE TABLE u(a INT) AS VALUES (1);
CREATE TABLE v(x INT) AS VALUES (1), (2);

SELECT s.k, s.a
FROM (SELECT t.a, -2 AS k FROM t JOIN v ON t.b <> v.x) s
JOIN u ON s.a = u.a
ORDER BY s.k DESC;

In a new session with target_partitions = 1, a window function over a simpler join fails the same way:

SET datafusion.execution.target_partitions = 1;
CREATE TABLE t(a INT) AS VALUES (2), (2), (3);
CREATE TABLE e(a INT) AS VALUES (2);

SELECT s.a, row_number() OVER (PARTITION BY s.a ORDER BY s.k) AS r
FROM e JOIN (SELECT a, 'x' AS k FROM t) AS s ON s.a = e.a;

SanityCheckPlan
caused by
Error during planning: Plan: ["BoundedWindowAggExec: wdw=[row_number() PARTITION BY [s.a] ORDER BY [s.k ASC NULLS LAST] ...], mode=[Sorted]", "  HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, a@0)], projection=[a@1, k@2]", "    DataSourceExec: partitions=1, partition_sizes=[1]", "    SortExec: expr=[a@0 ASC NULLS LAST], preserve_partitioning=[false]", ...] does not satisfy order requirements: [a@0 NA, k@1 ASC NULLS LAST]. Child-0 order: [[a@0 ASC NULLS LAST]]

Tested on main at 0566b55.

Expected behavior

The first query returns one row, (-2, 1), and the second returns (2, 1) and (2, 2), as in PostgreSQL.

Additional context

• EquivalenceGroup::join shifts the right input's classes with EquivalenceClass::try_with_offset, which builds the new class from Self::default() and doesn't copy constant. So constants from a join's right input are dropped, while constants from the left input are kept.

• Copying constant in try_with_offset makes both queries above return the expected rows in a local build. On its own, though, it also keeps the constants of a LEFT JOIN's nullable right side (the problem in Wrong ORDER BY results after an outer join when the nullable side equates a column to coalesce/CASE #26036). For example, this query, which is correct on main ((2, x) first), starts returning (1, NULL) first:

  CREATE TABLE l(a INT) AS VALUES (1), (2);
  CREATE TABLE r(a INT) AS VALUES (2), (3), (4), (5), (6), (7);
  SELECT l.a, s.k FROM l LEFT JOIN (SELECT a, 'x' AS k FROM r) s ON l.a = s.a ORDER BY s.k, l.a;

  With fix: preserve outer join equivalences for null rows #26042 applied as well, all of these queries returned the expected rows.