You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "zhuqi-lucas (via GitHub)" <gi...@apache.org> on 2026/04/05 07:51:07 UTC
[I] Parallel merge for SortPreservingMergeExec [datafusion]
zhuqi-lucas opened a new issue, #21381:
URL: https://github.com/apache/datafusion/issues/21381
**Is your feature request related to a problem or challenge?**
When `SortExec` is eliminated via sort pushdown (statistics-based file reordering), `SortPreservingMergeExec` reads directly from I/O-bound sources instead of from `SortExec`'s in-memory buffer. Currently SPM does a single K-way merge of all input streams, which can become a bottleneck when there are many partitions.
**Describe the solution you'd like**
Implement parallel merge for `SortPreservingMergeExec`: split the N input streams into groups, merge each group in parallel, then merge the intermediate results. This creates a tree of merges instead of a single flat K-way merge.
For example, with 8 input streams:
```
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 merge computation itself becomes a bottleneck
**Additional context**
Suggested by @Dandandan in https://github.com/apache/datafusion/pull/21182#discussion_r3036542606:
> Also slightly looking forward: I think we could benefit from _parallel merge_ (e.g. finding some split in the n streams and merging in parallel) in these situations where sorting becomes mostly about merging.
Related: DuckDB implements a similar [parallel merge sort](https://duckdb.org/2021/08/27/external-sorting.html) strategy.
Parent issue: https://github.com/apache/datafusion/issues/17348
--
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: github-unsubscribe@datafusion.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge for SortPreservingMergeExec [datafusion]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4190420957
Thanks @2010YOUY01 for the context! This issue is specifically about the case after SortExec is eliminated via sort pushdown (#21182). When sort elimination removes SortExec entirely, there is no Stage 1 merge. SPM becomes the only merge operator, reading directly from I/O-bound DataSourceExec partitions.
In that scenario, a parallel merge within SPM itself (splitting N input streams into groups and merging in parallel) could help. The DuckDB parallel k-way merge link is great — thanks for sharing!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge for SortPreservingMergeExec [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4190351686
> When `SortExec` is eliminated via sort pushdown (statistics-based file reordering), `SortPreservingMergeExec` reads directly from I/O-bound sources instead of from `SortExec`'s in-memory buffer. Currently SPM does a single K-way merge of all input streams, which can become a bottleneck when there are many partitions.
The current implementation already forms a tree of SPMs similar to what you have described, so there shouldn’t be a major bottleneck I think, though there may still be room for improvement.
Currently, there are two stages of SPM:
- Stage 1: `SortExec` output, where the merge degree equals the number of in-memory batches
- Stage 2: Final `SortPreservingMergeExec`, where the merge degree equals the number of partitions
Stage 1 is non-blocking, so the two SPM stages can run in parallel. The main optimization opportunity seems to be balancing the merge degrees across the two stages to avoid one becoming a bottleneck. For example, if `SortExec` performs a 4-way merge while Stage 2 performs a 32-way merge, Stage 2 is likely to be the bottleneck. This could potentially be improved with a more recursive merging scheme.
> Related: DuckDB implements a similar [parallel merge sort](https://duckdb.org/2021/08/27/external-sorting.html) strategy.
They have a more recent version with a parallel k-way merge algorithm: https://duckdb.org/2025/09/24/sorting-again#k-way-merge-path
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge in SortPreservingMergeExec after sort elimination [datafusion]
Posted by "2010YOUY01 (via GitHub)" <gi...@apache.org>.
2010YOUY01 commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4196015885
> Thanks [@2010YOUY01](https://github.com/2010YOUY01) for the context! This issue is specifically about the case after SortExec is eliminated via sort pushdown ([#21182](https://github.com/apache/datafusion/pull/21182)). When sort elimination removes SortExec entirely, there is no Stage 1 merge. SPM becomes the only merge operator, reading directly from I/O-bound DataSourceExec partitions.
>
> I've updated the issue description to clarify in case any misunderstanding.
>
> In that scenario, a parallel merge within SPM itself (splitting N input streams into groups and merging in parallel) could help. The DuckDB parallel k-way merge link is great — thanks for sharing!
Ah, I see — that's a good optimization opportunity.
Would you mind if I work on this, if you haven’t started on it yet? I’ve been thinking about improving the merge strategy similarly.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge in SortPreservingMergeExec after sort elimination [datafusion]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4196136668
> > Thanks [@2010YOUY01](https://github.com/2010YOUY01) for the context! This issue is specifically about the case after SortExec is eliminated via sort pushdown ([#21182](https://github.com/apache/datafusion/pull/21182)). When sort elimination removes SortExec entirely, there is no Stage 1 merge. SPM becomes the only merge operator, reading directly from I/O-bound DataSourceExec partitions.
> > I've updated the issue description to clarify in case any misunderstanding.
> > In that scenario, a parallel merge within SPM itself (splitting N input streams into groups and merging in parallel) could help. The DuckDB parallel k-way merge link is great — thanks for sharing!
>
> Ah, I see — that's a good optimization opportunity.
>
> Would you mind if I work on this, if you haven’t started on it yet? I’ve been thinking about improving the merge strategy similarly.
Sure @2010YOUY01 , feel free to take it.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge in SortPreservingMergeExec after sort elimination [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-5455983191
@2010YOUY01 are you still working on this?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge in SortPreservingMergeExec after sort elimination [datafusion]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4190427355
Thanks for the context! I think there might be a slight misunderstanding — I've updated the issue description to clarify. This is specifically about the case **after SortExec is eliminated** via sort pushdown (#21182). When sort elimination removes SortExec entirely, there is no Stage 1 merge. SPM becomes the only merge operator, reading directly from I/O-bound DataSourceExec partitions.
In that scenario, a parallel merge within SPM itself (splitting N input streams into groups and merging in parallel) could help reduce I/O stalls. The DuckDB parallel k-way merge link is great — thanks for sharing!
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [I] Parallel merge in SortPreservingMergeExec after sort elimination [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #21381:
URL: https://github.com/apache/datafusion/issues/21381#issuecomment-4191094936
My comment was about the final `SortPreservingMergeExec` stage indeed, not the internal merging of batches within `SortExec`.
I think both cases (full sort and merge-only) might benefit from more parallelism in the final stage, but in cases SPM is the only stage there might be substantial more benefit, probably less buffering will be necessary to introduce enough parallelism in the inner streams.
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org