Det beror på lagringsmotorn.
- För MyISAM lagras det totala radantalet för varje tabell så
SELECT COUNT(*) FROM yourtable
är en operation O(1). Den behöver bara läsa detta värde. - För InnoDB lagras inte det totala radantalet så en fullständig genomsökning krävs. Detta är en O(n)-operation.
Från manualen :