[andrewstuart]

Partial indexes might help.

[runeks]

Also: an ordered index that matches the ordering clause in your job-grabbing query. This is useful if you have lots of pending jobs.

[emilsedgh]

Exactly. A partial index should make things fly here.