Unneccessary sort operation when merge output is already known to be sorted.
- Dominant language
- Go
- Stars
- 24.4k
- Forks
- 873
- Avg merge
- 1d 8h
- Merged PRs (30d)
- 120
Description
Example:
```
create table onepk(pk int primary key, c0 int);
create table onepk2 like onepk;
analyze table onepk update histogram on (pk) using data '{"row_count": 1000}';
analyze table onepk2 update histogram on (pk) using data '{"row_count": 1000}';
describe plan select onepk.c0 from onepk join onepk2 using (pk) order by pk;
```
Observed output:
```
+-----------------------------------------+
| plan |
+-----------------------------------------+
| Project |
| ├─ columns: [onepk.c0] |
| └─ Sort(onepk.pk ASC) |
| └─ MergeJoin |
| ├─ cmp: (onepk.pk = onepk2.pk) |
| ├─ IndexedTableAccess(onepk) |
| │ ├─ index: [onepk.pk] |
| │ ├─ filters: [{[NULL, ∞)}] |
| │ └─ columns: [pk c0] |
| └─ IndexedTableAccess(onepk2) |
| ├─ index: [onepk2.pk] |
| ├─ filters: [{[NULL, ∞)}] |
| └─ columns: [pk] |
+-----------------------------------------+
```
Expected output: the Sort node is extraneous and can be removed: the merge join is guaranteed to produce outputs in the same order as the chosen indexes. Including a sort operation can significantly slow down execution if there's also a `LIMIT` clause, since all results must be pulled in order to sort them.
Solution: if the sort order is a prefix of either of the indexes used in the merge join, it should be safe to remove.
We should make sure we also handle the case of `ORDER BY pk DESC` by reversing both indexes used in the merge join.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.