As I understand it the order the of evaluation of search arguments is up to the optimizer. I've tested the following query, that is supposed to take advantage of advisory locks to skip over rows that are locked by other consumers running the exact same query and it seems to work fine. It seems to me the optimizer should always prefer to scan by status. What say you?
begin;
select * from queue q where q.status = 'unprocessed' and pg_try_advisory_xact_lock(q.qid, q.tableoid::int) = true limit 2 -- specify batch size here for update;