Poor overall performance unless regular VACUUM FULL

Howdy. Some months back, when advised on one of these lists that it
should not be necessary to issue VACUUM FULL/REINDEX DATABASE, we quit
this nightly "maintenance" practice. We've been very happy to not
have to do that, since it locked the database all night. Since then,
however, our database performance has decreased. The decrease took a
few weeks to become noticable; perhaps six weeks to become awful.

I have no objective measurement of the decrease in performance. I
have just created a benchmark that exercises our system and used it to
measure the current degraded performance. I hope it will show me,
objectively, how much any attempted fix improves system performance.

One thing I noticed is that when we stopped doing the VACUUM
FULL/REINDEX is that the size of the weekly backups (a compressed
tarball of main + WAL files) jumped in size. A steady 53GB before we
stopped doing the vacuum, the next backup after stopping the VACUUM
FULL was 97GB. The backup sizes have grown in the three months since
then and are now hovering at around 130GB. We believe, but have no
hard numbers to prove, that this growth in physical backup size is out
of proportion with the growth of the logical database that we expect
due to the slow growth of the business. We are pretty sure we would
have noticed the business growing at more than 50% per quarter.

I did a VACUUM VERBOSE and looked at the statistics at the end; they
seem to indicated that my max_fsm_pages is large enough to keep track
of all of the dead rows that are being created (we do a fair amount of
deleting as well as inserting). Postgres prints no complaint saying
we need more slots, and we have more than the number of slots needed
(if I recall, about twice as many).

What options do I have for restoring performance other than VACUUM
FULL/REINDEX DATABASE?

Before trying any fix, what data do I want to collect that might
indicate where the performance problem is?

Best Regards,
Wayne Conrad