sql/opt: use maximally selective constant filter for lookup joins#64509
Merged
craig[bot] merged 1 commit intocockroachdb:masterfrom May 3, 2021
Merged
sql/opt: use maximally selective constant filter for lookup joins#64509craig[bot] merged 1 commit intocockroachdb:masterfrom
craig[bot] merged 1 commit intocockroachdb:masterfrom
Conversation
Member
8a2f1c2 to
646f741
Compare
rytaft
approved these changes
May 3, 2021
Collaborator
rytaft
left a comment
There was a problem hiding this comment.
Reviewed 2 of 2 files at r1.
Reviewable status:complete! 1 of 0 LGTMs obtained (waiting on @mgartner and @nvanbenschoten)
pkg/sql/opt/xform/join_funcs.go, line 911 at r1 (raw file):
// constraining the given column to a constant value or a set of constant // values. If successful, the constant values and the index of the constraining // FiltersItem are returned. If multiple filters are equivalent, the one that
nit: I'd say, "if multiple filters match"
Fixes cockroachdb#63735. This commit addresses cockroachdb#63735 by reworking how constant filters are selected when being applied to lookup joins. findJoinFilterConstants is adjusted to return the filter that minimizes the number of returned values, instead of returning the first matching filter that it finds. This affects lookup joins which have constant filters due to both CHECK constraints and computed column constraints, as we saw in cockroachdb#63735. This has an effect on both standard and inverted lookup joins, as the new test cases demonstrate. For standard lookup joins, a plan which used to look like: ```sql SELECT * FROM small INNER LOOKUP JOIN t63735 ON n = y WHERE m = 5 AND n = 15 ---- inner-join (lookup t63735) ├── flags: force lookup join (into right side) ├── lookup columns are key ├── inner-join (cross) │ ├── values │ │ ├── (10,) │ │ ├── (20,) │ │ └── (30,) │ ├── select │ │ ├── scan small │ │ └── filters │ │ ├── n = 15 │ │ └── m = 5 │ └── filters (true) └── filters └── y = 15 ``` now looks like: ```sql inner-join (lookup t63735) ├── flags: force lookup join (into right side) ├── lookup columns are key ├── project │ ├── select │ │ ├── scan small │ │ └── filters │ │ ├── n = 15 │ │ └── m = 5 │ └── projections │ └── 30 └── filters └── y = 15 ``` For inverted lookup joins, a plan which used to look like: ```sql SELECT * FROM t63735_a AS a INNER INVERTED JOIN t63735_b AS b ON a.k = 15 AND b.j @> a.j AND b.y = a.k ---- inner-join (lookup t63735_b [as=b]) ├── lookup columns are key ├── inner-join (inverted t63735_b@secondary [as=b]) │ ├── flags: force inverted join (into right side) │ ├── inverted-expr │ │ └── b.j @> a.j │ ├── inner-join (cross) │ │ ├── values │ │ │ ├── (10,) │ │ │ ├── (20,) │ │ │ └── (30,) │ │ ├── scan t63735_a [as=a] │ │ │ └── constraint: /1: [/15 - /15] │ │ └── filters (true) │ └── filters │ └── y = 15 └── filters └── b.j @> a.j ``` now looks like: ```sql inner-join (lookup t63735_b [as=b]) ├── lookup columns are key ├── inner-join (inverted t63735_b@secondary [as=b]) │ ├── flags: force inverted join (into right side) │ ├── inverted-expr │ │ └── b.j @> a.j │ ├── project │ │ ├── scan t63735_a [as=a] │ │ │ └── constraint: /1: [/15 - /15] │ │ └── projections │ │ └── 30 │ └── filters │ └── y = 15 └── filters └── b.j @> a.j ``` Release note (sql change): Lookup joins on indexes with computed columns which are also either constrained by CHECK constraints or use an ENUM data type may now choose a more optimal plan.
646f741 to
41fa0d5
Compare
nvb
commented
May 3, 2021
Contributor
Author
nvb
left a comment
There was a problem hiding this comment.
TFTR! How do you feel about backporting this to v21.1.1?
bors r=rytaft
Reviewable status:
complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @mgartner and @rytaft)
pkg/sql/opt/xform/join_funcs.go, line 911 at r1 (raw file):
Previously, rytaft (Rebecca Taft) wrote…
nit: I'd say, "if multiple filters match"
Done.
Collaborator
|
I do think we should backport to v21.1.1 - thanks! |
Contributor
|
Build succeeded: |
Contributor
|
Very cool! Thanks again for finding and fixing this! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #63735.
This commit addresses #63735 by reworking how constant filters are selected when being applied to lookup joins.
findJoinFilterConstantsis adjusted to return the filter that minimizes the number of returned values, instead of returning the first matching filter that it finds. This affects lookup joins which have constant filters due to both CHECK constraints and computed column constraints, as we saw in #63735.This has an effect on both standard and inverted lookup joins, as the new test cases demonstrate. For standard lookup joins, a plan which used to look like:
now looks like:
For inverted lookup joins, a plan which used to look like:
now looks like:
Release note (sql change): Lookup joins on indexes with computed columns which are also either constrained by CHECK constraints or use an ENUM data type may now choose a more optimal plan.