Bug #72690 A 5.6's optimizer bug which is releated to 'or' operator's number
Submitted: 20 May 2014 9:13 Modified: 3 Jun 2014 2:38
Reporter: Hao Liu Email Updates:
Status: Not a Bug Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S2 (Serious)
Version:5.6.17 OS:Any
Assigned to: CPU Architecture:Any

[20 May 2014 9:13] Hao Liu
Description:
I think it is a optimizer bug which may cause wrong index selection.

I will introduce how to repeat it:

create a table like below:

root@test 05:05:51>show create table sbtest_data1\G
*************************** 1. row ***************************
       Table: sbtest_data1
Create Table: CREATE TABLE `sbtest_data1` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `a` int(10) unsigned NOT NULL,
  `b` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_a_b` (`a`,`b`)
) ENGINE=InnoDB AUTO_INCREMENT=2000001 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

The table have 2000000 lines. The id is automent and the `a` column  is always the value of 100, and the `b` is added 1 every 10000. I made the table with a sysbench's lua script as below:

 1 function create_insert(table_id)
  2     local j
  3     local i
  4     local query
  5
  6     print ("Creating table 'sbtest_data" .. table_id)
  7     query = [[
  8     create table sbtest_data]] .. table_id .. [[ (id INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  9     a INTEGER UNSIGNED NOT NULL,
 10     b INTEGER UNSIGNED NOT NULL,
 11     PRIMARY KEY (`id`), key `idx_a_b` (`a`,`b`))
 12     ]]
 13
 14     db_query(query)
 15
 16     print ("Inserting "..oltp_table_size .. " records into 'sbtest_data" .. table_id.."'")
 17
 18     db_bulk_insert_init("INSERT INTO sbtest_data"..table_id.." (a,b) VALUES")
 19
 20     for j = 1, oltp_table_size/10000 do
 21         for i = 1, 10000 do
 22             db_bulk_insert_next("(100,"..j..")")
 23         end
 24     end
 25
 26     db_bulk_insert_done()
 27 end

The i will execute explain select to get the results:

root@test 03:49:41>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 );
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 159732 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
root@test 03:50:55>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9);
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 179688 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
root@test 03:51:02>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10);
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 18250 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
1 row in set (0.00 sec)
root@test 03:51:07>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10 or b=11);
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 20075 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+--------------------------+
1 row in set (0.00 sec)

You can see that the rows of the third and the fourth are very strange. The value is smaller than the first and the second results;

I test it on the Percona 5518 and the result is to be expected。

root@test 03:55:05>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 );
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 159732 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
root@test 03:55:15>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9);
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 179688 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
root@test 03:55:19>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10);
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 199644 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)
root@test 03:55:24>explain select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10 or b=11);
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
| 1 | SIMPLE | sbtest_data1 | range | idx_a_b | idx_a_b | 8 | NULL | 219600 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)

The bug is very bad because it may cause wrong index selection.

How to repeat:
You can see the description

Suggested fix:
I am trying to find the root cause.
[20 May 2014 11:07] Hao Liu
If there are ten or more 'or' operator , the ha_innobase::records_in_range will not be called when the explain select is excuted.
[20 May 2014 11:07] Hao Liu
If there are ten or more 'or' operator , the ha_innobase::records_in_range will not be called when the explain select is excuted.
[20 May 2014 11:18] Hao Liu
I found the code is related as below:

sql/handler.cc:

5632     /*
5633       Get the number of rows in the range. This is done by calling
5634       records_in_range() unless:
5635
5636         1) The range is an equality range and the index is unique.
5637            There cannot be more than one matching row, so 1 is
5638            assumed. Note that it is possible that the correct number
5639            is actually 0, so the row estimate may be too high in this
5640            case. Also note: ranges of the form "x IS NULL" may have more
5641            than 1 mathing row so records_in_range() is called for these.
5642         2) a) The range is an equality range but the index is either
5643               not unique or all of the keyparts are not used.
5644            b) The user has requested that index statistics should be used
5645               for equality ranges to avoid the incurred overhead of
5646               index dives in records_in_range().
5647            c) Index statistics is available.
5648            Ranges of the form "x IS NULL" will not use index statistics
5649            because the number of rows with this value are likely to be
5650            very different than the values in the index statistics.
5651     */
5652     int keyparts_used= 0;
5653     if ((range.range_flag & UNIQUE_RANGE) &&                        // 1)
5654         !(range.range_flag & NULL_RANGE))
5655       rows= 1; /* there can be at most one row */
5656     //else if ((range.range_flag & EQ_RANGE) &&                       // 2a)
5657     //         (range.range_flag & USE_INDEX_STATISTICS) &&           // 2b)
5658     //         (keyparts_used= my_count_bits(range.start_key.keypart_map)) &&
5659     //         table->key_info[keyno].rec_per_key[keyparts_used-1] && // 2c)
5660     //         !(range.range_flag & NULL_RANGE))
5661     //  rows= table->key_info[keyno].rec_per_key[keyparts_used-1];

I commeted the lines from 5656 to 5661, the result will correct.
[20 May 2014 11:40] Hao Liu
I guss it is related to Multi-Range Read Optimization
[21 May 2014 18:02] Sinisa Milivojevic
Mr. Hao,

Thank you very much for reporting this behavior.

In order to pinpoint the problem, we would require some additional info from you. First, we would need your db_bulk_insert...() functions. Even better, it would be fine if you could dump this table with mysqldump, then zip it or gzip it, and upload it to this bug.

Next thing that we would like you to do is to check that  your server is started with --innodb-stats-persistent is on. The 'on' is by default, so it is enough not to have this option in configuration file or in mysqld starting arguments.

Next , can you send us the output of EXPLAIN EXTENDED .... for the same set of EXPLAINs that you have provided in the bug. If that does not help, we shall try some other variants.

Next thing you can try is to set the index idx_a_b as UNIQUE when creating a table. As far as I can see, there is not there a single combo of the values of columns `a` and `b` so, the index can be UNIQUE.

Last that I would like to ask you is how many rows are actually returned by each query ?? You can easily obtain it by omitting EXPLAIN and replacing `id` in the SELECT list with count(*).

Thank you very much, in advance.
[22 May 2014 2:26] Hao Liu
Hi, Sinisa:

I have put the mysqldump result file to sftp.oracle.com:/support/incoming/, you can see it with the file name mysql-bug-data-72690.zip.

The option --innodb-stats-persistent is not related to the bug. Whether the option is on or not, the result is the same.

At the same time, the idx_a_b is not UNIQUE, you will find it from the mysqldump's sql.

I will give more information you need:

root@test 10:01:54>explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 );
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 159732 |   100.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+

root@test 10:02:36>explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9);
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 179688 |   100.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+

root@test 10:02:53>explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10);
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 35980 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+

root@test 10:03:06>explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10 or b=11);
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 39578 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+

root@test 10:03:17>select count(*) from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 );
+----------+
| count(*) |
+----------+
|    80000 |
+----------+
1 row in set (0.05 sec)

root@test 10:04:17>select count(*) from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9);
+----------+
| count(*) |
+----------+
|    90000 |
+----------+
1 row in set (0.05 sec)

root@test 10:04:26>select count(*) from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10);
+----------+
| count(*) |
+----------+
|   100000 |
+----------+
1 row in set (0.06 sec)

root@test 10:04:29>select count(*) from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10 or b=11);
+----------+
| count(*) |
+----------+
|   110000 |
+----------+
1 row in set (0.07 sec)

That's all. Thank you!
[28 May 2014 16:23] Sinisa Milivojevic
Hao Li,

Thank you very much. What you discover is truly a bug. I have tested this bug with all possible variants of the persistence of the index statistics and the results are always the same !!!!

Here are my results:

$ ./client/mysql bug -e "explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 );"
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 159732 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
[sinisa@local mysql-5.6.14]$ ./client/mysql bug -e "explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 );"
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 179688 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+--------+----------+--------------------------+
[sinisa@local mysql-5.6.14]$ ./client/mysql bug -e "explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10);"
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 49660 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
[sinisa@local mysql-5.6.14]$ ./client/mysql bug -e "explain extended select id from sbtest_data1 where a=100 and (b=1 or b=2 or b=3 or b=4 or b=5 or b=6 or b=7 or b=8 or b=9 or b=10 or b=11);"
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
| id | select_type | table        | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                    |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+
|  1 | SIMPLE      | sbtest_data1 | range | idx_a_b       | idx_a_b | 8       | NULL | 54626 |    75.00 | Using where; Using index |
+----+-------------+--------------+-------+---------------+---------+---------+------+-------+----------+--------------------------+

Hence, this is a fully verified bug.
[30 May 2014 7:19] Øystein Grøvlen
AFAICT, this is intended behavior.  See description of eq_range_index_dive_limit.
(http://dev.mysql.com/doc/refman/5.6/en/server-system-variables.html#sysvar_eq_range_index_...)

Some background for this variable can be found here:  http://jorgenloland.blogspot.co.uk/2012/04/on-queries-with-many-values-in-in.html

In other words, to get more accurate statistics, at the expense of more B-Tree look-ups by the optimizer, you should increase the session variable eq_range_index_dive_limit.
[30 May 2014 13:12] Sinisa Milivojevic
As Oystein pointed out this is not a bug. He even printed the solution to the problem.
[3 Jun 2014 2:38] Hao Liu
Thanks, Oystein and Sinisa.

I have found the solution to this problem, but I also think it is a bug, not a feature.

Because of this bug or "feature", a real query of our online oltp business uses 10 us on MySQL 5.5 but use 16 s on MySQL 5.6. It is a disaster!!!

Mark has talked a lot on MySQLatFaceook (https://www.facebook.com/notes/mysql-at-facebook/eq_range_index_dive_limit-system-variable...) , I think the default value 200 of this variable on MySQL 5.7 is a better option.
[11 Jul 2014 14:14] Stefan Ring
This issue sounds very much like a problem I am having, which is described here: http://www.percona.com/forums/questions-discussions/mysql-and-percona-server/12373-percona...

The test case is in comment #9. It issues queries like "select * from TBL where id=a0 or id=a1 or ..." with 500 ors from 8 concurrent processes. With MySQL 5.5, it will run smoothly forever. With 5.6 and later, it will run for a while (usually 10-20 seconds), then break down completely.

When I found this bug report, I was really optimistic that tweaking eq_range_index_dive_limit would eliminate the issue, but unfortunately, this is not the case.
[14 Jul 2014 12:42] Øystein Grøvlen
Stefan Ring: Using your test script/database, I am not able to reproduce the issue if I set both optimizer_switch='use_index_extensions=off' and eq_range_index_dive_limit=0.  Alternative, you can force the use of the primary index by adding the optimizer hint FORCE INDEX(PRIMARY) to your query.
[15 Jul 2014 8:59] Stefan Ring
Øystein: Thanks for looking into this. Combining the two settings does indeed eliminate the issue.