Select count(*) takes a long time

Hello,

Forgive me if this is the wrong forum for such a question.

What can I do to make "select count(*) from ..." return quickly?  I
think I had read that PostgreSQL, unlike most RDBMSs, does not store
the current row count and so must be re-calculated on the fly.  In my
particular situation I have a home page that must select a "featured"
article by choosing one at random from a table of 300 thousand or so.
Doing select count(*) takes a few seconds.  I could probably select
all the rows and get the data in the same time.

I thought I came up with a good solution, now I "select ... from ...
order by random() limit 1", which is nice because it only requires one
query to get what I want but it's still slow.

I now cache the "featured" article because this query is too slow to
make during a web page request.  I have indexes on all the columns
referenced by the where clause.  Am I missing something obvious or
does everyone just deal with slow "select count(*)" when using
PostgreSQL?

Thanks,
Jeff

PS: I'm running PostgreSQL 7.1.2 on FreeBSD 4.3.