Bug #70247 Using many WHERE conditions makes range scan disabled
Submitted: 5 Sep 2013 6:21 Modified: 30 Sep 2015 15:47
Reporter: Yoshinori Matsunobu (OCA) Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S4 (Feature request)
Version:51.71,5.5.33, 5.6.13, 5.5.23 OS:Any
Assigned to: CPU Architecture:Any

[5 Sep 2013 6:21] Yoshinori Matsunobu
Description:
If there are many WHERE conditions, range scan is disabled and MySQL does full table scan instead, even if range scan is much more efficient.

How to repeat:
1. create test table
create table t (c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int, c10 int, primary key (c1, c2, c3, c4)) engine=innodb;

2. generate 5mil test rows, and load it into table t
----
#!/usr/bin/perl

for($i=1; $i <= 5000000; $i++) {
  print "$i,$i,$i,$i,$i,$i,$i,$i,$i,$i\n";
}
----

3. generate select statement using many where conditions. Here is an example
----------------------
#!/usr/bin/perl

$num_in1= 100;
$num_in2= 162;

$query = "explain select * from t where c1 in (";
for($i= 1; $i <= $num_in1; $i++) {
  $query .= "$i";
  if($i < $num_in1) {
    $query .= ",";
  }
}
$query .= ") and c2 in (";
for($i= 1; $i <= $num_in2; $i++) {
  $query .= "$i";
  if($i < $num_in2) {
    $query .= ",";
  }
}
$query .= ") and c3 = 1 and c4 = 1;";

print "$query\n";
---------------------

4. change $num_in1 and $num_in2 values, run the explain statements and see query execution plans.
In my case:
* $num_in1= 100; $num_in2= 160; (or less)
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | t     | range | PRIMARY       | PRIMARY | 16      | NULL | 16000 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+

* $num_in1= 100; $num_in2= 162; (or more)
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | t     | ALL  | PRIMARY       | NULL | NULL    | NULL | 4855188 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+

On SEL_ARG class (opt_range.cc), there is a MAX_SEL_ARGS definition.
  enum { MAX_SEL_ARGS = 16000 };

This is hard coded. And there are some logic to check whether this value is exceeded or not, for example:
  bool statement_should_be_aborted() const
  {
    return
      thd->is_fatal_error ||
      thd->is_error() ||
      alloced_sel_args > SEL_ARG::MAX_SEL_ARGS;
  }

If I increased MAX_SEL_ARGS, the number of where conditions to shift from range to ALL has changed.
[5 Sep 2013 6:43] MySQL Verification Team
Hello Yoshinori,

Thank you for the bug report and test case.
Verified as described.

Thanks,
Umesh
[5 Sep 2013 6:45] MySQL Verification Team
// 5.6.13

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162) and c3 = 1 and c4 = 1;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | t     | ALL  | PRIMARY       | NULL | NULL    | NULL | 4867431 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.01 sec)

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150) and c3 = 1 and c4 = 1;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | t     | range | PRIMARY       | PRIMARY | 16      | NULL | 15000 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
1 row in set (0.01 sec)

mysql> select version();
+------------+
| version()  |
+------------+
| 5.6.13-log |
+------------+
1 row in set (0.00 sec)
[5 Sep 2013 7:18] MySQL Verification Team
// 5.5.33 - affected

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150) and c3 = 1 and c4 = 1;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | t     | range | PRIMARY       | PRIMARY | 16      | NULL | 15000 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
1 row in set (0.07 sec)

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162) and c3 = 1 and c4 = 1;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | t     | ALL  | PRIMARY       | NULL | NULL    | NULL | 5000358 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.00 sec)

mysql> select version();
+-------------------------------------------+
| version()                                 |
+-------------------------------------------+
| 5.5.33-enterprise-commercial-advanced-log |
+-------------------------------------------+
1 row in set (0.00 sec)
[13 Sep 2013 6:54] MySQL Verification Team
// 5.1.71 - affected

mysql> select version();
+------------+
| version()  |
+------------+
| 5.1.71-log |
+------------+
1 row in set (0.00 sec)

mysql> create table t (c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int, c10 int, primary key (c1, c2, c3, c4)) engine=innodb;
Query OK, 0 rows affected (0.03 sec)

mysql> LOAD DATA INFILE '/tmp/load.csv' INTO TABLE t FIELDS TERMINATED BY ',';
Query OK, 5000000 rows affected (1 min 2.87 sec)
Records: 5000000  Deleted: 0  Skipped: 0  Warnings: 0

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150) and c3 = 1 and c4 = 1;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | t     | range | PRIMARY       | PRIMARY | 16      | NULL | 15000 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
1 row in set (0.08 sec)

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162) and c3 = 1 and c4 = 1;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | t     | ALL  | PRIMARY       | NULL | NULL    | NULL | 5000265 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.00 sec)
[13 Sep 2013 8:14] MySQL Verification Team
// 5.5.23

mysql> select version();
+-------------------------------------------+
| version()                                 |
+-------------------------------------------+
| 5.5.23-enterprise-commercial-advanced-log |
+-------------------------------------------+
1 row in set (0.00 sec)

mysql> create table t (c1 int, c2 int, c3 int, c4 int, c5 int, c6 int, c7 int, c8 int, c9 int, c10 int, primary key (c1, c2, c3, c4)) engine=innodb;
Query OK, 0 rows affected (0.02 sec)

mysql> LOAD DATA INFILE '/tmp/load.csv' INTO TABLE t FIELDS TERMINATED BY ',';
Query OK, 5000000 rows affected (1 min 3.37 sec)
Records: 5000000  Deleted: 0  Skipped: 0  Warnings: 0

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150) and c3 = 1 and c4 = 1;
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | t     | range | PRIMARY       | PRIMARY | 16      | NULL | 15000 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+-------+-------------+
1 row in set (0.08 sec)

mysql> explain select * from t where c1 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100) and c2 in (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162) and c3 = 1 and c4 = 1;
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | t     | ALL  | PRIMARY       | NULL | NULL    | NULL | 5000298 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.00 sec)
[23 Sep 2013 9:10] Jørgen Løland
The limitation is explicitly set to cap memory consumption and time spent in the range optimizer. It has been like this since the dawn of the mysql range access method. We'll look into it for sure, but reclassifying it as FR.
[30 Sep 2015 15:47] Paul DuBois
Noted in 5.7.9, 5.8.0 changelogs.

For a query with many range conditions, the optimizer could
overestimate the amount of memory required for a range scan and fall
back to a less efficient full table scan.
[5 Oct 2015 14:36] Paul DuBois
Revised changelog entry:

For a query with many range conditions, the optimizer could estimate
that too much memory would be required for a range scan and fall back
to a less efficient full table scan.

A new range_optimizer_max_mem_size system variable now controls the
limit on memory consumption for the range optimizer. A value of 0 
means "no limit." If an execution plan considered by the optimizer
uses the range access method but the optimizer estimates that the
amount of memory needed for this method would exceed the limit, it
abandons the plan and considers other plans.
[8 Oct 2015 13:03] MySQL Verification Team
should this variable be mentioned in
https://dev.mysql.com/doc/refman/5.7/en/range-optimization.html ?