Mysql performance and Count(*)

Question

I want to know that my sql execute count queries in linear time or in log(n) time i think that if query parameter was indexed it can do it by cubing

Answer 1

It all depends on the query, or more precisely, on the query plan MySql eventually select to process the query.

Also it all depend what we mean by 'n', in these big O expression. For example if 'n' is the count value eventually returned, and if that counts is that produced by a query which requires iteratively scanning multiple tables, the complexity could be worse than linear.

Answer 2

The answer to this is complicated. Not only does it depend on the number of tables involved, but it can also depend on what storage engine you're using.

Having said that, this is what the manual says:

COUNT(*) is optimized to return very quickly if the SELECT retrieves from one table, no other columns are retrieved, and there is no WHERE clause. For example:

mysql> SELECT COUNT(*) FROM student;

This optimization applies only to MyISAM tables only, because an exact row count is stored for this storage engine and can be accessed very quickly. For transactional storage engines such as InnoDB, storing an exact row count is more problematic because multiple transactions may be occurring, each of which may affect the count.

-- MySQL Manual

Answer 3

• MyISAM will return immediatelly.
• InnoDB will do PK scan, so time will lineary increase with number of records.

If you need to see approximately how many records InnoDB table holds, the fastest way is using

EXPLAIN select * from student;

(but innodb statistics may be wrong, so 40% error is quite possible also)