Incorrect join ordering properties can cause required sorts to be removed

[lyne7-sc]

Describe the bug

Joins can incorrectly append the other input's ordering to the maintained input's ordering.

With duplicate probe keys, matching rows from the other input repeat for each probe row. The combined ordering is therefore not guaranteed. This can cause the optimizer to remove required sorts, affecting ORDER BY, ORDER BY with LIMIT, and ranking window functions.

To Reproduce

SET datafusion.optimizer.prefer_hash_join = false;

CREATE TABLE join_left AS VALUES (1, 10), (1, 20);
CREATE TABLE join_right AS VALUES (1, 100), (1, 200);

SELECT l.column1 AS key, r.column2 AS value
FROM join_left l
JOIN join_right r ON l.column1 = r.column1
ORDER BY l.column1, r.column2;

The join can emit:

key  value
1    100
1    200
1    100
1    200

Although the key ordering is preserved, the output is not ordered by (key, value).

Expected behavior

Join output ordering properties should reflect the ordering actually guaranteed by the join. Required sorts should remain when the other input's ordering is not preserved.

Additional context

No response

[lyne7-sc]

take