tidb
tidb copied to clipboard
pingcap
Join's cost calculation during join reorder mismatches the real physical cost of index join
Bug Report
Please answer these questions before submitting your issue. Thanks!
1. Minimal reproduce step (Required)
Plan changed in Job 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 |
+---------------------------------------------------------------------+---------+-----------+-----------+-------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| 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]]
2. What did you expect to see? (Required)
3. What did you see instead (Required)
4. What is your TiDB version? (Required)
To support the physical cost during join reorder. Introducing the memo struct of cascades is necessary. We need to bring memoization/dynamic programming into the logical optimization phase.
Table t has few rows, and it can apply index join with mk(The one has 7.480087e+06 rows). So the cost of t join mk is a small value. But we use the sum of the row count as the join cost during the join reorder. So we get the cost as 7.480087000000016e+06.
The table it1 has few rows, and it can only do a hash join with ci. But the table ci is not larger than mk. The cost of it1 join ci during the join reorder is 128941, which is smaller than 1.480087000000016e+06.
Thus it's hard for us to choose a good and stable join order for this query.
