Push down TopK below Join
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
One case where pushing down sorts is when the sort has a `fetch` (aka TopK).
This will result in less input to the join, so the join will execute faster / with less memory usage.
### Describe the solution you'd like
Push down sorts with fetch for joins is (at least) possible when there is no join filter and:
* When sort expression is based on columns on the left side and type is left join
* When sort expression is based on columns on the right side and type is right join.
We should still keep the final sort on top of the result as not all planned join types will preserve the input ordering.
As we have the TopK as input for join, the resulting. The other optimization rules might remove the final sort if the physical join does in fact preserve the ordering (e.g. right joins and others).
The proposed optimization looks like:
```
Sort (fetch = 100) -> (projection) -> LeftJoin
```
```
Sort (fetch = 100) -> (projection) -> Join(join_type=Left) -> Sort (fetch = 100)
```
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Research direction
Start by reading DataFusion's optimizer rules for sort/fetch and join plans, then trace how join type, join filters, projections, and ordering are represented. Compare the proposed left- and right-join cases and identify existing tests for sort pushdown or TopK. Done means the eligible TopK is pushed below the join while the final sort remains available when ordering is not preserved, with coverage for the stated constraints.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100