We ran a (admittedly poorly written) select query against a subset of tables which performed poorly. Then we ran a vacuum analyze against just those tables involved in that query, then ran the same query again, which performed exponentially better.
Did/can you observe query buffer usage/performance for the two explain analyze executions?
