pingcap / pingcap/tidb

planner: cost model ver2 charges the descending scan factor for rows a limit never reads

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

Description

## Bug Report

Cost model ver2 charges the descending scan factor over the whole estimated range even when a
small limit stops the scan after a few rows, so an ordered descending scan is priced out of plans
where the ascending equivalent is chosen. Cost model ver1 does not have this problem.

### 1. Minimal reproduce step (Required)

```sql
CREATE TABLE t (a int NOT NULL, b int NOT NULL, PRIMARY KEY (a, b) CLUSTERED);
-- 3000 rows, 3 distinct values of a
INSERT INTO t VALUES (0,0),(1,1),(2,2),(0,3),(1,4),(2,5) /* ... */;
ANALYZE TABLE t ALL COLUMNS;

EXPLAIN format='verbose' SELECT /*+ ORDER_INDEX(t, `PRIMARY`) */ b FROM t WHERE a = 1 ORDER BY b LIMIT 1;
EXPLAIN format='verbose' SELECT /*+ ORDER_INDEX(t, `PRIMARY`) */ b FROM t WHERE a = 1 ORDER BY b DESC LIMIT 1;
```

`ORDER_INDEX` is used only to hold the ordered scan in both plans so their costs can be compared
directly.

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

Both scans read the same estimated rows (10.99) and stop at the same limit, so the descending scan
should not cost more:

| `LIMIT` | ascending `TableRangeScan` estCost | descending `TableRangeScan` estCost |
| --- | --- | --- |
| 1 | 2236.47 | 2236.47 |
| 20000 | 203500.00 | 305250.00 |

The premium is expected above `cost.SmallScanThreshold`, where the scan may really read many rows.

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

The descending scan is charged 1.5x at `LIMIT 1` as well — both rows report `estRows` 10.99, so the
whole difference is the factor:

| `LIMIT` | ascending estCost | descending estCost |
| --- | --- | --- |
| 1 | 2236.47 | **3354.70** |
| 20000 | 203500.00 | 305250.00 |

3354.70 / 2236.47 = 1.4999 = `tikv_desc_scan_factor` (61.05) / `tikv_scan_factor` (40.70).

`getTaskScanFactorVer2` in `pkg/planner/core/plan_cost_ver2.go` returns `TiKVDescScan` whenever the
scan is descending, with no regard for how many rows the scan may actually read:

```go
if desc {
return defaultVer2Factors.TiKVDescScan
}
return defaultVer2Factors.TiKVScan
```

Cost model ver1 has drawn the line at `cost.SmallScanThreshold` since the factor was introduced
(`getPlanCostVer14PhysicalTableScan` / `getPlanCostVer14PhysicalIndexScan`):

```go
if p.Desc && p.Prop != nil && p.Prop.ExpectedCnt >= cost.SmallScanThreshold {
scanFactor = p.SCtx().GetSessionVars().GetDescScanFactor(p.Table)
}
```

with the comment on `SmallScanThreshold` stating the intent directly: *"So when a limit exists, we
don't apply the DescScanFactor."*

Plan-level impact: MIN is optimized but MAX is not

The premium decides the plan whenever the ordered scan and the sorting alternative estimate the
same number of rows. That happens for a correlated equality (see #70216), where the range is
rebuilt per execution and the estimate is not reduced by the limit. With that fix applied, `MIN`
reads one row from an ordered scan while `MAX` still sorts the whole range:

```
MIN(k2): StreamAgg -> Limit(count:1) -> TableRangeScan keep order:true
MAX(k2): StreamAgg -> TopN(count:1) -> TableRangeScan keep order:false
```

`ORDER_INDEX` produces the descending ordered plan with no warnings, confirming the optimizer can
build it and is only rejecting it on cost.

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

master at 93f713cf55 (`Release Version: v9.0.0-beta.2.pre`). Not version specific: ver2 has charged
the factor unconditionally since it was added, and ver2 is the default cost model.

Contributor guide

Open the contributing guide

Research direction

Start in pkg/planner/core/plan_cost_ver2.go at getTaskScanFactorVer2, then compare the ver1 table- and index-scan cost functions named in the report. Reproduce the two EXPLAIN queries with LIMIT 1 and a large LIMIT to compare ascending and descending costs. Done means the descending factor is not charged for scans below cost.SmallScanThreshold, while the existing premium remains for larger scans.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.