| Bug #18165 | SQL optimizer ineficiencies with "BETWEEN" statements | ||
|---|---|---|---|
| Submitted: | 12 Mar 2006 13:12 | Modified: | 10 Oct 2006 20:51 |
| Reporter: | Martin Sperl | ||
| Status: | Closed | ||
| Category: | Server: Optimizer | Severity: | S3 (Non-critical) |
| Version: | 5.0.21-BK, 4.1.14, 5.0.18 | OS: | Linux (Linux) |
| Assigned to: | Bugs System | Target Version: | |
[22 Apr 2006 17:59]
Valeriy Kravchuk
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.
[28 Jul 2006 4:37]
Bugs System
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
[16 Aug 2006 18:37]
Bugs System
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.
[29 Aug 2006 15:23]
Evgeny Potemkin
Fixed in 5.0.25
[4 Sep 2006 13:38]
Evgeny Potemkin
Fixed in 5.1.12
[16 Sep 2006 21:07]
Sergey Petrunya
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 .
[10 Oct 2006 20:51]
Paul DuBois
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.
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>