Обогнать MSSQL COUNT DISTINCT не удалось. Приближённый, написанный с помощью HyperLogLog на C#, работает с практически идентичной скоростью, по крайней мере в пределах 20млн строк (10млн различных, 630Мб данных). Время точно тратится не только на I/O, т.к. select sum(value) отрабатывает во много раз быстрее.