MySQL Bugs: #35819: Multi column IN does not use index

Bug #35819	Multi column IN does not use index
Submitted:	4 Apr 2008 2:32	Modified:	21 Oct 2009 5:08
Reporter:	Peter Zaitsev (Basic Quality Contributor)	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.0.54, 5.0.56	OS:	Any
Assigned to:	Assigned Account	CPU Architecture:	Any
Tags:	qc

Description:
When multi-colum IN is used and index is defined only on first column It is not used:

mysql> explain select * from rt where (i,j) in ((266,841),(407,511));
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
|  1 | SIMPLE      | rt    | ALL  | NULL          | NULL | NULL    | NULL | 40960 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------+
1 row in set (0.00 sec)

Compare to:

mysql> explain select * from rt where (i) in (266,407);
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | rt    | range | i             | i    | 5       | NULL |   65 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

How to repeat:
 CREATE TABLE `rt` (
  `i` int(11) default NULL,
  `j` int(11) default NULL,
  KEY `i` (`i`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1

mysql> select * from rt limit 100;
+------+------+
| i    | j    |
+------+------+
|  266 |  841 |
|  407 |  511 |
|  333 |  133 |
|  668 |  939 |
|  692 |  641 |
|  129 |  723 |
|  226 |  962 |
|  133 |  778 |
|  491 |  121 |
|  134 |  306 |
|  128 |  723 |
|  229 |  978 |
|  201 |   71 |
|  752 |  546 |
|  473 |  729 |
|  224 |  933 |
|  994 |  170 |
|  867 |  825 |
|  526 |  153 |
|  189 |  484 |
|  853 |  814 |
|  512 |  119 |
|   57 |  927 |
|  463 |  535 |
|  288 |  832 |
|  297 |  988 |
|   49 |  281 |
|  256 |  440 |
|  432 |  840 |
|  904 |  998 |
|  279 |  402 |
|  171 |  652 |
|  745 |  771 |
|  620 |  784 |
|   64 |  965 |
|  634 |  274 |
|  467 |  516 |
|  177 |  338 |
|  157 |  771 |
|  384 |  605 |
|  877 |  567 |
|  204 |  321 |
|  994 |    5 |
|   45 |  211 |
|  917 |  953 |
|   16 |  218 |
|   41 |  554 |
|  644 |  561 |
|  871 |  674 |
|  755 |  754 |
|  506 |  266 |
|  812 |  264 |
|  884 |  628 |
|  486 |  547 |
|  277 |  745 |
|  892 |  225 |
|  450 |  574 |
|  522 |  887 |
|  868 |  680 |
|  794 |  931 |
|  273 |  572 |
|   39 |  482 |
|  291 |   10 |
|  179 |  862 |
|  772 |  277 |
|   69 |  513 |
|  357 |  247 |
|  166 |   86 |
|  932 |  402 |
|  216 |  872 |
|  712 |  946 |
|  594 |  133 |
|  880 |    1 |
|  367 |  831 |
|   54 |  779 |
|  730 |  314 |
|  382 |  966 |
|  684 |  520 |
|  550 |  192 |
|  308 |  963 |
|  892 |  569 |
|  172 |  151 |
|  241 |  751 |
|   32 |  909 |
|  446 |  504 |
|  181 |  394 |
|  429 |  960 |
|  512 |  683 |
|  879 |  346 |
|   94 |  429 |
|  865 |   38 |
|  593 |  853 |
|  483 |  859 |
|  846 |  652 |
|  723 |  657 |
|  119 |  623 |
|  757 |  918 |
|  316 |  829 |
|  195 |  488 |
|  855 |  813 |
+------+------+
100 rows in set (0.00 sec)

This is not the only feature missing from IN-list optimization -- http://bugs.mysql.com/bug.php?id=31188

Thank you for a problem report. Indeed, optimizer just refuses to use the index, so it may be a missing feature:

mysql> CREATE TABLE `rt` (
    ->   `i` int(11) default NULL,
    ->   `j` int(11) default NULL,
    ->   KEY `i` (`i`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.09 sec)

mysql> insert into rt values(1,1);
Query OK, 1 row affected (0.03 sec)

mysql> insert into rt select rand()*1000, rand()*1000 from rt;
Query OK, 1 row affected (0.06 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql> insert into rt select rand()*1000, rand()*1000 from rt;
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

...

mysql> insert into rt select rand()*1000, rand()*1000 from rt;
Query OK, 32768 rows affected (0.50 sec)
Records: 32768  Duplicates: 0  Warnings: 0

mysql> analyze table rt;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.rt | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.03 sec)

mysql> explain select * from rt where (i,j) in ((266,841),(407,511))\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: rt
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 65536
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain select * from rt force index(i) where (i,j) in ((266,841),(407,51
1))\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: rt
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 65536
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain select * from rt where (i) in (266,407)\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: rt
         type: range
possible_keys: i
          key: i
      key_len: 5
          ref: NULL
         rows: 109
        Extra: Using where
1 row in set (0.02 sec)

Workaround in this case is simple:

mysql> explain select * from rt where (i=266 and j=841) or (i=407 and j=511)\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: rt
         type: range
possible_keys: i
          key: i
      key_len: 5
          ref: NULL
         rows: 109
        Extra: Using where
1 row in set (0.03 sec)

But with longer IN() lists it will be problematic.

This is an additional request for a feature optimization. The target version is MySQL 6.x.

Duplicate of Bug#31188