El mejor índice para su consulta es un índice compuesto en (country, state, latitude, longitude) (country y state se puede cambiar). MySQL tiene buena documentación sobre índices de varias columnas, que es aquí
.
Básicamente, latitude y longitude no son particularmente selectivos individualmente. Desafortunadamente, el índice de árbol B estándar solo admite una desigualdad y su consulta tiene dos.
En realidad, si desea procesamiento GIS, debe usar una extensión espacial para MySQL.
