Hmmm...
INDEX(state, priority, fire_time);
This one should have the following characteristics:
* The query will be "Using index"
* Hopefully the ORDER BY will use the index, then filter on fire_time.
* There are often enough with the correct `state` to meet the LIMIT
* There are often enough with the priority=0 (or small number) to meet the LIMIT
What is the value of innodb_buffer_pool_size? autocommit? How much RAM do you have?
Why are there 3M rows in the table? Sounds like you have a huge backlog of things to do.
Is it always LIMIT 10?
It may be worth it to do something like
for $prio = 0, 1, ...
SELECT ...
where state='ARMED'
and priority = $prio
and fire_time < 20101127
order by fire_time
limit 10;
IF got some rows, process them and exit loop