locator - Geo-Search(Distancia) en PHP/MySQL(rendimiento)
google maps php mysql demo (4)
Tengo una tabla MySQL (MyISAM) que contiene aproximadamente 200k entradas de pares lat / long de los que selecciono, en función de la distancia de pares (fórmula de círculo grande) de otro par lat / long. (por ejemplo, todas las entradas que están dentro de un radio de 10 km alrededor de 50.281852, 2.504883)
Mi problema es que esta consulta tarda unos 0,28 segundos. para ejecutar solo para esas 200k entradas (que continúan recibiendo más cada día). Mientras que 0,28 seg. Estaría bien normalmente, esta consulta se ejecuta muy a menudo ya que alimenta la característica principal de mi aplicación web, y muchas veces es parte de una consulta más grande.
Hay alguna manera de acelerar esto? Obviamente, MySQL tiene que ejecutar todas las 200k entradas cada vez y realizar la fórmula de gran círculo para cada entrada. Leí algo sobre geohashing, R-Trees y similares aquí en stackoverflow, pero no creo que sea la forma en que quiero ir. En parte porque nunca he sido un gran admirador de las matemáticas, pero sobre todo porque creo que este problema ya ha sido resuelto por alguien más inteligente que yo en una biblioteca / extensión / etc. que ha sido probado exhaustivamente y se actualiza regularmente.
MySQL parece tener una extensión espacial, pero esa no proporciona una función de distancia. ¿Debo buscar otra base de datos para poner estos pares de coordenadas? PostgreSQL parece tener una extensión espacial bastante madura. Sabes algo al respecto? ¿O simplemente PostgreSQL simplemente usaría la fórmula del gran círculo para obtener todas las entradas dentro de una región determinada?
¿Existe tal vez un producto independiente especializado o una extensión mysql que ya hace lo que estoy buscando?
¿O tal vez haya una biblioteca PHP que podría usar para hacer los cálculos? Utilizando APC pude encajar fácilmente los pares lat-long en la memoria (esas entradas de 200k toman alrededor de 5MB) y luego ejecutar la consulta dentro de PHP. Sin embargo, el problema con este enfoque es que tendría una consulta MySQL como SELECT .. FROM .. WHERE id in (id1, id2, ..) para todos los resultados que pueden ser de hasta miles. ¿Qué tan bien maneja MySQL las consultas como estas? Y luego (dado que esta es una tarea de cálculo numérico), ¿sería suficiente hacerlo en PHP?
¿Alguna otra idea que debería / no debería hacer?
Para completar, aquí está la consulta de muestra, despojada de cualquier parte irrelevante (como dije, generalmente esto es parte de una consulta más grande en la que uní varias tablas):
SELECT id, 6371 * acos( sin( radians( 52.4042924 ) ) * sin( radians( lat ) ) + cos( radians( 50.281852 ) ) * cos( radians( lat ) ) * cos( radians( 2.504883 ) - radians( lon ) ) ) AS dst
FROM geoloc
HAVING dst <10
ORDER BY dst ASC
¡Gracias!
¿Qué pasa si abordas el problema desde un ángulo diferente?
10 km en línea recta es:
- en la latitud es igual a ~ 1 ''(minuto)
- en la longitud es igual a ~ 6 ''(minutos)
Usando esto como base, haga algunos cálculos rápidos y en su consulta agregue a la cláusula WHERE quitando cualquier ubicación que esté fuera de la ''caja'' que se crea al agregar la zona de amortiguamiento con la suposición de 1 ''lat y 6'' de largo
Trabajando desde esta imagen:
- Ubicación GPS que busca (34 ° 12 ''34.0 ", -85 ° 1'' 1.0") [34.2094444444, -85.0169444444]
Usted encuentra la latitud / longitud mínima / máxima
2a. Min Latitude: 34.1927777778, -85.0169444444
2b. Longitud mínima - 34.2094444444, -85.1169444444
2c. Max Latitude: 34.2261111111, -85.0169444444
2d. Longitud máxima: 34.2094444444, -84.9169444444
Ejecute su consulta con el mínimo y máximo de cada dirección
SELECT * FROM geoloc WHERE lat >= 34.1927777 AND lat <= 34.2261111 AND long >= -85.1169444 AND long <= -84.9169444;
Puede integrar el cálculo de distancia con la consulta SQL o puede usar una biblioteca / clase PHP para ejecutar la verificación de distancia después de extraer los datos. De cualquier manera, ha reducido el número de cálculos en un gran porcentaje.
Uso la siguiente función para calcular la distancia entre dos ubicaciones de GPS US84. Se pasan dos parámetros, cada parámetro es una matriz con el primer elemento siendo la latitud y el segundo elemento es la longitud. Creo que tiene una precisión de unos pocos pies, que debería ser suficiente para todos, excepto para los ophiles GPS más duros. Además, creo que esto usa la fórmula de distancia de Haversine.
$ distance = calculateGPSDistance (array (34.32343, -86.342343), array (34.433223, -96.0032344));
function calculateGPSDistance($site1, $site2)
{
$distance = 0;
$earthMeanRadius = 2.0891 * pow(10, 7);
$deltaLatitude = deg2rad($site2[0] - $site1[0]);
$deltaLongitude = deg2rad($site2[1] - $site1[1]);
$a = sin($deltaLatitude / 2) * sin($deltaLatitude / 2) + cos(deg2rad($site1[0])) *
cos(deg2rad($site2[0])) * sin($deltaLongitude / 2) * sin($deltaLongitude / 2);
$c = 2 * atan2(sqrt($a), sqrt(1-$a));
$distance = $earthMeanRadius * $c;
return $distance;
}
ACTUALIZAR
Olvidé mencionar que mi función de distancia devolverá la distancia en pies.
Calcule un cuadro delimitador para seleccionar un subconjunto de las filas en la cláusula WHERE de su consulta SQL, de modo que solo esté ejecutando el costoso cálculo de distancia en ese subconjunto de filas en lugar de ejecutarlo en los 200,000 registros de su tabla. El método se describe en este artículo en Movable Type (con ejemplos de código PHP). Luego puede incluir el cálculo de Haversine en su consulta contra ese subconjunto para calcular las distancias reales y factorizar la cláusula HAVING en ese punto.
Es el cuadro delimitador que ayuda a su rendimiento, porque significa que solo está haciendo el cálculo de distancia caro en un pequeño subconjunto de sus datos. Este es efectivamente el mismo método que Patrick ha sugerido, pero el enlace de Tipo movible tiene explicaciones extensas del método, así como el código PHP que puede usar para construir el cuadro delimitador y su consulta SQL.
EDITAR
Si no cree que haversine es lo suficientemente preciso, entonces también está la fórmula de Vincenty.
// Vincenty formula to calculate great circle distance between 2 locations expressed as Lat/Long in KM
function VincentyDistance($lat1,$lat2,$lon1,$lon2){
$a = 6378137 - 21 * sin($lat1);
$b = 6356752.3142;
$f = 1/298.257223563;
$p1_lat = $lat1/57.29577951;
$p2_lat = $lat2/57.29577951;
$p1_lon = $lon1/57.29577951;
$p2_lon = $lon2/57.29577951;
$L = $p2_lon - $p1_lon;
$U1 = atan((1-$f) * tan($p1_lat));
$U2 = atan((1-$f) * tan($p2_lat));
$sinU1 = sin($U1);
$cosU1 = cos($U1);
$sinU2 = sin($U2);
$cosU2 = cos($U2);
$lambda = $L;
$lambdaP = 2*M_PI;
$iterLimit = 20;
while(abs($lambda-$lambdaP) > 1e-12 && $iterLimit>0) {
$sinLambda = sin($lambda);
$cosLambda = cos($lambda);
$sinSigma = sqrt(($cosU2*$sinLambda) * ($cosU2*$sinLambda) + ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda) * ($cosU1*$sinU2-$sinU1*$cosU2*$cosLambda));
//if ($sinSigma==0){return 0;} // co-incident points
$cosSigma = $sinU1*$sinU2 + $cosU1*$cosU2*$cosLambda;
$sigma = atan2($sinSigma, $cosSigma);
$alpha = asin($cosU1 * $cosU2 * $sinLambda / $sinSigma);
$cosSqAlpha = cos($alpha) * cos($alpha);
$cos2SigmaM = $cosSigma - 2*$sinU1*$sinU2/$cosSqAlpha;
$C = $f/16*$cosSqAlpha*(4+$f*(4-3*$cosSqAlpha));
$lambdaP = $lambda;
$lambda = $L + (1-$C) * $f * sin($alpha) * ($sigma + $C*$sinSigma*($cos2SigmaM+$C*$cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)));
}
$uSq = $cosSqAlpha*($a*$a-$b*$b)/($b*$b);
$A = 1 + $uSq/16384*(4096+$uSq*(-768+$uSq*(320-175*$uSq)));
$B = $uSq/1024 * (256+$uSq*(-128+$uSq*(74-47*$uSq)));
$deltaSigma = $B*$sinSigma*($cos2SigmaM+$B/4*($cosSigma*(-1+2*$cos2SigmaM*$cos2SigmaM)- $B/6*$cos2SigmaM*(-3+4*$sinSigma*$sinSigma)*(-3+4*$cos2SigmaM*$cos2SigmaM)));
$s = $b*$A*($sigma-$deltaSigma);
return $s/1000;
}
echo VincentyDistance($lat1,$lat2,$lon1,$lon2);
Lo que estaba haciendo hasta ahora es exactamente como @Mark descrito anteriormente. Creo que una solución viable para sitios pequeños no fue tan buena para mi caso (200k entradas localizadas dentro de un cuadro de 100x100 km cuadrados centrado alrededor de un punto dado. Estaba usando el mismo truco de Mark pero el rendimiento es muy pobre. 5 usuarios / segundo preguntando por puntos Lat / Lon cercanos por algunas horas y las consultas comienzan a tomar hasta 10 - 15 segundos, y esto sucede después de haber ajustado la configuración mySQL en mi.cnf. Ni siquiera quiero pensar qué pasaría cuando haya serán 2 millones de entradas en todo el mundo.
Entonces, ahora es el momento para el paso 2: curva de Hilbert . Debería resolver el problema del índice B-tree en columnas (lat, lon) que es derrochador (exploraciones onrange, solo se usa una parte del índice B-tree) empleando solo un índice en una columna (hilbert_number). hilbert_number es un número calculado en función de las coordenadas lat / lon de un punto en la curva de Hilbert.
Pero el segundo problema, de probar la distancia entre el punto fijo y todo desde el subconjunto de resultados previo a través de la fórmula de Haversine, permanece. Esa parte puede ser muy lenta. Así que estaba pensando en probar de alguna manera la distancia más directamente, colocando todo en la curva hilbert y aplicando alguna máscara de bits a ese subconjunto de resultados en lugar de aplicar la fórmula Haversine. Simplemente no sé cómo voy a hacer eso ...
De todos modos, otro truco que he empleado para reducir el número de puntos en el subconjunto de resultados fue usar dos cuadros delimitadores e incluir en el subconjunto solo los puntos grises / blancos para más pruebas de Haversine:
Lo que necesito hacer ahora es cambiar a los números de Hilbert y ver cómo se comporta. ¡Pero dudo que esto aumente 10 veces el rendimiento!
Podrías probar un quadkey. Es un índice espacial y reduce la dimensión. Subdivide un mapa en mosaicos pero puede usarlo para almacenar puntos. Puede descargar mi clase php hilbert-curve @ phpclasses.org. También incluye una curva zy una curva moore. Importante es saber que usa una proyección Mercator. Puede buscar mosaicos de mapas de Bing. Explica cómo usar un quadkey. Necesita la coordenada x, yy el valor z (zoom o profundidad). Luego te da un quadkey.