apache / apache/datafusion

Support spilling in `TopK` queries

Open
#15,538 1 comment 3 reactions 0 assignees View on GitHub
enhancement
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.