Bug #106003 MySQL does not use indexes correctly for backwards ORDER BY conditions
Submitted: 29 Dec 2021 20:06 Modified: 30 Dec 2021 9:28
Reporter: Domas Mituzas Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:8.0.27/5.7 OS:Any
Assigned to: CPU Architecture:Any

[29 Dec 2021 20:06] Domas Mituzas
Description:
There are multiple bugs in how MySQL is not using composite indexes for ORDER BY ... LIMIT optimizations.

In some cases it will use "index" plan, even if that means scanning 100x more rows  and forced "ref" plan is super-efficient.

In other cases it will not use ordered index and will pick another index that doesn't have the order, even if prefer_ordering_index=on is set up.

Example bad query plans:

mysql> explain select le from lb where a=1 order by b desc, c asc limit 10 ;
+----+-------------+-------+------------+------+---------------+------+---------+-------+-------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref   | rows  | filtered | Extra                       |
+----+-------------+-------+------------+------+---------------+------+---------+-------+-------+----------+-----------------------------+
|  1 | SIMPLE      | lb    | NULL       | ref  | fwd,rev       | fwd  | 5       | const | 18962 |   100.00 | Using index; Using filesort |
+----+-------------+-------+------------+------+---------------+------+---------+-------+-------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select le from lb where a=2 order by b desc, c asc limit 10 ;
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                         |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------------------------+
|  1 | SIMPLE      | lb    | NULL       | index | fwd,rev       | rev  | 20      | NULL |   20 |    50.00 | Using where; Backward index scan; Using index |
+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-----------------------------------------------+
1 row in set, 1 warning (0.01 sec)

it works fine with FORCE:

mysql> explain analyze select le from lb where a=1 order by b desc, c asc limit 10 \G
*************************** 1. row ***************************
EXPLAIN: -> Limit: 10 row(s)  (cost=1910.31 rows=10) (actual time=3.939..3.940 rows=10 loops=1)
    -> Sort: lb.b DESC, lb.c, limit input to 10 row(s) per chunk  (cost=1910.31 rows=18962) (actual time=3.938..3.938 rows=10 loops=1)
        -> Index lookup on lb using fwd (a=1)  (actual time=0.018..2.482 rows=10000 loops=1)

1 row in set (0.00 sec)

mysql> explain analyze select le from lb where a=2 order by b desc, c asc limit 10 \G
*************************** 1. row ***************************
EXPLAIN: -> Limit: 10 row(s)  (cost=0.01 rows=10) (actual time=3.456..3.458 rows=10 loops=1)
    -> Filter: (lb.a = 2)  (cost=0.01 rows=10) (actual time=3.454..3.456 rows=10 loops=1)
        -> Covering index scan on lb using rev (reverse)  (cost=0.01 rows=20) (actual time=0.020..2.966 rows=10010 loops=1)

1 row in set (0.00 sec)

mysql> explain analyze select le from lb force index(rev) where a=1 order by b desc, c asc limit 10 \G
*************************** 1. row ***************************
EXPLAIN: -> Limit: 10 row(s)  (cost=1910.31 rows=10) (actual time=0.038..0.041 rows=10 loops=1)
    -> Covering index lookup on lb using rev (a=1; iterate backwards)  (cost=1910.31 rows=18962) (actual time=0.037..0.039 rows=10 loops=1)

1 row in set (0.00 sec)

mysql> explain analyze select le from lb force index(rev) where a=2 order by b desc, c asc limit 10 \G
*************************** 1. row ***************************
EXPLAIN: -> Limit: 10 row(s)  (cost=6053.78 rows=10) (actual time=0.035..0.038 rows=10 loops=1)
    -> Covering index lookup on lb using rev (a=2; iterate backwards)  (cost=6053.78 rows=60096) (actual time=0.034..0.036 rows=10 loops=1)

How to repeat:
(ints table is just 1..1000000 numbers for easier data population).

create table lb (le int auto_increment, a int, b int, c int, u int, primary key (le), index fwd (a, b asc, c asc, u), index rev (a, b asc, c desc, u));
insert into lb (a,b,c,u) select 1, a, rand()*10000, rand()*1000000 from ints limit 10000;
insert into lb (a,b,c,u) select 2, a, rand()*10000, rand()*1000000 from ints limit 100000;
insert into lb (a,b,c,u) select 3, a, rand()*10000, rand()*1000000 from ints limit 10000;
explain select le from lb where a=1 order by b desc, c asc limit 10 ;
explain select le from lb where a=2 order by b desc, c asc limit 10 ;

Suggested fix:
avoid doing index scans if better range condition is possible
prefer index-order reads if there's an index in place
[29 Dec 2021 20:11] Domas Mituzas
(this is on 8.0.27)
[30 Dec 2021 9:28] MySQL Verification Team
Thank you for the bug report.