The analyzer won't push filters that contain lateral references
- Dominant language
- Go
- Stars
- 24.4k
- Forks
- 873
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 108
Description
Consider the following:
```
CREATE TABLE `kv` (`k` int NOT NULL PRIMARY KEY, `v` int);
analyze table kv update histogram on (k) using data '{"row_count": 1000}';
describe plan select * from kv kv1 join lateral (select * from kv kv2 join kv kv3 where kv1.v = kv2.k and kv2.v = kv3.k) r;
```
We currently produce a plan that looks like this:
```
+----------------------------------------+
| plan |
+----------------------------------------+
| LateralCrossJoin |
| ├─ TableAlias(kv1) |
| │ └─ Table |
| │ └─ name: kv |
| └─ SubqueryAlias |
| ├─ name: r |
| ├─ outerVisibility: false |
| ├─ isLateral: true |
| ├─ cacheable: false |
| ├─ colSet: (7-10) |
| ├─ tableId: 4 |
| └─ LookupJoin |
| ├─ (kv1.v = kv2.k) |
| ├─ TableAlias(kv2) |
| │ └─ Table |
| │ ├─ name: kv |
| │ └─ columns: [k v] |
| └─ TableAlias(kv3) |
| └─ IndexedTableAccess(kv) |
| ├─ index: [kv.k] |
| ├─ columns: [k v] |
| └─ keys: kv2.v |
+----------------------------------------+
```
Note how `(kv1.v = kv2.k)` is a filter, and `kv2` is a full table scan. It would be strictly better to instead generate an IndexedTableAccess for kv2.
There are two separate reasons why this isn't happening:
1. We are not pushing the filter into the left child of the LookupJoin because it contains references to multiple tables.
2. If I change the `pushFilters` optimization to *force* it to push the filter, we still don't generate an IndexedTableAccess because the join planner does not consider the filter-and-table to be a valid leaf node in the join tree because it compares kv2.k to the non-literal value kv1.v
There is a separate optimization, `applyIndexesFromOuterScope` that purports to do this, but doesn't. It currently runs after `optimizeJoins`, but even when I reorder the rules, it still doesn't apply here for reasons I don't fully understand. Most likely, this should be part of `optimizeJoins`.
In order to fix (1), I made an experimental branch where I allow filters to be pushed down even if they reference multiple tables. However, it's difficult to reason about when this is actually safe to do so, and it appears to break computed column indexes in recursive table expressions, and it causes the join planner to emit HashJoins with out-of-scope references, which compute incorrect results. Most likely, a better solution is to improve the AST to have better tracking of which references are out-of-scope, and allow us to treat them as constant values for the purposes of specific optimizations, while avoiding any transformations that would be unsafe.
In order to fix (2), we likely need to incorporate `applyIndexesFromOuterScope` into the join planner.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.