cockroachdb / cockroachdb/cockroach
opt: zigzag join costing underestimates rows scanned
- 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
Assessment
This issue has not been assessed yet.