Depende del motor de almacenamiento.
- Para MyISAM, el recuento total de filas se almacena para cada tabla, por lo que
SELECT COUNT(*) FROM yourtable
es una operación O(1). Solo necesita leer este valor. - Para InnoDB, el recuento total de filas no se almacena, por lo que se requiere un análisis completo. Esta es una operación O(n).
Del manual :