Att räkna alla rader i en tabell är en mycket långsam operation; du kan inte påskynda det såvida du inte är beredd att hålla en räkning någon annanstans (och det kan naturligtvis bli osynkroniserat).
Människor som är vana vid MyISAM tenderar att tro att de får count(*) "gratis", men det är det inte riktigt. MyISAM fuskar genom att inte ha MVCC, vilket gör det ganska enkelt.
Frågan du visar gör en fullständig indexsökning av ett index som inte är null, vilket i allmänhet är det snabbaste sättet att räkna raderna i en innodb-tabell.
Det är svårt att gissa vad din applikation är utifrån informationen du har gett, men i allmänhet är det ok för användare (etc.) att se nära uppskattningar av antalet rader i stora tabeller.