cockroachdb / cockroachdb/cockroach

opt: reduce join reordering of equality joins that do not duplicate LHS rows

Open
#151,808 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

Consider the example:

```
exec-ddl
CREATE TABLE t1 (
k INT PRIMARY KEY,
i INT,
INDEX (i)
)
----

exec-ddl
CREATE TABLE t2 (
k INT PRIMARY KEY,
i INT
)
----

exec-ddl
CREATE TABLE t3 (
k INT PRIMARY KEY,
i INT
)
----

exec-ddl
CREATE TABLE t4 (
k INT PRIMARY KEY,
i INT
)
----

opt
SELECT * FROM t1
LEFT JOIN t2 ON t2.k = t1.k
LEFT JOIN t3 ON t3.k = t1.k
LEFT JOIN t4 ON t4.k = t1.k
WHERE t1.i = 33
----
left-join (lookup t4)
├── columns: k:1!null i:2!null k:5 i:6 k:9 i:10 k:13 i:14
├── key columns: [1] = [13]
├── lookup columns are key
├── key: (1)
├── fd: ()-->(2), (5)-->(6), (1)-->(5,6,9,10,13,14), (9)-->(10), (13)-->(14)
├── left-join (lookup t3)
│ ├── columns: t1.k:1!null t1.i:2!null t2.k:5 t2.i:6 t3.k:9 t3.i:10
│ ├── key columns: [1] = [9]
│ ├── lookup columns are key
│ ├── key: (1)
│ ├── fd: ()-->(2), (5)-->(6), (1)-->(5,6,9,10), (9)-->(10)
│ ├── left-join (lookup t2)
│ │ ├── columns: t1.k:1!null t1.i:2!null t2.k:5 t2.i:6
│ │ ├── key columns: [1] = [5]
│ │ ├── lookup columns are key
│ │ ├── key: (1)
│ │ ├── fd: ()-->(2), (5)-->(6), (1)-->(5,6)
│ │ ├── scan t1@t1_i_idx
│ │ │ ├── columns: t1.k:1!null t1.i:2!null
│ │ │ ├── constraint: /2/1: [/33 - /33]
│ │ │ ├── key: (1)
│ │ │ └── fd: ()-->(2)
│ │ └── filters (true)
│ └── filters (true)
└── filters (true)
```

The optimizer will explore different orderings of all the joins and subsequent explorations rules will fire for each ordering. This can increase query optimization latency significantly.

In this example, however, there is only one join ordering that really matters—`t1` should be scanned first. If it is not, then a full-table scan will be performed. And the ordering of joins within the `t2 LEFT JOIN t3 LEFT JOIN t4` doesn't really matter because none of them will duplicate rows on the LHS (if one projects a lot more columns then another, it might matter, but marginally so).

Can we lean on join-multiplicity here—if the join does not duplicate rows, should it be reordered? I think that's probably far to restrictive in practice. What other criteria makes it obvious in the above example that some orderings should not be explored?

Jira issue: CRDB-53484

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.