Вы проверили индексы в своей базе данных? Если ваш запрос отформатирован правильно, и у вас есть правильные индексы в вашей таблице, вы можете запросить базу данных из 5 миллионов строк и получить результаты менее чем за секунду. Я бы посоветовал посмотреть, есть ли у вас индекс по городу с добавленным столбцом State к индексу. Таким образом, когда вы делаете запрос по городу, он будет возвращать как город, так и штат из индекса.
Если вы выполните свой запрос в sql management studio и нажмете ctrl-m, вы увидите план выполнения по вашему запросу. Если вы видите что-то вроде сканирования таблицы или сканирования индекса, значит, у вас неверный индекс в таблице. Вы хотите убедиться, что ваши результаты имеют поиск по индексу, это означает, что ваш запрос проходит через соответствующие страницы в базе данных, чтобы найти ваши данные.
Надеюсь, это поможет.