[np422]

Since they are using postgresql, it might be relevant to know that count distinct have for a very long time been a weak spot for pg.

Since release 9.3 index-only scans have been implemented and performance of count distinct queries improved significantly - no more full table scans.

Wiki page: https://wiki.postgresql.org/wiki/Slow_Counting

It would be fun to have access to the same dataset or a more detailed description of the tables involved for further tinkering ....

[Fishkins]

Just a nit pick, but index-only scans were added in 9.2 https://wiki.postgresql.org/wiki/Index-only_scans