I find it baffling that the query planner can't provide a way to do count(*) quickly in the common case. It does so many other clever things; this one seems fairly straightforward to implement by comparison, and there's obviously a need for it, as the existence of this article shows.