12

What is the complexity of this MySQL query

SELECT COUNT(*) FROM MyTable;

Is the count of number of entries in a table stored somewhere and updated every time a row is inserted or deleted? If that is the case, then the complexity should be O(1).

Manish Singh
  • 5,848
  • 4
  • 43
  • 31
  • It seems like it would have to be `O(N)` the moment you tack on a `WHERE` statement, so be careful evaluating this. – crush Oct 09 '14 at 14:40

3 Answers3

10

It depends on the storage engine.

  • For MyISAM the total row count is stored for each table so SELECT COUNT(*) FROM yourtable is an operation O(1). It just needs to read this value.
  • For InnoDB the total row count is not stored so a full scan is required. This is an O(n) operation.

From the manual:

InnoDB does not keep an internal count of rows in a table. (In practice, this would be somewhat complicated due to multi-versioning.) To process a SELECT COUNT(*) FROM t statement, InnoDB must scan an index of the table, which takes some time if the index is not entirely in the buffer pool. If your table does not change often, using the MySQL query cache is a good solution. To get a fast count, you have to use a counter table you create yourself and let your application update it according to the inserts and deletes it does. SHOW TABLE STATUS also can be used if an approximate row count is sufficient. See Section 13.2.13.1, "InnoDB Performance Tuning Tips".

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • I have a question. If by complexity, we mean the number of disk reads, will it still be `O(n)` to scan the index of the table? Doesn't it depend on the index type? – ypercubeᵀᴹ Mar 10 '11 at 11:43
1

AFAIK in MyISAM rows-count are cached, in InnoDB not, and with every count-all he counts all rows.

cichy
  • 10,464
  • 4
  • 26
  • 36
-5

I'm not sure if that value is stored or not, but that isn't important at all for your query. Using MySQL with your query it will count all the returned rows the moment you execute it.

Pieter888
  • 4,882
  • 13
  • 53
  • 74
  • 4
    Important or not, it's his decision, isn't it? It seems a perfectly valid question to me. – ypercubeᵀᴹ Mar 10 '11 at 11:54
  • 3
    It's very important to know the complexity of functions, especially to avoid long queries a perform more intelligent ones when you have a large amount of data. – daniel souza Jan 19 '17 at 01:24