pingcap / pingcap/tidb

Join's cost calculation during join reorder mismatches the real physical cost of index join

Open
#38,660 3 comments 0 reactions 0 assignees View on GitHub
affects-4.0 affects-5.0 affects-5.1 affects-5.2 affects-5.3 affects-5.4 affects-6.0 affects-6.1 affects-6.2 affects-6.3 affects-6.4 affects-6.5 affects-7.1 affects-7.5 affects-8.1 epic/cardinality-estimation 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)

Plan changed in Job 25B

```sql
mysql> explain format='verbose' SELECT MIN(mi.info) AS movie_budget, MIN(mi_idx.info) AS movie_votes, MIN(n.name) AS male_writer, MIN(t.title) AS violent_movie_title FROM cast_info AS ci, info_type AS it1, info_type AS it2, keyword AS k, movie_info AS mi, movie_info_idx AS mi_idx, movie_keyword AS mk, name AS n, title AS t WHERE ci.note in ('(writer)', '(head writer)', '(written by)', '(story)', '(story editor)') AND it1.info = 'genres' AND it2.info = 'votes' AND k.keyword in ('murder', 'blood', 'gore', 'death', 'female-nudity') AND mi.info = 'Horror' AND n.gender = 'm' AND t.production_year > 2010 AND t.title like 'Vampire%' AND t.id = mi.movie_id AND t.id = mi_idx.movie_id AND t.id = ci.movie_id AND t.id = mk.movie_id AND ci.movie_id = mi.movie_id AND ci.movie_id = mi_idx.movie_id AND ci.movie_id = mk.movie_id AND mi.movie_id = mi_idx.movie_id AND mi.movie_id = mk.movie_id AND mi_idx.movie_id = mk.movie_id AND n.id = ci.person_id AND it1.id = mi.info_type_id AND it2.id = mi_idx.info_type_id AND k.id = mk.keyword_id;
+---------------------------------------------------------------------+---------+-----------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | estCost | task | access object | operator info |
+---------------------------------------------------------------------+---------+-----------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| StreamAgg_44 | 1.00 | 181.33 | root | | funcs:min(imdb.movie_info.info)->Column#49, funcs:min(imdb.movie_info_idx.info)->Column#50, funcs:min(imdb.name.name)->Column#51, funcs:min(imdb.title.title)->Column#52 |
| └─Projection_45 | 0.00 | 181.33 | root | | imdb.movie_info.info, imdb.movie_info_idx.info, imdb.name.name, imdb.title.title |
| └─IndexJoin_53 | 0.00 | 163.33 | root | | inner join, inner:TableReader_49, outer key:imdb.movie_keyword.keyword_id, inner key:imdb.keyword.id, equal cond:eq(imdb.movie_keyword.keyword_id, imdb.keyword.id) |
| ├─IndexHashJoin_65(Build) | 0.00 | 145.33 | root | | inner join, inner:IndexLookUp_62, outer key:imdb.cast_info.movie_id, inner key:imdb.movie_keyword.movie_id, equal cond:eq(imdb.cast_info.movie_id, imdb.movie_keyword.movie_id), eq(imdb.movie_info.movie_id, imdb.movie_keyword.movie_id), eq(imdb.movie_info_idx.movie_id, imdb.movie_keyword.movie_id), eq(imdb.title.id, imdb.movie_keyword.movie_id) |
| │ ├─IndexJoin_80(Build) | 0.00 | 127.33 | root | | inner join, inner:TableReader_76, outer key:imdb.cast_info.person_id, inner key:imdb.name.id, equal cond:eq(imdb.cast_info.person_id, imdb.name.id) |
| │ │ ├─IndexHashJoin_93(Build) | 0.00 | 109.33 | root | | inner join, inner:IndexLookUp_90, outer key:imdb.movie_info.movie_id, inner key:imdb.cast_info.movie_id, equal cond:eq(imdb.movie_info.movie_id, imdb.cast_info.movie_id), eq(imdb.movie_info_idx.movie_id, imdb.cast_info.movie_id), eq(imdb.title.id, imdb.cast_info.movie_id) |
| │ │ │ ├─IndexJoin_109(Build) | 0.00 | 91.33 | root | | inner join, inner:TableReader_105, outer key:imdb.movie_info.info_type_id, inner key:imdb.info_type.id, equal cond:eq(imdb.movie_info.info_type_id, imdb.info_type.id) |
| │ │ │ │ ├─IndexHashJoin_122(Build) | 0.00 | 73.33 | root | | inner join, inner:IndexLookUp_119, outer key:imdb.movie_info_idx.movie_id, inner key:imdb.movie_info.movie_id, equal cond:eq(imdb.movie_info_idx.movie_id, imdb.movie_info.movie_id), eq(imdb.title.id, imdb.movie_info.movie_id) |
| │ │ │ │ │ ├─IndexJoin_138(Build) | 0.00 | 55.33 | root | | inner join, inner:TableReader_134, outer key:imdb.movie_info_idx.info_type_id, inner key:imdb.info_type.id, equal cond:eq(imdb.movie_info_idx.info_type_id, imdb.info_type.id) |
| │ │ │ │ │ │ ├─IndexJoin_171(Build) | 0.00 | 37.33 | root | | inner join, inner:IndexLookUp_170, outer key:imdb.title.id, inner key:imdb.movie_info_idx.movie_id, equal cond:eq(imdb.title.id, imdb.movie_info_idx.movie_id) |
| │ │ │ │ │ │ │ ├─IndexLookUp_206(Build) | 0.00 | 19.33 | root | | |
| │ │ │ │ │ │ │ │ ├─IndexRangeScan_203(Build) | 0.00 | 0.00 | cop[tikv] | table:t, index:title_idx_title(title) | range:["Vampire","Vampirf"), keep order:false |
| │ │ │ │ │ │ │ │ └─Selection_205(Probe) | 0.00 | 0.00 | cop[tikv] | | gt(imdb.title.production_year, 2010), like(imdb.title.title, "Vampire%", 92) |
| │ │ │ │ │ │ │ │ └─TableRowIDScan_204 | 0.00 | 0.00 | cop[tikv] | table:t | keep order:false |
| │ │ │ │ │ │ │ └─IndexLookUp_170(Probe) | 0.00 | 38.22 | root | | |
| │ │ │ │ │ │ │ ├─IndexRangeScan_168(Build) | 0.00 | 71.25 | cop[tikv] | table:mi_idx, index:movie_id_movie_info_idx(movie_id) | range: decided by [eq(imdb.movie_info_idx.movie_id, imdb.title.id)], keep order:false, stats:pseudo |
| │ │ │ │ │ │ │ └─TableRowIDScan_169(Probe) | 0.00 | 105.00 | cop[tikv] | table:mi_idx | keep order:false, stats:pseudo |
| │ │ │ │ │ │ └─TableReader_134(Probe) | 0.00 | 5.07 | root | | data:Selection_133 |
| │ │ │ │ │ │ └─Selection_133 | 0.00 | 55.53 | cop[tikv] | | eq(imdb.info_type.info, "votes") |
| │ │ │ │ │ │ └─TableRangeScan_132 | 0.00 | 52.53 | cop[tikv] | table:it2 | range: decided by [imdb.movie_info_idx.info_type_id], keep order:false |
| │ │ │ │ │ └─IndexLookUp_119(Probe) | 0.00 | 71243.88 | root | | |
| │ │ │ │ │ ├─IndexRangeScan_116(Build) | 0.00 | 173846.11 | cop[tikv] | table:mi, index:movie_info_idx_mid(movie_id) | range: decided by [eq(imdb.movie_info.movie_id, imdb.movie_info_idx.movie_id)], keep order:false |
| │ │ │ │ │ └─Selection_118(Probe) | 0.00 | 389598.29 | cop[tikv] | | eq(imdb.movie_info.info, "Horror") |
| │ │ │ │ │ └─TableRowIDScan_117 | 0.00 | 380448.50 | cop[tikv] | table:mi | keep order:false |
| │ │ │ │ └─TableReader_105(Probe) | 0.00 | 5.05 | root | | data:Selection_104 |
| │ │ │ │ └─Selection_104 | 0.00 | 55.53 | cop[tikv] | | eq(imdb.info_type.info, "genres") |
| │ │ │ │ └─TableRangeScan_103 | 0.00 | 52.53 | cop[tikv] | table:it1 | range: decided by [imdb.movie_info.info_type_id], keep order:false |
| │ │ │ └─IndexLookUp_90(Probe) | 0.00 | 10088.46 | root | | |
| │ │ │ ├─IndexRangeScan_87(Build) | 0.00 | 28831.26 | cop[tikv] | table:ci, index:cast_info_idx_mid(movie_id) | range: decided by [eq(imdb.cast_info.movie_id, imdb.movie_info.movie_id)], keep order:false |
| │ │ │ └─Selection_89(Probe) | 0.00 | 49893.25 | cop[tikv] | | in(imdb.cast_info.note, "(writer)", "(head writer)", "(written by)", "(story)", "(story editor)") |
| │ │ │ └─TableRowIDScan_88 | 0.00 | 48375.82 | cop[tikv] | table:ci | keep order:false |
| │ │ └─TableReader_76(Probe) | 0.00 | 11.88 | root | | data:Selection_75 |
| │ │ └─Selection_75 | 0.00 | 142.77 | cop[tikv] | | eq(imdb.name.gender, "m") |
| │ │ └─TableRangeScan_74 | 0.00 | 139.77 | cop[tikv] | table:n | range: decided by [imdb.cast_info.person_id], keep order:false |
| │ └─IndexLookUp_62(Probe) | 0.00 | 169.84 | root | | |
| │ ├─IndexRangeScan_60(Build) | 0.00 | 580.61 | cop[tikv] | table:mk, index:movie_keyword_idx_mid(movie_id) | range: decided by [eq(imdb.movie_keyword.movie_id, imdb.cast_info.movie_id)], keep order:false |
| │ └─TableRowIDScan_61(Probe) | 0.00 | 580.61 | cop[tikv] | table:mk | keep order:false |
| └─TableReader_49(Probe) | 0.00 | 6.10 | root | | data:Selection_48 |
| └─Selection_48 | 0.00 | 71.31 | cop[tikv] | | in(imdb.keyword.keyword, "murder", "blood", "gore", "death", "female-nudity") |
| └─TableRangeScan_47 | 0.00 | 68.31 | cop[tikv] | table:k | range: decided by [imdb.movie_keyword.keyword_id], keep order:false |
+---------------------------------------------------------------------+---------+-----------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
40 rows in set, 1 warning (0.02 sec)

(k * (((((((t*mi_idx) * it2) * mi) * it1) * ci) * n) *mk)

kan2 25B
mysql> explain format='verbose' SELECT MIN(mi.info) AS movie_budget, MIN(mi_idx.info) AS movie_votes, MIN(n.name) AS male_writer, MIN(t.title) AS violent_movie_title FROM cast_info AS ci, info_type AS it1, info_type AS it2, keyword AS k, movie_info AS mi, movie_info_idx AS mi_idx, movie_keyword AS mk, name AS n, title AS t WHERE ci.note in ('(writer)', '(head writer)', '(written by)', '(story)', '(story editor)') AND it1.info = 'genres' AND it2.info = 'votes' AND k.keyword in ('murder', 'blood', 'gore', 'death', 'female-nudity') AND mi.info = 'Horror' AND n.gender = 'm' AND t.production_year > 2010 AND t.title like 'Vampire%' AND t.id = mi.movie_id AND t.id = mi_idx.movie_id AND t.id = ci.movie_id AND t.id = mk.movie_id AND ci.movie_id = mi.movie_id AND ci.movie_id = mi_idx.movie_id AND ci.movie_id = mk.movie_id AND mi.movie_id = mi_idx.movie_id AND mi.movie_id = mk.movie_id AND mi_idx.movie_id = mk.movie_id AND n.id = ci.person_id AND it1.id = mi.info_type_id AND it2.id = mi_idx.info_type_id AND k.id = mk.keyword_id;
+-----------------------------------------------------------------+----------+------------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | estCost | task | access object | operator info |
+-----------------------------------------------------------------+----------+------------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| HashAgg_40 | 1.00 | 2312155.97 | root | | funcs:min(imdb.movie_info.info)->Column#49, funcs:min(imdb.movie_info_idx.info)->Column#50, funcs:min(imdb.name.name)->Column#51, funcs:min(imdb.title.title)->Column#52 |
| └─Projection_42 | 309.89 | 2311379.23 | root | | imdb.movie_info.info, imdb.movie_info_idx.info, imdb.name.name, imdb.title.title |
| └─IndexJoin_50 | 309.89 | 2311175.30 | root | | inner join, inner:TableReader_46, outer key:imdb.movie_keyword.keyword_id, inner key:imdb.keyword.id, equal cond:eq(imdb.movie_keyword.keyword_id, imdb.keyword.id) |
| ├─IndexHashJoin_62(Build) | 306.89 | 2307240.27 | root | | inner join, inner:IndexLookUp_59, outer key:imdb.cast_info.movie_id, inner key:imdb.movie_keyword.movie_id, equal cond:eq(imdb.cast_info.movie_id, imdb.movie_keyword.movie_id), eq(imdb.movie_info.movie_id, imdb.movie_keyword.movie_id), eq(imdb.movie_info_idx.movie_id, imdb.movie_keyword.movie_id), eq(imdb.title.id, imdb.movie_keyword.movie_id) |
| │ ├─IndexJoin_77(Build) | 30.13 | 2301025.88 | root | | inner join, inner:TableReader_73, outer key:imdb.cast_info.person_id, inner key:imdb.name.id, equal cond:eq(imdb.cast_info.person_id, imdb.name.id) |
| │ │ ├─IndexHashJoin_90(Build) | 30.13 | 2300466.75 | root | | inner join, inner:IndexLookUp_87, outer key:imdb.movie_info.movie_id, inner key:imdb.cast_info.movie_id, equal cond:eq(imdb.movie_info.movie_id, imdb.cast_info.movie_id), eq(imdb.movie_info_idx.movie_id, imdb.cast_info.movie_id), eq(imdb.title.id, imdb.cast_info.movie_id) |
| │ │ │ ├─HashJoin_111(Build) | 2.00 | 2280442.81 | root | | inner join, equal:[eq(imdb.movie_info_idx.info_type_id, imdb.info_type.id)] |
| │ │ │ │ ├─IndexLookUp_234(Build) | 2.00 | 48.60 | root | | |
| │ │ │ │ │ ├─IndexRangeScan_231(Build) | 2.00 | 132.06 | cop[tikv] | table:it2, index:info_type_info(info) | range:["votes","votes"], keep order:false |
| │ │ │ │ │ └─Selection_233(Probe) | 2.00 | 111.06 | cop[tikv] | | eq(imdb.info_type.info, "votes") |
| │ │ │ │ │ └─TableRowIDScan_232 | 2.00 | 105.06 | cop[tikv] | table:it2 | keep order:false |
| │ │ │ │ └─IndexJoin_116(Probe) | 8.67 | 2280369.01 | root | | inner join, inner:IndexLookUp_115, outer key:imdb.movie_info.movie_id, inner key:imdb.movie_info_idx.movie_id, equal cond:eq(imdb.movie_info.movie_id, imdb.movie_info_idx.movie_id), eq(imdb.title.id, imdb.movie_info_idx.movie_id) |
| │ │ │ │ ├─HashJoin_138(Build) | 6.94 | 2280032.41 | root | | inner join, equal:[eq(imdb.movie_info.movie_id, imdb.title.id)] |
| │ │ │ │ │ ├─IndexLookUp_221(Build) | 1.05 | 82.72 | root | | |
| │ │ │ │ │ │ ├─IndexRangeScan_218(Build) | 2.72 | 194.73 | cop[tikv] | table:t, index:title_idx_title(title) | range:["Vampire","Vampirf"), keep order:false |
| │ │ │ │ │ │ └─Selection_220(Probe) | 1.05 | 477.36 | cop[tikv] | | gt(imdb.title.production_year, 2010), like(imdb.title.title, "Vampire%", 92) |
| │ │ │ │ │ │ └─TableRowIDScan_219 | 2.72 | 469.18 | cop[tikv] | table:t | keep order:false |
| │ │ │ │ │ └─HashJoin_188(Probe) | 64470.00 | 2279924.38 | root | | inner join, equal:[eq(imdb.info_type.id, imdb.movie_info.info_type_id)] |
| │ │ │ │ │ ├─IndexLookUp_207(Build) | 1.00 | 33.97 | root | | |
| │ │ │ │ │ │ ├─IndexRangeScan_204(Build) | 1.00 | 66.03 | cop[tikv] | table:it1, index:info_type_info(info) | range:["genre","genre"], keep order:false |
| │ │ │ │ │ │ └─Selection_206(Probe) | 1.00 | 55.53 | cop[tikv] | | eq(imdb.info_type.info, "genres") |
| │ │ │ │ │ │ └─TableRowIDScan_205 | 1.00 | 52.53 | cop[tikv] | table:it1 | keep order:false |
| │ │ │ │ │ └─IndexLookUp_214(Probe) | 64470.00 | 2241187.41 | root | | |
| │ │ │ │ │ ├─IndexRangeScan_211(Build) | 64470.00 | 6914407.50 | cop[tikv] | table:mi, index:movie_info_idx_info(info) | range:["Horror","Horror"], keep order:false |
| │ │ │ │ │ └─Selection_213(Probe) | 64470.00 | 8235397.80 | cop[tikv] | | eq(imdb.movie_info.info, "Horror") |
| │ │ │ │ │ └─TableRowIDScan_212 | 64470.00 | 8041987.80 | cop[tikv] | table:mi | keep order:false |
| │ │ │ │ └─IndexLookUp_115(Probe) | 8.67 | 38.22 | root | | |
| │ │ │ │ ├─IndexRangeScan_113(Build) | 8.67 | 71.25 | cop[tikv] | table:mi_idx, index:movie_id_movie_info_idx(movie_id) | range: decided by [eq(imdb.movie_info_idx.movie_id, imdb.movie_info.movie_id)], keep order:false, stats:pseudo |
| │ │ │ │ └─TableRowIDScan_114(Probe) | 8.67 | 105.00 | cop[tikv] | table:mi_idx | keep order:false, stats:pseudo |
| │ │ │ └─IndexLookUp_87(Probe) | 30.13 | 9956.04 | root | | |
| │ │ │ ├─IndexRangeScan_84(Build) | 998.83 | 28466.78 | cop[tikv] | table:ci, index:cast_info_idx_mid(movie_id) | range: decided by [eq(imdb.cast_info.movie_id, imdb.movie_info.movie_id)], keep order:false |
| │ │ │ └─Selection_86(Probe) | 30.13 | 49262.52 | cop[tikv] | | in(imdb.cast_info.note, "(writer)", "(head writer)", "(written by)", "(story)", "(story editor)") |
| │ │ │ └─TableRowIDScan_85 | 998.83 | 47764.27 | cop[tikv] | table:ci | keep order:false |
| │ │ └─TableReader_73(Probe) | 12.58 | 11.88 | root | | data:Selection_72 |
| │ │ └─Selection_72 | 12.58 | 142.77 | cop[tikv] | | eq(imdb.name.gender, "m") |
| │ │ └─TableRangeScan_71 | 30.13 | 139.77 | cop[tikv] | table:n | range: decided by [imdb.cast_info.person_id], keep order:false |
| │ └─IndexLookUp_59(Probe) | 306.89 | 169.84 | root | | |
| │ ├─IndexRangeScan_57(Build) | 306.89 | 580.61 | cop[tikv] | table:mk, index:movie_keyword_idx_mid(movie_id) | range: decided by [eq(imdb.movie_keyword.movie_id, imdb.cast_info.movie_id)], keep order:false |
| │ └─TableRowIDScan_58(Probe) | 306.89 | 580.61 | cop[tikv] | table:mk | keep order:false |
| └─TableReader_46(Probe) | 2.21 | 6.10 | root | | data:Selection_45 |
| └─Selection_45 | 2.21 | 71.31 | cop[tikv] | | in(imdb.keyword.keyword, "murder", "blood", "gore", "death", "female-nudity") |
| └─TableRangeScan_44 | 306.89 | 68.31 | cop[tikv] | table:k | range: decided by [imdb.movie_keyword.keyword_id], keep order:false |
+-----------------------------------------------------------------+----------+------------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
42 rows in set, 2 warnings (0.02 sec)
```

The root cause is that the cost of index join for (t * mk) is larger than (it1 * mi) during join reorder:

```
action 0: join order becomes
((((((((it1*mi)*t)*mi_idx)*it2)*ci)*n)*mk)*k) from
original ((((((((ci*it1)*it2)*k)*mi)*mi_idx)*mk)*n)*t) , reason: join cost during reorder:
[(it1*mi), cost:128941],
[ci, cost:1.914624e+06],
[it1, cost:1],
[it2, cost:2],
[k, cost:1704.1909539668359],
[mi, cost:64470],
[mi_idx, cost:10000],
[mk, cost:7.480087e+06],
[n, cost:2.6635253911394197e+06],
[t, cost:1.046921216965675]]

action 0: join order becomes
((((((((t*mi_idx)*it2)*mi)*it1)*ci)*n)*mk)*k) from original
((((((((ci*it1)*it2)*k)*mi)*mi_idx)*mk)*n)*t) ,
reason: join cost during reorder:
[(t*mk), cost:7.480087000000016e+06],
[ci, cost:1.89042e+06],
[it1, cost:1],
[it2, cost:2],
[k, cost:1661.191403181918],
[mi, cost:64684.00000000001],
[mi_idx, cost:10000],
[mk, cost:7.480087e+06],
[n, cost:2.65861837928314e+06],
[t, cost:1.382569179641448e-09]]
```
[25b-1.zip](https://github.com/pingcap/tidb/files/9868025/25b-1.zip)

[25b-2.zip](https://github.com/pingcap/tidb/files/9868024/25b-2.zip)

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

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

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

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.