I might be out of touch a little with Postgres (I last used it in 2010), but my impression was that COUNT(*) still needed to scan the actual table in order to exclude rows that had been deleted in a transaction, due to the way multi-version concurrency worked. Is this something that has been improved since then?