Problem with large table not using indexes (I think)

Hi,

The largest table in my database (30GB) has mysteriously went from
taking milli-seconds to perform a query to minutes.  This disks are fine
and I have a 4GB shared_memory.  Could this slow down have to do with
the fsm_max_pages or something else like that?  I made it larger but the
queries still taking a long time.  I do daily vacuum's but I don't run
it with -z or --full.  I would like to avoid doing a --full if possible
because it would literally take over a week to complete.  Any help would
be greatly appreciated.

Benjamin