План запроса тут влияет слабо.
Если в запросе нет GROUP BY и ORDER BY, сервер может быстро вернуть вам первую найденную запись и потихоньку тратить время на поиск следующих строк. Для пользователя время отклика на получение следующей строки может быть не заметно. Ведь ему надо затратить какое-то время на обработку первой строки.
В случае COUNT(), сервер вынужден сформировать весь список выборки, после этого он сможет ответить на ответ, сколько строк он нашел. Поэтому вы и видите задержку.