apache / apache/datafusion

Push down TopK below Join

Closed
#11,900 1 comment 0 reactions 0 assignees View on GitHub
enhancement performance
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.