cockroachdb / cockroachdb/cockroach

opt: plan locality optimized search on unique partial index

Open
#114,495 0 comments 0 reactions 0 assignees View on GitHub
A-multiregion C-enhancement O-support P-3 T-sql-queries
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.