MySQL Bugs: #12113: Composite index chosen partially for ORDER BY ... LIMIT query.

Bug #12113	Composite index chosen partially for ORDER BY ... LIMIT query.
Submitted:	22 Jul 2005 14:23	Modified:	24 Jan 2014 12:43
Reporter:	Domas Mituzas	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S1 (Critical)
Version:	5.0.28-BK, 4.0,5.0	OS:	Any
Assigned to:	Assigned Account	CPU Architecture:	Any
Tags:	bfsm_2006_11_02, bfsm_2007_03_01

Description:
We have a query on a large table, which sometimes is optimized to use only a part of index, thus by causing table scans, filesorts and other bad stuff. This is caused by bad optimizer's evaluation of row counts and job that needs to be done.

The query below should simply scan an index from an offset (fixed namespace and >= title) and return a limited set of values from it. What optimizer does wrong - picks only namespace part of an index then works with resulting dataset itself (as you can see, without FORCE INDEX it reports more rows to be scanned - this is absolute lie, considering what query is really doing).

So here we have either LIMIT or ORDER BY not considered by optimizer/planner, or something else/magic.

How to repeat:
| page  | CREATE TABLE `page` (
  `page_id` int(8) unsigned NOT NULL auto_increment,
  `page_namespace` int(11) NOT NULL default '0',
  `page_title` varchar(255) binary NOT NULL default '',
  `page_restrictions` tinyblob NOT NULL,
  `page_counter` bigint(20) unsigned NOT NULL default '0',
  `page_is_redirect` tinyint(1) unsigned NOT NULL default '0',
  `page_is_new` tinyint(1) unsigned NOT NULL default '0',
  `page_random` double unsigned NOT NULL default '0',
  `page_touched` varchar(14) binary NOT NULL default '',
  `page_latest` int(8) unsigned NOT NULL default '0',
  `page_len` int(8) unsigned NOT NULL default '0',
  PRIMARY KEY  (`page_id`),
  UNIQUE KEY `name_title` (`page_namespace`,`page_title`),
  KEY `page_random` (`page_random`),
  KEY `page_len` (`page_len`)
) TYPE=InnoDB |

mysql> show table status like 'page' \G
*************************** 1. row ***************************
           Name: page
           Type: InnoDB
     Row_format: Dynamic
           Rows: 1983457
 Avg_row_length: 106
    Data_length: 211533824
Max_data_length: NULL
   Index_length: 251543552
      Data_free: 0
 Auto_increment: 2287000
    Create_time: NULL
    Update_time: NULL
     Check_time: NULL
 Create_options:
        Comment: InnoDB free: 9216 kB
1 row in set (0.08 sec)

FAST ONE: 
 
mysql> explain /* indexShowChunk */ 
SELECT page_namespace,page_title,page_is_redirect  
FROM `page` FORCE  INDEX (name_title) 
WHERE page_namespace = '0' AND (page_title >= 'Sg')  
ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
        table: page
         type: range
possible_keys: name_title
          key: name_title
      key_len: 259
          ref: NULL
         rows: 566770
        Extra: Using where
1 row in set (0.00 sec)
 
SLOW ONE: 
 
mysql> explain /* indexShowChunk */ 
SELECT page_namespace,page_title,page_is_redirect  
FROM `page` USE INDEX (name_title) WHERE page_namespace = '0' 
AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
        table: page
         type: ref
possible_keys: name_title
          key: name_title
      key_len: 4
          ref: const
         rows: 109897
        Extra: Using where
1 row in set (0.00 sec)

Suggested fix:
*shrug*

Because InnoDB is a multi-versioning database, it cannot know the exact number of rows a transaction is seeing. Instead, it estimates the number of rows by random dives into the B-tree index. If the B-tree is not very well balanced or the keys are not evenly distributed, the guess may be badly wrong.

Recently, there was a feature request (outside this bug reporting system) that the number of random index dives in InnoDB should be configureable. I believe that this bug could be worked around by incrementing the number of random dives. Currently, InnoDB does 8 dives.

If you would like to experiment with this, please increment the value of BTR_KEY_VAL_ESTIMATE_N_PAGES in innobase/btr/btr0cur.c and report if it helped. Large values will of course slow down the query optimizer.

one more thing, when I remove is_redirect from select fields, query becomes 'using index' and does not hit tables at all. Then query plan is used as required - uses full name_title index and runs in 0.00s.

Some query speeds on not loaded server, USE INDEX and without any index hints query is executed in 5s (16GB RAM, dual-opteron box), with FORCE INDEX - 0.01s

and yes, I checked namespace=0 and namespace='0' - there's no performance difference in both cases.

regarding InnoDB random dives - it is really strange then, that dives using _same _ index always differ that much. what could be the reason of it? multiple ANALYZE TABLEs didn't help :)

Hi!

I recall some LIMIT optimization was made a year ago. Please test with 4.1.13.

Regards,

Heikki

I tested this on 5.0.9, results are same, on another box, 40s without FORCE, 0.01s with FORCE:

SLOW:
mysql> explain   SELECT page_namespace,page_title,page_is_redirect   FROM `page` USE INDEX (name_title) WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: ref
possible_keys: name_title
          key: name_title
      key_len: 4
          ref: const
         rows: 1
        Extra: Using where
1 row in set (0.00 sec)

FAST:
mysql> explain   SELECT page_namespace,page_title,page_is_redirect   FROM `page` FORCE INDEX (name_title) WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: range
possible_keys: name_title
          key: name_title
      key_len: 261
          ref: NULL
         rows: 200134
        Extra: Using where
1 row in set (0.00 sec)

after ANALYZE TABLE rows=1 changed into rows=1200 for USE INDEX query, after another one - rows=20000, after yet another one rows=30000, though, there're about 500k or 600k rows with namespace=0

changed synopsis to real error description

it works correctly on MyISAM

table dump can be found at http://download.wikipedia.org/en.wikipedia-page.dump.gz

Domas, Marko,

this bug is not about random dives. The wrong estimates (100 000 versus 500 000) are a key range size estimation error. InnoDB dives into the index tree at the both ends of the range, and tries to estimate the size of the range.

I am putting this bug report to the category Server: Optimizer. Regardless of the estimates, the optimizer should use the full length of the key in this query. The optimizer should not consider the shorter key at all. Using the full key it can get the big benefit from LIMIT.

Regards,

Heikki

I repeated the test with your dataset in 5.1.12 and got the same explain & times for both queries:
mysql> EXPLAIN SELECT page_namespace,page_title,page_is_redirect   FROM `page` WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: ref
possible_keys: name_title
          key: name_title
      key_len: 4
          ref: const
         rows: 23203
        Extra: Using where
1 row in set (0.00 sec)
 
mysql> EXPLAIN SELECT page_namespace,page_title,page_is_redirect   FROM `page` USE INDEX (name_title) WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: ref
possible_keys: name_title
          key: name_title
      key_len: 4
          ref: const
         rows: 23203
        Extra: Using where
1 row in set (0.00 sec)
 
I haven't tried with the 4.x tree yet.

Hola, you did try wrong queries. Both USE INDEX and without any hint only partial index is used (what this bug is about). You should try with FORCE INDEX and get 100x faster execution and a proper query plan.

I tried it on 5.0.13, still the same:

mysql> explain SELECT page_namespace,page_title,page_is_redirect   FROM `page` USE INDEX (name_title) WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: ref
possible_keys: name_title
          key: name_title
      key_len: 4
          ref: const
         rows: 106639
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain SELECT page_namespace,page_title,page_is_redirect   FROM `page` FORCE INDEX (name_title) WHERE page_namespace = '0'  AND (page_title >= 'Sg')  ORDER BY page_title LIMIT 961 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: page
         type: range
possible_keys: name_title
          key: name_title
      key_len: 771
          ref: NULL
         rows: 572944
        Extra: Using where
1 row in set (0.00 sec)

... second query being much faster (though, using full-width, here even multibyte, index).

I seem to have an issue that is related to this.

I am using Mysql 5.0.18 on freebsd

I have a large database loaded into innodb.

I have created several index's for how I do my selects and orderby functions.

Select * from some_table WHERE id=5112 and Private=0 Order By date DESC Limit 0,20;
Perfer to use Index (id,Private,date)

Select * from some_table WHERE id=5112 Order By date DESC Limit 0,20;
Perfer to use Index (id,date)

The problem is when I make an index, it find the first one needed that matchs
(in my case the first index is found so the second queue is slow)

When I converted the table to myism everything worked as expected.
So it seems to be the optimizer is using the wrong key, it's just selecting the key that works for the where, and not also the orderby.

Domas,

Please, try to repeat with the latest version, 5.0.24a (or 5.0.26-BK :). If you'll still have same results, please, upload that table (http://download.wikipedia.org/en.wikipedia-page.dump.gz) again to our FTP server (or elsewhere). Your old URL gives me 404 - Not found.

I am having a similar problem on 5.0.24a.  Before I upload the table, I wanted to check that I am doing this properly.  The table has about 700k rows.

mysql> select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1
    -> ;
Empty set (41.06 sec)

mysql>  select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1 order by EDCLICENSEENTITY.sequencenumber ASC limit 1000
    -> ;
Empty set (17 min 30.21 sec)

There is an index on (sequencenumber, version).  Why is the second query so much slower?  I thought this might be related to bug 4981, but 4.1.21 didn't fix this either.

Please, send SHOW CREATE TABLE and SHOW TABLE STATUS results for this EDCLICENSEENTITY table. Send the results of

EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0
and   EDCLICENSEENTITY.version > 1\G

and

EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0
and   EDCLICENSEENTITY.version > 1 order by EDCLICENSEENTITY.sequencenumber ASC
limit 1000\G

also.

I am still on 5.0.24a.  I have not gone back to 4.1.21 yet as I don't want to revert my system yet, nor do I want to 

confuse the situation.  I tried as InnoDB and as MyISAM and I am receiving slow query similar results, perhaps this is more 

of a general optimizer issue?

To rule out any sort of dependency (FK) issue, I dropped the database and loaded this one table into a clean database 

without the dependencies (FK's removed).  Same issue.

Below is the output for the information requested.

mysql> show create table EDCLICENSEENTITY;
+------------------+-------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------+
| Table            | Create Table                                                                                           

                                                                                                                            

                                                                                                                            

                                                                                                                            

                                                                                                                            

                                                                                                                            

                                                                                                                            

                                                                                                    |
+------------------+-------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------+
| EDCLICENSEENTITY | CREATE TABLE `EDCLICENSEENTITY` (
  `id` varchar(36) character set latin1 collate latin1_bin NOT NULL default '',
  `sequencenumber` bigint(20) NOT NULL default '0',
  `clientname` varchar(255) default NULL,
  `documentid` varchar(36) character set latin1 collate latin1_bin default NULL,
  `encryptionkey` varchar(255) default NULL,
  `issuetime` bigint(20) default NULL,
  `issuingauthority` varchar(120) default NULL,
  `policyid` varchar(36) character set latin1 collate latin1_bin default NULL,
  `publisherid` varchar(36) character set latin1 collate latin1_bin default NULL,
  `publishertime` bigint(20) default NULL,
  `revokeid` varchar(36) character set latin1 collate latin1_bin default NULL,
  `version` int(11) default NULL,
  PRIMARY KEY  (`id`),
  KEY `LICENSE_SEQNUM_INDX` (`sequencenumber`,`version`),
  KEY `LICENSE_TIME_INDEX` (`publishertime`),
  KEY `ALTEDCLICENSEENTITY` (`clientname`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+------------------+-------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

---------------------------------------------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------+
1 row in set (0.04 sec)

mysql> show table status;
+------------------+--------+---------+------------+--------+----------------+-------------+-----------------+-------------

-+-----------+----------------+---------------------+-------------+------------+-------------------+----------+------------

----+----------------------+
| Name             | Engine | Version | Row_format | Rows   | Avg_row_length | Data_length | Max_data_length | Index_length 

| Data_free | Auto_increment | Create_time         | Update_time | Check_time | Collation         | Checksum | 

Create_options | Comment              |
+------------------+--------+---------+------------+--------+----------------+-------------+-----------------+-------------

-+-----------+----------------+---------------------+-------------+------------+-------------------+----------+------------

----+----------------------+
| EDCLICENSEENTITY | InnoDB |      10 | Compact    | 719013 |            498 |   358612992 |               0 |    283672576 

|         0 |           NULL | 2006-09-30 11:41:05 | NULL        | NULL       | latin1_swedish_ci |     NULL |              

  | InnoDB free: 8192 kB |
+------------------+--------+---------+------------+--------+----------------+-------------+-----------------+-------------

-+-----------+----------------+---------------------+-------------+------------+-------------------+----------+------------

----+----------------------+
1 row in set (0.27 sec)

The somewhat fast one:

mysql> EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber >
    -> 0
    -> and   EDCLICENSEENTITY.version > 1;
+----+-------------+------------------+------+---------------------+------+---------+------+--------+-------------+
| id | select_type | table            | type | possible_keys       | key  | key_len | ref  | rows   | Extra       |
+----+-------------+------------------+------+---------------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | EDCLICENSEENTITY | ALL  | LICENSE_SEQNUM_INDX | NULL | NULL    | NULL | 719013 | Using where |
+----+-------------+------------------+------+---------------------+------+---------+------+--------+-------------+
1 row in set (0.16 sec)

The SLOW one:

mysql> EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber >
    -> 0
    -> and   EDCLICENSEENTITY.version > 1 order by EDCLICENSEENTITY.sequencenumber ASC
    -> limit 1000
    -> ;
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
| id | select_type | table            | type  | possible_keys       | key                 | key_len | ref  | rows   | Extra 

      |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
|  1 | SIMPLE      | EDCLICENSEENTITY | range | LICENSE_SEQNUM_INDX | LICENSE_SEQNUM_INDX | 8       | NULL | 359506 | Using 

where |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
1 row in set (0.00 sec)

mysql>

If I specify a single column then it does a "Using Where; Using Index" and is really really fast, apparently because it's 

never scanning the data portion of the table.

mysql> select id from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1 order 

by  EDCLICENSEENTITY.sequencenumber ASC limit 1000;
Empty set (1.74 sec)

mysql> explain select id from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1 

order by
    ->
    -> EDCLICENSEENTITY.sequencenumber ASC limit 1000;
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

--------------------+
| id | select_type | table            | type  | possible_keys       | key                 | key_len | ref  | rows   | Extra 

                   |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

--------------------+
|  1 | SIMPLE      | EDCLICENSEENTITY | range | LICENSE_SEQNUM_INDX | LICENSE_SEQNUM_INDX | 8       | NULL | 359506 | Using 

where; Using index |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

--------------------+
1 row in set (0.00 sec)

mysql>

But shouldn't the where clause first determine the matched results before the ORDER BY, LIMIT or SELECT columns even come 

into play??

It almost appears that the ORDER BY _or_ LIMIT send the optimizer a curve ball.  Specifying *either* appears to make the 

system table scan or something, it's almost 100% IO Wait when I run the query with either:

mysql>  select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1 order 

by EDCLICENSEENTITY.sequencenumber ASC
    -> ;
Empty set (16 min 2.95 sec)

mysql>  select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1 limit 

1000
    -> ;
Empty set (15 min 33.81 sec)

mysql> EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1
    ->
    -> order by EDCLICENSEENTITY.sequencenumber ASC;
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
| id | select_type | table            | type  | possible_keys       | key                 | key_len | ref  | rows   | Extra 

      |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
|  1 | SIMPLE      | EDCLICENSEENTITY | index | LICENSE_SEQNUM_INDX | LICENSE_SEQNUM_INDX | 13      | NULL | 719013 | Using 

where |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
1 row in set (0.00 sec)

mysql> EXPLAIN select * from EDCLICENSEENTITY where EDCLICENSEENTITY.sequenceNumber > 0 and   EDCLICENSEENTITY.version > 1
    ->
    -> limit 1000;
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
| id | select_type | table            | type  | possible_keys       | key                 | key_len | ref  | rows   | Extra 

      |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
|  1 | SIMPLE      | EDCLICENSEENTITY | range | LICENSE_SEQNUM_INDX | LICENSE_SEQNUM_INDX | 8       | NULL | 359506 | Using 

where |
+----+-------------+------------------+-------+---------------------+---------------------+---------+------+--------+------

-------+
1 row in set (0.01 sec)

mysql>

I will post the table dump as a non-public commment.  Please private message me if you can't get to this file.

[Sorry for so much information, I'm attempting to be as concise as I can]

Any updates on this?  Can I provide any further information?

No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".

Please reopen, this item should not be closed.  I will contact MySQL support to escalate this.

I've posted an email to the internals mailing list which may be related to this issue:
http://lists.mysql.com/internals/34281