dolthub / dolthub/dolt

Unneccessary sort operation when merge output is already known to be sorted.

Open
#8,728 1 comment 0 reactions 1 assignee Claimed by @jycor View on GitHub
analyzer performance sql
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.