cockroachdb / cockroachdb/cockroach

opt: at high cardinalities, cost of wide scan too high relative to lookup join

Open
#128,641 0 comments 3 reactions 0 assignees View on GitHub
A-sql-optimizer C-performance O-support P-3 T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

When working with high-cardinality queries, it looks like our costing of `scan` is too sensitive to average row size, and can sometimes be higher than a lookup join that is several orders of magnitude slower.

Here's the example I'm playing with on v24.2.0-rc.1:

```sql
CREATE TABLE a (
a0 STRING NOT NULL,
a1 INT NOT NULL,
a2 STRING NOT NULL,
a3 STRING NOT NULL,
a4 STRING NOT NULL,
a5 STRING NOT NULL,
a6 STRING NOT NULL,
a7 STRING NOT NULL,
a8 STRING NOT NULL,
a9 STRING NOT NULL,
PRIMARY KEY (a0),
INDEX (a1) STORING (a2, a3, a4)
);

CREATE TABLE b (
b0 STRING NOT NULL,
b1 INT NOT NULL,
b2 STRING NOT NULL,
b3 INT NOT NULL,
b4 INT NOT NULL,
b5 STRING NOT NULL,
b6 STRING NOT NULL,
b7 STRING NOT NULL,
b8 STRING NOT NULL,
b9 STRING NOT NULL,
PRIMARY KEY (b0),
INDEX (b1, b2, b4) STORING (b3)
);

-- insert 1m rows, with 50% a1 = 1
INSERT INTO a SELECT 'a0_' || i, i % 2, j, j, j, j, j, j, j, j FROM (SELECT generate_series(0, 999999) i, repeat('a', 32) j);
ANALYZE a;

-- insert 1m rows, with 25% b1 = 1
INSERT INTO b SELECT 'b0_' || i, i % 4, 'a0_' || i, i % 20, (i % 20) + 5, j, j, j, j, j FROM (SELECT generate_series(0, 999999) i, repeat('b', 32) j);
ANALYZE b;

-- with no hints, we pick a lookup join, takes 7-9s on my laptop
EXPLAIN ANALYZE SELECT a0, a1, a2, a3, a4, b0, b1, b2, b3, b4 FROM a INNER JOIN b ON b2 = a0 WHERE a1 = 1 AND b1 = 1 AND b3 <= 10 AND b4 >= 1 ORDER BY b1;

-- with a hash join hint takes 250-280ms on my laptop
EXPLAIN ANALYZE SELECT a0, a1, a2, a3, a4, b0, b1, b2, b3, b4 FROM a INNER HASH JOIN b ON b2 = a0 WHERE a1 = 1 AND b1 = 1 AND b3 <= 10 AND b4 >= 1 ORDER BY b1;
```

In this example, the scan of 50% of `a@a_a1_idx` in the hash join plan drives the cost above the lookup join plan, even though this scan only takes about 160ms, much less than the 7s of the lookup join over 15% of `a@a_a1_idx`. By changing the width of a2, a3, and a4 we can change the costing significantly, even though the actual runtimes are not much different. So I think costing of scan is too sensitive to avg row size.

Jira issue: CRDB-41119

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.