sql/opt: join cardinality overestimation for nearly disjoint skewed keys causes a ~26x slower full-scan hash-join plan

**Describe the problem**

On CockroachDB v26.2.2, the optimizer severely overestimates join cardinalities for a three-table equality join whose join-key domains are highly skewed and nearly disjoint.

The default plan uses two hash joins and performs full scans of all three inputs:

```text
Hash Join on t3.c0 = t1.c0
├── Full Scan t1@t1_c0_lookup_idx
└── Hash Join on t3.c3 = t0.c3
├── Full Scan t0@t0_c3_lookup_idx
└── Full Scan t3
````

A semantically equivalent plan using two forced lookup joins is much faster:

```text
Scan t3
-> Lookup Join into t0@t0_c3_lookup_idx
-> Lookup Join into t1@t1_c0_lookup_idx
```

Explicit statistics and histograms were collected on all four join columns.

The base-table cardinalities are estimated correctly, but the join cardinalities are overestimated by several orders of magnitude:

| Expression | Estimated rows | Actual rows | Overestimation |
| ----------------------------- | -------------: | ----------: | -------------: |
| `t3 JOIN t0 ON t3.c3 = t0.c3` | 20,003 | 6 | ~3,334x |
| Final three-table join | 1,581,985 | 12 | ~131,832x |

The optimizer assigns the following costs:

| Plan | Estimated cost |
| ----------------------- | -------------: |
| Default hash-join plan | 1,451,218.54 |
| Forced lookup-join plan | 4,125,055.99 |

The optimizer therefore estimates the lookup-join plan to be approximately 2.84x more expensive.

However, three `EXPLAIN ANALYZE` executions produced the following results:

| Plan | Execution times | Median | KV rows decoded | KV bytes |
| ------------------- | ---------------------- | -----: | --------------: | -------: |
| Default | 694 ms, 703 ms, 676 ms | 694 ms | 1,320,015 | 60 MiB |
| Forced lookup joins | 26 ms, 27 ms, 30 ms | 27 ms | 20,015 | 1.5 MiB |

The forced lookup-join plan is therefore approximately 25.7x faster and reads approximately 66x fewer KV rows.

The data distribution has the following characteristics:

* `t0.c3` has 300,003 distinct values.
* `t3.c3` has 4 distinct values.
* The dominant `t3.c3` value does not occur in `t0.c3`.
* Only three rare `t3.c3` values overlap with `t0.c3`.
* `t1.c0` has 4 distinct values and is heavily concentrated on one dominant value.
* `t3.c0` has 20,003 distinct values.
* The dominant `t1.c0` value does not occur in `t3.c0`.
* Only three rare `t1.c0` values overlap with `t3.c0`.
* Each overlapping key produces only a small number of matching rows.

This appears to be primarily a join-domain overlap or join-fanout estimation issue.

The overestimated cardinalities make the lookup joins appear prohibitively expensive, causing the optimizer to prefer full index scans and hash joins.

I am not asserting that the base lookup-join cost formula is independently incorrect. Lookup-join costing may amplify the problem, but this testcase directly demonstrates severe join cardinality overestimation and a resulting physical-plan misranking.

---

**To Reproduce**

1. Start a local single-node CockroachDB v26.2.2 cluster.

2. Run the attached SQL testcase:

```bash
cockroach sql --insecure --host=localhost:26257 \
< crdb_skewed_nearly_disjoint_join_lookup_costing.sql \
> crdb_skewed_nearly_disjoint_join_lookup_costing_result.txt 2>&1
```

3. In the output, locate the following sections:

```text
DEFAULT PLAN - EXPLAIN
DEFAULT PLAN - EXPLAIN ANALYZE RUN 1 OF 3
DEFAULT PLAN - EXPLAIN ANALYZE RUN 2 OF 3
DEFAULT PLAN - EXPLAIN ANALYZE RUN 3 OF 3

FORCED LOOKUP PLAN - EXPLAIN
FORCED LOOKUP PLAN - EXPLAIN ANALYZE RUN 1 OF 3
FORCED LOOKUP PLAN - EXPLAIN ANALYZE RUN 2 OF 3
FORCED LOOKUP PLAN - EXPLAIN ANALYZE RUN 3 OF 3
```

4. Compare:

* Estimated optimizer costs.
* Estimated and actual row counts.
* Execution times.
* KV rows decoded.
* KV bytes read.

The default query is:

```sql
SELECT
t0.c4 AS ref0,
t0.c3 AS ref1
FROM t3
JOIN t0
ON t3.c3 = t0.c3
JOIN t1
ON t3.c0 = t1.c0;
```

The semantically equivalent forced plan is:

```sql
SELECT
t0.c4 AS ref0,
t0.c3 AS ref1
FROM (
t3
INNER LOOKUP JOIN t0@t0_c3_lookup_idx
ON t3.c3 = t0.c3
)
INNER LOOKUP JOIN t1@t1_c0_lookup_idx
ON t3.c0 = t1.c0;
```

The relevant indexes are:

```sql
CREATE INDEX t0_c3_lookup_idx
ON t0 (c3)
STORING (c4);

CREATE INDEX t1_c0_lookup_idx
ON t1 (c0);
```

Explicit statistics are collected on every join key:

```sql
CREATE STATISTICS t0_c3_stats ON c3 FROM t0;
CREATE STATISTICS t1_c0_stats ON c0 FROM t1;
CREATE STATISTICS t3_c0_stats ON c0 FROM t3;
CREATE STATISTICS t3_c3_stats ON c3 FROM t3;
```

The attached SQL file contains the complete deterministic schema and data-generation steps.

Both queries return the same 12 rows.

The testcase also performs the following result validation:

```text
result_rows = 12
sum_ref0 = 24000000030
min_ref1 = match_key_000
max_ref1 = match_key_002
```

---

**Expected behavior**

The optimizer does not need to estimate the exact join cardinalities of 6 and 12 rows.

However, it should estimate the low overlap between these highly skewed and nearly disjoint join-key domains accurately enough to avoid ranking a plan that scans approximately 1.32 million KV rows above a lookup-join plan that reads approximately 20 thousand KV rows.

An efficient plan should use the available indexes to avoid full scans of `t0` and `t1`, or otherwise have performance reasonably comparable to the forced lookup-join plan.

Potential areas to investigate include:

* Estimation of overlap between highly skewed join-key domains.
* Non-overlapping high-frequency values across join inputs.
* Histogram or most-common-value overlap between both sides of an equality join.
* Containment assumptions used for equality-join selectivity.
* Robustness of lookup-join costing when join fanout estimates are highly uncertain.

---

**Additional data / screenshots**

I will attach the following files:

* `crdb_skewed_nearly_disjoint_join_lookup_costing.sql`

* Complete schema.
* Deterministic data generation.
* Index definitions.
* Explicit statistics collection.
* Result validation.
* Default and forced queries.
* One optimizer `EXPLAIN` followed by three `EXPLAIN ANALYZE` executions for each plan.

* `crdb_skewed_nearly_disjoint_join_lookup_costing_result.txt`

* Complete output from executing the testcase.
* Estimated optimizer costs.
* Estimated and actual row counts.
* All six measured executions.

[crdb_skewed_nearly_disjoint_join_lookup_costing_result.txt](https://github.com/user-attachments/files/29874361/crdb_skewed_nearly_disjoint_join_lookup_costing_result.txt)
[crdb_skewed_nearly_disjoint_join_lookup_costing.sql](https://github.com/user-attachments/files/29874360/crdb_skewed_nearly_disjoint_join_lookup_costing.sql)

Key results:

```text
Default plan:
estimated cost: 1,451,218.54
execution times: 694 ms, 703 ms, 676 ms
median execution time: 694 ms
rows decoded from KV: 1,320,015
KV bytes read: 60 MiB

Forced lookup-join plan:
estimated cost: 4,125,055.99
execution times: 26 ms, 27 ms, 30 ms
median execution time: 27 ms
rows decoded from KV: 20,015
KV bytes read: 1.5 MiB

Observed difference:
runtime improvement: ~25.7x
KV-row reduction: ~66x
```

There was no fatal error or correctness failure.

---

**Environment:**

* CockroachDB version: CockroachDB CCL v26.2.2
* Server OS: Ubuntu 22.04.4 LTS
* Client app: `cockroach sql`
* Cluster topology: local single-node test cluster
* Execution distribution: local
* Vectorized execution: enabled
* `reorder_joins_limit`: `8`
* `optimizer_always_use_histograms`: `on`

---

**Additional context**

The impact is a stable and substantial performance difference caused by physical-plan selection.

The default plan:

* Scans all 1,000,006 rows from `t1`.
* Scans all 300,006 rows from `t0`.
* Scans all 20,003 rows from `t3`.
* Decodes 1,320,015 KV rows in total.
* Has a median execution time of 694 ms.

The forced lookup-join plan:

* Scans the 20,003 rows from `t3`.
* Retrieves only 6 matching KV rows from `t0`.
* Retrieves only 6 matching KV rows from `t1`.
* Decodes 20,015 KV rows in total.
* Has a median execution time of 27 ms.

The performance difference reproduces consistently across the initial custom plans and the reused generic plans.

Planning time is negligible compared with execution time.

The difference is caused by the amount of storage work performed, rather than by planning overhead, result size, or a correctness difference.

Jira issue: CRDB-65648

Start by running crdb_skewed_nearly_disjoint_join_lookup_costing.sql and comparing the default and forced plans in the attached result file. Investigate the optimizer's equality-join cardinality estimates, histogram or most-common-value overlap handling, and lookup-join costing. Done means the nearly disjoint skewed-key case no longer ranks the full-scan hash-join plan above an efficient indexed alternative.

Written by the indexing model from the issue text.