MySQL Bugs: #56714: Slow MAX() on primary key retrieved by secondary index in InnoDB

Bug #56714	Slow MAX() on primary key retrieved by secondary index in InnoDB
Submitted:	10 Sep 2010 12:45	Modified:	2 Apr 2013 7:20
Reporter:	Nicholas Sherlock	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.1.50, 5.1.51-bzr	OS:	Windows
Assigned to:		CPU Architecture:	Any

Description:
If rows are retrieved from an InnoDB table by a secondary index, the results are (AFAIK) already sorted by the primary key, because that's how InnoDB's secondary indexes are laid out. 

However, if I ask for the MAX() of the primary key where the secondary key equals a given value, the optimizer's plan seems to touch every row that matches the secondary key.

How to repeat:
CREATE TABLE test (
    a INT PRIMARY KEY AUTO_INCREMENT,
    b INT NOT NULL,
    INDEX (b)
) engine=INNODB;

# Create 1,000,000 rows to fill test
CREATE TABLE integers(i INT UNSIGNED NOT NULL);
INSERT INTO integers(i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);

INSERT INTO test (b)
SELECT units.i MOD 2
FROM integers AS units
    CROSS JOIN integers AS tens
    CROSS JOIN integers AS hundreds
    CROSS JOIN integers AS thousands
    CROSS JOIN integers AS tenthousands
    CROSS JOIN integers AS hundredthousands;
    
EXPLAIN SELECT MAX(a)
FROM test
WHERE b=0;

SELECT MAX(a)
FROM test
WHERE b=0;

The result on my system was:

| id | select_type | table | type | possible_keys | key  | key_len | ref   | row
s   | Extra       |
|  1 | SIMPLE      | test  | ref  | b             | b    | 4       | const | 500
360 | Using index |

mysql> SELECT MAX(a)
    -> FROM test
    -> WHERE b=0;
+--------+
| MAX(a) |
+--------+
| 999999 |
+--------+
1 row in set (3.02 sec)

Suggested fix:
"rows" in explain should, as far as I can see, be 1, as it only needs to read the first entry in the secondary index. I would expect the query to be significantly faster.

Bug #28591 seems to be related

Reproduced on 5.1.50 now

Looks like server really reads all these 500000 rows:

macbook-pro:5.1 openxs$ bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.51-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> CREATE TABLE test (
    ->     a INT PRIMARY KEY AUTO_INCREMENT,
    ->     b INT NOT NULL,
    ->     INDEX (b)
    -> ) engine=INNODB;
Query OK, 0 rows affected (0.08 sec)

mysql> CREATE TABLE integers(i INT UNSIGNED NOT NULL);
Query OK, 0 rows affected (0.21 sec)

mysql> INSERT INTO integers(i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9);
Query OK, 10 rows affected (0.00 sec)
Records: 10  Duplicates: 0  Warnings: 0

mysql> INSERT INTO test (b)
    -> SELECT units.i MOD 2
    -> FROM integers AS units
    ->     CROSS JOIN integers AS tens
    ->     CROSS JOIN integers AS hundreds
    ->     CROSS JOIN integers AS thousands
    ->     CROSS JOIN integers AS tenthousands
    ->     CROSS JOIN integers AS hundredthousands;
Query OK, 1000000 rows affected (40.07 sec)
Records: 1000000  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT MAX(a)
    -> FROM test
    -> WHERE b=0;
+----+-------------+-------+------+---------------+------+---------+-------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref   | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+-------+--------+-------------+
|  1 | SIMPLE      | test  | ref  | b             | b    | 4       | const | 500190 | Using index |
+----+-------------+-------+------+---------------+------+---------+-------+--------+-------------+
1 row in set (0.35 sec)

mysql> show session status like 'Handler_re%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| Handler_read_first    | 0     |
| Handler_read_key      | 1     |
| Handler_read_next     | 0     |
| Handler_read_prev     | 0     |
| Handler_read_rnd      | 0     |
| Handler_read_rnd_next | 108   |
+-----------------------+-------+
6 rows in set (0.00 sec)

mysql> SELECT MAX(a)
    -> FROM test
    -> WHERE b=0;
+--------+
| MAX(a) |
+--------+
| 999999 |
+--------+
1 row in set (1.04 sec)

mysql> show session status like 'Handler_re%';
+-----------------------+--------+
| Variable_name         | Value  |
+-----------------------+--------+
| Handler_read_first    | 0      |
| Handler_read_key      | 3      |
| Handler_read_next     | 500000 |
| Handler_read_prev     | 0      |
| Handler_read_rnd      | 0      |
| Handler_read_rnd_next | 108    |
+-----------------------+--------+
6 rows in set (0.01 sec)

Note the difference in Handler_read_next values before and after query execution. So, EXPLAIN tells you the truth about (non-optimal) execution path.

This equivalent query executes instantaneously, but still has a really funky EXPLAIN:

mysql> explain SELECT a
    -> FROM test
    -> WHERE b=0
    -> ORDER BY a DESC
    -> LIMIT 1;
+----+-------------+-------+------+---------------+------+---------+-------+--------+--------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref   | rows   | Extra                    |
+----+-------------+-------+------+---------------+------+---------+-------+--------+--------------------------+
|  1 | SIMPLE      | test  | ref  | b             | b    | 4       | const | 500329 | Using where; Using index |
+----+-------------+-------+------+---------------+------+---------+-------+--------+--------------------------+
1 row in set (0.00 sec)

mysql> SELECT a
    -> FROM test
    -> WHERE b=0
    -> ORDER BY a DESC
    -> LIMIT 1;
+--------+
| a      |
+--------+
| 999999 |
+--------+
1 row in set (0.00 sec)

Seems to be fixed on 5.6.10:

mysql> EXPLAIN SELECT MAX(a)
    -> FROM test
    -> WHERE b=0;
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                        |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Select tables optimized away |
+----+-------------+-------+------+---------------+------+---------+------+------+------------------------------+
1 row in set (0.00 sec)

mysql> SELECT MAX(a)
    -> FROM test
    -> WHERE b=0;
+--------+
| MAX(a) |
+--------+
| 999999 |
+--------+
1 row in set (0.00 sec)

(removing 5.6.10 from affected versions list, whoops)

Fixed by WL#6266