Contar todas las filas de una tabla es una operación muy lenta; realmente no puede acelerarlo, a menos que esté preparado para llevar un conteo en otro lugar (y, por supuesto, eso puede desincronizarse).
Las personas que están acostumbradas a MyISAM tienden a pensar que obtienen count (*) "gratis", pero en realidad no es así. MyISAM hace trampa al no tener MVCC, lo que lo hace bastante fácil.
La consulta que muestra está realizando un escaneo de índice completo de un índice no nulo, que generalmente es la forma más rápida de contar las filas en una tabla de innodb.
Es difícil adivinar a partir de la información que ha proporcionado cuál es su aplicación, pero en general, está bien para los usuarios (etc.) ver aproximaciones cercanas del número de filas en tablas grandes.
