Tengo la siguiente tabla de MySQL (MyISAM) con aproximadamente 3 millones de filas.

CREATE TABLE `tasks` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `node` smallint(6) NOT NULL,
  `pid` int(11) NOT NULL,
  `job` int(11) NOT NULL,
  `a_id` int(11) DEFAULT NULL,
  `user_id` int(11) NOT NULL,
  `state` int(11) NOT NULL,
  `start_time` int(11) NOT NULL,
  `end_time` int(11) NOT NULL,
  `stop_time` int(11) NOT NULL,
  `end_stream` int(11) NOT NULL,
  `message` varchar(255) DEFAULT NULL,
  `rate` float NOT NULL,
  `exiting` int(11) NOT NULL DEFAULT '0',
  `bytes` int(11) NOT NULL,
  `motion` tinyint(4) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `a_id` (`a_id`),
  KEY `job` (`job`),
  KEY `state` (`state`),
  KEY `end_time` (`end_time`),
  KEY `start_time` (`start_time`),
) ENGINE=MyISAM AUTO_INCREMENT=100 DEFAULT CHARSET=utf8;

Ahora, cuando ejecuto la siguiente consulta, MySQL solo usa el índice a_id y necesita escanear unos pocos miles de filas.

SELECT count(id) AS tries FROM `tasks` WHERE ( job='1' OR job='3' ) 
AND a_id='614' AND state >'80' AND state < '100' AND start_time >='1386538013';

Cuando agrego un índice adicional KEYnewkey (a_id,state,start_time), MySQL sigue intentando usar solo a_id y no newkey. Solo cuando se utiliza el índice de sugerencia / fuerza en la consulta, se ha utilizado. Cambiar los campos en la consulta no ayuda.

¿Algunas ideas? No necesariamente quiero sugerencias en mis declaraciones. El hecho de que MySQL no esté haciendo esto automáticamente me indica que hay un problema con mi tabla, claves o consultas en algún lugar. Cualquier ayuda es muy apreciada.

Información adicional:

mysql> show index in tasks;
+-------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name  | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| tasks |          0 | PRIMARY   |            1 | id          | A         |     3130554 |     NULL | NULL   |      | BTREE      |         |               |
| tasks |          1 | a_id      |            1 | a_id        | A         |        2992 |     NULL | NULL   | YES  | BTREE      |         |               |
| tasks |          1 | job       |            1 | job         | A         |           5 |     NULL | NULL   |      | BTREE      |         |               |
| tasks |          1 | state     |            1 | state       | A         |           9 |     NULL | NULL   |      | BTREE      |         |               |
| tasks |          1 | end_time  |            1 | end_time    | A         |     1565277 |     NULL | NULL   |      | BTREE      |         |               |
| tasks |          1 | newkey    |            1 | a_id        | A         |        2992 |     NULL | NULL   | YES  | BTREE      |         |               |
| tasks |          1 | newkey    |            2 | state       | A         |        8506 |     NULL | NULL   |      | BTREE      |         |               |
| tasks |          1 | newkey    |            3 | start_time  | A         |     3130554 |     NULL | NULL   |      | BTREE      |         |               |
+-------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

EXPLICAR con y sin comillas:

mysql> DESCRIBE SELECT count(id) AS tries FROM `tasks` WHERE ( job='1' OR job='3' )  AND a_id='614' AND state >'80' AND state < '100' AND start_time >='1386538013';
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys              | key       | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
|  1 | SIMPLE      | tasks | ref  | a_id,job,state,newkey      | a_id      | 5       | const |  740 | Using where |
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
1 row in set (0.10 sec)

mysql> DESCRIBE SELECT count(id) AS tries FROM `tasks` WHERE ( job=1 OR job=3 )  AND a_id = 614 AND state > 80 AND state < 100 AND start_time >= 1386538013;
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys              | key       | key_len | ref   | rows | Extra       |
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
|  1 | SIMPLE      | tasks | ref  | a_id,job,state,newkey      | a_id      | 5       | const |  740 | Using where |
+----+-------------+-------+------+----------------------------+-----------+---------+-------+------+-------------+
1 row in set (0.01 sec)