Depends on the storage engine afair, but both innodb an myisam have either index or global metadata based solution for this. I think in myisam its an estimste if you use count(*) so you need to use count(id) to get an exact value. This is all well documented