| Bug #74030 | Filesort chosen where index should've been, using LIMIT | ||
|---|---|---|---|
| Submitted: | 23 Sep 2014 7:54 | Modified: | 11 Apr 2020 2:15 |
| Reporter: | Edgars Irmejs (OCA) | Email Updates: | |
| Status: | Closed | Impact on me: | |
| 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: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]
MySQL Verification Team
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]
MySQL Verification Team
// 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!
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; } {