Иногда, особенно для интенсивно обновляемых таблиц, начинают сыпаться deadlock'и и VACUUM 
выполняется нереально долгое время. Часто проблема из-за поврежденного индекса. Решение:
  REINDEX TABLE таблица;
  REINDEX INDEX индекс;