Entire input is resorted when the data is partially sorted (not using `PartialSortExec`)
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Describe the bug
When data is sorted on a prefix, but not all, of the input columns I expect DataFusion to use the faster / more memory efficient operator `PartialSortExec`: https://github.com/apache/datafusion/blob/07516aa4a369aceb2ef2438fa81e5a87691f76a6/datafusion/physical-plan/src/sorts/partial_sort.rs#L80
However, this does not appear to be happening
### To Reproduce
```
> copy (values(1, 'a'), (2,'b'), (3,'d'), (4,'a')) to '/tmp/order.csv';
+-------+
| count |
+-------+
| 4 |
+-------+
1 row(s) fetched.
Elapsed 0.005 seconds.
> create external table order stored as csv location '/tmp/order.csv' with order (column1 asc);
0 row(s) fetched.
Elapsed 0.002 seconds.
```
When ordering by just `column1` (which is the declared table order) we can see the plan correctly avoids sorting π
```sql
> explain select * from order ORDER BY column1;
+---------------+-------------------------------+
| plan_type | plan |
+---------------+-------------------------------+
| physical_plan | βββββββββββββββββββββββββββββ |
| | β DataSourceExec β |
| | β -------------------- β |
| | β files: 1 β |
| | β format: csv β |
| | βββββββββββββββββββββββββββββ |
| | |
+---------------+-------------------------------+
1 row(s) fetched.
Elapsed 0.009 seconds.
```
However, when ordering by `column1, column2` (the table is a prefix of the declared table order) we can see the plan uses a SortExec (which resorts the entire input, rather than just sorting within batches):
```sql
> explain select * from order ORDER BY column1, column2;
+---------------+-------------------------------+
| plan_type | plan |
+---------------+-------------------------------+
| physical_plan | βββββββββββββββββββββββββββββ |
| | β SortExec β |
| | β -------------------- β |
| | β column1@0 ASC NULLS LAST, β |
| | β column2@1 ASC NULLS LAST β |
| | βββββββββββββββ¬ββββββββββββββ |
| | βββββββββββββββ΄ββββββββββββββ |
| | β DataSourceExec β |
| | β -------------------- β |
| | β files: 1 β |
| | β format: csv β |
| | βββββββββββββββββββββββββββββ |
| | |
+---------------+-------------------------------+
```
### Expected behavior
I expect the existing sort order to be used
Specifically, in the query above I expect that `PartialSortExec` is used instead:
```sql
> explain select * from order ORDER BY column1, column2;
```
### Additional context
_No response_
Contributor guide
Assessment
This issue has not been assessed yet.