sql/opt: optimizer misses early-stop plan for DISTINCT ORDER BY LIMIT over CROSS JOIN

[distinct_order_limit_cross_join_early_stop_median.sql](https://github.com/user-attachments/files/29838726/distinct_order_limit_cross_join_early_stop_median.sql)
[distinct_order_limit_cross_join_early_stop_median_result.txt](https://github.com/user-attachments/files/29838725/distinct_order_limit_cross_join_early_stop_median_result.txt)

**Describe the problem**

CockroachDB appears to miss an early-stop optimization for a `DISTINCT + ORDER BY + LIMIT` query over `CROSS JOIN`s when the projected column and ordering key come from only one table.

The original query is:

```sql
SELECT DISTINCT a.c0 AS ref0
FROM dol_cross_t0 AS a
CROSS JOIN dol_cross_t1 AS b
CROSS JOIN dol_cross_t2 AS c
ORDER BY a.c0 DESC
LIMIT 1;
```

In this query, only `dol_cross_t0.c0` is projected and ordered. The other two cross-joined tables only affect whether the result is empty. The `CROSS JOIN` inputs are logically independent and may be reordered, but regardless of join order, the output and ordering depend only on `dol_cross_t0.c0`.

Since both `dol_cross_t1` and `dol_cross_t2` are non-empty, the query is semantically equivalent to finding the top distinct `c0` value from `dol_cross_t0`, plus existence checks for the two other tables.

However, CockroachDB evaluates the full Cartesian product before `DISTINCT` / `TOP-K`.

In the attached reproduction, the table sizes are:

```text
dol_cross_t0: 100 rows
dol_cross_t1: 1000 rows
dol_cross_t2: 500 rows
full Cartesian product: 50,000,000 rows
```

For the original query, `EXPLAIN ANALYZE` shows:

```text
execution time: 3.4s / 3.4s / 3.5s
median execution time: 3.4s
cross join actual row count: 50,000,000
rows decoded from KV: 1,600
```

An equivalent `EXISTS` rewrite is:

```sql
SELECT top_t0.ref0
FROM (
SELECT DISTINCT a.c0 AS ref0
FROM dol_cross_t0@{FORCE_INDEX=dol_cross_t0_c0_idx,DESC} AS a
ORDER BY a.c0 DESC
LIMIT 1
) AS top_t0
WHERE EXISTS (SELECT 1 FROM dol_cross_t1 LIMIT 1)
AND EXISTS (SELECT 1 FROM dol_cross_t2 LIMIT 1);
```

For this rewritten query, `EXPLAIN ANALYZE` shows:

```text
execution time: 958µs / 780µs / 761µs
median execution time: 780µs
rows decoded from KV: 4
```

Both queries return the same result, and the attached script includes an `EXCEPT ALL`-based equivalence check whose `diff_count` is `0`.

This looks like a missed optimizer transformation / early-stop opportunity. The cross-joined tables do not contribute any projected columns, ordering columns, filters, or join predicates. They only determine whether the result is empty. A plan equivalent to the `EXISTS` rewrite can avoid materializing the full Cartesian product and can stop after reading only a few rows.

**To Reproduce**

Run the attached SQL file:

```bash
cockroach sql --insecure --host=: -f distinct_order_limit_cross_join_early_stop_median.sql
```

The script does the following:

1. Sets up the session:

```sql
SET plan_cache_mode = force_custom_plan;
SET reorder_joins_limit = 8;
SET distsql = off;
```

2. Creates three tables:

```sql
CREATE TABLE dol_cross_t0 (
id INT PRIMARY KEY,
c0 INT NOT NULL
);

CREATE TABLE dol_cross_t1 (
id INT PRIMARY KEY,
pad INT NOT NULL
);

CREATE TABLE dol_cross_t2 (
id INT PRIMARY KEY,
pad INT NOT NULL
);
```

3. Inserts:

```text
dol_cross_t0: 100 rows
dol_cross_t1: 1000 rows
dol_cross_t2: 500 rows
```

4. Creates an index on the ordered column:

```sql
CREATE INDEX dol_cross_t0_c0_idx ON dol_cross_t0 (c0);
```

5. Runs `ANALYZE`.

6. Runs `EXPLAIN (OPT)` and `EXPLAIN ANALYZE` for the original query.

7. Runs `EXPLAIN (OPT)` and `EXPLAIN ANALYZE` for the equivalent `EXISTS` rewrite.

8. Runs an equivalence check between the original query and the rewritten query.

The original query plan has the shape:

```text
top-k
└── distinct-on
└── inner-join (cross)
├── inner-join (cross)
│ ├── scan dol_cross_t1
│ ├── scan dol_cross_t0
└── scan dol_cross_t2
```

The original query executes the full Cartesian product:

```text
actual row count: 50,000,000
```

The equivalent rewrite has the shape:

```text
select
├── limit
│ ├── distinct-on
│ │ └── scan dol_cross_t0@dol_cross_t0_c0_idx,rev
│ └── 1
└── filters
├── EXISTS (SELECT 1 FROM dol_cross_t1 LIMIT 1)
└── EXISTS (SELECT 1 FROM dol_cross_t2 LIMIT 1)
```

The rewritten query reads only a few rows:

```text
rows decoded from KV: 4
```

**Expected behavior**
I expected CockroachDB to avoid evaluating the full Cartesian product in this case.

Since the projected column and ordering key come only from `dol_cross_t0`, and the other cross-joined tables only determine whether the result is empty, CockroachDB could use a plan equivalent to:

```sql
SELECT top_t0.ref0
FROM (
SELECT DISTINCT a.c0 AS ref0
FROM dol_cross_t0@{FORCE_INDEX=dol_cross_t0_c0_idx,DESC} AS a
ORDER BY a.c0 DESC
LIMIT 1
) AS top_t0
WHERE EXISTS (SELECT 1 FROM dol_cross_t1 LIMIT 1)
AND EXISTS (SELECT 1 FROM dol_cross_t2 LIMIT 1);
```

This plan can perform a reverse index scan on `dol_cross_t0.c0`, stop after the first distinct ordered value, and check that the other cross-joined inputs are non-empty.

**Additional data / screenshots**

Attached files:

- `distinct_order_limit_cross_join_early_stop_median.sql`
- `distinct_order_limit_cross_join_early_stop_median_result.txt`

Important results from the attached output:

Original query:

```text
EXPLAIN ANALYZE run 1: execution time: 3.4s
EXPLAIN ANALYZE run 2: execution time: 3.4s
EXPLAIN ANALYZE run 3: execution time: 3.5s
median execution time: 3.4s
actual cross join rows: 50,000,000
```

Equivalent `EXISTS` rewrite:

```text
EXPLAIN ANALYZE run 1: execution time: 958µs
EXPLAIN ANALYZE run 2: execution time: 780µs
EXPLAIN ANALYZE run 3: execution time: 761µs
median execution time: 780µs
rows decoded from KV: 4
```

Equivalence check:

```text
diff_count: 0
```

Both queries return:

```text
ref0 = 100
```

**Environment:**

- CockroachDB version: CockroachDB CCL v26.2.2
- Server OS: Ubuntu 22.04.4 LTS
- Client app: `cockroach sql`
- Session settings:
- `plan_cache_mode = force_custom_plan`
- `reorder_joins_limit = 8`
- `distsql = off`

**Additional context**

This is a performance issue / missed optimization, not a correctness issue.

The impact can become very large as the sizes of the cross-joined tables grow. In this reproduction, a small dataset already creates a 50,000,000-row Cartesian product. The original query takes about 3.4s median, while the equivalent rewrite takes about 780µs median.

The performance gap is caused by the optimizer evaluating the full cross product before `DISTINCT` / `TOP-K`, even though the output and ordering depend only on one table and the other cross-joined tables can be reduced to non-emptiness checks.

Jira issue: CRDB-65623

Start by running distinct_order_limit_cross_join_early_stop_median.sql with cockroach sql, then compare the original and EXISTS-rewrite plans using EXPLAIN (OPT) and EXPLAIN ANALYZE. Use the attached result file as the baseline. Done means the original query avoids materializing the 50,000,000-row Cartesian product while preserving the equivalence check result.

Written by the indexing model from the issue text.