pingcap / pingcap/tidb

Cost Model v2: `IndexHashJoin` cost underestimation

Open
#65,556 2 comments 0 reactions 0 assignees View on GitHub
epic/cost-model report/customer 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)
```
set @@tidb_cost_model_version=2;

drop table if exists t1, t2;
create table t1(a int, b int, key(a));
create table t2(a int, b int, key idx_a(a)); -- only prefix index on (a)

insert into t1 values (1,1),(2,2),(3,3),(4,4),(5,5);
insert into t2 values (1,1),(2,2),(3,3),(4,4),(5,5);
analyze table t1, t2;

-- force IndexHashJoin
explain format='cost_trace'
select /*+ inl_hash_join(t1, t2), use_index(t2, idx_a) */
*
from t1 join t2
on t1.a=t2.a and t1.b=t2.b;
```

### 2. What did you expect to see? (Required)
- IndexHashJoin cost formula should include probe-side hash cost (e.g. hashprobe(...)).
- Hash key count should reflect the actual hash key set used in execution (e.g. hashkey(...*2*...) for join on (a,b)).

The IndexHashJoin operator (executed as IndexNestedLoopHashJoin) follows a logic where each task builds a hash table using outer rows, and then for every retrieved inner row, it performs a hash key calculation and a probe (including key equality checks for collisions). From a cost perspective, the complexity consists of Build Cost `O(probeRowsTotal* nKeys)` and Probe Cost `O(probeRowsTotal* nKeys)`, where probeRowsTotal is the total number of rows returned from the inner side. When the inner index only matches a prefix of the join keys or has low selectivity, probeRowsTotal can reach millions, making the probe phase the dominant CPU cost. If the cost formula omits hashprobe(...) and the corresponding hashkey(probeRowsTotal * ...), this major cost component is treated as zero, leading to an order-of-magnitude underestimation and causing the optimizer to incorrectly favor IndexHashJoin.

### 3. What did you see instead (Required)
```
+-----------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------+--------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | estCost | costFormula | task | access object | operator info |
+-----------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------+--------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
| IndexHashJoin_15 | 5.00 | 14136.21 | ((cpu(10*3*tidb_cpu_factor(49.9))) + (((((net(5*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((scan(5*logrowsize(32)*tikv_scan_factor(40.7)))*1.00))/15.00) + (((((net(5*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(5*filters(1)*tikv_cpu_factor(49.9))) + ((scan(5*logrowsize(48)*tikv_scan_factor(40.7)))*1.00)))/15.00) + ((double-read-cpu(5*tidb_cpu_factor(49.9))) + (doubleRead(tasks(0.008)*tidb_request_factor(6e+06)))))/5.00))*1.00) + (cpu(5*filters(0)*tidb_cpu_factor(49.9))) + (cpu(5*10*tidb_cpu_factor(49.9))) + (((((((((net(1*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(32)*tikv_scan_factor(40.7)))*1.00)))/15.00) + (((((net(1*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(48)*tikv_scan_factor(40.7)))*1.00)))/15.00) + ((double-read-cpu(1*tidb_cpu_factor(49.9))) + (doubleRead(tasks(0.0016)*tidb_request_factor(6e+06)))))/5.00))*1.00)*5.00)/6.00) + (cpu(5*filters(0)*tidb_cpu_factor(49.9))) + ((hashkey(5*0*tidb_cpu_factor(49.9))) + (hashmem(5*32*tidb_mem_factor(0.2))) + (hashbuild(5*tidb_cpu_factor(49.9)))))/5.00))*1.00 | root | | inner join, inner:IndexLookUp_35, outer key:oa_doc.t1.a, inner key:oa_doc.t2.a, equal cond:eq(oa_doc.t1.a, oa_doc.t2.a), eq(oa_doc.t1.b, oa_doc.t2.b) |
| ├─IndexLookUp_30(Build) | 5.00 | 9761.95 | ((((net(5*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((scan(5*logrowsize(32)*tikv_scan_factor(40.7)))*1.00))/15.00) + (((((net(5*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(5*filters(1)*tikv_cpu_factor(49.9))) + ((scan(5*logrowsize(48)*tikv_scan_factor(40.7)))*1.00)))/15.00) + ((double-read-cpu(5*tidb_cpu_factor(49.9))) + (doubleRead(tasks(0.008)*tidb_request_factor(6e+06)))))/5.00))*1.00 | root | | |
| │ ├─IndexFullScan_27(Build) | 5.00 | 1017.50 | (scan(5*logrowsize(32)*tikv_scan_factor(40.7)))*1.00 | cop[tikv] | table:t1, index:a(a) | keep order:false |
| │ └─Selection_29(Probe) | 5.00 | 1386.04 | (cpu(5*filters(1)*tikv_cpu_factor(49.9))) + ((scan(5*logrowsize(48)*tikv_scan_factor(40.7)))*1.00) | cop[tikv] | | not(isnull(oa_doc.t1.b)) |
| │ └─TableRowIDScan_28 | 5.00 | 1136.54 | (scan(5*logrowsize(48)*tikv_scan_factor(40.7)))*1.00 | cop[tikv] | table:t1 | keep order:false |
| └─IndexLookUp_35(Probe) | 5.00 | 1955.72 | ((((net(1*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(32)*tikv_scan_factor(40.7)))*1.00)))/15.00) + (((((net(1*rowsize(16.25)*tidb_kv_net_factor(3.96))) + ((cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(48)*tikv_scan_factor(40.7)))*1.00)))/15.00) + ((double-read-cpu(1*tidb_cpu_factor(49.9))) + (doubleRead(tasks(0.0016)*tidb_request_factor(6e+06)))))/5.00))*1.00 | root | | |
| ├─Selection_33(Build) | 5.00 | 253.40 | (cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(32)*tikv_scan_factor(40.7)))*1.00) | cop[tikv] | | not(isnull(oa_doc.t2.a)) |
| │ └─IndexRangeScan_31 | 5.00 | 203.50 | (scan(1*logrowsize(32)*tikv_scan_factor(40.7)))*1.00 | cop[tikv] | table:t2, index:idx_a(a) | range: decided by [eq(oa_doc.t2.a, oa_doc.t1.a)], keep order:false |
| └─Selection_34(Probe) | 5.00 | 277.21 | (cpu(1*filters(1)*tikv_cpu_factor(49.9))) + ((scan(1*logrowsize(48)*tikv_scan_factor(40.7)))*1.00) | cop[tikv] | | not(isnull(oa_doc.t2.b)) |
| └─TableRowIDScan_32 | 5.00 | 227.31 | (scan(1*logrowsize(48)*tikv_scan_factor(40.7)))*1.00 | cop[tikv] | table:t2 | keep order:false |
+-----------------------------------+---------+----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------+--------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
```
- IndexHashJoin cost formula misses hashprobe(...) and shows hashkey(...*0*...) in `hashkey(5*0*tidb_cpu_factor(49.9))`.

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

lastest master

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.