Det bedste indeks til din forespørgsel er et sammensat indeks på (country, state, latitude, longitude) (country og state kunne byttes). MySQL har god dokumentation om indekser med flere kolonner, som er her
.
Grundlæggende latitude og longitude er ikke særligt selektive individuelt. Desværre understøtter standard B-tree-indekset kun én ulighed, og din forespørgsel har to.
Faktisk, hvis du ønsker GIS-behandling, bør du bruge en rumlig udvidelse til MySQL.