Skip to content

sql/opt: use maximally selective constant filter for lookup joins#64509

Merged
craig[bot] merged 1 commit intocockroachdb:masterfrom
nvb:nvanbenschoten/optComputerCol
May 3, 2021
Merged

sql/opt: use maximally selective constant filter for lookup joins#64509
craig[bot] merged 1 commit intocockroachdb:masterfrom
nvb:nvanbenschoten/optComputerCol

Conversation

@nvb
Copy link
Copy Markdown
Contributor

@nvb nvb commented May 1, 2021

Fixes #63735.

This commit addresses #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 #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:

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:

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:

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:

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.

@nvb nvb requested review from a team, mgartner and rytaft May 1, 2021 17:08
@cockroach-teamcity
Copy link
Copy Markdown
Member

This change is Reviewable

@nvb nvb force-pushed the nvanbenschoten/optComputerCol branch from 8a2f1c2 to 646f741 Compare May 1, 2021 17:11
Copy link
Copy Markdown
Collaborator

@rytaft rytaft left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

:lgtm: Thanks!!

Reviewed 2 of 2 files at r1.
Reviewable status: :shipit: 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.
@nvb nvb force-pushed the nvanbenschoten/optComputerCol branch from 646f741 to 41fa0d5 Compare May 3, 2021 19:45
Copy link
Copy Markdown
Contributor Author

@nvb nvb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TFTR! How do you feel about backporting this to v21.1.1?

bors r=rytaft

Reviewable status: :shipit: 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.

@rytaft
Copy link
Copy Markdown
Collaborator

rytaft commented May 3, 2021

I do think we should backport to v21.1.1 - thanks!

@craig
Copy link
Copy Markdown
Contributor

craig bot commented May 3, 2021

Build succeeded:

@craig craig bot merged commit dab7c8b into cockroachdb:master May 3, 2021
@mgartner
Copy link
Copy Markdown
Contributor

mgartner commented May 5, 2021

Very cool! Thanks again for finding and fixing this!

@nvb nvb deleted the nvanbenschoten/optComputerCol branch May 5, 2021 03:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

opt: computed columns not derived when pushed through lookup join

4 participants