Is count(*) constant time in SQLite, and if not what are alternatives?

Question

I'm looking for the best way to count how many rows there are in a large (15 million+ rows) table. The naive way of select count(*) from table; is apparently O(n) according to a few older posts I've found on the matter, e.g. http://osdir.com/ml/sqlite-users/2010-07/msg00437.html.

Is there a constant time mechanism to get this information, or failing that are there preferred alternatives to the straightforward select count(*) query?

Answer 1

SQLite has a special optimization for COUNT(*) without a WHERE clause, where it goes through the table's B-tree pages and counts entries without actually loading the records. However, this still requires that all the table's data (except overflow pages for large records) is visited, so the runtime is still O(n).

SQLite does not store a separate record count in the database because that would make all changes slower.

Answer 2

No, it is not constant time.

sqlite> CREATE TABLE test ( a );
sqlite> EXPLAIN QUERY PLAN SELECT COUNT(*) FROM test;
0|0|0|SCAN TABLE test (~1000000 rows)
sqlite> EXPLAIN QUERY PLAN SELECT COUNT(1) FROM test;
0|0|0|SCAN TABLE test (~1000000 rows)

You can use EXPLAIN QUERY PLAN SELECT ... to get an idea of the performance of a query.