Подсчет строк в таблице SQL в O (1)

Question

Я понимаю, что лучший способ подсчитать количество строк в таблице SQL - это count (*) (или эквивалентно count (PrimaryKey)).

1. Это O (1)?
2. Если нет, то почему?

Почему бы просто не реализовать счетчик и не вернуть его для этого конкретного запроса? Это потому, что этот запрос не является распространенным случаем?

Если ответы различаются в зависимости от механизма SQL, я бы хотел услышать о различиях, но в любом случае меня интересует фактическая реализация в производственных механизмах SQL.

Answer 1

База данных может хранить количество строк в таблице и отвечать O (1) на select count(*) From MyTable

Но, на самом деле, что хорошего в этом? Любое отклонение от этого (скажем, select count(*) from MyTable where Category = 5) потребует полного сканирования таблицы (или сканирования индекса) и будет O (N).