De beste index voor uw zoekopdracht is een samengestelde index op (country, state, latitude, longitude) (country en state verwisseld kunnen worden). MySQL heeft goede documentatie over indexen met meerdere kolommen, namelijk hier
.
Kortom, latitude en longitude zijn individueel niet bijzonder selectief. Helaas ondersteunt de standaard B-tree-index slechts één ongelijkheid, en uw zoekopdracht heeft er twee.
Als u GIS-verwerking wilt, moet u eigenlijk een ruimtelijke uitbreiding van MySQL gebruiken.