MySQL Bugs: #34140: Allow MySQL to transform range lookups to IN for certain datatypes

Bug #34140	Allow MySQL to transform range lookups to IN for certain datatypes
Submitted:	29 Jan 2008 16:58	Modified:	29 Jan 2010 3:31
Reporter:	Harrison Fisk	Email Updates:
Status:	No Feedback	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S4 (Feature request)
Version:	5.0.54	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
When dealing with multi-column indexes, it can be preferable to use IN instead of range lookups for certain data types.  The use of the IN allows more of the index to be used due to the different access patterns.

For example, use the following table:

CREATE TABLE `range_test` (
  `a` int(11) default NULL,
  `b` int(11) default NULL,
  `c` char(10) default NULL,
  UNIQUE KEY `a` (`a`,`b`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

With the two queries that return the same results:

mysql> explain SELECT * FROM range_test WHERE a > 1 and a < 11 AND b = 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: range_test
         type: range
possible_keys: a
          key: a
      key_len: 5
          ref: NULL
         rows: 511
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain SELECT * FROM range_test WHERE a IN (2, 3, 4, 5, 6, 7, 8, 9, 10) AND b = 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: range_test
         type: range
possible_keys: a
          key: a
      key_len: 10
          ref: NULL
         rows: 9
        Extra: Using where
1 row in set (0.00 sec)

You can see that the second IN statement is able to use more of the index and hence scan much fewer rows.

It could be possible for the MySQL optimizer to do this transformation for any datatypes that can have a list of values in a range, the most common ones being INT and DATE.

How to repeat:
CREATE TABLE `range_test` (
  `a` int(11) default NULL,
  `b` int(11) default NULL,
  `c` char(10) default NULL,
  UNIQUE KEY `a` (`a`,`b`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

insert into range_test values (1, 1, 'val'), (1, 2, 'val'), (1, 3, 'val'), (2, 1, 'val'), (2, 2, 'val'), (2, 3, 'val'), (3, 1, 'val'), (3, 2, 'val'), (3, 3, 'val'), (4, 1, 'val'), (4, 2, 'val'), (4, 3, 'val'), (4, 4, 'val');

explain SELECT * FROM range_test WHERE a IN (2, 3) AND b = 2;

explain SELECT * FROM range_test WHERE a > 1 AND a < 4 AND b = 2;

Suggested fix:
Allow the optimizer to perform this transformation when it makes sense to do so.

Checking with the latest 5.1-bugteam I think the range access now uses the full index, hence no transformation should be needed. Can you please confirm that this is what you needed ? 

Here's my test case output : 
CREATE TABLE `range_test` (
`a` int(11) default NULL,
`b` int(11) default NULL,
`c` char(10) default NULL,
UNIQUE KEY `a` (`a`,`b`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
insert into range_test values (1,1,1),(2,2,2),(3,3,3),(4,4,4);
insert into range_test select a+4,b+4,c from range_test;
insert into range_test select a+8,b+8,c from range_test;
insert into range_test select a+16,b+16,c from range_test;
explain SELECT * FROM range_test WHERE a > 1 and a < 11 AND b = 10;;
id      1
select_type     SIMPLE
table   range_test
type    ALL
possible_keys   a
key     NULL
key_len NULL
ref     NULL
rows    32
Extra   Using where
explain SELECT * FROM range_test WHERE a IN (2, 3, 4, 5, 6, 7, 8, 9, 10) AND b = 10;;
id      1
select_type     SIMPLE
table   range_test
type    ALL
possible_keys   a
key     NULL
key_len NULL
ref     NULL
rows    32
Extra   Using where

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".

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".