Be careful when using Postgres as queue with priorites, especially if your messages are large. Removing rows doesn't free up the memory in Postgres and vacuum could remove rows only from the end of a 'page'. As a result of that queue will require enormous amount of space to work. The only way to free up space is to use VACUUM FULL which rewrites whole database and will lock queue for long time. I've had a lot of headaches when we've tried 'use Postgres for everything' on production :)