sql/opt: Optimizer switches from sort-before-lookup early-stop to full join + top-k at LIMIT 80, causing ~25x slowdown

**Describe the problem**

I observed a large `ORDER BY ... LIMIT` plan-quality regression over an inner join / lookup join.

The query joins two tables on:

```sql
t1.c0 = t0.c0
```

and orders by:

```sql
ORDER BY t0.c0 ASC, t1.c3 DESC
```

Since `t0.c0 = t1.c0` on joined rows, I also tested the equivalent order variant:

```sql
ORDER BY t1.c0 ASC, t1.c3 DESC
```

The equivalent-order rewrite does not materially change the default plan choice. The interesting behavior is instead a plan flip around the LIMIT value.

In this testcase, CockroachDB chooses a good sort-before-lookup plan for smaller LIMIT values. The good plan scans and sorts the `t1` side, performs lookup joins into `t0`, and stops once the LIMIT is satisfied.

However, when the LIMIT increases from 70 to 80, the optimizer switches to a much slower full join + top-k plan. The slower plan produces the full joined result of 859,680 rows before applying top-k.

A forced comparator still gets the good sort-before-lookup plan for LIMIT 80, LIMIT 100, and LIMIT 300, and is about 25x-35x faster than the default plan.

I will attach:

- `crdb_order_limit_plan_flip_repro.sql`

[crdb_order_limit_plan_flip_repro_with_explain.sql](https://github.com/user-attachments/files/29872631/crdb_order_limit_plan_flip_repro_with_explain.sql)

- `crdb_order_limit_plan_flip_repro_result.txt`

[crdb_order_limit_plan_flip_repro_result.txt](https://github.com/user-attachments/files/29872634/crdb_order_limit_plan_flip_repro_result.txt)

The SQL file creates the schema, inserts deterministic data, creates indexes, runs `ANALYZE`, and then runs plain `EXPLAIN (VERBOSE)` once and `EXPLAIN ANALYZE (VERBOSE)` three times for each query variant.

**To Reproduce**

Run the attached SQL file:

```bash
cockroach sql --insecure --file=crdb_order_limit_plan_flip_repro.sql > crdb_order_limit_plan_flip_repro_result.txt
```

The testcase creates two tables:

- `t0`: 48,000 rows
- `t1`: 72,000 rows
- `NDV(t0.c0) = 4000`
- `NDV(t1.c0) = 4000`
- `t0` rows per `c0`: 12
- `t1` rows per `c0`: 18
- join condition: `t1.c0 = t0.c0`
- joined rows before filter: 864,000
- joined rows after `t0.c4 IS NOT NULL`: 859,680

The relevant indexes intentionally do **not** include an order-covering index on `t1(c0 ASC, c3 DESC)`.

The testcase compares three query variants for multiple LIMIT values.

A. Default original:

```sql
SELECT t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t0.c0 ASC, t1.c3 DESC
LIMIT ;
```

B. Default equivalent-order variant:

```sql
SELECT t1.c2 AS ref0
FROM t1
INNER JOIN t0 ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT ;
```

C. Forced comparator:

```sql
SELECT t1.c2 AS ref0
FROM t1@idx_t1_c3_c0_c2
INNER LOOKUP JOIN t0@idx_t0_c0_storing_c4
ON t1.c0 = t0.c0
WHERE t0.c4 IS NOT NULL
ORDER BY t1.c0 ASC, t1.c3 DESC
LIMIT ;
```

The forced comparator is not meant as a user workaround recommendation. It is included to show that a much faster sort-before-lookup plan shape exists.

Each variant is tested with:

```text
LIMIT 10
LIMIT 50
LIMIT 70
LIMIT 80
LIMIT 100
LIMIT 300
```

Each `EXPLAIN ANALYZE` is executed three times. The table below summarizes the median execution time from the attached result file.

| LIMIT | Variant | Plain EXPLAIN plan shape | Key estimated row count | Median EXPLAIN ANALYZE time | Key actual row count |
|---:|---|---|---:|---:|---:|
| 10 | A default original | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 88ms | lookup join actual 10 |
| 10 | B equivalent-order | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 94ms | lookup join actual 10 |
| 10 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 88ms | lookup join actual 10 |
| 50 | A default original | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 87ms | lookup join actual 50 |
| 50 | B equivalent-order | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 88ms | lookup join actual 50 |
| 50 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 88ms | lookup join actual 50 |
| 70 | A default original | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 89ms | lookup join actual 70 |
| 70 | B equivalent-order | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 80ms | lookup join actual 70 |
| 70 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 84ms | lookup join actual 70 |
| 80 | A default original | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.3s | lookup join actual 859,680 |
| 80 | B equivalent-order | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.3s | lookup join actual 859,680 |
| 80 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 73ms | lookup join actual 80 |
| 100 | A default original | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.6s | lookup join actual 859,680 |
| 100 | B equivalent-order | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.7s | lookup join actual 859,680 |
| 100 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 90ms | lookup join actual 100 |
| 300 | A default original | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.7s | lookup join actual 859,680 |
| 300 | B equivalent-order | `top-k -> lookup join -> lookup join -> scan t0` | lookup join est. 859,680 | 2.6s | lookup join actual 859,680 |
| 300 | C forced comparator | `limit -> lookup join -> sort -> scan t1` | lookup join est. 859,680 | 75ms | lookup join actual 300 |

The key transition is between LIMIT 70 and LIMIT 80.

For LIMIT 70, the default original query gets the good plan in plain `EXPLAIN`:

```text
limit
lookup join
sort
scan t1
```

The corresponding `EXPLAIN ANALYZE` run finishes in about 89ms. The lookup join outputs only 70 rows.

For LIMIT 80, the default original query switches to the following plan already in plain `EXPLAIN`:

```text
top-k
lookup join
lookup join
scan t0
```

The corresponding `EXPLAIN ANALYZE` run takes about 2.3s and the lookup join produces 859,680 rows before the top-k operator returns 80 rows.

For the same LIMIT 80, the forced comparator still gets the good plan:

```text
limit
lookup join
sort
scan t1
```

It finishes in about 73ms and the lookup join outputs only 80 rows.

So the plan flip is visible before execution in plain `EXPLAIN`, and `EXPLAIN ANALYZE` confirms that the selected plan is much slower.

**Expected behavior**

I expected the optimizer to continue choosing the sort-before-lookup early-stop plan for LIMIT 80, LIMIT 100, and LIMIT 300, or at least to avoid a full join + top-k plan that is more than 20x slower in this testcase.

The sort-before-lookup plan seems preferable here because it scans and sorts the `t1` side once, then probes `t0` only until the LIMIT is satisfied.

The selected full join + top-k plan instead scans `t0`, looks up matching `t1` rows, fetches `t1` rows, produces the full 859,680-row joined result, and only then applies top-k.

This looks like the optimizer may be underestimating the cost of the full lookup join + top-k plan, or overestimating the cost/underestimating the early-stop benefit of the sort-before-lookup alternative for moderate LIMIT values.

Another way to phrase the suspected issue:

The row estimate below the lookup join remains 859,680 even for the good `limit -> lookup join -> sort -> scan t1` plan, while the actual lookup join output is only the LIMIT value due to early stop. It looks like the costing decision may not fully account for the parent LIMIT's early-stop effect when comparing the sort-before-lookup plan against the full join + top-k plan.

**Additional data / screenshots**

The attached SQL file contains:

- schema
- deterministic data generation
- indexes
- `ANALYZE`
- plain `EXPLAIN (VERBOSE)` for each query variant
- three `EXPLAIN ANALYZE (VERBOSE)` runs for each query variant
- result equivalence sanity checks for representative LIMIT values

Important observations from the attached result file:

- Data shape:
- `t0` rows: 48,000
- `t1` rows: 72,000
- joined rows after filter: 859,680
- `t1` intentionally does not have an index on `(c0, c3 DESC)`.
- Plain `EXPLAIN` shows the plan flip:
- LIMIT 70 default: `limit -> lookup join -> sort -> scan t1`
- LIMIT 80 default: `top-k -> lookup join -> lookup join -> scan t0`
- `EXPLAIN ANALYZE` confirms the actual effect:
- LIMIT 70 default: about 89ms, lookup join actual row count 70
- LIMIT 80 default: about 2.3s, lookup join actual row count 859,680
- LIMIT 80 forced comparator: about 73ms, lookup join actual row count 80
- LIMIT 300 default: about 2.6s-2.7s, lookup join actual row count 859,680
- LIMIT 300 forced comparator: about 75ms, lookup join actual row count 300

The equivalent-order variant does not materially change the default behavior. Therefore, this does not appear to be primarily an ORDER BY equivalence issue. The relevant issue seems to be the cost-based plan choice between:

1. sort-before-lookup with early stop, and
2. full lookup join + top-k.

**Environment:**

- CockroachDB version: 26.2.2
- Server OS: Ubuntu 22.04.4 LTS
- Client app: `cockroach sql`
- Repro setup: single-node local test

**Additional context**

Impact: this plan flip causes a 20x-35x slowdown in this testcase.

Increasing the LIMIT from 70 to 80 changes the default plan from a sort-before-lookup early-stop plan to a full join + top-k plan. Runtime increases from about 89ms to about 2.3s. A forced comparator for LIMIT 80 still finishes in about 73ms, suggesting that a much faster plan shape exists but is not selected by the optimizer.

For LIMIT 300, the default plan takes about 2.6s-2.7s, while the forced comparator takes about 75ms.

Jira issue: CRDB-65646

Run crdb_order_limit_plan_flip_repro.sql with cockroach sql, then compare plain EXPLAIN and EXPLAIN ANALYZE for LIMIT 70 and LIMIT 80. Focus on the optimizer's costing of sort-before-lookup with early stop versus full lookup join plus top-k. Done means the default plan avoids the demonstrated severe regression while preserving query results.

Written by the indexing model from the issue text.