Пустой UPDATE намного медленнее, чем соответствующий SELECT

Я использую MySQL 5.1.73 с InnoDB.

У меня есть очень медленный запрос UPDATE (около 10 с), где количество измененных строк (часто) равно нулю (это занимает примерно столько же времени, если изменено несколько строк):

UPDATE job_queue SET state=4 WHERE error_counter>=5 AND state=1;
Query OK, 0 rows affected (9.33 sec)

Однако соответствующий SELECT выполняется довольно быстро:

SELECT id FROM job_queue WHERE error_counter>=5 AND state=1;
Empty set (0.03 sec)

EXPLAIN SELECT id FROM job_queue WHERE error_counter>=5 AND state=1;
+----+-------------+-----------+-------+--------------------------------------------+---------------------+---------+------+-------+--------------------------+
| id | select_type | table     | type  | possible_keys                              | key                 | key_len | ref  | rows  | Extra                    |
+----+-------------+-----------+-------+--------------------------------------------+---------------------+---------+------+-------+--------------------------+
|  1 | SIMPLE      | job_queue | index | Allinone,state_timeout,state_error_counter | state_error_counter | 5       | NULL | 13515 | Using where; Using index |
+----+-------------+-----------+-------+--------------------------------------------+---------------------+---------+------+-------+--------------------------+

Как видите, это (должен быть?) индексированный запрос к не слишком большой базе данных (около 9000 строк, хотя она содержит несколько больших двоичных объектов, поэтому общий размер БД составляет около 800 МБ).

Вопросы:

• Почему обновление такое медленное?
• Как я могу отладить это?
• Как я могу ускорить его?

ОБНОВЛЕНИЕ: я попробовал ту же базу данных на другом сервере с MySQL 5.5.35 (Debian wheezy по умолчанию). Запрос по-прежнему быстрый, а обновление по-прежнему медленное, и до сих пор нет объяснений обновлений... Я могу попробовать перейти на mysql 5.6 с dotdeb или попробовать mariadb. :)

ОБНОВЛЕНИЕ 2: я пробовал разные форматы строк (динамические и сжатые), но это тоже не (значительно) быстрее.

ОБНОВЛЕНИЕ 3: я обновился до MySQL 5.6.17 (из dotdeb), и производительность в целом такая же, но наконец-то я получил объяснение обновления:

EXPLAIN UPDATE job_queue.job_queue SET state=4 WHERE error_counter>=5 AND state=1;
+----+-------------+-----------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table     | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-----------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | job_queue | index | NULL          | PRIMARY | 8       | NULL | 70222 | Using where |
+----+-------------+-----------+-------+---------------+---------+---------+------+-------+-------------+

Это только подтверждает то, что можно было подозревать с самого начала: ОБНОВЛЕНИЕ не использует никаких индексов. Итак, остается вопрос: ПОЧЕМУ?

Я попытаюсь создать минимальный пример, который обеспечивает такое поведение; может быть, в ходе этого я найду некоторые ответы....