По поводу медленного COUNT на всю таблицу вам написали, а вот второй запрос "по нормальному" должен отрабатывать мгновенно, при условии что постгрес правильно настроен.
Вы случайно не используете настройки по умолчанию (а они там такие чтоб работало даже на калькуляторе)?
есди да то советую
postgresql.leopard.in.ua там какраз новая версия недавно вышла.