Re: Massive parallel queue table causes index deterioration, butREINDEX fails with deadlocks.

Why do you want to do that?  If you are trying to force the queue to be handled in a "fair" order, then this isn't the way to do it, you would want to add an "ORDER BY" to your dequeueing query (in which case you are probably back to adding an index).  

Once the space in the beginning of the table has been reclaimed as free, then it will be reused for newly inserted tuples.  After the space is freed up but before it is reused, the seq scan can't skip those blocks entirely, but it can deal with the blocks quickly because they are empty.  If the blocks are full of dead but not freed tuples (because the long-running transactions are preventing them from being cleaned up) then it will have to go through each dead tuple to satisfy itself that it actually is dead.  This might not be as bad as it is for indexes, but certainly won't be good for performance.

 Cheers,

Jeff