Subquery analysis considers outer filters in costing, but generates plans that cannot be optimized with those filters
- Dominant language
- Go
- Stars
- 24.4k
- Forks
- 873
- Avg merge
- 1d 8h
- Merged PRs (30d)
- 120
Description
Example query:
```
CREATE TABLE test2_small(pk int primay key, c0 int);
CREATE TABLE test2_big(pk int primay key, c0 int);
ANALYZE TABLE test_small UPDATE HISTOGRAM ON (pk) USING DATA '{"row_count": 3}';
ANALYZE TABLE test_big UPDATE HISTOGRAM ON (pk) USING DATA '{"row_count": 10000}';
DESCRIBE PLAN
SELECT COUNT(*)
FROM test2_small AS outer_table
WHERE EXISTS (
SELECT 1 FROM (
SELECT left_table.pk FROM test2_big AS left_table JOIN test2_big AS right_table ON left_table.c0 = right_table.pk
) AS joined
WHERE joined.pk = outer_table.c0
) AND outer_table.pk = 1
```
Results in the following plan:
```
+-----------------------------------------------------------+
| plan |
+-----------------------------------------------------------+
| Project |
| ├─ columns: [count(1)] |
| └─ GroupBy |
| ├─ select: COUNT(1) |
| ├─ group: |
| └─ SemiJoin |
| ├─ (joined.pk = outer_table.c0) |
| ├─ TableAlias(outer_table) |
| │ └─ Table |
| │ └─ name: test2_small |
| └─ CachedResults |
| └─ SubqueryAlias |
| ├─ name: joined |
| ├─ outerVisibility: true |
| ├─ isLateral: false |
| ├─ cacheable: true |
| └─ Project |
| ├─ columns: [left_table.pk] |
| └─ LookupJoin |
| ├─ TableAlias(left_table) |
| │ └─ Table |
| │ ├─ name: test2 |
| │ └─ columns: [pk c0] |
| └─ TableAlias(right_table) |
| └─ IndexedTableAccess(test2) |
| ├─ index: [test2.pk] |
| ├─ columns: [pk] |
| └─ keys: left_table.c0 |
+-----------------------------------------------------------+
```
Update: I wasn't properly setting the histogram, this paragraph doesn't apply. ~~This plan is terrible: It uses an InnerJoin within the Subquery, which will result in 10000 * 10000 comparisons, and then caching a 10000 row intermediate result in memory. The engine will then scan this entire table looking for a match for the single row that it gets from the left side of the SemiJoin.~~
It would be much more efficient to not cache the Subquery result, and to generate a indexed lookup on both `left_table` and `right_table. In such a plan, the entire query reduces to a single indexed lookup on each table.
~~The reason we produce this plan is because our Functional Dependency Analysis produces bounds on the number of results, and then the join planner incorrectly assumes that these bounds apply to intermediate results even when they don't.~~
~~Essentially, the analyzer deduces that `joined.pk` is constant, because it is equal to `outer_table.pk`, and `outer_table.pk` is constant. Thus, it deduces that both sides of the innermost join contain at most one row, at which point a InnerJoin becomes the cheapest plan. But since the filter that led to this deduction is outside of the subquery, it does not influence the subquery's plan , and at execution time we end up iterating over the entire tables.~~
Note that we can't solve this by simply not incorporating the equivalence information from outside the subquery, since we need that information in order to deduce that a LookupJoin is optimal here. Instead, we must be able to push the filter into the subquery so that the runtime characteristics of the subquery match the analysis.
~~A similar problem occurs if we don't have the `AND outer_table.pk = 1` filter. In this case, the optimal plan is less obvious and depends on the selectivity of other filters in the query: if we expect that most rows in the innermost join will appear in the result set, it might make sense to use a cached MergeJoin and pay the memory cost of caching. If we expect that most rows in the innermost join won't appear in the result set, it might make sense to generate a LookupJoin here. However, the analyzer will once again produce an InnerJoin. This is because it deduces that `joined.pk` is constant within each iteration of the subquery and thus can be treated as a constant while evaluating the subquery... even though this provides no benefit if the subquery is going to be cached.~~
Again, the correct fix would be to push the filter into the subquery, allowing the subquery to contain IndexedTableAccesses at appropriate places.
The reason why we don't currently do this is because:
- the `pushdownSubqueryAliasFilters` optimization only pushes filters into subquery aliases if the filter references a single table. This is reasonable in most cases, but overly conservative.
- the more general `pushFilters` optimization only pushes filters until they are sitting above every referenced table in the filter. This is to prevent pushing a filter into an expression where the table references can no longer resolve. This is necessary in general, but doesn't account for circumstances where expressions can reference tables in sibling nodes (lateral joins) or parent nodes (exists subqueries). In those cases, it's safe to push the filter deeper, but we don't.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.