I basically find your sentiment accurate: databases with high concurrency support need to do a lot of work to do an accurate count(*). However, many that were

I basically find your sentiment accurate: databases with high concurrency support need to do a lot of work to do an accurate count(*). However, many that were not postgres supported index-only scans to do it. That doesn't change the algorithmic complexity of O(n) to grovel through the tuples, but it can have a large constant time difference. No anymore, though....9.2 supports index only scans in many common cases. Still, as you say, counting all your tuples repeatedly in a table is going to be much, much more expensive than maintaining the count on categories you care about up-front, paying the lock contention and update-costs as one goes in virtually any database that supports SMP.