You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Re-sort file groups in FileScanConfig to satisfy ordering requirements #19724
FileScanConfig::try_pushdown_sort could support re-sorting or re-arranging the FileGroups themselves using min/max statistics to satisfy the queries preferred sort order.
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 Analysis to supportSortPreservingMerge --> ProgressiveEval #15191).
I think the proposal is more advanced than the issue #15191.
The previous discussion is doing things like:
Reorganize the file groups to make sure that each group files are ordered
To check if there is no overlap between partitions(file groups)
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.
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:
Start with unsorted groups and N partitions.
Optimizer knows there is an upstream Sort so it ideally wants to set up a ProgressiveEval type plan.
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.
@adriangb Let the optimizer decide how to re-arrange files/file groups, and decide whether parallel makes sense to me.
Some other thoughts:
Multi-round negotiation vs. the current single pushdown. Currently, try_pushdown_sort is a single invocation with a single return, we might change this.
ProgressiveEval doesn’t exist yet. We might need a separate PR to introduce this node in order to reduce the review burden.
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.
Activity
adriangb commentedon Jan 9, 2026
cc @alamb @zhuqi-lucas
alamb commentedon Jan 14, 2026
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
adriangb commentedon Feb 10, 2026
@xudong963 any thoughts you could share? I might take a crack at this.
xudong963 commentedon Feb 10, 2026
Sorry, missed the issue, checking
xudong963 commentedon Feb 10, 2026
I think the proposal is more advanced than the issue #15191.
The previous discussion is doing things like:
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.
adriangb commentedon Feb 10, 2026
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
FileSourceknowing 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:
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
InexactThe 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.
xudong963 commentedon Feb 10, 2026
@adriangb Let the optimizer decide how to re-arrange files/file groups, and decide whether parallel makes sense to me.
Some other thoughts:
adriangb commentedon Feb 10, 2026
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.
test: add SLT tests for sort pushdown with statistics-based file reor…
feat: sort file groups by statistics during sort pushdown
feat: sort file groups by statistics during sort pushdown
feat: sort file groups by statistics during sort pushdown
feat: sort file groups by statistics during sort pushdown
fix: validate inter-file ordering in eq_properties() (#20329)
fix: validate inter-file ordering in eq_properties() (apache#20329)
fix: validate inter-file ordering in eq_properties() (apache#20329)
fix: validate inter-file ordering in eq_properties() (apache#20329)
feat: sort file groups by statistics during sort pushdown
fix: validate inter-file ordering in eq_properties() (apache#20329)