Support spilling in `TopK` queries
- 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?
When running sort queries with large `LIMIT` and small memory limit, it can go out of memory
```
select *
from tbl
order by c1
limit 1000000000
```
It's possible to enable spilling capability inside `TopK` data structure to let such queries complete.
### Describe the solution you'd like
### Approach 1
Add back `fetch` field back to `ExternalSorter` to support external TopK queries, which is removed in https://github.com/apache/datafusion/pull/15525 (because it's unused now)
This approach can be slightly faster, but requires to add a configuration option to switch to `ExternalSorter` path for large `LIMIT`, instead of the default `TopK` path. (or let optimizer figure out when to switch automatically, though it's also tricky)
### Approach 2
Add spilling capability inside [TopK](https://github.com/apache/datafusion/blob/main/datafusion/physical-plan/src/topk/mod.rs) executor. When the memory limit is reached, it can fallback to out-of-core execution without introducing a new configuration.
### Describe alternatives you've considered
_No response_
### Additional context
The sort + limit query is usually run with a small `LIMIT` count, so it's mostly memory-efficient.
@alamb is referring to this issue as a sort of exploratory idea, so perhaps someone with real usage knows better how to get it implemented 🤔
Contributor guide
Research direction
Reproduce the ORDER BY c1 LIMIT 1000000000 query with a small memory limit, then read datafusion/physical-plan/src/topk/mod.rs and the ExternalSorter path. Compare adding spilling inside TopK with restoring ExternalSorter support; done means the query completes without an out-of-memory failure while preserving TopK behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- data-engineering, databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100