Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Avoid sorts for descending ORDER BY on lookup join index columns #88319

Closed
msirek opened this issue Sep 21, 2022 · 5 comments · Fixed by #93673
Closed

Avoid sorts for descending ORDER BY on lookup join index columns #88319

msirek opened this issue Sep 21, 2022 · 5 comments · Fixed by #93673
Assignees
Labels
C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception) O-qa T-sql-queries SQL Queries Team

Comments

@msirek
Copy link
Contributor

msirek commented Sep 21, 2022

Is your feature request related to a problem? Please describe.
#84689 improves the number of cases a sort is avoided for lookup join queries with ORDER BY on the lookup index columns, but does not handle descending index columns

Example:

CREATE TABLE xyz (x INT, y INT, z INT, PRIMARY KEY(x, y, z));
CREATE TABLE uvw (u INT, v INT, w INT, PRIMARY KEY(u, v, w));

The following avoids a sort:

SELECT * FROM xyz INNER LOOKUP JOIN uvw ON x = u AND y = v ORDER BY x, y, z, u, v, w;

But if the PK of table uvw is (u, v, w DESC) and we have ORDER BY x, y, z, u, v, w DESC; This should avoid a sort.
A reverse scan is not required so I believe lookup join should be able to support it.

Describe alternatives you've considered
None

Jira issue: CRDB-19769

@msirek msirek added C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception) T-sql-queries SQL Queries Team labels Sep 21, 2022
@exalate-issue-sync exalate-issue-sync bot assigned dasrirez and unassigned dasrirez Sep 21, 2022
@DrewKimball

This comment was marked as outdated.

@DrewKimball

This comment was marked as outdated.

@msirek msirek changed the title Avoid sorts in more cases of ORDER BY on lookup join index columns Avoid sorts for descending ORDER BY on lookup join index columns Sep 21, 2022
@msirek

This comment was marked as outdated.

@DrewKimball

This comment was marked as outdated.

@DrewKimball
Copy link
Collaborator

In order to make this happen, the joinreader will need to be able to issue reverse scan requests. We'll also have to change the streamer codepath to make sure the scan iteration in Enqueue respects the index ordering, at least when the ordering has to be preserved. Assuming the non-streamer codepath is still around whenever we get around to this, that will have to be changed as well.

@msirek msirek added the O-qa label Sep 27, 2022
@DrewKimball DrewKimball self-assigned this Dec 15, 2022
DrewKimball added a commit to DrewKimball/cockroach that referenced this issue Dec 15, 2022
This patch fixes an oversight of cockroachdb#84689 that prevented lookup joins
from maintaining the index ordering for each lookup if the index ordering
contained descending columns. The execution logic will respect descending
index columns as-is, so only the optimizer code needed to be changed.
This will allow plans with lookup joins to avoid sorts in more cases.

Fixes cockroachdb#88319

Release note (performance improvement): The optimizer can now avoid
planning a sort in more cases with joins that perform lookups into an
index with one or more columns sorted in descending order. This can
significantly decrease the number of rows that have to be scanned in
order to satisfy a `LIMIT` clause.
craig bot pushed a commit that referenced this issue Dec 16, 2022
93483: sql: introduce hash group-join operator r=yuzefovich a=yuzefovich

This PR introduces the hash group-join operator (which combines a hash join followed by a hash aggregation when the join's equality columns are the same as aggregation's grouping columns into a single operator) to the execution engines . The optimizer is currently unaware of this new operator - the changes are plumbed only from the DistSQL physical planning. Naive implementations (which simply use a hash joiner followed by a hash aggregator) are introduced to both engines with the proper disk-spilling. The usage of this new operator is gated behind an experimental session variable.

See each commit for details.

Addresses: #38307.

Epic: None

93513: sql: add voting_replicas, non_voting_replicas columns to SHOW RANGES r=arulajmani a=ecwall

Fixes #93508

Some of the multitenant admin functions accept VOTERS, NONVOTERS as input.

Add voting_replicas, non_voting_replicas columns to SHOW RANGE(S) to make working with the admin functions easier.

Release note (sql change): Add voting_replicas, non_voting_replicas columns to output of SHOW RANGE(S) statements.

93673: opt: allow lookup joins to preserve index ordering with DESC columns r=DrewKimball a=DrewKimball

This patch fixes an oversight of #84689 that prevented lookup joins from maintaining the index ordering for each lookup if the index ordering contained descending columns. The execution logic will respect descending index columns as-is, so only the optimizer code needed to be changed. This will allow plans with lookup joins to avoid sorts in more cases.

Fixes #88319

Release note (performance improvement): The optimizer can now avoid planning a sort in more cases with joins that perform lookups into an index with one or more columns sorted in descending order. This can significantly decrease the number of rows that have to be scanned in order to satisfy a `LIMIT` clause.

Co-authored-by: Yahor Yuzefovich <[email protected]>
Co-authored-by: Evan Wall <[email protected]>
Co-authored-by: Drew Kimball <[email protected]>
@craig craig bot closed this as completed in 5615482 Dec 16, 2022
blathers-crl bot pushed a commit that referenced this issue Dec 16, 2022
This patch fixes an oversight of #84689 that prevented lookup joins
from maintaining the index ordering for each lookup if the index ordering
contained descending columns. The execution logic will respect descending
index columns as-is, so only the optimizer code needed to be changed.
This will allow plans with lookup joins to avoid sorts in more cases.

Fixes #88319

Release note (performance improvement): The optimizer can now avoid
planning a sort in more cases with joins that perform lookups into an
index with one or more columns sorted in descending order. This can
significantly decrease the number of rows that have to be scanned in
order to satisfy a `LIMIT` clause.
@mgartner mgartner moved this to Done in SQL Queries Jul 24, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-enhancement Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception) O-qa T-sql-queries SQL Queries Team
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

3 participants