[MDEV-13756] Implement descending index: KEY (a DESC, b ASC) Created: 2017-09-07  Updated: 2024-01-25  Resolved: 2022-01-26

Status: Closed
Project: MariaDB Server
Component/s: Optimizer, Storage Engine - InnoDB
Fix Version/s: 10.8.1

Type: Task Priority: Blocker
Reporter: Marko Mäkelä Assignee: Sergei Golubchik
Resolution: Fixed Votes: 24
Labels: Compatibility, Oracle, Preview_10.8, SQL, optimizer-feature

Issue Links:
PartOf
includes MDEV-26938 support descending indexes internally... Closed
includes MDEV-26939 support descending indexes for simple... Closed
includes MDEV-26996 Support descending indexes in the ran... Closed
is part of MDEV-27373 Q1 2022 release merge Closed
Problem/Incident
causes MDEV-27300 Result differs with DESC index upon c... Open
causes MDEV-27303 Table corruption after insert into a ... Closed
causes MDEV-27309 Server crash or ASAN memcpy-param-ove... Closed
causes MDEV-27330 Wrong sorting order with DESC index a... Closed
causes MDEV-27340 NULL gets lost (becomes empty string)... Closed
causes MDEV-27347 MyISAM/Aria table is marked as crashe... Closed
causes MDEV-27374 InnoDB table becomes corrupt after re... Closed
causes MDEV-27392 DESC attribute is ignored when index ... Closed
causes MDEV-27393 Timezone tables cannot have descendin... Closed
causes MDEV-27396 DESC index attribute remains in Archi... Closed
causes MDEV-27398 DESC index causes wrong (empty) resul... Closed
causes MDEV-27406 Index on a HEAP table retains DESC at... Closed
causes MDEV-27407 Different ASC/DESC index attributes o... Closed
causes MDEV-27408 DESC index on a Mroonga table causes ... Closed
causes MDEV-27419 MariaDB doesn't choose DESC index for... Confirmed
causes MDEV-27420 Spider tables retain DESC attribute o... Closed
causes MDEV-27426 Wrong result upon query using index_m... Closed
causes MDEV-27432 ASC/DESC primary and unique keys caus... Closed
causes MDEV-27434 DESC attribute does not work with aut... Closed
causes MDEV-27439 AUTO_INCREMENT columns with DESC inde... Closed
causes MDEV-27445 Index inconsistency and assertion fai... Closed
causes MDEV-27529 Wrong result upon query using index_m... Closed
causes MDEV-27576 Use DESC indexes for MIN/MAX optimiza... Closed
causes MDEV-27578 DESC attribute upon spatial index cre... Open
causes MDEV-27580 Bogus warning ER_TRUNCATED_WRONG_VALU... Open
causes MDEV-27581 Wrong result with DESC key on partiti... Closed
causes MDEV-27585 Auto-increment on secondary column in... Closed
causes MDEV-27586 Auto-increment does not work with DES... Closed
causes MDEV-27588 MyISAM/Aria descending index compress... Closed
causes MDEV-27589 OQGRAPH returns a different result se... Open
causes MDEV-27590 Auto-increment on Spider tables with ... Closed
causes MDEV-27591 Connect tables (FIX/DOS) don't work w... Closed
causes MDEV-27592 DESC keys: Data corruption or Asserti... Closed
causes MDEV-27617 HANDLER KEY > (x) does not work with ... Closed
causes MDEV-27623 Wrong result with DESC key on InnoDB ... Closed
causes MDEV-27633 Wrong result with different direction... Open
causes MDEV-27683 EXCHANGE PARTITION allows different i... Closed
causes MDEV-29047 RocksDB retains unsupported DESC key ... Open
causes MDEV-30845 filesort still select when desc/asc i... Open
Relates
relates to MDEV-4621 select returns null for information_s... Closed
relates to MDEV-23571 InnoDB does not raise a warning if AL... Open
relates to MDEV-27577 Recovery behaves differently with DES... Closed
relates to MDEV-27302 Backward index scan is not reflected ... Open
relates to MDEV-27582 Fulltext search DDL decrements FTS_DO... Closed

 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.



 Comments   
Comment by Tom Conlon [ 2020-09-22 ]

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

Comment by ssauravy [ 2021-08-11 ]

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.

Comment by Sergei Petrunia [ 2021-12-07 ]

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

Comment by Elena Stepanova [ 2022-01-24 ]

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".

Comment by Elena Stepanova [ 2022-01-26 ]

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.

Comment by Philip orleans [ 2022-10-18 ]

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

Comment by Max Mether [ 2022-10-18 ]

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

Comment by Rick James [ 2022-10-18 ]

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.

Comment by Artem Russakovskii [ 2024-01-25 ]

@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.

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