[MDEV-13756] Implement descending index: KEY (a DESC, b ASC) - Jira

Details

Type: Task
Status: Closed (View Workflow)
Priority: Blocker
Resolution: Fixed
Fix Version/s: 10.8.1
Component/s: Optimizer, Storage Engine - InnoDB
Labels:

Description

MySQL 8.0 introduced support for descending indexes in WL#1074. This involved some changes in InnoDB and many in the optimizer.

MariaDB and older versions of MySQL silently ignore the ASC/DESC attribute in KEY definitions. All index fields (KEY_PART) are sorted in ascending order.

The Oracle database defines the NULLS FIRST and NULLS LAST attributes for the ORDER BY clause, but not for CREATE INDEX. The defaults are the exact opposite of InnoDB behaviour:

NULLS LAST is the default for ascending order, and NULLS FIRST is the default for descending order.

InnoDB in MariaDB and before MySQL 8.0 supports only ascending order, and it sorts NULLS FIRST, not NULLS LAST like the above quote suggests Oracle to do.

Attachments

Issue Links

causes

MDEV-27300 Result differs with DESC index upon comparison of timestamp with incompatible value

Open

MDEV-27303 Table corruption after insert into a non-InnoDB table with DESC index

Closed

MDEV-27309 Server crash or ASAN memcpy-param-overlap upon INSERT into Aria/MyISAM table with DESC key

Closed

MDEV-27330 Wrong sorting order with DESC index and empty strings in MyISAM/Aria table

Closed

MDEV-27340 NULL gets lost (becomes empty string), SELECT hangs with DESC index on MyISAM/Aria table

Closed

MDEV-27347 MyISAM/Aria table is marked as crashed upon updating NULL values in DESC index

Closed

MDEV-27374 InnoDB table becomes corrupt after renaming DESC-indexed column

Closed

MDEV-27392 DESC attribute is ignored when index is re-created within single ALTER on InnoDB table

Closed

MDEV-27393 Timezone tables cannot have descending indexes

Closed

MDEV-27396 DESC index attribute remains in Archive table definition, despite being apparently ignored

Closed

MDEV-27398 DESC index causes wrong (empty) result on Federated tables

Closed

MDEV-27406 Index on a HEAP table retains DESC attribute despite being hash

Closed

MDEV-27407 Different ASC/DESC index attributes on MERGE and underlying table can cause wrong results

Closed

MDEV-27408 DESC index on a Mroonga table causes wrong order of result set

Closed

MDEV-27419 MariaDB doesn't choose DESC index for ORDER BY DESC when MySQL does

Confirmed

MDEV-27420 Spider tables retain DESC attribute on indexes even though it has no meaning

Closed

MDEV-27426 Wrong result upon query using index_merge with DESC key

Closed

MDEV-27432 ASC/DESC primary and unique keys cause index inconsistency between InnoDB and server

Closed

MDEV-27434 DESC attribute does not work with auto-increment on secondary column of multi-part index

Closed

MDEV-27439 AUTO_INCREMENT columns with DESC index do not work

Closed

MDEV-27445 Index inconsistency and assertion failure after renaming virtual column with DESC key

Closed

MDEV-27529 Wrong result upon query using index_merge with DESC key (#2)

Closed

MDEV-27576 Use DESC indexes for MIN/MAX optimization

Closed

MDEV-27578 DESC attribute upon spatial index creation prevents ER_DUP_INDEX warning

Open

MDEV-27580 Bogus warning ER_TRUNCATED_WRONG_VALUE with DESC key on partitioned Spider table

Open

MDEV-27581 Wrong result with DESC key on partitioned Spider table

Closed

MDEV-27585 Auto-increment on secondary column increments unexpectedly with DESC key

Closed

MDEV-27586 Auto-increment does not work with DESC on MERGE table

Closed

MDEV-27588 MyISAM/Aria descending index compression is not as efficient as ascending

Closed

MDEV-27589 OQGRAPH returns a different result set if backing table has descending PK

Open

MDEV-27590 Auto-increment on Spider tables with DESC PK does not work properly

Closed

MDEV-27591 Connect tables (FIX/DOS) don't work with DESC keys - wrong results

Closed

MDEV-27592 DESC keys: Data corruption or Assertion `index->n_core_null_bytes <= (((index->n_nullable) + 7) >> 3) || index->in_instant_init' failed

Closed

MDEV-27617 HANDLER KEY > (x) does not work with DESC keys, Spider is affected and returns wrong results

Closed

MDEV-27623 Wrong result with DESC key on InnoDB table

Closed

MDEV-27633 Wrong result with different direction of index on Spider and underlying tables in handler mode

Open

MDEV-27683 EXCHANGE PARTITION allows different index direction, but causes further errors

Closed

MDEV-29047 RocksDB retains unsupported DESC key option after error, causes further failures

Open

MDEV-30845 filesort still select when desc/asc index matches ORDER BY

Open

MDEV-35169 ALTER TABLE...IMPORT TABLESPACE does not work with INDEX DESC

Closed

includes

MDEV-26938 support descending indexes internally in InnoDB

Closed

MDEV-26939 support descending indexes for simple ORDER BY

Closed

MDEV-26996 Support descending indexes in the range optimizer

Closed

is part of

MDEV-27373 Q1 2022 release merge

Closed

relates to

MDEV-4621 select returns null for information_schema.statistics.collation field

Closed

MDEV-23571 InnoDB does not raise a warning if ALTER TABLE index operations are optimized away

Open

MDEV-27577 Recovery behaves differently with DESC PK in innodb.leaf_page_corrupted_during_recovery

Closed

MDEV-27302 Backward index scan is not reflected in EXPLAIN output

Open

MDEV-27582 Fulltext search DDL decrements FTS_DOC_ID

Closed

MDEV-35849 InnoDB: index records in a wrong order upon CHECK with DESC index

Closed

(35 causes, 3 includes, 1 is part of, 6 relates to)

Activity

Ascending order - Click to sort in descending order

Tom Conlon added a comment - 2020-09-22 18:38 - edited

Two years since MySQL supported this and no progress on this fundamental feature unfortunately.

Am aware that we can use a kludge for this:
Persistent columns - but it reminds me of Firebird years ago when a similar kludge was needed
(extra column populated by a trigger).

Eventually Firebird (always kept close to ANSI standards, don't know if this syntax is or not) but they implemented:
*CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX <index name> ON <table name>
COMPUTED BY ( <value expression> )*
And this was transparent to the user. No extra fields, no extra triggers, and was able to use these indexes where ORDER BY queries contained the COMPUTED BY expression.

Be great to have something similarly implemented but if not then - in 2020 - just:
*CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX <index name> *
where the DESC clause wasn't ignored, would be beyond most welcome.

Genuine thanks for all the work

Tom Conlon added a comment - 2020-09-22 18:38 - edited Two years since MySQL supported this and no progress on this fundamental feature unfortunately. Am aware that we can use a kludge for this: Persistent columns - but it reminds me of Firebird years ago when a similar kludge was needed (extra column populated by a trigger). Eventually Firebird (always kept close to ANSI standards, don't know if this syntax is or not) but they implemented: *CREATE [UNIQUE] [ASC [ENDING] | DESC [ENDING] ] INDEX <index name> ON <table name> COMPUTED BY ( <value expression> )* And this was transparent to the user. No extra fields, no extra triggers, and was able to use these indexes where ORDER BY queries contained the COMPUTED BY expression. Be great to have something similarly implemented but if not then - in 2020 - just: *CREATE [UNIQUE] [ASC [ENDING] | DESC [ENDING] ] INDEX <index name> * where the DESC clause wasn't ignored , would be beyond most welcome. Genuine thanks for all the work

ssauravy added a comment - 2021-08-11 04:45

It was missing in MariaDB 10.6, and it is also excluded in the 10.7 plan.
Surprisingly, there are many cases of choosing MySQL between MySQL and MariaDB for performance issues caused by this problem.

ssauravy added a comment - 2021-08-11 04:45 It was missing in MariaDB 10.6, and it is also excluded in the 10.7 plan. Surprisingly, there are many cases of choosing MySQL between MySQL and MariaDB for performance issues caused by this problem.

Sergei Petrunia added a comment - 2021-12-07 20:25

For those who were wondering whether MyRocks upstream supports these indexes: it doesn't:

mysql> create table t1 (a int, b int, key(a desc));

Query OK, 0 rows affected (0.05 sec)

mysql> alter table t1 engine=rocksdb;

ERROR 1178 (42000): The storage engine for the table doesn't support descending indexes

This is latest fb-mysql-8.0,

commit 0a03beadc6f4a9aa247ee2e886b542ff02182f0c (HEAD -> fb-mysql-8.0.20, origin/fb-mysql-8.0.20)

Author: Chi-I Huang <chii@fb.com>

Date:   Thu Nov 18 17:18:42 2021 -0800

    Build column lineage info from SELECT_LEX_UNIT, SELECT_LEX and TABLE_LIST

Sergei Petrunia added a comment - 2021-12-07 20:25 For those who were wondering whether MyRocks upstream supports these indexes: it doesn't: mysql> create table t1 (a int, b int, key(a desc)); Query OK, 0 rows affected (0.05 sec) mysql> alter table t1 engine=rocksdb; ERROR 1178 (42000): The storage engine for the table doesn't support descending indexes This is latest fb-mysql-8.0, commit 0a03beadc6f4a9aa247ee2e886b542ff02182f0c (HEAD -> fb-mysql-8.0.20, origin/fb-mysql-8.0.20) Author: Chi-I Huang <chii@fb.com> Date: Thu Nov 18 17:18:42 2021 -0800 Build column lineage info from SELECT_LEX_UNIT, SELECT_LEX and TABLE_LIST

Elena Stepanova added a comment - 2022-01-24 02:12 - edited

The last tested revision, preview-10.8-MDEV-13756-desc-indexes / c10e10c, has shown generally acceptable results, I think the feature can be merged into the main branch and released with 10.8.1 without a new round of tests, provided that the following issues are addressed:

DESC key attribute becomes prohibited for CONNECT and SPIDER engines to avoid revealed problems leading to wrong results (~~MDEV-27591~~, ~~MDEV-27590~~, ~~MDEV-27581~~ and likely more);
~~MDEV-27592~~ (InnoDB index corruption) gets fixed – I assume if the fix requires extra testing, it will be done within InnoDB team before the push;
MIN/MAX optimization is not enabled before the release, but instead ~~MDEV-27576~~ is targeted for 10.9+ (if any at all). If it is enabled, further testing will be definitely required.

There are other open bugs related to the feature, but I do not consider them blockers for the release. I expect most of them to be fixed before the GA though, so that we do not increase the amount of "known legacy issues".

Elena Stepanova added a comment - 2022-01-24 02:12 - edited The last tested revision, preview-10.8-MDEV-13756-desc-indexes / c10e10c , has shown generally acceptable results, I think the feature can be merged into the main branch and released with 10.8.1 without a new round of tests, provided that the following issues are addressed: DESC key attribute becomes prohibited for CONNECT and SPIDER engines to avoid revealed problems leading to wrong results ( MDEV-27591 , MDEV-27590 , MDEV-27581 and likely more); MDEV-27592 (InnoDB index corruption) gets fixed – I assume if the fix requires extra testing, it will be done within InnoDB team before the push; MIN/MAX optimization is not enabled before the release, but instead MDEV-27576 is targeted for 10.9+ (if any at all). If it is enabled, further testing will be definitely required. There are other open bugs related to the feature, but I do not consider them blockers for the release. I expect most of them to be fixed before the GA though, so that we do not increase the amount of "known legacy issues".

Elena Stepanova added a comment - 2022-01-26 14:44 - edited

I think the last [partially] tested revision, preview-10.8-MDEV-13756-desc-indexes / 1c4cbb946, can be pushed into the main branch and released with 10.8.1.

There are a few known issues remain, but they are not deemed critical for the initial release.
Examples (not an exhaustive list):

fulltext search on tables with descending PK may misbehave (~~MDEV-27582~~),
different direction of indexes on a Spider table and an underlying table should be avoided (MDEV-27633).

Due to existing legacy issues causing wrong query results, adding descending indexes to tables or converting ascending ones into descending sometimes bring different results comparing to what they were before. It happens because the change in the execution plan can trigger an old issue or, on the contrary, circumvent an old issue so that the result becomes correct while it was wrong before. These problems are usually reproducible even after replacing the use of the descending index with slight tweaks in query/schema/data, and thus need to be dealt with out of the scope of this task. Many of such legacy issues already exist in MariaDB bug tracking system, possibly there are more to be revealed. If in doubt whether it's a known problem or not, users should report the ones that they encounter.

Elena Stepanova added a comment - 2022-01-26 14:44 - edited I think the last [partially] tested revision, preview-10.8-MDEV-13756-desc-indexes / 1c4cbb946 , can be pushed into the main branch and released with 10.8.1. There are a few known issues remain, but they are not deemed critical for the initial release. Examples (not an exhaustive list): fulltext search on tables with descending PK may misbehave ( MDEV-27582 ), different direction of indexes on a Spider table and an underlying table should be avoided ( MDEV-27633 ). Due to existing legacy issues causing wrong query results, adding descending indexes to tables or converting ascending ones into descending sometimes bring different results comparing to what they were before. It happens because the change in the execution plan can trigger an old issue or, on the contrary, circumvent an old issue so that the result becomes correct while it was wrong before. These problems are usually reproducible even after replacing the use of the descending index with slight tweaks in query/schema/data, and thus need to be dealt with out of the scope of this task. Many of such legacy issues already exist in MariaDB bug tracking system, possibly there are more to be revealed. If in doubt whether it's a known problem or not, users should report the ones that they encounter.

Philip orleans added a comment - 2022-10-18 17:59

I need this feature for INNODB, is there any version that already has it?
Are there plans to have it?

Philip orleans added a comment - 2022-10-18 17:59 I need this feature for INNODB, is there any version that already has it? Are there plans to have it?

Max Mether added a comment - 2022-10-18 18:20

This was added to MariaDB Community Server 10.8. Any subsequent release series will also have the feature.

Max Mether added a comment - 2022-10-18 18:20 This was added to MariaDB Community Server 10.8. Any subsequent release series will also have the feature.

Rick James added a comment - 2022-10-18 18:26

Be aware that `ORDER BY a DESC, b DESC` with `INDEX(a,b)` has always been supported – by scanning the index backward.

I think this is already optimized:
WHERE a=constant
ORDER BY a ASC, b DESC

The feature missing is when `ORDER BY` has multiple columns, but not in the same direction.

Rick James added a comment - 2022-10-18 18:26 Be aware that `ORDER BY a DESC, b DESC` with `INDEX(a,b)` has always been supported – by scanning the index backward. I think this is already optimized: WHERE a=constant ORDER BY a ASC, b DESC The feature missing is when `ORDER BY` has multiple columns, but not in the same direction.

Artem Russakovskii added a comment - 2024-01-25 23:39

@Rick James, I tested on 11.0.3-MariaDB-log and 10.11.3-MariaDB-log, and as soon as I add DESC to b, it adds "using filesort" to explain and the query takes twice as much time.

Artem Russakovskii added a comment - 2024-01-25 23:39 @Rick James, I tested on 11.0.3-MariaDB-log and 10.11.3-MariaDB-log, and as soon as I add DESC to b, it adds "using filesort" to explain and the query takes twice as much time.

People

Assignee:: Sergei Golubchik

Reporter:: Marko Mäkelä

Votes:: 24 Vote for this issue

Watchers:: 24 Start watching this issue

Dates

Created:: 2017-09-07 12:30

Updated:: 2025-01-15 05:28

Resolved:: 2022-01-26 18:15

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server