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

[Yisaer]

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]]

25b-1.zip

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)

[winoros]

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.

[winoros]

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.

[seiya-annie]

/report customer