Wie kann die Abfrageleistung verbessert werden, die haversine Formel berechnet?

Question

Bei einer Tabelle mit Orten mit Breiten- und Längengraden, welche dieser Orte sind am nächsten zu einem bestimmten Standort?

Natürlich bedeutet das Finden von Entfernungen auf der Erdoberfläche die Verwendung von Großkreisdistanzen, die mit der Haversine-Formel, auch Spherical Cosine Law-Formel genannt, berechnet wurden.

Ich habe den folgenden Code:

SELECT zip, latitude, longitude, distance 
FROM (
    SELECT z.zip, 
     z.latitude, z.longitude, 
     p.radius, 
     p.distance_unit 
      * DEGREES(ACOS(COS(RADIANS(p.latpoint)) 
      * COS(RADIANS(z.latitude)) 
      * COS(RADIANS(p.longpoint - z.longitude)) 
      + SIN(RADIANS(p.latpoint)) 
      * SIN(RADIANS(z.latitude)))) AS distance 
    FROM zip AS z 
    JOIN ( /* these are the query parameters */ 
    SELECT 42.81 AS latpoint, -70.81 AS longpoint, 
      50.0 AS radius, 111.045 AS distance_unit 
     ) AS p ON 1=1 
    WHERE z.latitude 
    BETWEEN p.latpoint - (p.radius/p.distance_unit) 
     AND p.latpoint + (p.radius/p.distance_unit) 
    AND z.longitude 
    BETWEEN p.longpoint - (p.radius/(p.distance_unit * COS(RADIANS(p.latpoint)))) 
     AND p.longpoint + (p.radius/(p.distance_unit * COS(RADIANS(p.latpoint)))) 
) AS d 
WHERE distance <= radius 

Gibt es eine Möglichkeit, eine Leistung dieser Abfrage zu verbessern?

Ist es notwendig, PostGIS zu verwenden, um es zu verbessern, oder es ist nur ein Wrapper für meine hairsine Formel?

Answer 1

Ich denke, der Planer wird diese Abfrage neu schreiben alles von selbst, aber einen Versuch wert. Zumindest ist es besser.

select zip, latitude, longitude, distance 
from (
    select z.zip, 
      z.latitude, z.longitude, 
      p.radius, 
      p.distance_unit 
       * p.degrees_acos_cos_radians_latpoint 
       * cos(radians(z.latitude)) 
       * cos(radians(p.longpoint - z.longitude)) 
       + p.sin_radians_latpoint 
       * sin(radians(z.latitude)))) as distance 
    from 
     zip z 
     cross join (
      select 
       latpoint, longpoint, radius, distance_unit, 
       latpoint - radius/distance_unit as lat0, 
       latpoint + radius/distance_unit as lat1, 
       longpoint - radius/distance_unit * cos(radians(latpoint)) as long0, 
       longpoint + radius/distance_unit * cos(radians(latpoint)) as long1, 
       sin(radians(latpoint)) as sin_radians_latpoint, 
       degrees(acos(cos(radians(latpoint)) as degrees_acos_cos_radians_latpoint 
      from (
       values (42.81, -70.81, 50.0, 111.045) 
      ) v (latpoint, longpoint, radius, distance_unit) 
     ) p 
    where 
     z.latitude between lat0 and lat1 
     and 
     z.longitude between long0 and long1 
) d 
where distance <= radius 

Answer 2

Die Ausdrücke sind nicht der langsame Teil. Das Problem bei der Suche nach dem nächsten ist die Schwierigkeit, einen Index zu verwenden, um die Anzahl der zu betrachtenden Zeilen zu begrenzen.

Wenn Sie nicht bereits diese z auf, dann werden sie helfen:

INDEX(latitude), 
INDEX(longitude) 

Wenn Sie sie bereits hatten, stellen Sie sicher, dass einer von ihnen tatsächlich von der Unterabfrage verwendet wurde.

Das wird die nächste Schritt drastischer sein (und fruchtbare): http://mysql.rjweb.org/doc.php/latlng

Answer 3

Diese Abfrage wird nie besonders schnell. Es gibt jedoch einige Möglichkeiten, wie es verbessert werden kann.

Zuerst: Die Haversine Formel ist hier nicht notwendig. Die Korrekturen, die es anwendet, sind nur notwendig, wenn die Erdkrümmung ein bedeutender Faktor oder sehr nahe bei den Polen ist. Beides ist hier nicht der Fall - die größte Entfernung, die genau berechnet werden muss, beträgt 12 Meilen, was kaum über dem Horizont liegt. Auf dieser Skala ist die Erde effektiv flach, so dass der Satz des Pythagoras gut genug ist, um Entfernungen zu berechnen.

Ein Grad der Breite ist etwa 69 Meilen, und bei 52 ° N (um, wo die Niederlande), ein Längengrad ist cos (52 °) x 69 = 42,5 Meilen, so dass die Formel zu:

sqrt (pow (69 * (lat - $ Breite), 2) + Pow (42,5 * (lng - $ Längengrad), 2))

Zweite: können wir eine „Scheren Test verwenden "für Breiten- und Längengrade. Wenn ein Punkt mehr als 12 Meilen in beliebiger Himmelsrichtung von Ihrem Zielpunkt entfernt ist, kann er nicht innerhalb eines 12-Meilen-Kreises von diesem Punkt liegen. Wir können diese Tatsache verwenden, um einen schnellen Vergleich der Breiten- und Längengrade durchzuführen, wobei die Entfernungsberechnung vollständig übersprungen wird. Mit den Zahlen für einen Breitengrad/Längen wir oben abgeleitet, die wir haben:

WHERE (lat ZWISCHEN ($ Breite - 12/69,0) und ($ Breite + 12/69,0)) UND (lng ZWISCHEN ($ Länge - 12/42.5) UND ($ Länge + 12/42.5))

Beachten Sie, dass dies nicht die vollständige Distanzprüfung ersetzt! Es ist nur ein erster Schritt, um schnell Punkte zu entfernen, die nicht im richtigen Radius liegen können. Wenn ein Index auf lat oder lng gesetzt ist, kann der Datenbankserver es vermeiden, viele der Zeilen in der Datenbank zu untersuchen.