Is it possible to make MySQL use an index for the ORDER by 1 DESC, 2 ASC?

Question

I have a materialized path-driven bulletin board. It is using the following query to get the messages in order,

SELECT * FROM Board ORDER by root DESC, path ASC LIMIT 0,100

where root is an id of the root message for the thread, and path is a materialized path.

However, none of my efforts to make this query to use indexes were of any success.

mysql> explain extended select path from Board order by root desc, path asc limit 100;
+-------+---------------+----------+---------+------+-------+----------+----------------------------+
| type  | possible_keys | key      | key_len | ref  | rows  | filtered | Extra
+-------+---------------+----------+---------+------+-------+----------+-----------------------------
| index | NULL          | rootpath | 261     | NULL | 21998 |   100.00 | Using index; Using filesort

At the moment it is showing the number of all the rows in the table under rows column. I am wondering, is there a way to reduce that number or optimize the query any other way?

CREATE TABLE `Board` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `path` varchar(255) NOT NULL DEFAULT '0',
  `root` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `root` (`root`),
  KEY `path` (`path`),
  KEY `rootpath` (`root`,`path`)
)

The main problem with the query is pagination - I need to start the second page right from the message next to the last one on the previous page. That's why I want it the straight way - without sublelects and stuff.
The current setup is not quite nice though, as it starts the second page from the middle of the thread, but it is quite logical at least.

Answer 1

The problem you are facing is explained nicely in this article. And the important part is:

Most typical case is when you want to order by two colums in different directions: … ORDER BY price ASC, date DESC LIMIT 10 If you have indexed on (price,date) in ascending order you will not be able to optimize this query well – external sort (“filesort”) will be needed. If you would be able to build index on price ASC, date DESC the same query could retrive data in aready sorted order.

Also the article mentions a valid workaround for the problem as well: Having the second "order" clause reversed:

This is however something you can workaround by having something like “reverse_date” column and using it for sort. With MySQL 5.0 you even can use triggers to update it as real date updates so it becomes less ugly. In fact this is for example why you would see “reverse_timestamp” field in Wikipedia table structure.

Also from official MySQL documentation:

In some cases, MySQL cannot use indexes to resolve the ORDER BY, although it still uses indexes to find the rows that match the WHERE clause. These cases include the following:

.....

You mix ASC and DESC:

SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;

As a suggestion you would better have a reversed_root column which is Integer.MAX_VALUE - root AND have an index on (reversed_root, path). Then you can have a query as:

SELECT * FROM Board ORDER by reversed_root ASC,path ASC LIMIT 0,100