apache / apache/datafusion

Parallel merge in SortPreservingMergeExec after sort elimination

Open
#21,381 6 comments 5 reactions 1 assignee Claimed by @2010YOUY01 View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.