cockroachdb / cockroachdb/cockroach
opt: plan locality optimized search on unique partial index
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
The optimizer does not plan a locality-optimized search on a partial unique index when the unique columns are held constant by the filters and the partial index predicate is implied by the filters. Below is a logic test showing a case where locality-optimized search could be planned, but is not:
```
# LogicTest: multiregion-9node-3region-3azs !metamorphic-batch-sizes
statement ok
SET CLUSTER SETTING kv.closed_timestamp.side_transport_interval = '10ms';
statement ok
SET CLUSTER SETTING kv.closed_timestamp.target_duration = '10ms';
statement ok
CREATE DATABASE multi_region_test_db PRIMARY REGION "ca-central-1" REGIONS "ap-southeast-2", "us-east-1" SURVIVE REGION FAILURE;
statement ok
USE multi_region_test_db
statement ok
CREATE TABLE t1 (
id INT PRIMARY KEY,
a INT NOT NULL,
t TIMESTAMPTZ,
UNIQUE INDEX (a) WHERE t IS NULL
) LOCALITY REGIONAL BY ROW
query T
EXPLAIN (OPT, VERBOSE)
SELECT * FROM t1 WHERE a = 11 AND t IS NULL
----
distribute
├── columns: id:1 a:2 t:3
├── stats: [rows=0.91, distinct(2)=0.91, null(2)=0, distinct(3)=0.91, null(3)=0.91, distinct(2,3)=0.91, null(2,3)=0]
├── cost: 423.0792
├── key: (1)
├── fd: ()-->(2,3)
├── distribution: ap-southeast-2
├── input distribution: ap-southeast-2,ca-central-1,us-east-1
├── prune: (1)
└── project
├── columns: t:3 id:1 a:2
├── stats: [rows=0.91, distinct(2)=0.91, null(2)=0, distinct(3)=0.91, null(3)=0.91, distinct(2,3)=0.91, null(2,3)=0]
├── cost: 223.0592
├── key: (1)
├── fd: ()-->(2,3)
├── prune: (1)
├── scan t1@t1_a_key,partial
│ ├── columns: id:1 a:2
│ ├── constraint: /4/2
│ │ ├── [/'ap-southeast-2'/11 - /'ap-southeast-2'/11]
│ │ ├── [/'ca-central-1'/11 - /'ca-central-1'/11]
│ │ └── [/'us-east-1'/11 - /'us-east-1'/11]
│ ├── stats: [rows=0.91, distinct(2)=0.91, null(2)=0, distinct(3)=0.91, null(3)=0.91, distinct(4)=0.91, null(4)=0, distinct(2,3)=0.91, null(2,3)=0]
│ ├── cost: 223.021
│ ├── key: (1)
│ └── fd: ()-->(2)
└── projections
└── CAST(NULL AS TIMESTAMPTZ) [as=t:3]
```
I believe the major thing preventing LOS in this case is that we aren't able to determine that the scan on `t1_a_key` has a cardinality of 1. In the logical props builder, we add lax key columns from the scanned partial index; in this case `crdb_region` and `a`. But we do not add lax key columns from the corresponding `UNIQUE WITHOUT INDEX` constraint where `a` is a lax key. Thus, we the FDs cannot determine that the scan produces a single row, failing to meet the requirements to trigger the LOS optimization.
To fix this, we can add all lax key columns from unique constraints with predicates matching the partial index predicate here: https://github.com/cockroachdb/cockroach/blob/70ba6b9e9d1cea24b8188b635668b68ff145734a/pkg/sql/opt/memo/logical_props_builder.go#L132-L142
We may run into some issues when the constrained partial index scan is placed in the same memo group as the Select that it originates from. In this case, logical properties will not be re-generated because all expressions in the same memo group share the same logical properties. So the partial index scan will retain the same properties as the Select, which won't have FDs to prove that that the cardinality of the group is 1.
Jira issue: CRDB-33531
Contributor guide
Research direction
Start in pkg/sql/opt/memo/logical_props_builder.go at the cited lines and use the embedded LogicTest as the reproduction. Trace how lax key columns from the partial index and matching unique constraint contribute to functional dependencies, including the memo-group concern. Done means the EXPLAIN plan can trigger locality-optimized search for the shown query without breaking logical properties.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100