You may be interested in this technique, or some of the others in the article: https://www.citusdata.com/blog/2016/10/12/count-performance/...

EDIT: I'm also curious what version of Postgres you've experienced this on? Sounds like there may have been improvements to COUNT (DISTINCT in v11+