Sql – Count rows in an SQL table in O(1)


I understand the best way to count the number of rows in an SQL table is count(*) (or equivalently count(PrimaryKey)).

  1. Is this O(1)?
  2. If not, why not?

Why not just implement a counter and return it for this specific query? Is it because this query is not a common use case?

If the answers vary according to SQL engine, I'd like to hear the differences – but in any case, I'm interested in the actual implementation in production SQL engines.

Best Solution

In some RDBM's this is O(1) (most notably MySQL), put AFAIK it is generally frowned upon and considered an "ugly performance hack". The reasons is that if you have transactions (which every real RDBM should have), the total number of rows in the table might or might not be equal to the total number you can see from the current transaction. This is why the server needs to check which rows are actually visible to your transaction, making it more O(n) than O(1).

If you want to optimize the process of getting the number of rows and are satisfied with an approximate result, most RDBM's have special "info" tables which hold information about the tables, including the approximate number of rows (again, it is not the exact number of rows because of the transactions).