> Как уменьшить это время ?

Написать триггер и хранить значение в отдельной таблице.

> SELECT COUNT(*) FROM table;
> Как уменьшить это время ?

Считать строки можно....

1/ count()-ом, и даже пытаться повернуть мозг в сторону

google://pgsql SELECT COUNT speed

разницы между count(*), count(1), count(ALL), count(PrimaryKey), ...

2/ _приблизительно_ по таблицам статистики ANALYZe-а (в постгресе)

google://pgsql record number approximate

http://stackoverflow.com/questions/2596670/how-do-you-find-t...

(Мне, например, на 100,000,000+ записях в Zabbix-е дальше 4-го значащего не сильно интересно, "точное" значение.)

3/ может, ещё как (триггеры на insert/delete + хранимый счётчик уже предложили)