IMHO: Well, MHO disagrees some...
* The cost of cosine, etc is pretty minimal.
* Adding a compound index probably won't help by itself. Try it; try both (lat,lng) and (lng,lat) so it can choose between them. Check the EXPLAIN, it might still say "20705 Rows".
* The ORDER BY being a hairy expression is not nearly as important as having to filter 20705 rows.
Here's something else to try:
1. Get ids in a rectangle
2. Compute distances and do the ORDER BY.
Thus:
ALTER TABLE city
ADD INDEX (latitude, longitude, id),
ADD INDEX (longitude, latitude, id);
SELECT city_id,
city_name,
ROUND( 3959 *
acos(
cos( radians( 48.983334 ) ) *
cos( radians( latitude ) ) *
cos( radians( longitude ) - radians( 6.0833335 ) ) +
sin( radians( 48.983334 ) ) *
sin( radians( latitude ) )
),
1
) AS distance
FROM city a,
( SELECT id FROM city
WHERE latitude BETWEEN 48.283333 AND 49.683334
AND longitude BETWEEN 5.3833337 AND 6.7833333
) b
WHERE a.id = b.id
ORDER BY distance
LIMIT 40;
This way, the subquery will be "using index" (although it will still have to search 20K rows). But it will whittle the list of ids down to maybe 100 before doing the rest of the work.
If you like that, then drop these:
INDEX idx_lat (`latitude` ASC) ,
INDEX idx_lng (`longitude` ASC) ,
In any case
INDEX fk_city_region (`region_id` ASC) ,
is redundant -- it is 'covered' by the last index.
A minor note: FLOAT has only 24 bits of precision, so your FLOAT(12,7) won't always have a full 7 digits of precision. Still you have precision to something like 2 meters, much more than is required for a "city".
As you observed, > and < and BETWEEN are probably mapped to identical code.
I would even do
BETWEEN ? - ? AND ? + ?
and substitute $center, $radius, $center, $radius
MySQL will quickly do the arithmetic before starting to do the query.