pingcap / pingcap/tidb

planner/joinorder: synthetic-cartesian joins should retain +Inf penalty in the second greedy round when CartesianJoinOrderThreshold <= 0

Open
#68,515 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Background

In `optimizeWithStart` (pkg/planner/core/joinorder/join_order.go), when the first greedy pass leaves remaining edges (e.g. a non-equi inner join such as `R1.c1 < R2.c2`), a second pass is triggered with `allowNoEQ = true`. To avoid `cumCost * 0 = 0` making non-EQ joins appear free, the code clamps `secondRoundFactor` to 1 when `CartesianJoinOrderThreshold <= 0`:

```go
secondRoundFactor := cartesianFactor
if secondRoundFactor <= 0 {
secondRoundFactor = 1
}
```

This override is applied uniformly inside `greedyConnectJoinNodes` via `applyCartesianFactor`, affecting **both** genuine non-equi join candidates **and** synthetic cartesian candidates produced by `TryCreateCartesianCheckResult`. The result is that synthetic cartesian joins get cost `= originalCost * 1` instead of `+Inf`, which can make them cheaper than a real non-equi join and cause the reorder to pick the synthetic cartesian merge first — defeating the intended "push cartesian joins to the final stitch" behavior.

## Minimal reproduce scenario

```sql
-- CartesianJoinOrderThreshold <= 0 (e.g. tidb_opt_cartesian_join_threshold = 0)
-- Non-equi inner join between R1/R2, plus an unrelated table R3
SELECT * FROM R1
INNER JOIN R2 ON R1.c1 < R2.c2 -- non-equi, first round skips it
CROSS JOIN R3; -- R3 has no join condition with R1 or R2
```

**Expected:** Second round connects R1⋈R2 via the non-equi edge first; the synthetic R3 cartesian join is deferred to the final bushy-tree stitch (cost = +Inf).

**Actual:** With `secondRoundFactor = 1`, the synthetic R3 cartesian candidate costs `rowCount(R3) * 1`, which may be **lower** than the non-equi R1⋈R2 candidate. The reorder then picks the cartesian merge early and can fall back to the original plan even though a valid non-equi merge existed.

## Proposed fix

Inside `greedyConnectJoinNodes`, distinguish between a synthetic-cartesian result (`checkResult.SyntheticCartesian() == true`, already exposed by `conflict_detector.go`) and a real non-equi edge, and apply the penalty selectively:

- **Real non-equi edge** with `secondRoundFactor = 1`: apply cost × 1 (acceptable, avoids free joins).
- **Synthetic cartesian** with `secondRoundFactor = 1` but original `cartesianFactor <= 0`: preserve `+Inf` so cartesian joins remain deferred.

The `SyntheticCartesian()` method already exists on `CheckConnectionResult` (added in this PR), so the hook is in place.

## Related

- PR that introduced the multi-seed greedy reorder and the second-round clamp: https://github.com/pingcap/tidb/pull/68340
- Original review comment: https://github.com/pingcap/tidb/pull/68340#discussion_r3231330586
- Requested by: @AilinKid

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.