cockroachdb / cockroachdb/cockroach
opt: push ordered limits through synthesized NULL-ordering projections
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
### Problem
Ordered limits cannot currently be pushed through a `Project` when the ordering depends on a synthesized column. This prevents the existing join-limit rules, as well as the cross-join limit rules, from applying when non-default NULL ordering is used.
For example:
```sql
CREATE TABLE ab (a INT PRIMARY KEY, b INT);
CREATE TABLE uv (u INT PRIMARY KEY, v INT);
SET null_ordered_last = true;
SELECT * FROM ab CROSS JOIN uv ORDER BY b LIMIT 10;
```
The optimizer implements the implicit `b ASC NULLS LAST` ordering by synthesizing a Boolean column equivalent to `b IS NULL`. The relevant plan shape is:
```text
Limit(ordering: nulls_ordering_b, b)
└── Project(nulls_ordering_b := b IS NULL)
└── CrossJoin(ab, uv)
```
`PushLimitIntoProject` requires the limit ordering to be expressible using columns from the project's input. Since `nulls_ordering_b` does not exist below the project, the rule correctly declines to push the limit. The project consequently separates the limit from the join, so `PushLimitIntoJoinLeft/Right` and the cross-join limit rules cannot match.
Explicit `ORDER BY b ASC NULLS LAST` has the same limitation.
### Desired behavior
Generate an equivalent plan that retains the NULL ordering while limiting the join inputs, for example by placing the required ordering projection on the input that provides `b`:
```text
Limit
└── CrossJoin
├── Limit(ordering: nulls_ordering_b, b)
│ └── Project(nulls_ordering_b := b IS NULL)
│ └── ab
└── Limit
└── uv
```
An equivalent implementation would also be fine. A targeted rule could match `Limit -> Project -> Join`, identify ordering projections whose expressions depend on only one join input, and make those projections available to the corresponding pushed limit.
Care is needed to avoid a normalization cycle with `HoistJoinProjectLeft/Right`, which normally hoists projections above joins.
Jira issue: CRDB-66938
Contributor guide
Research direction
Start with PushLimitIntoProject and the PushLimitIntoJoinLeft/Right and cross-join limit rules, using the supplied CROSS JOIN query as the reproducer. Trace how synthesized NULL-ordering projections are represented, then verify that limits can reach the join inputs while preserving ordering and avoiding a cycle with HoistJoinProjectLeft/Right.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- database
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100