pingcap / pingcap/tidb

planner: similar estimated cost but 3x runtime gap for HashJoin join orders under TopN

Open
#69,564 2 comments 0 reactions 0 assignees View on GitHub
contribution severity/moderate sig/planner type/bug
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Bug Report

Please answer these questions before submitting your issue. Thanks!

### 1. Minimal reproduce step (Required)

Run the attached SQL script:

```bash
mysql -h 127.0.0.1 -P 4000 -u root --comments --table \
< tidb_hashjoin_topn_cost_model_blindspot_repro.sql \
> tidb_hashjoin_topn_cost_model_blindspot_repro_result.txt 2>&1
```

[tidb_hashjoin_topn_cost_model_blindspot_repro.sql](https://github.com/user-attachments/files/29541632/tidb_hashjoin_topn_cost_model_blindspot_repro.sql)
[tidb_hashjoin_topn_cost_model_blindspot_repro_result.txt](https://github.com/user-attachments/files/29541631/tidb_hashjoin_topn_cost_model_blindspot_repro_result.txt)

The attached script creates three tables (`t0`, `t2`, `t3`), builds indexes, runs `ANALYZE TABLE ... ALL COLUMNS`, and compares the default plan with a hinted plan.

The query is:

```sql
SELECT t0.c4 AS ref0, t2.c0, t0.c2, t0.c0
FROM t2
LEFT JOIN t3 ON t2.c0 = t3.c0
INNER JOIN t0 ON t3.c0 = t0.c0
WHERE (t2.c5 < 0) OR (t3.c1 < 0)
ORDER BY t3.c2 ASC
LIMIT 2;
```

The hinted query is:

```sql
SELECT /*+ LEADING(t2, t3, t0) */ t0.c4 AS ref0, t2.c0, t0.c2, t0.c0
FROM t2
LEFT JOIN t3 ON t2.c0 = t3.c0
INNER JOIN t0 ON t3.c0 = t0.c0
WHERE (t2.c5 < 0) OR (t3.c1 < 0)
ORDER BY t3.c2 ASC
LIMIT 2;
```

The table cardinalities are:

```text
t0: 890 rows, 113 distinct c0
t2: 1690 rows, 31 distinct c0
t3: 850 rows, 27 distinct c0
```

The join/filter cardinalities are:

```text
t3 JOIN t0: 6786 rows
t2 JOIN t3: 139842 rows
filtered t2 JOIN t3 after (t2.c5 < 0 OR t3.c1 < 0): 2 rows
final result count: 2 rows
```

### 2. What did you expect to see? (Required)

I expected the cost model to reflect the actual runtime difference between the two HashJoin join orders more accurately.

In this case, the default plan and the hinted plan have very close estimated costs:

```text
default cost: 18925607.23
hinted cost: 19468638.53
hinted/default cost ratio: 1.0287x
```

So the hinted plan is estimated to be only about 2.87% more expensive than the default plan.

However, the actual runtime difference is much larger. The hinted plan is more than 3x faster in repeated `EXPLAIN ANALYZE` runs. Therefore, I would expect either:

1. the optimizer to choose the faster HashJoin join order, or
2. the cost model to assign a clearly lower estimated cost to the faster join order.

This may be related to `sig/planner` / `planner/performance`. The main point is the cost-model blind spot under `ORDER BY ... LIMIT`: two HashJoin join orders have almost the same estimated cost, but their actual runtimes differ by more than 3x.

### 3. What did you see instead (Required)

TiDB chooses the slower default HashJoin join order, while another HashJoin join order has a very similar estimated cost but runs much faster.

The default plan is:

```text
(t3 JOIN t0) JOIN t2
```

The hinted plan is:

```text
(t2 JOIN t3) JOIN t0
```

The estimated costs are very close:

```text
default cost: 18925607.23
hinted cost: 19468638.53
hinted/default cost ratio: 1.0287x
```

So the hinted plan is estimated to be only about 2.87% more expensive.

But repeated `EXPLAIN ANALYZE` runs show a much larger runtime gap:

```text
default run 1: 95.1 ms
default run 2: 103.7 ms
default run 3: 117.5 ms

hinted run 1: 30.4 ms
hinted run 2: 30.8 ms
hinted run 3: 31.0 ms
```

The median runtime ratio is:

```text
median(default) / median(hinted) = 103.7 ms / 30.8 ms = 3.37x
```

The average runtime ratio is:

```text
avg(default) / avg(hinted) = 105.4 ms / 30.7 ms = 3.43x
```

In other words, the estimated costs differ by only about 2.87%, but the actual runtime differs by about 237% using the median runtime ratio. The runtime relative gap is roughly:

```text
(3.37 - 1) / (1.0287 - 1) ≈ 82.6x
```

larger than the estimated-cost relative gap.

This suggests that the cost model does not capture the real runtime difference between these two HashJoin join orders.

The predicate:

```sql
(t2.c5 < 0) OR (t3.c1 < 0)
```

only depends on `t2` and `t3`. The hinted plan joins `t2` and `t3` first, so this predicate is evaluated earlier. In this data set, most `t2`/`t3` matches are rejected by this predicate, and only 2 rows survive.

The default plan joins `t3` and `t0` first, and evaluates the `t2`/`t3` predicate later. This causes significantly more HashJoin probe work at runtime, but the estimated cost remains very close to the hinted plan.

I also included a control query with `LEADING(t3,t0,t2)`. It reproduces the slow shape and has runtime similar to the default plan.

### 4. What is your TiDB version? (Required)

```text
Release Version: v8.5.0
Edition: Community
Git Commit Hash: d13e52ed6e22cc5789bed7c64c861578cd2ed55b
Git Branch: HEAD
UTC Build Time: 2024-12-18 02:26:06
GoVersion: go1.23.3
Race Enabled: false
Check Table Before Drop: false
Store: tikv
```

Contributor guide

Open the contributing guide

Research direction

Start by running the attached tidb_hashjoin_topn_cost_model_blindspot_repro.sql script and compare the default, hinted, and control plans with EXPLAIN ANALYZE. Then inspect the planner/performance and sig/planner areas for how ORDER BY ... LIMIT, predicate pushdown, and HashJoin costs are estimated; done means the two join orders receive cost estimates that better reflect their measured runtime or the faster plan is selected.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.