Bug #74030 Filesort chosen where index should've been, using LIMIT
Submitted: 23 Sep 2014 7:54 Modified: 26 Jun 2017 11:57
Reporter: Edgars Irmejs (OCA) Email Updates:
Status: In progress Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:8.0dev, 5.7.16, 5.6.20, 5.5.39, OS:Any
Assigned to: Assigned Account CPU Architecture:Any
Tags: Contribution

[23 Sep 2014 7:54] Edgars Irmejs
Description:
There are cases where MySQL chooses the wrong index in "SELECT..ORDER..LIMIT" statement execution, causing unnecessary filesort. These cases require multiple indexes which all start with fields f1..fn, a condition WHERE f1=c1 AND... fn=cn, and a sort clause with fields fn+1..fm, where the indexes cover all of them. Given unfortunate index statistics, MySQL chooses an index which requires a filesort, even when other indexes don't.
See the the appended testcase "test1.sh". Although making a testcase for InnoDB, instead of MyISAM, is difficult, I have tables in production whose index statistics prefer the wrong index, for the same reasons. I have appended an optimizer_trace output from Percona Server 5.6.13 of the production case.

I propose the patch added, following this reasoning:
"test_if_skip_sort_order" "ref_key" is chosen by "best_access_path" which doesn't care about the order clause, just index statistics. It is allowed for the chosen index to start with the referenced fields, cover the sort fields, yet have extra fields in-between and/or have the remaining fields in an order which does not match the order clause. This means that checking "!usable_keys.is_set(ref_key)" is too weak for verifying if alternatives should be considered. We need to call "test_if_order_by_key" to see if alternative keys need be considered.

It would be more powerful to fix the "best_access_path" to take the sort and limit into account, as it would also fix a bug where optimizer chooses "ref" with few keyparts from an index which could and should be used fully ("best_access_path" decides for a partial index scan with "ref", and no heuristics hacks fix the choice later on), testcase appended as "test2.sh", and it would allow for correct cost comparison where a "filesort" index needs an index only read but the correctly sorted index needs to read out of table, yet a limited amount of rows. I would avoid such a fix because "best_access_path" has a lot of dependencies and the MySQL Optimizer Cost Model Project aims to fix the issues in 5.7 or later. Neither of the mentioned problems are fixed yet as of 5.7.4 though.

Right now, the "test_if_skip_sort_order" patch is simple enough to be pushable even into 5.6, if the MySQL policy allows for any optimizer changes.

How to repeat:
#### test1.sh (for reproducing this problem) ####

#!/bin/bash

my="mysql test"

echo "drop table test.t" | $my
echo "create table if not exists test.t (id int not null primary key auto_increment, a int, b int, c int, key idx_ac(a,c), key idx_abc(a,b,c)) engine=myisam" | $my

echo -n "Loading the table with data "
counter=0
rows=
add_row() {
        if [ "${#rows}" -ne 0 ]; then
                rows="$rows, "
        fi
        rows="$rows$1"
}
commit_rows() {
        if [ "${#rows}" -ne 0 ]; then
                echo "insert into test.t (a, b, c) values $rows" | $my 2>&1 | grep -v password
                rows=
        fi
}
insert_loop() {
        for a in `eval echo {$1..$2}`; do
                for b in `eval echo {$3..$4}`; do
                        for c in `eval echo {$5..$6}`; do
                                if [ $((counter%100)) -eq 0 ]; then
                                        commit_rows
                                        echo -n .
                                fi
                                ((counter++))
                                add_row "($a, $b, $c)"
                        done
                done
        done
}
insert_loop     1 1     1 3     1 2000
insert_loop     2 200   1 1     1 5
commit_rows
echo

echo "For this query plan, the index idx_ac should been chosen!"
echo "alter table test.t engine=myisam" | $my # Needs to be MyISAM because it is more difficult to persuade InnoDB to use the wrong index, however - possible.
echo "analyze table test.t" | $my
echo "explain select c from test.t where a = 2 order by c desc limit 1" | $my -vvv

#### test2.sh (for understanding the related issue mentioned) ####

#!/bin/bash

my="mysql test"

echo "drop table if exists test.t" | $my
echo "create table if not exists test.t (id int not null primary key auto_increment, a int, b int, c int, key idx_ab(a,b)) engine=innodb" | $my

echo -n "Loading the table with data "
counter=0
rows=
add_row() {
        if [ "${#rows}" -ne 0 ]; then
                rows="$rows, "
        fi
        rows="$rows$1"
}
commit_rows() {
        if [ "${#rows}" -ne 0 ]; then
                echo "insert into test.t (a, b, c) values $rows" | $my 2>&1 | grep -v password
                rows=
        fi
}
insert_loop() {
        for a in `eval echo {$1..$2}`; do
                for b in `eval echo {$3..$4}`; do
                        for c in `eval echo {$5..$6}`; do
                                if [ $((counter%100)) -eq 0 ]; then
                                        commit_rows
                                        echo -n .
                                fi
                                ((counter++))
                                add_row "($a, $b, $c)"
                        done
                done
        done
}
insert_loop     1 1     1 1000  1 1
commit_rows
echo

echo "For this query plan, all keypars of idx_abc should be used in a 'range' access. See the 'FORCE INDEX' plan for the correct choice."
echo "alter table test.t engine=innodb" # Works with either MyISAM and InnoDB because in both cases a partial index scan is chosen.
echo "analyze table test.t" | $my
echo "explain select c from test.t where a = 1 and b > 500 order by b limit 1" | $my -vvv
echo "explain select c from test.t force index (idx_ab) where a = 1 and b > 500 order by b limit 1" | $my -vvv

Suggested fix:

#### Patch for 5.7.4 ####

--- sql/sql_optimizer_original.cc       2014-09-23 06:44:36.536520277 +0300
+++ sql/sql_optimizer.cc        2014-09-23 10:51:45.535263262 +0300
@@ -1537,11 +1537,13 @@
     /*
       We come here when there is a {ref or or ordered range access} key.
     */
-    if (!usable_keys.is_set(ref_key))
+    if (!usable_keys.is_set(ref_key) ||
+        !(order_direction= test_if_order_by_key(order,table,ref_key,
+                                              &used_key_parts)))
     {
       /*
-        We come here when ref_key is not among usable_keys, try to find a
-        usable prefix key of that key.
+        We come here when ref_key can not be used to get the rows in
+        requested sorted order, try to find a usable prefix key of that key.
       */
       uint new_ref_key;
       /*
@@ -1613,8 +1615,9 @@
     }
     /* Check if we get the rows in requested sorted order by using the key */
     if (usable_keys.is_set(ref_key) &&
-        (order_direction= test_if_order_by_key(order,table,ref_key,
-                                              &used_key_parts)))
+        (order_direction ||
+         (order_direction= test_if_order_by_key(order,table,ref_key,
+                                              &used_key_parts))))
       goto check_reverse_order;
   }
   {

#### Patch for 5.6.20 ####

--- sql/sql_select_original.cc  2014-09-23 10:45:26.985759544 +0300
+++ sql/sql_select.cc   2014-09-23 10:50:53.540117025 +0300
@@ -3964,11 +3964,13 @@
     /*
       We come here when there is a {ref or or ordered range access} key.
     */
-    if (!usable_keys.is_set(ref_key))
+    if (!usable_keys.is_set(ref_key) ||
+        !(order_direction= test_if_order_by_key(order,table,ref_key,
+                                              &used_key_parts)))
     {
       /*
-        We come here when ref_key is not among usable_keys, try to find a
-        usable prefix key of that key.
+        We come here when ref_key can not be used to get the rows in
+        requested sorted order, try to find a usable prefix key of that key.
       */
       uint new_ref_key;
       /*
@@ -4040,8 +4042,9 @@
     }
     /* Check if we get the rows in requested sorted order by using the key */
     if (usable_keys.is_set(ref_key) &&
-        (order_direction= test_if_order_by_key(order,table,ref_key,
-                                              &used_key_parts)))
+        (order_direction ||
+         (order_direction= test_if_order_by_key(order,table,ref_key,
+                                              &used_key_parts))))
       goto check_reverse_order;
   }
   {
[23 Sep 2014 7:55] Edgars Irmejs
InnoDB case where the problem occurs in production use

Attachment: trace_bug_74030.log (application/octet-stream, text), 16.96 KiB.

[26 Sep 2014 11:32] Umesh Shastry
Hello Edgars,

Thank you for reporting the issue, and supplying a patch along with it.
Please note that in order to submit contributions you must first sign the Oracle Contribution Agreement (OCA).

For additional information please check 

http://www.oracle.com/technetwork/community/oca-486395.html.
If you have any questions, please contact the MySQL community team - http://www.mysql.com/about/contact/?topic=community.

Thanks,
Umesh
[26 Sep 2014 11:33] Umesh Shastry
// With 5.6.22

[root@cluster-repo mysql-advanced-5.6.22]# ./test.sh
Loading the table with data ......................................................................
For this query plan, the index idx_ac should been chosen!
Table   Op      Msg_type        Msg_text
test.t  analyze status  Table is already up to date
--------------
explain select c from test.t where a = 2 order by c desc limit 1
--------------

+----+-------------+-------+------+----------------+---------+---------+-------+------+------------------------------------------+
| id | select_type | table | type | possible_keys  | key     | key_len | ref   | rows | Extra                                    |
+----+-------------+-------+------+----------------+---------+---------+-------+------+------------------------------------------+
|  1 | SIMPLE      | t     | ref  | idx_ac,idx_abc | idx_abc | 5       | const |    5 | Using where; Using index; Using filesort |
+----+-------------+-------+------+----------------+---------+---------+-------+------+------------------------------------------+
1 row in set (0.00 sec)

Bye
[root@cluster-repo mysql-advanced-5.6.22]# ./test2.sh
Loading the table with data ..........
For this query plan, all keypars of idx_abc should be used in a 'range' access. See the 'FORCE INDEX' plan for the correct choice.
alter table test.t engine=innodb
Table   Op      Msg_type        Msg_text
test.t  analyze status  OK
--------------
explain select c from test.t where a = 1 and b > 500 order by b limit 1
--------------

+----+-------------+-------+------+---------------+--------+---------+-------+------+------------------------------------+
| id | select_type | table | type | possible_keys | key    | key_len | ref   | rows | Extra                              |
+----+-------------+-------+------+---------------+--------+---------+-------+------+------------------------------------+
|  1 | SIMPLE      | t     | ref  | idx_ab        | idx_ab | 5       | const |  500 | Using index condition; Using where |
+----+-------------+-------+------+---------------+--------+---------+-------+------+------------------------------------+
1 row in set (0.00 sec)

Bye
--------------
explain select c from test.t force index (idx_ab) where a = 1 and b > 500 order by b limit 1
--------------

+----+-------------+-------+-------+---------------+--------+---------+------+------+-----------------------+
| id | select_type | table | type  | possible_keys | key    | key_len | ref  | rows | Extra                 |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-----------------------+
|  1 | SIMPLE      | t     | range | idx_ab        | idx_ab | 10      | NULL |  500 | Using index condition |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-----------------------+
1 row in set (0.00 sec)
[4 Oct 2014 10:51] Edgars Irmejs
OCA approved.

I assume you tested the non-patched version, as the wrong index is chosen in test.sh.

No need to run test2.sh - it was only made to show that the MySQL Optimizer Cost Model Project is very necessary, and I put high hopes on it. The bug shown by test2.sh is not being fixed by the patch.

If anything else is needed from me, let me know.
[9 Dec 2016 15:10] Jeremie Rioux
I'm affected. Any update? Doesn't seem to be fixed even in latest 5.7 version.
[12 Dec 2016 18:11] Edgars Irmejs
They actually did the Optimizer Cost Model project in 5.7.5 but the implementation did not fix this issue. It's unresolved in 8.0 branch too.

I see the commit "WL#7870: Create JOIN object after query preparation" has dealt with the test2.sh problem but the main one, that of test1.sh, still remains.

Thanks for raising awareness that this issue matters!
[26 Jun 2017 11:57] Manyi Lu
Hi, thanks for you contribution. We are currently looking into improving cost model for index vs filesort decision. As part of this work, we will process your contribution. We will certainly make sure your test cases are covered. 

We welcome more contributions!