Bug #57430 query optimizer does not pick covering index for some "order by" queries
Submitted: 13 Oct 2010 13:41 Modified: 23 Nov 2015 10:42
Reporter: richard prohaska Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.5.6-rc, 5.5.7 OS:Linux
Assigned to: CPU Architecture:Any
Triage: Triaged: D3 (Medium)

[13 Oct 2010 13:41] richard prohaska
Description:
the query optimizer does not pick a covering index for some "order by" queries.  suppose that a table has 2 keys with the same row estimate cost that may be used to optimize a query.  the query optimizer will pick the first usable index even when the second usable key is a covering key.  the covering key will have better performance.  

How to repeat:
create table t2970 (a int, b int, c int, d int, key(a), key(a,b));
insert into t2970 values (1,1,1,1),(1,2,3,4);
explain select a,count(b),max(b) from t2970 where a > 0 group by a order by a;

should pick the covering key a_2.

Suggested fix:
+++ sql_select.cc	(working copy)
@@ -17503,7 +17503,8 @@
           if (best_key < 0 ||
               (select_limit <= min(quick_records,best_records) ?
                keyinfo->key_parts < best_key_parts :
-               quick_records < best_records))
+               quick_records < best_records) ||
+              (quick_records == best_records && !is_best_covering && is_covering))
           {
             best_key= nr;
             best_key_parts= keyinfo->key_parts;
[13 Oct 2010 13:57] Valeriy Kravchuk
I think this is a duplicate of bug #36817. Please, check.

Look:

macbook-pro:5.5 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 6
Server version: 5.5.7-rc-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 t2970 (a int, b int, c int, d int, key(a), key(a,b));
Query OK, 0 rows affected (0.05 sec)

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

mysql> explain select a,count(b),max(b) from t2970 where a > 0 group by a order by a;
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | t2970 | index | a,a_2         | a    | 5       | NULL |    2 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql> analyze table t2970;
+------------+---------+----------+----------+
| Table      | Op      | Msg_type | Msg_text |
+------------+---------+----------+----------+
| test.t2970 | analyze | status   | OK       |
+------------+---------+----------+----------+
1 row in set (0.01 sec)

mysql> explain select a,count(b),max(b) from t2970 where a > 0 group by a order by a;
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | t2970 | index | a,a_2         | a    | 5       | NULL |    2 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql> alter table t2970 engine=InnoDB;
Query OK, 2 rows affected (0.42 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> explain select a,count(b),max(b) from t2970 where a > 0 group by a order by a;
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | t2970 | index | a,a_2         | a    | 5       | NULL |    2 | Using where |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql> alter table t2970 drop key a;
Query OK, 0 rows affected (0.41 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> alter table t2970 drop key a_2;
Query OK, 0 rows affected (0.06 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> alter table t2970 add key a_2(a,b), add key a(a);Query OK, 0 rows affected (0.08 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> explain select a,count(b),max(b) from t2970 where a > 0 group by a order by a;
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+
|  1 | SIMPLE      | t2970 | index | a_2,a         | a_2  | 10      | NULL |    2 | Using where; Using index |
+----+-------------+-------+-------+---------------+------+---------+------+------+--------------------------+
1 row in set (0.00 sec)
[13 Oct 2010 14:05] richard prohaska
this bug is different than 36817.  the keys in 36817 are not covering keys for the queries (id1 is not in the key).
[13 Oct 2010 14:13] Valeriy Kravchuk
OK, let's optimizer team decide. The bug is verified with current mysql-5.5 from bzr, as one can see from my previous comment.
[21 Apr 2011 3:26] Zardosht Kasheff
proposed patch

Attachment: 57430.diff (application/octet-stream, text), 634 bytes.

[23 Nov 2015 9:43] Olav Sandstå
This bug is fixed in MySQL 5.7.5 by the following commit:

commit 53f8b10dbab927df207339a7fc4136d8987cc2bb
Author: Jorgen Loland <jorgen.loland@oracle.com>
Date:   Fri Apr 25 10:34:42 2014 +0200

Bug#18035906: TEST_IF_SKIP_SORT_ORDER INCORRECTLY CHOSES
              NON-COVERING INDEX FOR ORDERING

test_if_skip_sort_order() didn't check if an index scan had
earlier been chosen and would therefore possibly replace it
with a different index scan. If the first index scan was
covering and the one chosen by test_if_skip_sort_order() was not,
a worse plan would be the result.
    
Fixed by making test_if_skip_sort_order() index scan aware.