cockroachdb / cockroachdb/cockroach
opt: omit lookup join in inverted index lookup when filter is tight
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Consider the table and query below:
```sql
CREATE TABLE t (
id INT PRIMARY KEY,
a UUID[],
INVERTED INDEX t_a_idx (a)
);
EXPLAIN (OPT, VERBOSE)
WITH input(e) AS (
VALUES
('490c7718-f347-44d6-812a-bf2f5714feaf'::UUID),
('45bf2d33-8a46-4bdb-b852-fe0411e58593'::UUID)
)
SELECT input.e, count(id)
FROM input
INNER INVERTED JOIN t@t_a_idx
ON a @> ARRAY[input.e]
GROUP BY input.e;
```
The query plan looks like:
```
group-by (hash)
├── columns: e:2 count:8
├── grouping columns: e:2
├── immutable
├── stats: [rows=2, distinct(2)=2, null(2)=0]
├── cost: 230.93
├── key: (2)
├── fd: (2)-->(8)
├── distribution: us-east1
├── prune: (8)
├── inner-join (lookup t)
│ ├── columns: e:2 a:4
│ ├── key columns: [10] = [3]
│ ├── lookup columns are key
│ ├── immutable
│ ├── stats: [rows=666.6667, distinct(2)=2, null(2)=0]
│ ├── cost: 210.88
│ ├── distribution: us-east1
│ ├── inner-join (inverted t@t_a_idx)
│ │ ├── columns: e:2 id:10
│ │ ├── flags: force inverted join (into right side)
│ │ ├── inverted-expr
│ │ │ └── a:11 @> ARRAY[e:2]
│ │ ├── stats: [rows=20, distinct(2)=1.99991, null(2)=0, distinct(10)=19.9, null(10)=0]
│ │ ├── cost: 85.45
│ │ ├── distribution: us-east1
│ │ ├── values
│ │ │ ├── columns: e:2
│ │ │ ├── cardinality: [2 - 2]
│ │ │ ├── stats: [rows=2, distinct(2)=2, null(2)=0]
│ │ │ ├── cost: 0.03
│ │ │ ├── distribution: us-east1
│ │ │ ├── prune: (2)
│ │ │ ├── ('490c7718-f347-44d6-812a-bf2f5714feaf',)
│ │ │ └── ('45bf2d33-8a46-4bdb-b852-fe0411e58593',)
│ │ └── filters (true)
│ └── filters
│ └── a:4 @> ARRAY[e:2] [outer=(2,4), immutable]
└── aggregations
└── count-rows [as=count:8]
```
The lookup join applied after the inverted join is used to fetch the full value of column `a` so that the `a:4 @> ARRAY[e:2]` filter can be applied. I believe the filter is unnecessary because the `ARRAY` on the RHS contains a single element, so the inverted join should be "tight". If the optimizer can recognize this tight-ness, the lookup join can be eliminated, speeding up this query.
Jira issue: CRDB-32854
Contributor guide
Research direction
Reproduce the supplied CREATE TABLE and query, then inspect the EXPLAIN (OPT, VERBOSE) plan, focusing on the inverted join and the lookup join that fetches column a. Done means the optimizer recognizes the tight single-element ARRAY case, omits the unnecessary lookup join, and preserves the query's results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases, performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100