To start off, I said optimistic locking before my and I actually meant pessimistic locking.

But I think it totally depends on what your queue is used for. In my case, I need durable queues that report status/errors and support retries/back off.

I deal with it using updates rather than deleting from the queue, because I need a log of what happened for audit purposes. If I need to optimize later, I can easily partition the table. At the start, I just use a partial index for the items to be processed.

Reindexing, and other maintenance functions that need to rewrite the table will happen more than you like in a production system, so I'd rather make them easy to do.