MyISAM, an aged MySQL engine with no transactional support and awful scalabililty spoiled many developers with an ultra fast count(*) implementation. But is ultra fast only when there is no conditions in the where part of the sentence.
At least in InnoDB (the common replacement for MySQL, at least until Maria gets more traction) every count(*) has to make a temporary table with all the matching lines and the count the lenght of the table.
There are two ways to deal with count(*).
1.- Don't use count(*) rather count(primaryKey).
In InnoDB the primary key is always part of any index
(Read more)