Details
-
Bug
-
Status: Confirmed (View Workflow)
-
Major
-
Resolution: Unresolved
-
N/A
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.
Attachments
Issue Links
- is caused by
-
MDEV-13756 Implement descending index: KEY (a DESC, b ASC)
-
- Closed
-
- relates to
-
-
- Open
-
Activity
| Field | Original Value | New Value |
|---|---|---|
| Link |
This issue is caused by |
| Assignee | Sergei Golubchik [ serg ] |
| Description |
MySQL's [WL#1074|https://dev.mysql.com/worklog/task/?id=1074] mentions a limitation:
{quote} 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 {quote} I suppose it applies to MariaDB as well, even though 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: {code:sql} # 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; {code} {code:sql|title=MariaDB preview-10.8- 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 {code} {code:sql|title=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 {code} ANALYZE/statistics collection doesn't change the outcome. Same happens on MariaDB with MyISAM/Aria, but it's not comparable to MySQL because MySQL doesn't support DESC indexes on MyISAM tables. |
MySQL's [WL#1074|https://dev.mysql.com/worklog/task/?id=1074] mentions a limitation:
{quote} 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 {quote} I suppose it applies to MariaDB as well, even though 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: {code:sql} # 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; {code} {code:sql|title=MariaDB preview-10.8- 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 {code} {code:sql|title=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 {code} 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. |
| Status | Open [ 1 ] | Confirmed [ 10101 ] |
| Assignee | Sergei Golubchik [ serg ] | Sergei Petrunia [ psergey ] |
| Fix Version/s | 10.12 [ 28320 ] | |
| Fix Version/s | 10.8 [ 26121 ] |
| Component/s | Optimizer [ 10200 ] | |
| Component/s | Server [ 13907 ] |
| Priority | Critical [ 2 ] | Major [ 3 ] |
| Link | This issue relates to MDEV-30845 [ MDEV-30845 ] |
| Labels | optimizer-feature |
| Assignee | Sergei Petrunia [ psergey ] | Yuchen Pei [ JIRAUSER52627 ] |
Note: in MySQL-8.4 it's still done with a basic heuristic:
if (best_key < 0 || |
(select_limit <= min(quick_records, best_records)
|
? keyinfo->user_defined_key_parts < best_key_parts
|
: quick_records < best_records) ||
|
// We assume forward scan is faster than backward even if the |
// key is longer. This should be taken into account in cost |
// calculation. |
direction > best_key_direction) {
|
best_key = nr;
|
best_key_parts = keyinfo->user_defined_key_parts;
|
if (saved_best_key_parts) *saved_best_key_parts = used_key_parts; |
best_records = quick_records;
|
is_best_covering = is_covering;
|
best_key_direction = direction;
|
best_select_limit = select_limit;
|
We can adapt the heuristics to the cost based model, see the following commit
upstream/bb-11.1-mdev-27419 cdeaefee21ce425211fdedd0092397ad0ac7dc2b MDEV-27419 [demo/check-ci] choose desc key for desc ordering
|
modified sql/sql_select.cc
|
@@ -32369,11 +32369,10 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
|
|
/*
|
We will try use the key if:
|
- - If there is no ref key and no usable keys has yet been found and
|
- there is either a group by or a FORCE_INDEX
|
- If the new cost is better than read_time
|
*/
|
- if (range_cost < read_time)
|
+ if (range_cost < read_time ||
|
+ (range_cost == read_time && direction > best_key_direction))
|
{
|
read_time= range_cost;
|
possible_key.add("chosen", true); |
To integrate the direction matching in the cost based model, it seems we need a KEY_PREV_FIND_COST with a higher cost than KEY_NEXT_FIND_COST below, which will be used in the calculation when the key direction is the opposite of the order direction
IO_AND_CPU_COST handler::ha_keyread_time(uint index, ulong ranges,
|
ha_rows rows,
|
ulonglong blocks)
|
{
|
if (rows < ranges) |
rows= ranges;
|
IO_AND_CPU_COST cost= keyread_time(index, ranges, rows, blocks);
|
cost.cpu+= ranges * KEY_LOOKUP_COST + (rows - ranges) * KEY_NEXT_FIND_COST;
|
return cost; |
}
|
Here's a partial stack leading to the function:
0 in handler::ha_keyread_time of /home/ycp/source/mariadb-server/11.1/src/sql/handler.cc:3439
|
1 in cost_for_index_read of /home/ycp/source/mariadb-server/11.1/src/sql/sql_select.cc:8171
|
2 in get_range_limit_read_cost of /home/ycp/source/mariadb-server/11.1/src/sql/sql_select.cc:32034
|
3 in test_if_cheaper_ordering of /home/ycp/source/mariadb-server/11.1/src/sql/sql_select.cc:32355
|
4 in test_if_skip_sort_order of /home/ycp/source/mariadb-server/11.1/src/sql/sql_select.cc:26813
|
5 in JOIN::optimize_stage2 of /home/ycp/source/mariadb-server/11.1/src/sql/sql_select.cc:3433
|
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)){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?