You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "adriangb (via GitHub)" <gi...@apache.org> on 2026/01/09 22:39:03 UTC
[I] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
adriangb opened a new issue, #19724:
URL: https://github.com/apache/datafusion/issues/19724
`FileScanConfig::try_pushdown_sort` could support re-sorting or re-arranging the `FileGroup`s themselves using min/max statistics to satisfy the queries preferred sort order.
This is described in section 5.3 of [Pruning in Snowflake: Working Smarter, Not Harder](https://arxiv.org/pdf/2504.11540).
Some considerations are:
- If we start re-building groups what should the parallelism be? One the one hand it would make sense to try to match the original parallelism, on the other hand that may not be possible (e.g. if we can only satisfy the sort ordering by making groups `[[f1, f2, f3], [f4]]` maybe it's worth it to have lopsided groups, less or more groups) or even optimal (in a TopK query reduced parallelism can lead to faster queries if we end up only scanning 1 group or even 1 file; all of the work opening the others is wasted effort; this is also known as `ProgressiveEval` and discussed in https://github.com/apache/datafusion/issues/15191).
-
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3730818561
cc @alamb @zhuqi-lucas
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3874811409
@xudong963 any thoughts you could share? I might take a crack at 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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3877020020
Sorry, missed the issue, checking
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3751811861
This sounds like a good idea
I vaguely remember @xudong963 had some notion about how to do this too
As you point out, if we want to actually preserve the ordering it will likely reduce the available parallelism
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3878010169
> Multi-round negotiation vs. the current single pushdown. Currently, try_pushdown_sort is a single invocation with a single return, we might change this.
My thought was that we might be able to do this without changing the APIs: the optimizer can try a plan and discard it and try something else. All of the APIs return new subtrees / all nodes are copied, not modified in place. So the optimizer can try multiple different setups.
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3877254521
I think the proposal is more advanced than the issue https://github.com/apache/datafusion/issues/15191.
The previous discussion is doing things like:
1. Reorganize the file groups to make sure that each group files are ordered
2. To check if there is no overlap between partitions(file groups)
3. Leverage the ProgressiveEval to optimize SortPreservingMergeExec to avoid merging non-overlapping partitions
IIUC, the issue is proposing to re-arrange files across file groups, then resplit the files into file groups with the ordering.
I have some issues:
a) If files are overlapped aggressively, how to process?
b) The decrease in parallelism is something that needs careful consideration, since query requests are quite diverse, not only topk.
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "adriangb (via GitHub)" <gi...@apache.org>.
adriangb commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3877524429
> I have some issues:
>
> a) If files are overlapped aggressively, how to process?
> b) The decrease in parallelism is something that needs careful consideration, since query requests are quite diverse, not only topk.
I think those are great questions.
Part of the issue is that even for slightly overlapping files there's benefit, so there's no black or white.
I'm not sure what heuristic to use or how to approach it.
One thought was that we'll need a combination of the `FileSource` knowing how to re-arrange files to satisfy a sort order + requested partitions *and* an optimizer rule with a global view of the query.
For example:
1. Start with unsorted groups and N partitions.
2. Optimizer knows there is an upstream Sort so it ideally wants to set up a ProgressiveEval type plan.
3. Optimizer pushes down 2 partitions + required sort order.
a. If scan can produce 2 non-overlapping groups it does so and sets it's output ordering to `Exact`.
The optimizer picks up on this and sets up a ProgressiveEval type plan (or even just a plan with the Sort with lower parallelism since parallelism would not be helpful)
b. If the scan cannot produce 2 non-overlapping groups it produces best effort sorted groups and sets it's ordering to `Inexact`
The optimizer may decide to keep this setup e.g. because there is a TopK and it's still a better plan to run with lower parallelism.
The optimizer may also decide that it would rather have 3 (or N) partitions w/ best effort sorting. In this case it discards the 2 partition + sort order plan and tries to push down a new request for N partitions w/ the sort order.
So basically: an optimizer decides what sort of plan it wants and pushes down partitioning + sort order requirements into the scan and depending on what the scan can support decides what the final plan should be.
--
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] Re-sort file groups in FileScanConfig to satisfy ordering requirements [datafusion]
Posted by "xudong963 (via GitHub)" <gi...@apache.org>.
xudong963 commented on issue #19724:
URL: https://github.com/apache/datafusion/issues/19724#issuecomment-3877979685
@adriangb Let the optimizer decide how to re-arrange files/file groups, and decide whether parallel makes sense to me.
Some other thoughts:
1. Multi-round negotiation vs. the current single pushdown. Currently, try_pushdown_sort is a single invocation with a single return, we might change this.
2. ProgressiveEval doesn’t exist yet. We might need a separate PR to introduce this node in order to reduce the review burden.
3.
--
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