cockroachdb / cockroachdb/cockroach

opt: push ordered limits through synthesized NULL-ordering projections

Open
#173,629 0 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer C-enhancement E-quick-win O-agent T-sql-queries
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.