Why scanning an index backwards is slower?

Posted on

Question :

Empirical tests show that a query like this on an InnoDB table:

SELECT indexed_column FROM tab ORDER BY indexes_column ASC;

is faster than its counterpart with ORDER BY ... DESC. Why is this the case?

Note: I did the tests with MySQL 5.7 and 5.6. So this has nothing to do with ascending indexes in 8.0.

Answer :

The author, Chaithra Gopalareddy, of the related article, MySQL 8.0 Labs – Descending Indexes in MySQL, explains in a comment why backwards index scans are slightly less efficient than forward scans:

Thanks for showing interest in the new feature. The ~15% cost benefit in forward scans can be attributed to the optimizations done in innodb to favor forward scans over backward scans.

For ex: W.r.t a scan within the page – The records in a page form a singly linked list. To get the next record, a forward scan just follows the link where as the backward scan need to start from the beginning (first slot) till the current slot/record to identify the previous record.

Along with the above, there are some more contributing factors like, during page switch – page latching rules currently defined in innodb favor forward scans over backward scans.

So there are two factors:

  • the single linked list structure of records inside a page
  • page latching rules regarding page switches

Leave a Reply

Your email address will not be published. Required fields are marked *