cockroachdb / cockroachdb/cockroach

sql/opt: LATERAL + ORDER BY + LIMIT decorrelation causes full table scan instead of using index

Open
#165,983 4 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-performance O-support P-3 T-sql-queries
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.