Во-первых, сделай VACUUM FULL, во-вторых, если результат запроса не сильно критичен - попробуй к примеру SELECT count(*) FROM users WHERE id>0, где id - pimary key. Суть та же, но это позволяет использовать индекс, и в некоторых запущенных случаях позволяет повысить производительность.

visselect count(<primary_key>) from <table> тоже покатит

Мне кажется, нет, поскольку при вычислении агрегатных функций индексы не используются.

Самое смешное, что предложенный мной способ (WHERE id>0) тоже не всегда цепляет индексы. Зависит от того, как лягут звезды для оптимизатора.

Да и вообще не дело это. Надо безо всяких условий писать :)

В свое время я связывался с одним из разработчиков Postgres, вот цитата из письма:

Мой вопрос:
> Добрый день, Теодор.
>
> Скажи пожалуйста, как рекомендуется вычислять точное количество > записей в таблице?
>
> Согласно документу
> http://www.postgresql.org/docs/7.4/interactive/functions-aggregate.html
> насколько я понял, есть определенные проблемы с вычислением
>
> select count(*)
> from some_table

Ответ Теодора Сигаева:

> Так и рекомендуется. Проблемы есть только в быстродействии. Но для
> быстродействия стоит написать триггера на insert & delete, которые щелкают
> счетчик в отдельной таблице).

> Проблемы с быстродействием заключаются в MVCC (multi version concurrence
> control) - в зависимости от настроек transaction isolation level и текущих
> транзакций рез-тат может быть разный. Поэтому только sequence scan гарантирует
> целостность count(*).