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

[6 May 2006 10:59] Sergey Vladimirov
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.
[17 May 2006 14:06] Sergey Vladimirov
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.
[20 May 2006 12:50] Sergey Vladimirov
Retest with 5.1.7-log... the same
[8 Jun 2006 15:50] Valeriy Kravchuk
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.
[8 Jun 2006 17:00] Sergey Vladimirov
File uploaded to ftp://ftp.mysql.com/pub/mysql/upload/bug-data-19579.zip
[3 Jul 2006 14:00] Valeriy Kravchuk
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.
[13 Oct 2006 23:05] Igor Babaev
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)
[14 Oct 2006 20:41] Bugs System
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.
[16 Oct 2006 21:25] Bugs System
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.
[21 Oct 2006 9:11] Georgi Kodinov
Pushed in 5.0.27/5.1.13-beta
[23 Oct 2006 14:10] Paul DuBois
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.