En general si la cantidad de registros a contar es relativamente reducida (menos de 2.000.000) el delay de ambas formas es más o menos el mismo. De todos modos, la forma más eficiente no es la de contar las instancias de un campo, por más que sea campo clave, porque estás obligando al motor a verificar un campo y no contando los registros existentes.
MySQL no va a diferenciar el proceso si es un campo clave o no. Va a verificar de todos modos si el campo es NULL antes de contarlo. El hecho que no pueda ser jamás NULL es algo que al algoritmo del conteo no le interesa: la verificación se hará igual.
Esto hace que en una gran cantidad de registros se vaya acumulando un delay que eventualmente puede ser significativo.
Simplificando:
Código:
SELECT COUNT(*) FROM TABLA;
es la forma más eficiente porque el algoritmo se ocupa de contar los registros que existen, y no el estado que los campos tengan.