-
Notifications
You must be signed in to change notification settings - Fork 1.7k
Description
Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Support Sorting "arbitrarily" large inputs (that don't fit in RAM or within some user defined budget)
This ticket concerns the memory potentially used the Sort operator -- it doesn't cover other potential targets (e.g. sort based aggregation, for example). That will be covered by other tasks tracked by #587
Describe the solution you'd like
- Allow DataFusion users to specify a RAM budget (aka via the config introduced in Initial MemoryManager and DiskManager APIs for query execution + External Sort implementation #1526) and have their queries complete running without the sort exceeding that budget.
- Make sure there is a single production ready implementation of
N-way Merge of Sorted Streamsto build on top of
For the Sort operator, I think the best behavior would be:
- Sort all the input in RAM (as is done today in
SortExec), if the memory budget allows - If all the input does not fit in the RAM budget, the in memory portion is sorted and written to temporary disk files
- Temporary disk files are read / merged to produce the final results
@yjshen 's PR #1526 has most of the individual pieces of this logic, but they aren't hooked up yet (that is if you run SELECT .. FROM foo ORDER BY x) it will still exhaust memory.
Some ideas of how to break this task down
- Consolidate the
SortExeccode (so there is only a single sort operator that does in memory sorting if it has enough memory budget but then spills to disk if needed). #1571 - SQL tests for when sorting exceeded available memory and had to spill to disk #1573
- Consolidate the N-way merging code and
SortPreservingMergeStream(which has quite good tests of what is often quite tricky code, and it will be performance critical) #1572 - Report
spill_countas well asspill_bytesin sort metrics #1611 - Research performance improvements in N-way merging #2148
- Optimize memory usage pattern to avoid "double memory" behavior #2149
- Research sort directly on raw bytes of composite sort keys for better performance #2150
- Research usage of row format for sort records buffering #2151
Describe alternatives you've considered
Use two implementations of Sort (one in memory and one that can spill). This would ensure no performance regressions for the non-spilling case but would require users to decide which one to use.
Context
This is follow on work from the great PR from @yjshen in #1526 and part of the story of limiting memory used by DataFusion #587