MySQL Bugs: #19579: Optimizer does not choose right index and thus query is slow.

Bug #19579	Optimizer does not choose right index and thus query is slow.
Submitted:	6 May 2006 10:59	Modified:	23 Oct 2006 14:10
Reporter:	Sergey Vladimirov	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.0.24-BK, 5.0.16-log, 5.0.18, 5.0.21-log, 5.1.7-log	OS:	Linux (Linux)
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
Optimizer selects wrong index to use:

Without hits: 89k rows to view, 1.86 seconds

mysql> explain SELECT t8.id FROM struct_cells_hr t7, struct_cells_hr t8, registry_objects t9  WHERE t8.obj=t9.id AND t9.erased=0 AND t8.sort BETWEEN t7.sort AND t7.maxch AND t9.class=16 AND t9.state=2 AND t7.id=288101;
+----+-------------+-------+-------+----------------------+---------+---------+-------------------+-------+-------------+
| id | select_type | table | type  | possible_keys        | key     | key_len | ref               | rows  | Extra       |
+----+-------------+-------+-------+----------------------+---------+---------+-------------------+-------+-------------+
|  1 | SIMPLE      | t7    | const | PRIMARY,iso          | PRIMARY | 4       | const             |     1 |             |
|  1 | SIMPLE      | t9    | ref   | PRIMARY,csc,esci,eci | esci    | 9       | const,const,const | 89174 | Using index |
|  1 | SIMPLE      | t8    | ref   | o,si,s               | o       | 4       | arpsite.t9.id     |     1 | Using where |
+----+-------------+-------+-------+----------------------+---------+---------+-------------------+-------+-------------+

With hints: 1.6k rows to view, 0.08 sec

mysql> explain SELECT t8.id FROM struct_cells_hr t7, struct_cells_hr t8 FORCE INDEX (si), registry_objects t9  WHERE t8.obj=t9.id AND t9.erased=0 AND t8.sort BETWEEN t7.sort AND t7.maxch AND t9.class=16 AND t9.state=2 AND t7.id=288101;
+----+-------------+-------+-------+----------------------+---------+---------+----------------------------+------+-------------+
| id | select_type | table | type  | possible_keys        | key     | key_len | ref                        | rows | Extra       |
+----+-------------+-------+-------+----------------------+---------+---------+----------------------------+------+-------------+
|  1 | SIMPLE      | t7    | const | PRIMARY,iso          | PRIMARY | 4       | const                      |    1 |             |
|  1 | SIMPLE      | t8    | range | si                   | si      | 8       | NULL                       | 1672 | Using where |
|  1 | SIMPLE      | t9    | ref   | PRIMARY,csc,esci,eci | eci     | 12      | const,const,arpsite.t8.obj |    1 | Using where |
+----+-------------+-------+-------+----------------------+---------+---------+----------------------------+------+-------------+

Tables indecies:

mysql> show index from struct_cells_hr;
+-----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table           | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+-----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| struct_cells_hr |          0 | PRIMARY  |            1 | id          | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | maxch    |            1 | maxch       | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | o        |            1 | obj         | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | iso      |            1 | id          | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | iso      |            2 | sort        | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | iso      |            3 | obj         | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | si       |            1 | sort        | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | si       |            2 | id          | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
| struct_cells_hr |          1 | s        |            1 | sort        | A         |      307176 |     NULL | NULL   |      | BTREE      |         |
+-----------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
9 rows in set (0.01 sec)

mysql> show index from registry_objects;
+------------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table            | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+------------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| registry_objects |          0 | PRIMARY  |            1 | id          | A         |      394347 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | csc      |            1 | class       | A         |         100 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | csc      |            2 | state       | A         |         237 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | csc      |            3 | created     | A         |      394347 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | a        |            1 | author      | A         |         995 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | p        |            1 | publisher   | A         |         932 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | esci     |            1 | erased      | A         |           2 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | esci     |            2 | state       | A         |           7 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | esci     |            3 | class       | A         |         253 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | esci     |            4 | id          | A         |      394347 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | eci      |            1 | erased      | A         |           2 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | eci      |            2 | class       | A         |         174 |     NULL | NULL   |      | BTREE      |         |
| registry_objects |          1 | eci      |            3 | id          | A         |      394347 |     NULL | NULL   |      | BTREE      |         |
+------------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
13 rows in set (0.01 sec)

How to repeat:
repeatable everytime. May be it is dublicate of other bugs (like http://bugs.mysql.com/bug.php?id=19334), but if it is not, we would provide table data.

Another example:

SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_cells_hr t5, registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t6.id AND t6.erased=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id AND t7.erased=0 AND (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111200201,41,2003103001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46,4041201,5)) AND t4.id=131988;

Without forcing index: 
mysql> explain SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_cells_hr t5, registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t6.id AND t6.erased=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id AND t7.erased=0 AND (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111200201,41,2003103001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46,4041201,5)) AND t4.id=131988;
+----+-------------+-------+--------+--------------------------------------------+---------+---------+---------------+-------+--------------------------+
| id | select_type | table | type   | possible_keys                              | key     | key_len | ref           | rows  | Extra                    |
+----+-------------+-------+--------+--------------------------------------------+---------+---------+---------------+-------+--------------------------+
|  1 | SIMPLE      | t4    | const  | PRIMARY,iso                                | PRIMARY | 4       | const         |     1 |                          |
|  1 | SIMPLE      | t6    | range  | PRIMARY,csc,esci,eci                       | esci    | 9       | NULL          | 56397 | Using where; Using index |
|  1 | SIMPLE      | t5    | ref    | PRIMARY,o,iso,si,s                         | o       | 4       | arpsite.t6.id |     2 | Using where              |
|  1 | SIMPLE      | t7    | eq_ref | PRIMARY,epoi,esp,epobi,eobi,esi,eobori,obj | PRIMARY | 4       | arpsite.t5.id |     1 | Using where              |
+----+-------------+-------+--------+--------------------------------------------+---------+---------+---------------+-------+--------------------------+

56397*2 rows, 1.58 sec

With index forcing:
mysql> explain SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_cells_hr t5 force index (si), registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t6.id AND t6.erased=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id AND t7.erased=0 AND (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111200201,41,2003103001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46,4041201,5)) AND t4.id=131988;
+----+-------------+-------+--------+--------------------------------------------+---------+---------+----------------+------+-------------+
| id | select_type | table | type   | possible_keys                              | key     | key_len | ref            | rows | Extra       |
+----+-------------+-------+--------+--------------------------------------------+---------+---------+----------------+------+-------------+
|  1 | SIMPLE      | t4    | const  | PRIMARY,iso                                | PRIMARY | 4       | const          |    1 |             |
|  1 | SIMPLE      | t5    | range  | si                                         | si      | 8       | NULL           |  617 | Using where |
|  1 | SIMPLE      | t6    | eq_ref | PRIMARY,csc,esci,eci                       | PRIMARY | 4       | arpsite.t5.obj |    1 | Using where |
|  1 | SIMPLE      | t7    | ref    | PRIMARY,epoi,esp,epobi,eobi,esi,eobori,obj | obj     | 5       | arpsite.t5.obj |    1 | Using where |
+----+-------------+-------+--------+--------------------------------------------+---------+---------+----------------+------+-------------+

617 rows, 0.05 sec

more than 30 times faster with forcing index. It should be optimizer who do it automatically.

Retest with 5.1.7-log... the same

Thank you for a problem report. The query in bug #19334 is different, so, please, upload dump of your data (the smallest amount) that demonstrate this problem.

File uploaded to ftp://ftp.mysql.com/pub/mysql/upload/bug-data-19579.zip

Verified just as described on your data uploaded:

mysql> explain SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_ce
lls_hr t5, registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t6.id AND t6.erase
d=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id AND t7.erased=0 AN
D (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111200201,41,2003103
001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46,4041201,5)) AND
t4.id=131988\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t4
         type: const
possible_keys: PRIMARY,iso
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t6
         type: range
possible_keys: PRIMARY,csc,esci,eci
          key: esci
      key_len: 9
          ref: NULL
         rows: 58466
        Extra: Using where; Using index
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: t5
         type: ref
possible_keys: PRIMARY,o,iso,si,s
          key: o
      key_len: 4
          ref: arpsite.t6.id
         rows: 1
        Extra: Using where
*************************** 4. row ***************************
           id: 1
  select_type: SIMPLE
        table: t7
         type: eq_ref
possible_keys: PRIMARY,epoi,oi,esp,epobi,eobi,esi,eobori,obj
          key: PRIMARY
      key_len: 4
          ref: arpsite.t5.id
         rows: 1
        Extra: Using where
4 rows in set (0.00 sec)

This query returned:

...
128 rows in set (1.03 sec)

While with a hint we got:

mysql> SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_cells_hr t
5 force index (si), registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t6.id AND
 t6.erased=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id AND t7.er
ased=0 AND (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111200201,4
1,2003103001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46,4041201
,5)) AND t4.id=131988;
+--------+
| id     |
+--------+
| 136182 |
...
| 424446 |
+--------+
128 rows in set (0.05 sec)

And much better plan:

mysql> explain SELECT t5.id FROM struct_cells t7, struct_cells_hr t4, struct_ce
lls_hr t5 force index (si), registry_objects t6 WHERE t7.obj=t6.id AND t5.obj=t
6.id AND t6.erased=0 AND t5.sort BETWEEN t4.sort AND t4.maxch AND t7.id=t5.id A
ND t7.erased=0 AND (t6.state=2 AND t7.state IN (3,4)) AND (t6.class IN (15,2111
200201,41,2003103001,29,14,3,12,27,17,3060801,28,38,37,51,8,40,42,4,36,50,39,46
,4041201,5)) AND t4.id=131988\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t4
         type: const
possible_keys: PRIMARY,iso
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
        Extra:
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t5
         type: range
possible_keys: si
          key: si
      key_len: 8
          ref: NULL
         rows: 518
        Extra: Using where
*************************** 3. row ***************************
           id: 1
  select_type: SIMPLE
        table: t6
         type: eq_ref
possible_keys: PRIMARY,csc,esci,eci
          key: PRIMARY
      key_len: 4
          ref: arpsite.t5.obj
         rows: 1
        Extra: Using where
*************************** 4. row ***************************
           id: 1
  select_type: SIMPLE
        table: t7
         type: ref
possible_keys: PRIMARY,epoi,oi,esp,epobi,eobi,esi,eobori,obj
          key: obj
      key_len: 5
          ref: arpsite.t5.obj
         rows: 1
        Extra: Using where
4 rows in set (0.01 sec)

So, it is a bug in optimizer.

This problem can be demonstrated with a simpler test case:

mysql> CREATE TABLE t1(id int PRIMARY KEY, b int, e int);
Query OK, 0 rows affected (0.05 sec)

mysql> CREATE TABLE t2(i int, a int, INDEX si(i), INDEX ai(a));
Query OK, 0 rows affected (0.05 sec)

mysql> CREATE TABLE t3(a int PRIMARY KEY, c char(4), INDEX ci(c));
Query OK, 0 rows affected (0.05 sec)

mysql> INSERT INTO t1 VALUES
    ->   (1,10,19), (2,20,22), (4,41,42), (9,93,95), (7, 77,79),
    ->   (6,63,67), (5,55,58), (3,38,39), (8,81,89);
Query OK, 9 rows affected (0.00 sec)
Records: 9  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t2 VALUES
    ->   (21,210), (41,410), (82,820), (83,830), (84,840),
    ->   (65,650), (51,510), (37,370), (94,940), (76,760),
    ->   (22,220), (33,330), (40,400), (95,950), (38,380),
    ->   (67,670), (88,880), (57,570), (96,960), (97,970);
Query OK, 20 rows affected (0.00 sec)
Records: 20  Duplicates: 0  Warnings: 0

mysql> INSERT INTO t3 VALUES
    ->   (210,'bb'), (950,'ii'), (400,'ab'), (500,'ee'), (220,'gg'),
    ->   (440,'gg'), (310,'eg'), (380,'ee'), (840,'bb'), (830,'ff'),
    ->   (230,'aa'), (960,'ii'), (410,'aa'), (510,'ee'), (290,'bb'),
    ->   (450,'gg'), (320,'dd'), (390,'hh'), (850,'jj'), (860,'ff');
Query OK, 20 rows affected (0.00 sec)
Records: 20  Duplicates: 0  Warnings: 0

mysql> EXPLAIN
    -> SELECT t3.a FROM t1,t2 FORCE INDEX (si),t3
    ->   WHERE t1.id = 8 AND t2.i BETWEEN t1.b AND t1.e AND
    ->         t3.a=t2.a AND t3.c IN ('bb','ee');
+----+-------------+-------+--------+---------------+---------+---------+--------------+------+-------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref          | rows | Extra       |
+----+-------------+-------+--------+---------------+---------+---------+--------------+------+-------------+
|  1 | SIMPLE      | t1    | const  | PRIMARY       | PRIMARY | 4       | const        |    1 |             |
|  1 | SIMPLE      | t2    | range  | si            | si      | 5       | NULL         |    4 | Using where |
|  1 | SIMPLE      | t3    | eq_ref | PRIMARY,ci    | PRIMARY | 4       | arpsite.t2.a |    1 | Using where |
+----+-------------+-------+--------+---------------+---------+---------+--------------+------+-------------+
3 rows in set (0.00 sec)

mysql> EXPLAIN
    -> SELECT t3.a FROM t1,t2,t3
    ->   WHERE t1.id = 8 AND t2.i BETWEEN t1.b AND t1.e AND
    ->         t3.a=t2.a AND t3.c IN ('bb','ee') ;
+----+-------------+-------+-------+---------------+---------+---------+--------------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref          | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+--------------+------+-------------+
|  1 | SIMPLE      | t1    | const | PRIMARY       | PRIMARY | 4       | const        |    1 |             |
|  1 | SIMPLE      | t3    | range | PRIMARY,ci    | ci      | 5       | NULL         |    5 | Using where |
|  1 | SIMPLE      | t2    | ref   | si,ai         | ai      | 5       | arpsite.t3.a |    2 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+--------------+------+-------------+
3 rows in set (0.00 sec)

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/13703

ChangeSet@1.2299, 2006-10-14 13:41:21-07:00, igor@rurik.mysql.com +7 -0
  Fixed bug #19579: at range analysis optimizer does take into 
  account predicates that become sargable after reading const tables.
  In some cases this resulted in choosing non-optimal execution plans.
  Now info of such potentially saragable predicates is saved in
  an array and after reading const tables we check whether this
  predicates has become saragable.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/13777

ChangeSet@1.2301, 2006-10-16 14:25:28-07:00, igor@rurik.mysql.com +7 -0
  Fixed bug #19579: at range analysis optimizer did not take into 
  account predicates that become sargable after reading const tables.
  In some cases this resulted in choosing non-optimal execution plans.
  Now info of such potentially saragable predicates is saved in
  an array and after reading const tables we check whether this
  predicates has become saragable.

Pushed in 5.0.27/5.1.13-beta

Noted in 5.0.27, 5.1.13 changelogs.

The range analysis optimizer did not take into account predicates for
which an index could be used after reading const tables. In some
cases this resulted in non-optimal execution plans.