MySQL does not use effectively use the index for ORDER BY queries

Question

I have a simple Message table, with 2 indexes:

mysql> show keys from Message;
+---------+------------+-----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| Table   | Non_unique | Key_name  | Seq_in_index | Column_name    | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------+------------+-----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| Message |          0 | PRIMARY   |            1 | id             | A         |     5643295 |     NULL | NULL   |      | BTREE      |         |
| Message |          1 | timestamp |            1 | startTimestamp | A         |     5643295 |     NULL | NULL   |      | BTREE      |         |
+---------+------------+-----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+

When issuing an order by query, a very large number of rows is examined:

mysql> explain SELECT * from Message ORDER BY startTimestamp LIMIT 0,20;
+----+-------------+---------+-------+---------------+-----------+---------+------+---------+-------+
| id | select_type | table   | type  | possible_keys | key       | key_len | ref  | rows    | Extra |
+----+-------------+---------+-------+---------------+-----------+---------+------+---------+-------+
|  1 | SIMPLE      | Message | index | NULL          | timestamp | 8       | NULL | 5643592 |       |
+----+-------------+---------+-------+---------------+-----------+---------+------+---------+-------+

The total row count is:

mysql> select count(*) from Message;
+----------+
| count(*) |
+----------+
|  5837363 |
+----------+

This query touches 96.7% of the rows. The index is BTREE, so as far as I know it should simply yank out the top 20 rows and return them. As it stands, it's using an index to access almost all of the table's rows, which is presumably slower than a full table scan.

Am I mistaken in my assumption that it should simply pick the top 20 rows using the index and return them?

The MySQL server version is 5.0.45 and the table type is InnoDB.

Answer 1

With EXPLAIN SELECT ... ORDER BY, you can check whether MySQL can use indexes to resolve the query. It cannot if you see Using filesort in the Extra column.

It is using the index..

Answer 2

in the EXPLAIN, MySQL estimates the number of rows scanned to 5643592 but it's using the right index(order by column:timestamp) and is limited to 20 rows, so don't worry it's doing the right thing and will stop as soon as 20 rows are sent. Can you give us the query execution time?