Why is MySQL 5.5 ignoring this index? I have a pretty simple query that is not using an index I expect it to because of the WHERE.

Table:

CREATE TABLE `cba_device_log` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`device_id` varchar(30) NOT NULL,
`device_time_ms` bigint(20) NOT NULL DEFAULT '0',
`tag` varchar(30) NOT NULL DEFAULT 'NONE',
`message` text NOT NULL,
`created_at` datetime DEFAULT NULL,
`updated_at` datetime DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `device_id` (`device_id`),
KEY `device_time_ms` (`device_time_ms`),
KEY `tag` (`tag`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1


Indexes:

+----------------+------------+----------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table          | Non_unique | Key_name       | Seq_in_index | Column_name    | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------------+------------+----------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| cba_device_log |          0 | PRIMARY        |            1 | id             | A         |    84746959 |     NULL | NULL   |      | BTREE      |         |               |
| cba_device_log |          1 | device_id      |            1 | device_id      | A         |        1077 |     NULL | NULL   |      | BTREE      |         |               |
| cba_device_log |          1 | device_time_ms |            1 | device_time_ms | A         |    84746959 |     NULL | NULL   |      | BTREE      |         |               |
| cba_device_log |          1 | tag            |            1 | tag            | A         |          34 |     NULL | NULL   |      | BTREE      |         |               |
+----------------+------------+----------------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+---------------+


Query:

SELECT * 
FROM cba_device_log
WHERE device_id = 1067 
ORDER BY device_time_ms DESC, id DESC
LIMIT 0,500;


Explain:

+----+-------------+----------------+------+---------------+------+---------+------+----------+-----------------------------+
| id | select_type | table          | type | possible_keys | key  | key_len | ref  | rows     | Extra                       |
+----+-------------+----------------+------+---------------+------+---------+------+----------+-----------------------------+
|  1 | SIMPLE      | cba_device_log | ALL  | device_id     | NULL | NULL    | NULL | 84746858 | Using where; Using filesort |
+----+-------------+----------------+------+---------------+------+---------+------+----------+-----------------------------+
You want INDEX(device_id, device_time_ms, id).  First the '=' fields, then, if there is nothing else in WHERE, all the fields of the ORDER BY.

Assuming this is a really large table, and there are a relatively small number of devices, the I recommend you normalize device_id.  That would shrink it from VARCHAR(30) to, say 3 bytes for MEDIUMINT UNSIGNED.  Or maybe it is already a number?  But mistakenly put into a varchar?