MySQL Bugs: #76398: MySQL doing full scan depending on limit value with ORDER BY query

Bug #76398	MySQL doing full scan depending on limit value with ORDER BY query
Submitted:	19 Mar 2015 20:27	Modified:	11 Apr 2020 2:20
Reporter:	Christophe Fondacci	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S3 (Non-critical)
Version:	5.6.23, 5.6.25, 5.5.44	OS:	Any (CentOS, Mac OS X)
Assigned to:		CPU Architecture:	Any
Tags:	filesort, full scan, limit, order

Description:
Stackoverflow advised me to file this as a bug.

My table is a regular innodb table, very classic, no exotic datatypes. For the following query:
select * from ACTIVITIES order by ACTIVITY_DATE desc limit 20

Table has an index on ACTIVITY_DATE (only one column).

The execution plan changes based on the limit number. With 10K rows in the table, any number below 97 generates an index scan while any higher limit generates a full scan with filesort. With 30K row the limit is 160 (below = index scan, above = full table scan & filesort).

I would expect to always make an index scan even though it is a order by DESC. This is pretty basic sort by date descending to get the most recent elements. The behavior seems quite strange so I think it might be a bug. Everything works as expected with MyISAM: always index scan.

Here Is my table:
Create Table: CREATE TABLE `ACTIVITIES` (
  `ACTIVITY_ID` int(11) NOT NULL AUTO_INCREMENT,
  `ACTIVITY_DATE` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `USER_KEY` varchar(50) NOT NULL,
  `ITEM_KEY` varchar(50) NOT NULL,
  `ACTIVITY_TYPE` varchar(1) NOT NULL,
  `EXTRA` varchar(500) DEFAULT NULL,
  `IS_VISIBLE` varchar(1) NOT NULL DEFAULT 'Y',
  PRIMARY KEY (`ACTIVITY_ID`),
  KEY `ACTI_USER_I` (`USER_KEY`,`ACTIVITY_DATE`),
  KEY `ACTIVITY_ITEM_I` (`ITEM_KEY`,`ACTIVITY_DATE`),
  KEY `ACTI_ITEM_TYPE_I` (`ITEM_KEY`,`ACTIVITY_TYPE`,`ACTIVITY_DATE`),
  KEY `ACTI_DATE_I` (`ACTIVITY_DATE`)
) ENGINE=InnoDB AUTO_INCREMENT=10091 DEFAULT CHARSET=utf8 COMMENT='Logs    activity'

Stackoverflow thread: http://stackoverflow.com/questions/29125634

How to repeat:
Table:
mysql> show create table ACTIVITIES\G
*************************** 1. row ***************************
       Table: ACTIVITIES
Create Table: CREATE TABLE `ACTIVITIES` (
  `ACTIVITY_ID` int(11) NOT NULL AUTO_INCREMENT,
  `ACTIVITY_DATE` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  `USER_KEY` varchar(50) NOT NULL,
  `ITEM_KEY` varchar(50) NOT NULL,
  `ACTIVITY_TYPE` varchar(1) NOT NULL,
  `EXTRA` varchar(500) DEFAULT NULL,
  `IS_VISIBLE` varchar(1) NOT NULL DEFAULT 'Y',
  PRIMARY KEY (`ACTIVITY_ID`),
  KEY `ACTI_USER_I` (`USER_KEY`,`ACTIVITY_DATE`),
  KEY `ACTIVITY_ITEM_I` (`ITEM_KEY`,`ACTIVITY_DATE`),
  KEY `ACTI_ITEM_TYPE_I` (`ITEM_KEY`,`ACTIVITY_TYPE`,`ACTIVITY_DATE`),
  KEY `ACTI_DATE_I` (`ACTIVITY_DATE`)
) ENGINE=InnoDB AUTO_INCREMENT=10091 DEFAULT CHARSET=utf8 COMMENT='Logs    activity'
1 row in set (0.00 sec)

Put 10k Rows in it (not sure if it happens with less).

Run 
explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 20
AND
explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 150

Thank you for the report.
I could not repeat with the dummy data at my end.
Could you please provide repeatable data(sql dump - you can mark it as private note after uploading)?

Thanks,
Umesh

Thank you for the test case.
I see similar behavior with 5.5.44, 5.6.25.
It could be by design/known issue but I could not locate a bug which confirms whether plan changes depending on constant in LIMIT.

// 5.6.25

mysql> show variables like '%version%';
+-------------------------+---------------------------------------------------------+
| Variable_name           | Value                                                   |
+-------------------------+---------------------------------------------------------+
| innodb_version          | 5.6.25                                                  |
| protocol_version        | 10                                                      |
| slave_type_conversions  |                                                         |
| version                 | 5.6.25-enterprise-commercial-advanced                   |
| version_comment         | MySQL Enterprise Server - Advanced Edition (Commercial) |
| version_compile_machine | x86_64                                                  |
| version_compile_os      | linux-glibc2.5                                          |
+-------------------------+---------------------------------------------------------+
7 rows in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 20;
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
| id | select_type | table      | type  | possible_keys | key         | key_len | ref  | rows | Extra |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
|  1 | SIMPLE      | ACTIVITIES | index | NULL          | ACTI_DATE_I | 4       | NULL |   20 | NULL  |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
1 row in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 150;
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows  | Extra          |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
|  1 | SIMPLE      | ACTIVITIES | ALL  | NULL          | NULL | NULL    | NULL | 10914 | Using filesort |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
1 row in set (0.00 sec)

mysql>

// 5.5.44

mysql> show variables like '%version%';
+-------------------------+------------------------------+
| Variable_name           | Value                        |
+-------------------------+------------------------------+
| innodb_version          | 5.5.44                       |
| protocol_version        | 10                           |
| slave_type_conversions  |                              |
| version                 | 5.5.44                       |
| version_comment         | MySQL Community Server (GPL) |
| version_compile_machine | x86_64                       |
| version_compile_os      | linux2.6                     |
+-------------------------+------------------------------+
7 rows in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 20;
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
| id | select_type | table      | type  | possible_keys | key         | key_len | ref  | rows | Extra |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
|  1 | SIMPLE      | ACTIVITIES | index | NULL          | ACTI_DATE_I | 4       | NULL |   20 |       |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
1 row in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 150;
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows  | Extra          |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
|  1 | SIMPLE      | ACTIVITIES | ALL  | NULL          | NULL | NULL    | NULL | 10638 | Using filesort |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
1 row in set (0.00 sec)

mysql>

// 5.1.73

mysql> show variables like '%version%';
+-------------------------+------------------------------+
| Variable_name           | Value                        |
+-------------------------+------------------------------+
| protocol_version        | 10                           |
| version                 | 5.1.73                       |
| version_comment         | MySQL Community Server (GPL) |
| version_compile_machine | x86_64                       |
| version_compile_os      | unknown-linux-gnu            |
+-------------------------+------------------------------+
5 rows in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 20;
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
| id | select_type | table      | type  | possible_keys | key         | key_len | ref  | rows | Extra |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
|  1 | SIMPLE      | ACTIVITIES | index | NULL          | ACTI_DATE_I | 4       | NULL |   20 |       |
+----+-------------+------------+-------+---------------+-------------+---------+------+------+-------+
1 row in set (0.00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 150;
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows  | Extra          |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
|  1 | SIMPLE      | ACTIVITIES | ALL  | NULL          | NULL | NULL    | NULL | 11376 | Using filesort |
+----+-------------+------------+------+---------------+------+---------+------+-------+----------------+
1 row in set (0.00 sec)

mysql>

Posted by developer:
 
It seems the switch-over point is different when limit optimization is considered compared to when switch happen for range optimization.
Tested 5.7.16: Switch-over for limit query is same as report in the bug report (97):

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 96;                                                                          +----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-------+
| id | select_type | table      | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-------+
|  1 | SIMPLE      | ACTIVITIES | NULL       | index | NULL          | ACTI_DATE_I | 4       | NULL |   96 |   100.00 | NULL  |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-------+
1 row in set, 1 warning (0,00 sec)

mysql> explain select * from ACTIVITIES order by ACTIVITY_DATE desc limit 97;
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+----------------+
| id | select_type | table      | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra          |
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+----------------+
|  1 | SIMPLE      | ACTIVITIES | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 10914 |   100.00 | Using filesort |
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+----------------+
1 row in set, 1 warning (0,00 sec)

For range optimization the switch-over is around 1900:

mysql> explain select * from ACTIVITIES WHERE activity_date > '2014-10-02';
+----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+
| id | select_type | table      | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | ACTIVITIES | NULL       | range | ACTI_DATE_I   | ACTI_DATE_I | 4       | NULL | 1897 |   100.00 | Using index condition |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0,00 sec)

mysql> explain select * from ACTIVITIES WHERE activity_date > '2014-10-01';
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table      | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | ACTIVITIES | NULL       | ALL  | ACTI_DATE_I   | NULL | NULL    | NULL | 10914 |    17.44 | Using where |
+----+-------------+------------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set, 1 warning (0,00 sec)

mysql> select count(*) from ACTIVITIES WHERE activity_date > '2014-10-02';
+----------+
| count(*) |
+----------+
|     1897 |
+----------+
1 row in set (0,00 sec)

Disregard previous comment from me, was looking at wrong WL.