cockroachdb / cockroachdb/cockroach
opt: reduce join reordering of equality joins that do not duplicate LHS rows
- 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
Assessment
This issue has not been assessed yet.