For what it's worth, I had used MySQL on a table with ~20 million rows and doing a count on an index would also be extremely slow. I put in triggers to do counts which worked perfectly for 99% of the sites, but there was some issue (either a bug or programmer error, never figured out which), but a handful of rows on this count table would claim there were a negative number of rows for a given query. (Any row with a negative number was typically zero a count of zero in the real table. In the cases where it was not zero, it was very close to it).