Weird performance drop after VACUUM

Hello,

We are using PostgreSQL for our business application. Recently, during
testing of our application with large volumes of data, we faced a weird
problem. Our query performance dropped *dramatically* after "VACUUM FULL
ANALYZE" command. We have encountered a similar problem listed on
mailing list archives, but the submitter solved his problem by rewriting
his query, which is unfortunatelly very hard for us.

I am attaching two EXPLAIN ANALYZE outputs, first one is just before the
VACUUM FULL ANALYZE command and the other is the one after. Also
attached is the SQL query, which is simplified to clearify the problem.
In the example query time increases from 1.8 second to > 4.0 secons. The
difference for the complete query is much bigger, query time increases
from 7.8 seconds to > 110 seconds.

Any help is appreciated, we were unable to identify what causes the
query planner to choose a different/poor performing plan.

Notes:
Our production platform is Ubuntu Linux Hoary on i386, PostgreSQL 8.0.3,
compiled from sources. Same tests were carried on Windows XP
Professional and PostgreSQL 8.0.1 with similar results. The queries use
little IO, high CPU. The largest table involved in the sample query has
about 10000 rows. Indexes are used intensively, some tables use > 4
indexes.

Best regards,
Umit Oztosun