the reason that SELECT COUNT(*) comes back so fast from a myisam table is because the database engine keeps the count of rows separately
and of course it can easily do this because whenever it needs to make any change to the table (inserts, deletes, etc.), it must actually
lock the table, after which it just updates the count field it keeps for the table
innodb tables, on the other hand, use row locks, and therefore the SELECT COUNT(*) query must actually count the rows
if you need the count for paging, have a look at the FOUND_ROWS function
