@Max Kostikov ah... that is somehow suprising...

Anyway, i think i will go with

ALTER TABLE workerq
    ADD INDEX idx_claim (
        workerq_reservationid,
        workerq_priority DESC,
        workerq_id ASC
    );

as you suggested first.