apache / apache/datafusion

Entire input is resorted when the data is partially sorted (not using `PartialSortExec`)

Open
#16,899 2 comments 1 reaction 1 assignee Claimed by @EeshanBembi View on GitHub
bug performance
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

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.