pingcap / pingcap/tidb

planner: cost model underestimates request fanout cost for `IndexJoin+IndexReader`

Open
#69,392 4 comments 0 reactions 0 assignees View on GitHub
epic/cost-model 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)

Please see the case below from our testing environment. There are 2 plans, an `IndexHashJoin` plan and a `MPP` plan. First, the estimation is pretty accurate.
Then we can see the `MPP` plan is 6x faster than the `IndexHashJoin` plan, but they have almost the same cost, which means our cost model can't distinguish their performance.
Actually, in the user's environment, the `IndexHashJoin` cost is even smaller than `MPP`, and the optimizer can't select the optimal plan.

```
EXPLAIN ANALYZE FORMAT='VERBOSE'
SELECT
`o`.`sequential_id`,
`o`.`label`
FROM `obj_38m` `o`
WHERE
`o`.`workspace_id` = ?
AND (
`o`.`obj_tid` IN (?, ?, ?, ?, ?)
AND (
`o`.`tvalue_24` = ?
AND `o`.`obj_tid` IN (?, ?, ?, ?, ?)
)
AND EXISTS (
SELECT 1
FROM `obj_relationship_38m` `subR`
INNER JOIN `obj_38m` `subO1`
ON `subR`.`object_id` = `subO1`.`id`
AND `subO1`.`obj_tid` IN (?, ?, ?, ?, ?, ?, ?, ?, ?)
WHERE
`subR`.`workspace_id` = ?
AND (
`o`.`id` = `subR`.`referenced_object_id`
AND `subO1`.`workspace_id` = ?
AND (
`subO1`.`tvalue_8` = ?
AND `subO1`.`obj_tid` IN (?, ?, ?, ?, ?)
)
)
)
)
ORDER BY `o`.`label` ASC
LIMIT ?
OFFSET ?;
```

Image

The `IndexHashJoin` plan triggered lots of requests and caused this bottleneck, but the cost model is unaware of the request fanout.
Now the cost formula for `IndexJoin` is like `build-rows / batch-size * probe-cost`.
And `IndexReader` cost is like `scan-rows * scan-factor + total-bytes * net-factor`.
So the whole cost is like `build-rows / batch-size * (scan-rows * scan-factor + total-bytes * net-factor)`
In this case, `IndexJoin` calls `IndexReader` thousands of times, and triggers thousands of requests, but **the cost of these requests is missing in the cost formula**.

For all `DataSource` operators, only `IndexLookup` proactively considers the request cost with `build-rows/batch-size * num-ranges *request factor`.
All other `DataSource` operators `IndexReader/TableReader/IndexMerge/PointGet/BatchPointGet` don't consider request cost. Then if there is an `IndexJoin` or `Apply` above these operators, the cost model might miss the request fanout and underestimate their costs.

Image

Now `tidb_index_join_double_read_penalty_cost_rate` can mitigate this problem for `IndexJoin`, but it's disabled by default.

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

`MPP` cost should be much smaller than `IndexJoin` cost.

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

They have almost the same plan cost.

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

Master

Contributor guide

Open the contributing guide

Research direction

Start by tracing the cost formulas for IndexJoin, Apply, and the DataSource operators IndexReader, TableReader, IndexMerge, PointGet, and BatchPointGet, focusing on the existing IndexLookup request-cost handling. Reproduce the reported plan comparison with EXPLAIN ANALYZE and verify that the resulting costs account for request fanout and distinguish the MPP plan from the IndexHashJoin plan.

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.