Past the recommendation of counting based on an indexed column, I wonder if this should really be user's concern. This paragraph especially triggers a "this should be fixed upstream" feeling in me:
> A word of warning. When work_mem is high enough to hold the whole relation PostgreSQL will choose HashAggregate even when an index exists. Paradoxically, giving the database more memory resources can lead to a worse plan. You can force the index-only scan by setting SET enable_hashagg=false; but remember to set it true again afterward or other query plans will get messed up.
But worst case scenario, this article will be useful until this is fixed, so thanks again :)