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

Exactly. A partial index should make things fly here.