COUNT(*) very slow on table with primary key

Hi folks,

I've been having trouble with a slow query on a table that has a primary
key (which I understand is supported in PostgreSQL by a UNIQUE non-NULL
index).  It's a SELECT COUNT(*) without a WHERE clause; really simple
stuff.

I would have thought the number of entries in the primary key index
could simply be inspected and returned.

EXPLAIN reports that a sequential table scan is being performed, which
sounds right, since the actual operation takes about 10 seconds when
there are about half a million rows in the table.

The table's pretty wide (about 2.5KB), but has been subjected to a
VACUUM ANALYZE operation in accordance with the advice given in the FAQ.

Is this just "how it is" or is there more stuff I could look at?  I'm
actually trying to speed up a more complex query, but figured it would
be better to report (and get feedback on) the simplest case.

Ciao,
Sheldon.