[pestaa]

Note that recent versions of Postgres can now COUNT against indices so no need to do a full table scan.

[samstokes]

This certainly helps, but if your indices are several GB in size, even an index scan is a nontrivial expense.