cockroachdb / cockroachdb/cockroach

opt: overly-pessimistic statistics estimate for index join on top of inverted index scan

Open
#104,096 2 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer A-sql-table-stats 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

Our statistics estimates for index joins on top of inverted index scans seem wildly pessimistic. An index join should always have a row count estimate = the child row count estimate, but when the child is an inverted index scan we see estimates > 1000x the child estimate. Here's a demonstration:

```sql
CREATE TABLE ijk (i INT PRIMARY KEY, j JSONB, k STRING, INVERTED INDEX (j));
INSERT INTO ijk SELECT i, json_build_object('foo', i), i::string FROM generate_series(0, 9999) AS s(i);
ANALYZE ijk;
EXPLAIN SELECT i FROM ijk WHERE j->'foo' = '3';
EXPLAIN SELECT k FROM ijk WHERE j->'foo' = '3';
```

The first explain, using only an inverted index scan, shows a row count estimate of 0 (which doesn't seem right, either, should be 1):

```
demo@127.0.0.1:26257/demoapp/defaultdb> EXPLAIN SELECT i FROM ijk WHERE j->'foo' = '3';
info
---------------------------------------------------------------------------------
distribution: local
vectorized: true

• scan
estimated row count: 0 (<0.01% of the table; stats collected 2 seconds ago)
table: ijk@ijk_j_idx
spans: 1 span
(7 rows)

Time: 1ms total (execution 1ms / network 0ms)
```

The second explain, with an index join on top of an inverted index scan, shows a row count estimate of over 1000 which is wildly pessimistic (the query only returns 1 row):

```
demo@127.0.0.1:26257/demoapp/defaultdb> EXPLAIN SELECT k FROM ijk WHERE j->'foo' = '3';
info
-------------------------------------------------------------------------------------
distribution: local
vectorized: true

• index join
│ estimated row count: 1,111
│ table: ijk@ijk_pkey

└── • scan
estimated row count: 0 (<0.01% of the table; stats collected 5 seconds ago)
table: ijk@ijk_j_idx
spans: 1 span
(11 rows)

Time: 1ms total (execution 1ms / network 0ms)
```

Jira issue: CRDB-28352

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.