Count rows in an SQL table in O(1)

Question

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.

Answer 1

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).

Answer 2

No this is not a common use case. Most row counts I have seen have some where clause involved.

The main reason this is not implemented though is the row counter would be a cause of contention in a multi user environment. Every time a row was inserted or deleted the counter would need updating effectively locking the whole table for each insert/delete.