comphead opened a new issue, #26940: URL: https://github.com/apache/datafusion/issues/26940
### Describe the bug A multi-column sort under a memory limit can fail with `Failed to allocate additional ... for ExternalSorterMerge[N]` instead of spilling, when the sort keys make up most of each row. `ExternalSorter` reserves about twice each buffered batch: https://github.com/apache/datafusion/blob/49c67c296b9b43d98768fcd1592c6ee1bcde4dfb/datafusion/physical-plan/src/sorts/sort.rs#L1172-L1180 To spill, or to produce its output without spilling, it sorts each buffered batch into its own run and merges the runs: https://github.com/apache/datafusion/blob/49c67c296b9b43d98768fcd1592c6ee1bcde4dfb/datafusion/physical-plan/src/sorts/sort.rs#L732-L742 With more than one sort key, the merge uses `RowCursorStream`, which converts the keys of each run's current batch to the row format. Every run is a single batch, so the merge holds all sorted runs and all of their encoded keys at once. That is `(1 + k)` times the buffered bytes, where `k` is the size of the encoded keys over the size of the batch. https://github.com/apache/datafusion/blob/49c67c296b9b43d98768fcd1592c6ee1bcde4dfb/datafusion/physical-plan/src/sorts/stream.rs#L203-L227 The row format adds a null byte to each fixed-width value and keeps an 8-byte offset per row, so `k > 1` when the keys are most of the row: | Sort keys | Arrow bytes/row | Encoded keys bytes/row | Merge holds | |---|---|---|---| | 2 × Int64, no other columns | 16 | 26 | 2.6x | | 2 × nullable Int32, no other columns | 8.25 | 18 | 3.2x | | 85 nullable Int64 and 2 short strings, plus 3 other columns | 748 | 811 | 2.08x | Beyond the 2x, only `sort_spill_reservation_bytes` (10 MiB by default) is set aside for the merge. On a full pool the merge fails once `k - 1` times the buffered bytes exceeds that. For the third shape with 240 buffered 8192-row batches (1.4 GiB), a counting allocator showed the sorter reserving 1.99x the buffered bytes, and the merge then holding 2.08x until it finished. ### To Reproduce ```shell datafusion-cli -m 512M -c "SET datafusion.execution.target_partitions = 1" \ "EXPLAIN ANALYZE SELECT value % 1000003 AS a, value AS b FROM range(30000000) ORDER BY a, b" ``` On `main` (49c67c296): ``` Error: Failed to allocate additional 128.0 KB for ExternalSorterMerge[0] with 421.6 MB already allocated for this reservation - 11.2 KB remain available for the total memory pool: greedy(used: 512.0 MB, pool_size: 512.0 MB) ``` With the default number of partitions, the same query fails at both `-m 512M` and `-m 1G`, in `ExternalSorterMerge[N]` or in the `SortPreservingMergeExec` above it. Sorts that fit without spilling fail the same way in their final merge, when the buffered batches fit at 2 times their size but not at `1 + k` times. ### Expected behavior The sort spills and completes. ### Additional context - The shapes in #16979 (`sort-tpch` Q5: three keys and no other columns, fails at 100M but passes at 30M) and #14143 (two Int64 keys) match this. I have not rerun them. - #14748 proposes a reservation that accounts for the row format. #17163 implemented one from the first batch's ratio and was closed as stale. #25804 lists the related gap in the merge of spill files (finding 8). - Proposed fix: sort the runs that feed a row-format merge into smaller batches, for example `batch_size / 8` rows, so the merge holds the encoded keys of one small batch per run. The merge output keeps `batch_size`. A prototype passes the reproducer above, and lowers the peak heap while spilling the third shape from 2.08x to 1.28x the buffered bytes. It does not help input batches smaller than the chunk, which the coalescing in #26931 would address. ### Willingness to contribute I plan to contribute a fix for this bug independently -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
