cockroachdb / cockroachdb/cockroach

opt: omit lookup join in inverted index lookup when filter is tight

Open
#113,293 0 comments 0 reactions 0 assignees View on GitHub
C-enhancement T-sql-queries
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.