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.

Angadresma

The explain says it is using the "rootpath" index. – Diapause

Answer 1

Your original query

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

Create a table to hold the negative value of root called BoardDisplayOrder, where you add the new column called rootinv.

First here is the sample data and your original query:

mysql> drop database if exists YourCommonSense;
Query OK, 2 rows affected (0.06 sec)

mysql> create database YourCommonSense;
Query OK, 1 row affected (0.00 sec)

mysql> use YourCommonSense
Database changed
mysql> 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`)
    -> );
Query OK, 0 rows affected (0.11 sec)

mysql> INSERT INTO Board (path,root) VALUES
    -> ('Rolando Edwards',30),
    -> ('Daniel Edwards',30),
    -> ('Pamela Edwards',30),
    -> ('Dominiuqe Edwards',40),
    -> ('Diamond Edwards',40),
    -> ('Richard Washington',50),
    -> ('George Washington',50),
    -> ('Synora Washington',50);
Query OK, 8 rows affected (0.05 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM Board;
+----+--------------------+------+
| id | path               | root |
+----+--------------------+------+
|  2 | Daniel Edwards     |   30 |
|  3 | Pamela Edwards     |   30 |
|  1 | Rolando Edwards    |   30 |
|  5 | Diamond Edwards    |   40 |
|  4 | Dominiuqe Edwards  |   40 |
|  7 | George Washington  |   50 |
|  6 | Richard Washington |   50 |
|  8 | Synora Washington  |   50 |
+----+--------------------+------+
8 rows in set (0.00 sec)

mysql> SELECT * FROM Board ORDER by root DESC, path ASC LIMIT 0,100;
+----+--------------------+------+
| id | path               | root |
+----+--------------------+------+
|  7 | George Washington  |   50 |
|  6 | Richard Washington |   50 |
|  8 | Synora Washington  |   50 |
|  5 | Diamond Edwards    |   40 |
|  4 | Dominiuqe Edwards  |   40 |
|  2 | Daniel Edwards     |   30 |
|  3 | Pamela Edwards     |   30 |
|  1 | Rolando Edwards    |   30 |
+----+--------------------+------+
8 rows in set (0.00 sec)

mysql> EXPLAIN SELECT * FROM Board ORDER by root DESC, path ASC LIMIT 0,100;
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+
| id | select_type | table | type  | possible_keys | key      | key_len | ref  | rows | Extra                       |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | Board | index | NULL          | rootpath | 261     | NULL |    8 | Using index; Using filesort |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+
1 row in set (0.00 sec)

mysql>

Next, create the table BoardDisplayOrder using rootinv and an index involving rootinv:

mysql> CREATE TABLE BoardDisplayOrder LIKE Board;
Query OK, 0 rows affected (0.09 sec)

mysql> ALTER TABLE BoardDisplayOrder DROP INDEX root;
Query OK, 0 rows affected (0.11 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE BoardDisplayOrder DROP INDEX path;
Query OK, 0 rows affected (0.09 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE BoardDisplayOrder DROP INDEX rootpath;
Query OK, 0 rows affected (0.08 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE BoardDisplayOrder ADD COLUMN rootinv int(11) NOT NULL;
Query OK, 0 rows affected (0.17 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path,id,root);
Query OK, 0 rows affected (0.11 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> SHOW CREATE TABLE BoardDisplayOrder \G
*************************** 1. row ***************************
       Table: BoardDisplayOrder
Create Table: CREATE TABLE `boarddisplayorder` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `path` varchar(255) NOT NULL DEFAULT '0',
  `root` int(11) NOT NULL DEFAULT '0',
  `rootinv` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `rootpathid` (`rootinv`,`path`,`id`,`root`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql>

Then, populate BoardDisplayOrder:

mysql> INSERT INTO BoardDisplayOrder (id,path,root,rootinv)
    -> SELECT id,path,root,-root FROM Board;
Query OK, 8 rows affected (0.06 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM BoardDisplayOrder;
+----+--------------------+------+---------+
| id | path               | root | rootinv |
+----+--------------------+------+---------+
|  7 | George Washington  |   50 |     -50 |
|  6 | Richard Washington |   50 |     -50 |
|  8 | Synora Washington  |   50 |     -50 |
|  5 | Diamond Edwards    |   40 |     -40 |
|  4 | Dominiuqe Edwards  |   40 |     -40 |
|  2 | Daniel Edwards     |   30 |     -30 |
|  3 | Pamela Edwards     |   30 |     -30 |
|  1 | Rolando Edwards    |   30 |     -30 |
+----+--------------------+------+---------+
8 rows in set (0.00 sec)

mysql>

Now, run your query against BoardDisplayOrder but without DESC on rootinv:

mysql> SELECT id,path,root FROM BoardDisplayOrder ORDER by rootinv, path LIMIT 0,100;
+----+--------------------+------+
| id | path               | root |
+----+--------------------+------+
|  7 | George Washington  |   50 |
|  6 | Richard Washington |   50 |
|  8 | Synora Washington  |   50 |
|  5 | Diamond Edwards    |   40 |
|  4 | Dominiuqe Edwards  |   40 |
|  2 | Daniel Edwards     |   30 |
|  3 | Pamela Edwards     |   30 |
|  1 | Rolando Edwards    |   30 |
+----+--------------------+------+
8 rows in set (0.00 sec)

mysql> EXPLAIN SELECT id,path,root FROM BoardDisplayOrder ORDER by rootinv, path LIMIT 0,100;
+----+-------------+-------------------+-------+---------------+------------+---------+------+------+-------------+
| id | select_type | table             | type  | possible_keys | key        | key_len | ref  | rows | Extra       |
+----+-------------+-------------------+-------+---------------+------------+---------+------+------+-------------+
|  1 | SIMPLE      | BoardDisplayOrder | index | NULL          | rootpathid | 269     | NULL |    8 | Using index |
+----+-------------+-------------------+-------+---------------+------------+---------+------+------+-------------+
1 row in set (0.00 sec)

mysql>

Give it a try!!!

CAVEAT

This was easy to do because root was INT.

If root was a VARCHAR, rootinv would have to be a flipflop of characters. In other words,

• A -> Z
• B -> Y
• ...
• M -> N
• N -> M
• ...
• Y -> B
• Z -> A

This would principly work for any field you need to perform DESC on. The problem stems from the fact that MySQL does not order keys internally within in index as ASC or DESC. Everything in an index is ascending. That is why when you see handler stats in SHOW GLOBAL STATUS LIKE 'handler%';, you see the following:

• handler_read_first
• handler_read_next
• handler_read_prev
• handler_read_last (MySQL 5.5 only)

and so forth.

According to the current MySQL Documentation

An index_col_name specification can end with ASC or DESC. These keywords are permitted for future extensions for specifying ascending or descending index value storage. Currently, they are parsed but ignored; index values are always stored in ascending order.

Give it a try!!!

UPDATE 2012-05-04 06:54 EDT

@frail's comment about my answer

ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path,id,root) seems pretty unnecessary to me, ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path) should be enough

The reason my solution had ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path,id,root) is to provide a covering index. A covering index in this instance will:

• always have the needed columns for retrieval
• will improve the quality of the explain plan because
  • the query will never read from the table for data retrieval
  • the query will only read from the index for data retrieval
  • result in an index range scan

Think of the original query,

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

This requires retrieving the three columns path, id, and root. Thus, they need to be in the index. Of course, the increased size of the index would be the tradeoff. If the Board table was very large, some would not worry about the space if the retrieval could be made faster. If the rootpath index were just (rootinv,path), then every index range scan would be accompanied by a ref lookup into the table for the remaining columns. This is the reason I chose ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path,id,root);

Newfoundland

Man, I can't believe it's so easy yet I am so stupid not to see it myself! – Angadresma

ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path,id,root) seems pretty unnecessary to me, ALTER TABLE BoardDisplayOrder ADD INDEX rootpathid (rootinv,path) should be enough – Sumikosumma

@Sumikosumma I addressed your comment in my answer – Newfoundland

I am really sorry, but there is a simplified version of the table I posted. Of course there is a title, author and date fields which have to be retrieved along. I see no problem in reading from the table though – Angadresma

No worries. I was solving based on what was presented. I would not add a title to a covering index. – Newfoundland

@YourCommonSense, I have a question: Did my answer provide the solution you needed? – Newfoundland

@Newfoundland don't expect an answer – Haiphong

@ConradFrix OMG he is suspended. OK, I won't expect an answer. – Newfoundland

@YourCommonSense I think that 500 point boost of my rep was from you. If so, thank you !!! – Newfoundland

@Rolando you helped me before, could you please help me with another question? #48985625 – Angadresma

Answer 2

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

Sumikosumma

Answer 3

In this situation where the data itself does not lend itself to retrieval in the way you need, it may be appropriate to create an additional column that has the information you need -- this will allow you to retrieve on the order you want.

It would especially be appropriate in this case as it seems the data itself isn't updated once you save it. Once your messages are posted, they aren't updated (or so it seems from my initial reading).

The steps I'd recommend, assuming you take this path, would be:

• Add a new column root_path to the table.
• Execute this update statement update Board set root_path = root + path. (You may have to adapt that based on the data types of the existing columns.)
• Whenever you add a new row to the table, also add this new column. (This could be handled with a trigger, though I'd be wary of triggers since they can be overlooked when people are changing other parts of the code.)

Then you should be able to set an index on that new column and write your selects against that column -- hitting your indexes as you wish.

I believe this will work even though one of the keys has to be sorted in opposite order.

CREATE TABLE foo
(
  id serial NOT NULL,
  int_field integer DEFAULT 0,
  varchar_field character varying(255),
  composite_field character varying(255),
  CONSTRAINT foo_pkey PRIMARY KEY (id )
);

CREATE INDEX composite_field_idx ON foo (composite_field);

INSERT INTO foo (int_field, varchar_field, composite_field) VALUES 
(1,'t','t1'),
(2,'z','z2'),
(2,'w','w2'),
(4,'u','u4'),
(5,'u','u5'),
(5,'x','x5'),
(7,'v','v7');

explain select * from foo order by composite_field desc;

Run the above code and the explain statement should show the key composite_field_idx being referenced.

The result from the query is:

select * from foo order by composite_field desc;

 id | int_field | varchar_field | composite_field 
----+-----------+---------------+-----------------
  2 |         2 | z             | z2
  6 |         5 | x             | x5
  3 |         2 | w             | w2
  7 |         7 | v             | v7
  5 |         5 | u             | u5
  4 |         4 | u             | u4
  1 |         1 | t             | t1

Abstain

as one of the columns have to be sorted in the reverse order, I am afraid this will require update for the every row, which doesn't seem to be a good solution. – Angadresma