Parallel merge in SortPreservingMergeExec after sort elimination
- 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 `SortExec` is eliminated via sort pushdown (#21182, statistics-based file reordering), `SortPreservingMergeExec` becomes the only merge operator, reading directly from I/O-bound `DataSourceExec` partitions instead of from `SortExec`'s in-memory buffer.
Currently we insert a `BufferExec` to compensate, but with many partitions the single-threaded K-way merge in SPM can still become a bottleneck — it alternates between partitions, and each partition switch may stall on I/O even with buffering.
**Describe the solution you'd like**
When SPM reads from I/O-bound sources (no buffering SortExec), split the N input streams into groups and merge each group in parallel, then merge the intermediate results. This creates a tree of merges:
```
Level 1 (parallel): merge(s1,s2), merge(s3,s4), merge(s5,s6), merge(s7,s8)
Level 2 (parallel): merge(m1,m2), merge(m3,m4)
Level 3: merge(m5,m6) → final output
```
This would be especially beneficial when:
- Sort elimination removes the buffering `SortExec`, making SPM I/O-bound
- Many partitions with I/O-bound sources
- Large datasets where single-threaded merge becomes the bottleneck
**Additional context**
Suggested by @Dandandan in https://github.com/apache/datafusion/pull/21182#discussion_r3036542606
Related: DuckDB's [parallel k-way merge](https://duckdb.org/2025/09/24/sorting-again#k-way-merge-path)
Parent issue: https://github.com/apache/datafusion/issues/17348
Contributor guide
Assessment
This issue has not been assessed yet.