Eu tentei alguns SELECT COUNT(*) FROM MyTable vs. SELECT COUNT(SomeColumn) FROM MyTable com vários tamanhos de tabelas, e onde o SomeColumn uma vez é uma coluna de chave de cluster, uma vez que está em um índice não clusterizado e uma vez que não está em nenhum índice.

Em todos os casos, com todos os tamanhos de tabelas (de 300.000 linhas a 170 milhões de linhas), nunca vejo qualquer diferença em termos de velocidade ou plano de execução - em todos os casos, o COUNT é tratado fazendo uma varredura de índice clusterizado --> ou seja, varrendo toda a tabela, basicamente. Se houver um índice não clusterizado envolvido, a varredura será nesse índice - mesmo ao fazer um SELECT COUNT(*) !

Não parece haver nenhuma diferença em termos de velocidade ou abordagem de como essas coisas são contadas - para contá-las todas, o SQL Server só precisa verificar a tabela inteira - ponto final.

Os testes foram feitos no SQL Server 2008 R2 Developer Edition