BUG #8058: CLUSTER and VACUUM FULL fail to free space

The following bug has been logged on the website:

Bug reference: 8058
Logged by: Daniel Farina
Email address: daniel(at)heroku(dot)com
PostgreSQL version: 9.0.13
Operating system: Ubuntu 10.04
Description:

We have a somewhat high-churn table acting as a queue, and over time it's
grown to be something like a gigabyte. I surmised it might be vanilla
bloat, but the truth seems somewhat more exotic because both VACUUM FULL and
CLUSTER generated absolutely no new free space.

In the end, ALTER TABLE and CREATE TABLE ... (LIKE) ran nearly instantly and
got the table size down to a few hundred K from 900M.

This caused quite a few problems because would normally be cheap index scan
over a mere 100 tuples were taking a few seconds.

There are TOASTed fields on this table, ranging in a few hundred bytes of
text per attribute.

We have retained the old bloated table so we can poke at it.