cockroachdb / cockroachdb/cockroach

opt: zigzag join row-count estimate ignores equality filters

Open
#98,022 1 comment 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 removes equality filters that were used to form the `LeftEqCols` and `RightEqCols` lists from the zigzag join's ON condition. However, the statistics code only considers the ON condition when calculating selectivity, which misses any filters that were used to generate the equality columns. This could lead to over-estimates for the number of rows returned by a zigzag join. Note that this is likely only a problem when an index join is necessary to satisfy some of the extra filters, since that is the only case when a new memo group is constructed for the zigzag join.

Example:
```
exec-ddl
CREATE TABLE t (
a INT,
b INT,
c INT,
d INT,
INDEX ab_idx (a, b),
INDEX cd_idx (c, d)
);
----

opt
SELECT * FROM t@{FORCE_ZIGZAG} WHERE a = 1 AND c = 2 AND b = d;
----
inner-join (zigzag t@ab_idx t@cd_idx)
├── columns: a:1!null b:2!null c:3!null d:4!null
├── eq columns: [2 5] = [4 5]
├── left fixed columns: [1] = [1]
├── right fixed columns: [3] = [2]
├── fd: ()-->(1,3), (2)==(4), (4)==(2)
└── filters
├── a:1 = 1 [outer=(1), constraints=(/1: [/1 - /1]; tight), fd=()-->(1)]
└── c:3 = 2 [outer=(3), constraints=(/3: [/2 - /2]; tight), fd=()-->(3)]
```
Note how the `b = d` filter is not in the ON condition.

Jira issue: CRDB-25021

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.