Большое кол-во данных mysql?
Где?
Вот это "стран: 236 (норм), Городов: ~4,716,527 на сумму 239.8 мб" - очень малое количество данных, просто смешное.
Решил протестировать все это дело. Например по запросу Россия скрипт думал 12 сек.
Ну если у вас скрипт медленно "думает" значит надо написать нормальный скрипт.
Выборка из такого количества будет занимать доли секунды на самом старинном сервере.
Более того - за 12секунд или около того реально даже вручную выбрать эти данные из БД напечатанной на бумаге.