cockroachdb / cockroachdb/cockroach
sql/opt: LATERAL + ORDER BY + LIMIT decorrelation causes full table scan instead of using index
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
## Summary
When a `LATERAL` subquery contains `ORDER BY + LIMIT` and filters on a correlated column, the optimizer decorrelates it into a hash join + window function. This removes the per-group `LIMIT` short-circuit and causes a full table scan instead of using an available index on the correlated column.
A prior fix (#120866 / CRDB-36908) addressed some cases of this pattern, but it does not cover nested `LATERAL` joins. The same decorrelation behavior is still present on v26.1.
## Impact
Real-world query from a customer (Zendesk #30840):
- **PostgreSQL:** 1.6ms -- keeps the correlated loop structure, does 13 small index lookups on `(parent_id, index)` with `LIMIT 5` per parent
- **CockroachDB:** 6m15s -- decorrelates the lateral join, full scans the `assets` table (27.5M rows, 102 GiB), full scans `asset_paths` (2.2M rows), joins everything, then filters down
The indexes are present and correct. CRDB just doesn't use them because the decorrelation converts `sa0.parent_id = f0.id` (correlated) into a hash join equality, so there's no non-correlated predicate left to drive index selection.
## Reproduction pattern
The general shape that triggers this:
```sql
SELECT ...
FROM (SELECT unnest($1::uuid[]) id) AS f0
INNER JOIN LATERAL (
SELECT ...
FROM some_table AS t
WHERE t.parent_id = f0.id -- correlated predicate
AND t.deleted_at IS NULL
ORDER BY t.index
LIMIT 5 -- per-group limit
) AS s1 ON TRUE
```
CRDB decorrelates this into a full scan of `some_table` + hash join on `parent_id = unnest`, then applies the limit as a window function (`ROW_NUMBER()`) after the fact. PG keeps it as a correlated loop with index lookups.
The problem is worse with nested `LATERAL` joins (e.g., a `LATERAL` subquery inside another `LATERAL` subquery), which is the case the customer hit and which #120866's fix doesn't appear to cover.
## Workaround
Adding a redundant explicit filter that duplicates the correlated predicate as a non-correlated one:
```sql
WHERE t.parent_id = f0.id
AND t.parent_id = ANY($1::uuid[]) -- redundant but gives optimizer a non-correlated predicate
```
This lets the optimizer push down the `= ANY(...)` for index selection even after decorrelation flattens the lateral structure. The filter is logically redundant with the correlated predicate, so it doesn't affect correctness or PG performance.
With the workaround applied, the query went from 6m15s to ~13ms.
## Related issues
- #120866 / CRDB-36908 -- "Lateral join / SELECT DISTINCT ON failing to use index" -- closed as completed (April 2024), but fix doesn't cover nested lateral joins
- #151609 / CRDB-53357 -- "sql: incorrect decorrelation of lateral join" -- open/backlog, related but focused on correctness rather than performance
cc @cockroachdb/sql-queries
Jira issue: CRDB-61705
Contributor guide
Assessment
This issue has not been assessed yet.