Deadlock при сортировке результата выборки

Имеется запрос, выполняемый параллельно множеством потоков в собственных транзакциях:

SELECT `account_id` FROM `accounts`
WHERE `request_mts` < :request_mts
ORDER BY `request_mts` ASC
LIMIT 1 FOR UPDATE

...где "account_id" - первичный ключ, а ":request_mts" - число миллисекунд.

Этот запрос часто приводит к дедлокам:

Deadlock found when trying to get lock; try restarting transaction

QMYSQL3: Unable to store statement results

Проблема, как удалось выяснить, связана с сортировкой выборки. Если сортировку из запроса убрать, то дедлоки более не возникают:

SELECT `account_id` FROM `accounts`
WHERE `request_mts` < :request_mts
LIMIT 1 FOR UPDATE

Есть ли способ сохранить сортировку, но при этом избежать и дедлоков?

Дополнено

После выполнения выборки (если был найден подходящий account_id) идёт запрос на обновление колонки request_mts в той же транзакции, что и выборка. После этого транзакция закрывается.

UPDATE `accounts` SET `request_mts` = :request_mts
WHERE `account_id` = :account_id