cockroachdb / cockroachdb/cockroach

opt: zigzag join costing underestimates rows scanned

Open
#98,009 0 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-performance T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

The zigzag join [planning code](https://github.com/cockroachdb/cockroach/blob/007f794e7079ac91e1077b3dc48c3f7a07b6a245/pkg/sql/opt/xform/coster.go#L1330-L1331) uses the estimated number of output rows in determining how many seeks will be performed during costing. The problem is that this rowcount estimate includes extra join filters that aren't used in the zigzag join seeks. This can cause the cost of a zigzag join to be vastly underestimated.

Example:
```
CREATE TABLE t (
k INT PRIMARY KEY,
a INT,
b INT,
c INT NOT NULL UNIQUE,
INDEX a_idx (a) STORING (c),
INDEX b_idx (b) STORING (c)
);
INSERT INTO t SELECT t, 1, 2, t FROM generate_series(1, 10000) g(t);
ANALYZE t;

-- A zigzag join between a_idx and b_idx will scan the entire table, but we
-- cost the zigzag join as if it scans only one row from each index.
EXPLAIN (OPT, VERBOSE) SELECT * FROM t@{FORCE_ZIGZAG} WHERE a = 1 AND b = 2 AND c = 3;
----
inner-join (zigzag t@a_idx t@b_idx)
├── columns: k:1 a:2 b:3 c:4
├── eq columns: [1] = [1]
├── left fixed columns: [2] = [1]
├── right fixed columns: [3] = [2]
├── cardinality: [0 - 1]
├── stats: [rows=1, distinct(2)=1, null(2)=0, distinct(3)=1, null(3)=0, distinct(4)=1, null(4)=0]
├── cost: 12.1425
├── key: ()
├── fd: ()-->(1-4)
├── prune: (1)
└── filters
├── a:2 = 1 [outer=(2), constraints=(/2: [/1 - /1]; tight), fd=()-->(2)]
├── b:3 = 2 [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]
└── c:4 = 3 [outer=(4), constraints=(/4: [/3 - /3]; tight), fd=()-->(4)]
```

Jira issue: CRDB-25013

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.