Как сделать поиск по бд городов?

Попробуй сделать что б начинало искать после введенных 3-ех первыйх букв, тогда и нагрузка будет меньше! Я использовал https://jqueryui.com/autocomplete/

Решал подобную задачу. Для начала структурируйте сами данные. Разбейте города по странам и присвойте каждому городу свой приоритет (например, столицы - 1, миллионники - 2, областные центры - 3 и т.д.). Далее запускается поиск по этому приоритету (и выводятся города только той страны, к которой они относятся). В начале подсказки выводятся наиболее значимые объекты (например, всего в подсказке выводится 5 городов). Далее, если не хватает данных для вывода по самому высокому приоритету, выводятся данные по более низкому и т.д. Из плюсов здесь также будет то, что наиболее вероятные города-подсказки (которые и нужны пользователю) будут в верхней части списка.

Что-то мне подсказывает, что у вас не проставлены/неверно проставлены индексы. Миллион городов это относительно небольшая таблица, LIKE должен выполняться за доли секунды.

По хорошему, здесь вообще нужна структурированная геобаза по типу VK (где города упорядочены по отдельным географическим районам), т.к. даже в рамках одного района встречаются населенные пункты с одинаковым названием. Чтобы их не путать нужна подсказка с указанием географического района, к которому относится населенный пункт.