Planner: Planning time increases significantly with large number of indexes

[terry1purcell]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

CREATE TABLE `t8` (
  `a` int,
  `b` int,
  `c` int,
  `d` int,
  `e` int,
  `f` int,
  `g` int,
  `h` int,
  `i` int,
  `j` int,
  `k` int,
  `l` int,
  `m` int,
  `n` int,
  `o` int,
  `p` int,
  `q` int,
  `r` int,
  `s` int,
  `t` int,
  `u` int,
  `v` int,
  `w` int,
  `x` int,
  `y` int,
  `z` int,
  `aa` int,
  `ab` int,
  `ac` int,
  `ad` int,
  `ae` int,
  `af` int,
  `ag` int,
  `ah` int,
  `ai` int,
  `aj` int,
  `ak` int,
  `al` int,
  `am` int,
  `an` int,
  `ao` int,
  `ap` int,
  `aq` int,
  `ar` int,
  `as` int,
  `at` int,
  `au` int,
  `av` int,
  `aw` int,
  `ax` int,
  `ay` int,
  `az` int,
  `ba` int,
  `bb` int,
  `bc` int,
  `bd` int,
  `be` int,
  `bf` int,
  `bg` int,
  `bh` int,
  `bi` int,
  `bj` int,
  `bk` int,
  `bl` int,
  `bm` int,
  `bn` int,
  `bo` int,
  `bp` int,
  `bq` int,
  `br` int,
  `bs` int,
  `bt` int,
  `bu` int,
  `bv` int,
  `bw` int,
  `bx` int,
  `by` int,
  `bz` int,
  `ca` int,
  `cb` int,
  `cc` int,
  `cd` int,
  `ce` int,
  `cf` int,
  `cg` int,
  `ch` int,
  `ci` int,
  `cj` int,
  `ck` int,
  `cl` int,
  `cm` int,
  `cn` int,
  `co` int,
  `cp` int,
  `cq` int,
  `cr` int,
  `cs` int,
  `ct` int,
  `cu` int,
  `cv` int,
  `cw` int,
  `cx` int,
  `cy` int,
  `cz` int,
  `da` int,
  `db` int,
  `dc` int,
  `dd` int,
  `de` int,
  `df` int,
  `dg` int,
  `dh` int,
  `di` int,
  `dj` int,
  `dk` int,
  `dl` int,
  `dm` int,
  `dn` int,
  `do` int,
  `dp` int,
  `dq` int,
  `dr` int,
  `ds` int,
  `dt` int,
  `du` int,
  `dv` int,
  `dw` int,
  `dx` int,
  `dy` int,
  `dz` int,
  `ea` int,
  `eb` int,
  `ec` int,
  `ed` int,
  `ee` int,
  `ef` int,
  `eg` int,
  `eh` int,
  `ei` int,
  `ej` int,
  `ek` int,
  `el` int,
  `em` int,
  `en` int,
  `eo` int,
  `ep` int,
  `eq` int,
  `er` int,
  `es` int,
  `et` int,
  `eu` int,
  `ev` int,
  `ew` int,
  `ex` int,
  `ey` int,
  `ez` int,
  
  KEY `ia` (`aa`),
  KEY `iab` (`aa`, `b`),
  KEY `iac` (`a`, `c`),
  KEY `iad` (`aa`, `d`),
  KEY `iae` (`a`, `e`),
  KEY `iaf` (`a`, `f`),
  KEY `iabc` (`ea`, `b`, `c`),
  KEY `iabd` (`ea`, `b`, `d`),
  KEY `iabe` (`ea`, `b`, `e`),
  KEY `iabf` (`ea`, `b`, `f`),
  KEY `iacb` (`ea`, `c`, `b`),
  KEY `iacd` (`ea`, `c`, `d`),
  KEY `iace` (`ea`, `c`, `e`),
  KEY `iacf` (`ea`, `c`, `f`),
  
  KEY `iade` (`ea`, `d`, `e`),
  KEY `iadf` (`ea`, `d`, `f`),
  KEY `iaeb` (`ea`, `e`, `b`),
  KEY `iaec` (`ea`, `e`, `c`),
  KEY `iaed` (`ea`, `e`, `d`),
  KEY `iaef` (`ea`, `e`, `f`),
  KEY `iafb` (`a`, `f`, `b`),
  KEY `iafc` (`ea`, `f`, `a`),
  KEY `iafd` (`ea`, `f`, `d`),
  KEY `iafe` (`ea`, `f`, `e`),
  
  KEY `iabcd` (`a`, `b`, `c`, `ed`),
  KEY `iabce` (`a`, `b`, `c`, `ee`),
  KEY `iabcf` (`a`, `b`, `c`, `ef`),
  KEY `iabdc` (`a`, `b`, `d`, `ec`),
  KEY `iabfc` (`a`, `b`, `f`, `ec`),
  KEY `iabfd` (`a`, `b`, `f`, `ed`),
  KEY `iabfe` (`a`, `b`, `f`, `ee`),
  KEY `iacbd` (`a`, `c`, `b`, `ed`),
  KEY `iacbe` (`a`, `c`, `b`, `ee`),
  KEY `iacbf` (`a`, `c`, `b`, `ef`),
  KEY `iacdb` (`a`, `c`, `d`, `eb`),
  KEY `iacde` (`a`, `c`, `d`, `ee`),
  KEY `iadbe` (`a`, `d`, `b`, `ee`),
  KEY `iadcb` (`a`, `d`, `c`, `eb`),
  KEY `iadcf` (`a`, `d`, `c`, `ef`),
  
  KEY `ib` (`eb`),
  KEY `iba` (`eb`, `a`),
  KEY `ibc` (`eb`, `c`),
  KEY `ibd` (`eb`, `d`),
  KEY `ibe` (`eb`, `e`),
  KEY `ibf` (`eb`, `f`),
  KEY `ibac` (`b`, `a`, `c`),
  KEY `ibad` (`b`, `a`, `d`),
  KEY `ibae` (`b`, `a`, `e`),
  KEY `ibaf` (`b`, `a`, `f`),
  KEY `ibca` (`b`, `c`, `a`),
  KEY `ibcd` (`b`, `c`, `d`),
  KEY `ibce` (`b`, `c`, `e`),
  KEY `ibcf` (`b`, `c`, `f`),
  KEY `ibda` (`b`, `d`, `a`),
  KEY `ibdc` (`b`, `d`, `c`),
  KEY `ibde` (`b`, `d`, `e`),
  KEY `ibdf` (`b`, `d`, `f`),
  KEY `ibea` (`b`, `e`, `a`),
  KEY `ibec` (`b`, `e`, `c`),
  KEY `ibfa` (`b`, `f`, `a`),
  KEY `ibfc` (`b`, `f`, `c`),
  KEY `ibfd` (`b`, `f`, `d`),
  KEY `ibfe` (`b`, `f`, `e`)
);

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

This is optimistic - but when I specify "use index" - I can force one index to be considered, and the explain is fast:

tidb> explain select a from t8 use index (iaf) where (a = 1 and f = 1) or (a = 2 and f = 1) or (a = 3 and f = 1) or (a = 4 and f = 1) or (a = 5 and f = 1) or (a = 6 and f = 1) or (a = 7 and f = 1) or (a = 8 and f = 1) or (a = 9 and f = 1) or (a = 1 and f = 2) or (a = 2 and f = 2) or (a = 3 and f = 2) or (a = 4 and f = 2) or (a = 5 and f = 2) or (a = 6 and f = 2) or (a = 7 and f = 2) or (a = 8 and f = 2) or (a = 9 and f = 2);
+--------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
| id                       | estRows | task      | access object             | operator info                                                                                                                           |
+--------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
| IndexReader_10           | 22.50   | root      |                           | index:Projection_6                                                                                                                      |
| └─Projection_6           | 22.50   | cop[tikv] |                           | test.t8.a                                                                                                                               |
|   └─IndexRangeScan_9     | 22.50   | cop[tikv] | table:t8, index:iaf(a, f) | range:[1 1,1 2], [2 1,2 2], [3 1,3 2], [4 1,4 2], [5 1,5 2], [6 1,6 2], [7 1,7 2], [8 1,8 2], [9 1,9 2], keep order:false, stats:pseudo |
+--------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
3 rows in set (0.012 sec)

3. What did you see instead (Required)

Allowing the optimizer to consider all indexes in 8X slower for the above DDL:

tidb> explain select a from t8 where (a = 1 and f = 1) or (a = 2 and f = 1) or (a = 3 and f = 1) or (a = 4 and f = 1) or (a = 5 and f = 1) or (a = 6 and f = 1) or (a = 7 and f = 1) or (a = 8 and f = 1) or (a = 9 and f = 1) or (a = 1 and f = 2) or (a = 2 and f = 2) or (a = 3 and f = 2) or (a = 4 and f = 2) or (a = 5 and f = 2) or (a = 6 and f = 2) or (a = 7 and f = 2) or (a = 8 and f = 2) or (a = 9 and f = 2);
+---------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
| id                        | estRows | task      | access object             | operator info                                                                                                                           |
+---------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
| IndexReader_13            | 22.50   | root      |                           | index:Projection_6                                                                                                                      |
| └─Projection_6            | 22.50   | cop[tikv] |                           | test.t8.a                                                                                                                               |
|   └─IndexRangeScan_11     | 22.50   | cop[tikv] | table:t8, index:iaf(a, f) | range:[1 1,1 2], [2 1,2 2], [3 1,3 2], [4 1,4 2], [5 1,5 2], [6 1,6 2], [7 1,7 2], [8 1,8 2], [9 1,9 2], keep order:false, stats:pseudo |
+---------------------------+---------+-----------+---------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+
3 rows in set (0.087 sec)

4. What is your TiDB version? (Required)

master branch - but true in any release.