dolthub / dolthub/dolt

Subquery analysis considers outer filters in costing, but generates plans that cannot be optimized with those filters

Open
#10,216 2 comments 0 reactions 1 assignee Claimed by @nicktobey View on GitHub
analyzer performance sql
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.