apache / apache/datafusion

Incorrect join ordering properties can cause required sorts to be removed

Open
#25,052 1 comment 0 reactions 1 assignee Claimed by @lyne7-sc View on GitHub
bug
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### 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

```sql
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_

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.