MySQL Bugs: #18165: SQL optimizer ineficiencies with "BETWEEN" statements

Bug #18165	SQL optimizer ineficiencies with "BETWEEN" statements
Submitted:	12 Mar 2006 12:12	Modified:	10 Oct 2006 18:51
Reporter:	Martin Sperl	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.0.21-BK, 4.1.14, 5.0.18	OS:	Linux (Linux)
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
Hi!

mysql 5.0.18 and 4.1.14 seem to use different optimizer path depending on if  BETWEEN is used or the BETWEEN is expanded manually.

In the test case shown below you can see that for BETWEEN is doing a full table scan and that the expanded version is using an index.

I always thought that using "BETWEEN" should offer equal or possibly even better optimization paths than the expanded version, as it provides more information to the optimizer. And in the worst case BETWEEN is just expanded.

It is also interresting that 4.1 guesses a different number of rows than 5.0, but this can be explained by the different basic versions.

Ciao,
         Martin

P.s: the same thing also applies to INNODB type tables! (confirmed only on 5.0!)

How to repeat:
Here the table (has got 2.6M rows):
mysql> show create table EventTest;
+-----------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table     | Create Table                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
+-----------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EventTest | CREATE TABLE `EventTest` (
  `EventID` bigint(20) NOT NULL default '0',
  `BBServerID` bigint(20) NOT NULL default '0',
  `ServerID` bigint(20) NOT NULL default '0',
  `ServiceID` bigint(20) NOT NULL default '0',
  `IPID` bigint(20) NOT NULL default '0',
  `StartTime` datetime NOT NULL default '0000-00-00 00:00:00',
  `EndTime` datetime NOT NULL default '0000-00-00 00:00:00',
  `Position` enum('current','historic') NOT NULL default 'historic',
  `StateID` bigint(20) NOT NULL default '0',
  `BBAgentID` bigint(20) NOT NULL default '0',
  `QServerInfoID` bigint(20) NOT NULL default '0',
  KEY `ServiceIndex` (`Position`,`ServerID`,`ServiceID`,`BBServerID`),
  KEY `BBServerID` (`BBServerID`,`ServerID`,`ServiceID`,`StartTime`),
  KEY `Position` (`Position`,`StateID`),
  KEY `StartTime` (`StartTime`,`EndTime`),
  KEY `EndTime` (`EndTime`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 |
+-----------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

====================

mysql> SHOW VARIABLES LIKE "version";
+---------------+---------------------+
| Variable_name | Value               |
+---------------+---------------------+
| version       | 4.1.14-standard-log |
+---------------+---------------------+
1 row in set (0.00 sec)

mysql> DESC select * FROM EventTest WHERE "2006-03-11 11:00:00" BETWEEN StartTime AND EndTime;
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | EventTest | ALL  | NULL          | NULL |    NULL | NULL | 2615587 | Using where |
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.00 sec)

mysql> DESC select * FROM EventTest WHERE "2006-03-11 11:00:00" >StartTime AND "2006-03-11 11:00:00" < EndTime;
+----+-------------+-----------+-------+-------------------+---------+---------+------+-------+-------------+
| id | select_type | table     | type  | possible_keys     | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-----------+-------+-------------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | EventTest | range | StartTime,EndTime | EndTime |       8 | NULL | 11438 | Using where |
+----+-------------+-----------+-------+-------------------+---------+---------+------+-------+-------------+
1 row in set (0.00 sec)

==================

mysql> SHOW VARIABLES LIKE "version";
+---------------+---------------------+
| Variable_name | Value               |
+---------------+---------------------+
| version       | 5.0.18-standard-log |
+---------------+---------------------+
1 row in set (0.00 sec)

mysql> DESC select * FROM EventTest WHERE "2006-03-11 11:00:00" BETWEEN StartTime AND EndTime;
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows    | Extra       |
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
|  1 | SIMPLE      | EventTest | ALL  | NULL          | NULL | NULL    | NULL | 2615587 | Using where |
+----+-------------+-----------+------+---------------+------+---------+------+---------+-------------+
1 row in set (0.00 sec)

mysql> DESC select * FROM EventTest WHERE "2006-03-11 11:00:00" >StartTime AND "2006-03-11 11:00:00" < EndTime;
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
| id | select_type | table     | type  | possible_keys     | key     | key_len | ref  | rows | Extra       |
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | EventTest | range | StartTime,EndTime | EndTime | 8       | NULL | 4522 | Using where |
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
1 row in set (0.01 sec)

mysql>

Verified with 5.0.21-BK on Linux:

mysql> CREATE TABLE `EventTest` (
    ->   `EventID` bigint(20) NOT NULL default '0',
    ->   `BBServerID` bigint(20) NOT NULL default '0',
    ->   `ServerID` bigint(20) NOT NULL default '0',
    ->   `ServiceID` bigint(20) NOT NULL default '0',
    ->   `IPID` bigint(20) NOT NULL default '0',
    ->   `StartTime` datetime NOT NULL default '0000-00-00 00:00:00',
    ->   `EndTime` datetime NOT NULL default '0000-00-00 00:00:00',
    ->   `Position` enum('current','historic') NOT NULL default 'historic',
    ->   `StateID` bigint(20) NOT NULL default '0',
    ->   `BBAgentID` bigint(20) NOT NULL default '0',
    ->   `QServerInfoID` bigint(20) NOT NULL default '0',
    ->   KEY `ServiceIndex` (`Position`,`ServerID`,`ServiceID`,`BBServerID`),
    ->   KEY `BBServerID` (`BBServerID`,`ServerID`,`ServiceID`,`StartTime`),
    ->   KEY `Position` (`Position`,`StateID`),
    ->   KEY `StartTime` (`StartTime`,`EndTime`),
    ->   KEY `EndTime` (`EndTime`)
    -> ) ENGINE=MyISAM DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.01 sec)

mysql> insert into `EventTest` (`EventID`) values (1), (2), (3), (4), (5), (6);
Query OK, 6 rows affected (0.01 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> insert into `EventTest` (`StartTime`, `EndTime`) values('2006-03-11 11:00:00', '2006-03-11 11:00:02');
Query OK, 1 row affected (0.00 sec)

mysql> explain extended select * FROM EventTest WHERE "2006-03-11 11:00:00" BETWEEN StartTime and EndTime;
+----+-------------+-----------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-----------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | EventTest | ALL  | NULL          | NULL | NULL    | NULL |   7 | Using where |
+----+-------------+-----------+------+---------------+------+---------+------+------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> show warnings\G
*************************** 1. row ***************************
  Level: Note
   Code: 1003
Message: select `test`.`EventTest`.`EventID` AS `EventID`,`test`.`EventTest`.`BBServerID` AS `BBServerID`,`test`.`EventTest`.`ServerID` AS `ServerID`,`test`.`EventTest`.`ServiceID` AS `ServiceID`,`test`.`EventTest`.`IPID` AS `IPID`,`test`.`
EventTest`.`StartTime` AS `StartTime`,`test`.`EventTest`.`EndTime` AS `EndTime`,
`test`.`EventTest`.`Position` AS `Position`,`test`.`EventTest`.`StateID` AS `StateID`,`test`.`EventTest`.`BBAgentID` AS `BBAgentID`,`test`.`EventTest`.`QServerInfoID` AS `QServerInfoID` from `test`.`EventTest` where (_latin1'2006-03-11 11:00:00' between `test`.`EventTest`.`StartTime` and `test`.`EventTest`.`EndTime`)
1 row in set (0.01 sec)

mysql> explain extended select * FROM EventTest WHERE "2006-03-11 11:00:00" >=
StartTime AND "2006-03-11 11:00:00" <= EndTime;
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
| id | select_type | table     | type  | possible_keys     | key     | key_len | ref  | rows | Extra       |
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | EventTest | range | StartTime,EndTime | EndTime | 8       | NULL |    2 | Using where |
+----+-------------+-----------+-------+-------------------+---------+---------+------+------+-------------+
1 row in set, 1 warning (0.01 sec)

mysql> show warnings\G
*************************** 1. row ***************************
  Level: Note
   Code: 1003
Message: select `test`.`EventTest`.`EventID` AS `EventID`,`test`.`EventTest`.`BBServerID` AS `BBServerID`,`test`.`EventTest`.`ServerID` AS `ServerID`,`test`.`EventTest`.`ServiceID` AS `ServiceID`,`test`.`EventTest`.`IPID` AS `IPID`,`test`.`
EventTest`.`StartTime` AS `StartTime`,`test`.`EventTest`.`EndTime` AS `EndTime`,
`test`.`EventTest`.`Position` AS `Position`,`test`.`EventTest`.`StateID` AS `StateID`,`test`.`EventTest`.`BBAgentID` AS `BBAgentID`,`test`.`EventTest`.`QServerInfoID` AS `QServerInfoID` from `test`.`EventTest` where ((20060311110000 >= `test`.`EventTest`.`StartTime`) and (20060311110000 <= `test`.`EventTest`.`EndTime`)
)
1 row in set (0.00 sec)

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

I hope, the problem and possible solution is obvious from the above. Test case:

CREATE TABLE `EventTest` (
`EventID` bigint(20) NOT NULL default '0',
`BBServerID` bigint(20) NOT NULL default '0',
`ServerID` bigint(20) NOT NULL default '0',
`ServiceID` bigint(20) NOT NULL default '0',
`IPID` bigint(20) NOT NULL default '0',
`StartTime` datetime NOT NULL default '0000-00-00 00:00:00',
`EndTime` datetime NOT NULL default '0000-00-00 00:00:00',
`Position` enum('current','historic') NOT NULL default 'historic',
`StateID` bigint(20) NOT NULL default '0',
`BBAgentID` bigint(20) NOT NULL default '0',
`QServerInfoID` bigint(20) NOT NULL default '0',
KEY `ServiceIndex` (`Position`,`ServerID`,`ServiceID`,`BBServerID`),
KEY `BBServerID` (`BBServerID`,`ServerID`,`ServiceID`,`StartTime`),
KEY `Position` (`Position`,`StateID`),
KEY `StartTime` (`StartTime`,`EndTime`),
KEY `EndTime` (`EndTime`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

insert into `EventTest` (`EventID`) values (1), (2), (3), (4), (5), (6);
insert into `EventTest` (`StartTime`, `EndTime`) values('2006-03-11 11:00:00', '2006-03-11 11:00:02');

EXPLAIN select * FROM EventTest WHERE "2006-03-11 11:00:00" BETWEEN
StartTime AND EndTime;
EXPLAIN select * FROM EventTest WHERE "2006-03-11 11:00:00" >= StartTime AND "2006-03-11 11:00:00" <= EndTime;

Two statements above should give the same results according to the definition of BETWEEN.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/9692

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/10556

ChangeSet@1.2259, 2006-08-16 09:37:19-07:00, igor@rurik.mysql.com +4 -0
  Fixed bug #18165.
  Made [NOT]BETWEEN predicates SARGable in respect to the second and 
  the third arguments.

Fixed in 5.0.25

Fixed in 5.1.12

Paul, we use "Sargable" as defined here: http://en.wikipedia.org/wiki/Sargable
"a condition (or predicate) in a query is said to be sargable if the DBMS engine can take advantage of an index to speed up the execution of the query (using index seeks, not covering indexes)".
Before this fix BETWEEN was Sargable only w.r.t 1st argument, i.e. the only sargable form for t.keyX was:
  t.keyX BETWEEN a AND b
now the optimizer can also use those forms :
  a BETWEEN t.keyX AND b     (e.g. from here it infers t.keyX <=a)
  a BETWEEN b AND t.keyX
.

Noted in 5.0.25, 5.1.12 changelogs.

The optimizer did not take advantage of indexes on columns used for
the second or third arguments of BETWEEN.