Is count(*) constant time in SQLite, and if not what are alternatives?
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.
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.