opt: take advantage of index ordering for lookup joins #84685
Assignees
Labels
C-enhancement
Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception)
T-sql-queries
SQL Queries Team
Comments
DrewKimball
added
the
C-enhancement
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 20, 2022
It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Fixes cockroachdb#84685 Release note: None
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 20, 2022
It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Fixes cockroachdb#84685 Release note: None
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 21, 2022
It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Due to implementation details of the lookup join, order can only be preserved when none of the index columns involved in the ordering are sorted in descending order. Fixes cockroachdb#84685 Release note (performance improvement): The optimizer can now return the results of a join in sorted order in more cases. This can allow the optimizer to avoid expensive sorts that need to buffer all input rows.
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 21, 2022
It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Due to implementation details of the lookup join, order can only be preserved when none of the index columns involved in the ordering are sorted in descending order. Fixes cockroachdb#84685 Release note (performance improvement): The optimizer can now return the results of a join in sorted order in more cases. This can allow the optimizer to avoid expensive sorts that need to buffer all input rows.
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 21, 2022
It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Due to implementation details of the lookup join, order can only be preserved when none of the index columns involved in the ordering are sorted in descending order. Fixes cockroachdb#84685 Release note (performance improvement): The optimizer can now return the results of a join in sorted order in more cases. This can allow the optimizer to avoid expensive sorts that need to buffer all input rows.
craig bot
pushed a commit
that referenced
this issue
Jul 22, 2022
84689: opt: allow lookup joins to order on index columns r=DrewKimball a=DrewKimball It is possible for lookup joins to return the results of each lookup in the order of the lookup index. In the case when the input is ordered on a key, preserving the input ordering and then returning looked-up rows in index order is equivalent to performing a sort on the input ordering with the index columns appended. This patch teaches the optimizer that lookup joins can preserve the index ordering. This allows the optimizer to avoid sorting in some cases, which can significantly improve performance because sorts have to buffer all input rows. Fixes #84685 Release note: None 84920: sql: skip TestInformationSchemaMySQL r=wenyihu6 a=wenyihu6 Refs: #84915 Reason: There is a mismatch between MySQL version and CRDB in `pg_metadata_test.go`. More details in the issue above. Generated by bin/skip-test. Release justification: non-production code changes Release note: None 84930: roachprod: fix grafana-start permission issue r=irfansharif a=irfansharif Recent regression from #84670. Was seeing the following: chmod: cannot access '/etc/grafana/provisioning/dashboards/cockroach.yaml': No such file or directory chmod: cannot access '/etc/grafana/provisioning/datasources/prometheus.yaml': No such file or directory Release note: None Co-authored-by: DrewKimball <[email protected]> Co-authored-by: wenyihu3 <[email protected]> Co-authored-by: irfan sharif <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Is your feature request related to a problem? Please describe.
When the streamer is in
InOrderModeor the old code path hasMaintainOrderingset and parallelism disabled, lookup results for each input row are returned in the order of the lookup index. However, the optimizer does not know this, and only passes through input orderings for lookup joins. This leads to unnecessary sorting, which can have a drastic impact on performance because sort operators have to buffer all input rows (no pipelining).Describe the solution you'd like
We should teach the optimizer that lookup joins can provide orderings that include index columns. This will allow us to avoid sorting in more cases.
Jira issue: CRDB-17796
The text was updated successfully, but these errors were encountered: