[MDEV-27419] MariaDB doesn't choose DESC index for ORDER BY DESC when MySQL does Created: 2022-01-04  Updated: 2023-11-09

Status: Confirmed
Project: MariaDB Server
Component/s: Optimizer
Affects Version/s: N/A
Fix Version/s: 11.0

Type: Bug Priority: Major
Reporter: Elena Stepanova Assignee: Yuchen Pei
Resolution: Unresolved Votes: 0
Labels: optimizer-feature

Issue Links:
Problem/Incident
is caused by MDEV-13756 Implement descending index: KEY (a DE... Closed
Relates
relates to MDEV-30845 filesort still select when desc/asc i... Open

 Description   

MySQL's WL#1074 mentions a limitation:

when user has two indexes, one ASC and another DESC over the same column, optimizer won't necessary will be able to pick the right index

I suppose it applies to MariaDB as well, even though MDEV-13756 doesn't say so.

However, there might still be room for improvement. At least in some cases MySQL is able to pick up the DESC index out of two, while MariaDB isn't:

# Remove the include if you run the test on MySQL 8.0
 
--source include/have_innodb.inc
 
 
 
create table t (a int, key aa(a), key ad(a desc)) engine=InnoDB;
 
insert into t values (1),(5),(2),(8),(4),(6),(7),(9),(3);
 
 
 
explain select * from t order by a desc;
 
flush status;
 
select * from t order by a desc;
 
show status like 'Handler_read%';
 
 
 
# Cleanup
 
drop table t;

MariaDB preview-10.8-MDEV-13756-desc-indexes 43444ff5

 
explain select * from t order by a desc;
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 
1	SIMPLE	t	index	NULL	aa	5	NULL	9	Using index
 
 
 
Handler_read_first	0
 
Handler_read_key	0
 
Handler_read_last	1
 
Handler_read_next	0
 
Handler_read_prev	9
 
Handler_read_retry	0
 
Handler_read_rnd	0
 
Handler_read_rnd_deleted	0
 
Handler_read_rnd_next	0

MySQL 8.0.23

 
explain select * from t order by a desc;
 
id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 
1	SIMPLE	t	NULL	index	NULL	ad	5	NULL	10	100.00	Using index
 
 
 
Handler_read_first	1
 
Handler_read_key	1
 
Handler_read_last	0
 
Handler_read_next	9
 
Handler_read_prev	0
 
Handler_read_rnd	0
 
Handler_read_rnd_next	0

ANALYZE/statistics collection doesn't change the outcome.

Same happens on MariaDB with MyISAM/Aria (ASC index is chosen), but it's not comparable to MySQL because MySQL doesn't support DESC indexes on MyISAM tables.

 Comments   
Comment by Sergei Golubchik [ 2022-01-06 ]

We cannot do it in 10.8 properly. A simple heuristics would solve this particular case:

--- a/sql/sql_select.cc
 
+++ b/sql/sql_select.cc
 
@@ -29143,6 +29143,7 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
 
               (select_limit <= MY_MIN(quick_records,best_records) ?
 
                keyinfo->user_defined_key_parts < best_key_parts :
 
                quick_records < best_records) ||
 
+              direction > best_key_direction ||
 
               (!is_best_covering && is_covering))
 
           {
 
             possible_key.add("chosen", true);

But a universal fix should be cost based, with a new handler method to retrieve the cost of the reverse scan, proper estimation for index_scan_time, etc.

psergei, what do you think, shall we have a direction heuristics here until a cost based choice is implemented?

Generated at Thu Feb 08 09:52:46 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.