In InnoDB, count() will not work like MyISAM (row count stored in table files). So when you run count() on InnoDB , it will find small index of the table and then check counts and specially when you are running count on primary key, it will do full table scan as Primary key is clustered in InnoDB. That’s why it’s taking too much time. After first time running, its possible that data will be cache in Query cache OR buffer pool so second and third time it will be faster.
Partitions can be the better option to divide the data in multiple tables.
Thanks for your feedback.
Because we are using InnoDB, I’m wondering if migrating to Percona server (either 5.5 which will be as a quick replacement, or 5.6) would mitigate partially this performance problems, as I know Percona has XtraDB which is a InnoDB engine but with great optimisations.