Nós o implementamos mais ou menos como o código abaixo (disclaimer:eu tirei isso de um arquivo e apaguei o código que era irrelevante para o problema em questão. Eu não executei isso, mas você deve ter uma ideia.
$maxLat = $city->latitude + ($max_distance / 69); // 69 Miles/Degree
$minLat = $city->latitude - ($max_distance / 69);
$maxLon = $city->longitude + ($max_distance / (69.172 * cos($city->latitude * 0.0174533)));
$minLon = $city->longitude - ($max_distance / (69.172 * cos($city->latitude * 0.0174533)));
// Simplify terms to speed query
$originLatRadCos = cos($city->latitude * 0.0174533);
$originLatRadSin = sin($city->latitude * 0.0174533);
$originLonRad = $city->longitude * 0.0174533;
$city_distance_query = "
SELECT city_id,
3963 * acos(($originLatRadSin * sin( latitude * 0.0174533)) +
($originLatRadCos * cos(latitude * 0.0174533) * cos((longitude * 0.0174533) -
$originLonRad))) AS distanceFromOrigin
FROM cities
WHERE
latitude < $maxLat AND latitude > $minLat AND longitude < $maxLon AND longitude > $minLon";
O resto da consulta
SELECT cities.city_name, CityDistance.distanceFromOrigin,
FROM cities
INNER JOIN ($city_distance_query) AS CityDistance ON CityDistance.city_id=cities.city_id
WHERE (distanceFromOrigin < $distance OR distanceFromOrigin IS NULL)
