cockroachdb / cockroachdb/cockroach

opt: indexes on virtual computed columns cannot provide ordering

Open
#98,681 3 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

The optimizer does not explore index scans over indexes on virtual computed columns to provide an ordering.

Example:

```
exec-ddl
CREATE TABLE t (
k INT PRIMARY KEY,
j JSON,
v STRING AS (j->>'name') VIRTUAL,
s STRING AS (j->>'name') STORED,
INDEX (v),
INDEX (s)
)
----

opt
SELECT k FROM t ORDER BY s
----
scan t@t_s_idx
├── columns: k:1!null [hidden: s:4]
├── key: (1)
├── fd: (1)-->(4)
└── ordering: +4

opt
SELECT k FROM t ORDER BY v
----
sort
├── columns: k:1!null [hidden: v:3]
├── immutable
├── key: (1)
├── fd: (1)-->(3)
├── ordering: +3
└── project
├── columns: v:3 k:1!null
├── immutable
├── key: (1)
├── fd: (1)-->(3)
├── scan t
│ ├── columns: k:1!null j:2
│ ├── computed column expressions
│ │ ├── v:3
│ │ │ └── j:2->>'name'
│ │ └── s:4
│ │ └── j:2->>'name'
│ ├── key: (1)
│ └── fd: (1)-->(2)
└── projections
└── j:2->>'name' [as=v:3, outer=(2), immutable]
```

Notice that if we order by the `STORED` computed column `s`, we get an efficient scan over `t_s_idx`. But if we order by the `VIRTUAL` computed column `v`, we get a plan that sorts every row in the table.

I think we're missing a rule like `GenerateIndexScans` that can match on the virtual column pattern like `(Project (Scan ...))`. We might also need other rules like `GenerateLimitedScans` for this pattern.

Note: This also affects expression indexes because they are syntactic sugar for a virtual column plus an index.

Jira issue: CRDB-25444

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.