Да, как реализован COUNT()?
Зависит от:
а) того, что будет внутри COUNT
б) того что будет в WHERE (и будет ли он вообще);
в) реализации в конкртеной СУБД;
Пример 1: если вы сделаете COUNT с WHERE по неиндексированному полю, то без сканирования таблицы не обойтись. Кроме того, если поле внутри COUNT() может быть NULL, то СУБД придется выкидывать еще и нуллы, т.к. COUNT их не учитывает.
Пример 2: если вы сделаете COUNT по первичному ключу без каких-либо фильтров, то СУБД вероятно просто вернет вам количество строк из своих служебных структур, т.к. первичные ключи а) уникальны; б) не могут быть NULL в большинстве сегодняшних СУБД.
Вывод: SQL это высокоуровневый декларативный язык, который перекладывает принятие алгоритмических решений на планировщик СУБД, что дает очень большой простор для оптимизаций в конкретных реализациях. Лучший рецепт - построить план КОНКРЕТНОГО запроса и увидеть, что потребуется для его выполнения.