This is fair! This should as you descripbe work with a partial index, and with picking the lowest ID that has status = pending (via that index) which is not locked (via select ... for update skip locked). The query plan should be triple-checked though to actually use the index.