Ich habe derzeit knapp eine Million Standorte in einer MySQL-Datenbank, alle mit Längen- und Breitengradinformationen.
Ich versuche, den Abstand zwischen einem Punkt und vielen anderen Punkten über eine Abfrage zu ermitteln. Es ist nicht so schnell, wie ich es mir wünsche, besonders bei mehr als 100 Treffern pro Sekunde.
Gibt es dafür eine schnellere Abfrage oder möglicherweise ein schnelleres System als MySQL? Ich benutze diese Abfrage:
SELECT
name,
( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) )
* cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763))
* sin( radians(locations.lat)))) AS distance
FROM locations
WHERE active = 1
HAVING distance < 10
ORDER BY distance;
Hinweis: Die angegebene Entfernung ist in Meilen angegeben . Wenn Sie Kilometer benötigen , verwenden Sie 6371
anstelle von 3959
.
Antworten:
Erstellen Sie Ihre Punkte mit
Point
Werten vonGeometry
Datentypen in derMyISAM
Tabelle. Ab MySQL 5.7.5 unterstützenInnoDB
Tabellen jetzt auchSPATIAL
Indizes.Erstellen Sie einen
SPATIAL
Index für diese PunkteVerwenden Sie
MBRContains()
, um die Werte zu finden:oder in
MySQL 5.1
und über:Dadurch werden alle Punkte ungefähr innerhalb des Felds ausgewählt
(@lat +/- 10 km, @lon +/- 10km)
.Dies ist eigentlich keine Box, sondern ein kugelförmiges Rechteck: Breiten- und Längengrad-gebundenes Segment der Kugel. Dies mag sich von einem einfachen Rechteck im Franz-Joseph-Land unterscheiden , ist aber an den meisten bewohnten Orten ziemlich nahe daran.
Wenden Sie zusätzliche Filterung an, um alles innerhalb des Kreises auszuwählen (nicht das Quadrat).
Wenden Sie möglicherweise eine zusätzliche Feinfilterung an, um den großen Kreisabstand zu berücksichtigen (für große Entfernungen).
quelle
@lon - 10 / ( 111.1 / cos(@lat))
(und die zweite im Paar ist, sobald alles korrekt ist).cos(lon)
ist nur für kleinere Entfernungen genau. Siehe janmatuschek.de/LatitudeLongitudeBoundingCoordinates111.(1)
km in einem Breitengrad.mypoint
ist das Feld in der Tabelle, in dem die Koordinaten gespeichert sind.Keine MySQL-spezifische Antwort, aber es verbessert die Leistung Ihrer SQL-Anweisung.
Was Sie effektiv tun, ist die Berechnung des Abstands zu jedem Punkt in der Tabelle, um festzustellen, ob er innerhalb von 10 Einheiten eines bestimmten Punkts liegt.
Bevor Sie diese SQL ausführen, können Sie vier Punkte erstellen, die eine Box mit 20 Einheiten auf einer Seite zeichnen, wobei sich Ihr Punkt in der Mitte befindet. (x1, y1). . . (x4, y4), wobei (x1, y1) ist (gegeben + 10 Einheiten, gegebenLat + 10 Einheiten). . . (GivenLong - 10 Einheiten, GivenLat -10 Einheiten). Eigentlich brauchen Sie nur zwei Punkte, oben links und unten rechts nennen sie (X1, Y1) und (X2, Y2)
Jetzt verwendet Ihre SQL-Anweisung diese Punkte, um Zeilen auszuschließen, die definitiv mehr als 10u von Ihrem angegebenen Punkt entfernt sind. Sie kann Indizes für die Breiten- und Längengrade verwenden, sodass sie um Größenordnungen schneller sind als derzeit.
z.B
Der Box-Ansatz kann falsch positive Ergebnisse zurückgeben (Sie können Punkte in den Ecken der Box aufnehmen, die> 10u vom angegebenen Punkt entfernt sind), sodass Sie immer noch den Abstand jedes Punkts berechnen müssen. Dies wird jedoch wieder viel schneller sein, da Sie die Anzahl der zu testenden Punkte drastisch auf die Punkte in der Box beschränkt haben.
Ich nenne diese Technik "Denken in der Kiste" :)
EDIT: Kann dies in eine SQL-Anweisung eingefügt werden?
Ich habe keine Ahnung, wozu mySql oder Php in der Lage ist, sorry. Ich weiß nicht, wo der beste Ort ist, um die vier Punkte zu erstellen, oder wie sie an eine mySql-Abfrage in PHP übergeben werden könnten. Sobald Sie jedoch die vier Punkte erreicht haben, hindert Sie nichts mehr daran, Ihre eigene SQL-Anweisung mit meiner zu kombinieren.
Ich weiß, dass ich mit MS SQL eine SQL-Anweisung erstellen kann, die vier Gleitkommazahlen deklariert (X1, Y1, X2, Y2) und diese vor der "main" select-Anweisung berechnet, wie gesagt, ich habe keine Ahnung, ob dies möglich ist MySql. Ich wäre jedoch immer noch geneigt, die vier Punkte in C # zu erstellen und sie als Parameter an die SQL-Abfrage zu übergeben.
Es tut mir leid, ich kann nicht mehr helfen. Wenn jemand die MySQL- und PHP-spezifischen Teile davon beantworten kann, können Sie diese Antwort jederzeit bearbeiten.
quelle
Die folgende MySQL-Funktion wurde in diesem Blogbeitrag veröffentlicht . Ich habe es nicht viel getestet, aber nach dem, was ich aus dem Beitrag erfahren habe , kann dies für Sie gut funktionieren , wenn Ihre Längen- und Breitengrade indiziert sind :
Beispielnutzung:
Angenommen, eine Tabelle
places
mit den Feldernlatitude
&longitude
:quelle
SELECT ROUND(((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lnt1 - lnt2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) * 1.609344 * 1000) AS distance
Ich musste ein ähnliches Problem lösen (Zeilen nach Abstand von einem Punkt filtern) und durch die Kombination der ursprünglichen Frage mit Antworten und Kommentaren eine Lösung finden, die sowohl für MySQL 5.6 als auch für 5.7 perfekt funktioniert.
coordinates
Dieses Feld mit TypPOINT
undSPATIAL
Index6371
dient zur Berechnung der Entfernung in Kilometern. Der56.946285
Breitengrad für den Mittelpunkt24.105078
ist der Längengrad für den Mittelpunkt. Der15
maximale Abstand in KilometernIn meinen Tests verwendet MySQL den SPATIAL-Index für das
coordinates
Feld, um schnell alle Zeilen innerhalb des Rechtecks auszuwählen, und berechnet dann den tatsächlichen Abstand für alle gefilterten Stellen, um Orte von Rechteckecken auszuschließen und nur Stellen innerhalb des Kreises zu belassen .Dies ist eine Visualisierung meines Ergebnisses:
Graue Sterne visualisieren alle Punkte auf der Karte, gelbe Sterne werden von der MySQL-Abfrage zurückgegeben. Graue Sterne innerhalb der Ecken des Rechtecks (aber außerhalb des Kreises) wurden
MBRContains()
durch eineHAVING
Klausel ausgewählt und dann durch eine Klausel abgewählt .quelle
Wenn Sie MySQL 5.7. * verwenden, können Sie st_distance_sphere (POINT, POINT) verwenden .
quelle
Dies ist die Abfrage zur Entfernungsberechnung zwischen Punkten in MySQL. Ich habe sie in einer langen Datenbank verwendet. Sie funktioniert perfekt! Hinweis: Nehmen Sie die Änderungen (Datenbankname, Tabellenname, Spalte usw.) gemäß Ihren Anforderungen vor.
quelle
Quelle
quelle
quelle
Eine MySQL-Funktion, die die Anzahl der Meter zwischen den beiden Koordinaten zurückgibt:
Um den Wert in einem anderen Format zurückzugeben, ersetzen Sie die
6371000
Funktion in der Funktion durch den Erdradius in der von Ihnen gewählten Einheit. Zum Beispiel wären Kilometer6371
und Meilen3959
.Um die Funktion zu verwenden, rufen Sie sie einfach wie jede andere Funktion in MySQL auf. Wenn Sie beispielsweise einen Tisch hätten
city
, könnten Sie die Entfernung zwischen jeder Stadt und jeder anderen Stadt ermitteln:quelle
Der vollständige Code mit Details zur Installation als MySQL-Plugin finden Sie hier: https://github.com/lucasepe/lib_mysqludf_haversine
Ich habe dies letztes Jahr als Kommentar gepostet. Da mir freundlicherweise @TylerCollier vorgeschlagen hat, als Antwort zu posten, hier ist es.
Eine andere Möglichkeit besteht darin, eine benutzerdefinierte UDF-Funktion zu schreiben, die den Haversine-Abstand von zwei Punkten zurückgibt. Diese Funktion kann Eingaben aufnehmen:
Also können wir so etwas schreiben:
alle Datensätze mit einer Entfernung von weniger als 40 Kilometern abzurufen. Oder:
um alle Datensätze mit einer Entfernung von weniger als 25 Fuß abzurufen.
Die Kernfunktion ist:
quelle
Eine schnelle, einfache und genaue Annäherung (für kleinere Entfernungen) kann mit einer sphärischen Projektion erfolgen . Zumindest in meinem Routing-Algorithmus bekomme ich einen 20% igen Boost im Vergleich zur korrekten Berechnung. Im Java-Code sieht es so aus:
Ich bin mir nicht sicher über MySQL (sorry!).
Stellen Sie sicher, dass Sie die Einschränkung kennen (der dritte Parameter von assertEquals bedeutet die Genauigkeit in Kilometern):
quelle
Hier ist eine sehr detaillierte Beschreibung von Geo Distance Search mit MySQL, einer Lösung, die auf der Implementierung der Haversine-Formel in MySQL basiert. Die vollständige Lösungsbeschreibung mit Theorie, Implementierung und weiterer Leistungsoptimierung. Obwohl der räumliche Optimierungsteil in meinem Fall nicht richtig funktioniert hat. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
quelle
Lesen Sie Geo Distance Search mit MySQL , einer Lösung, die auf der Implementierung von Haversine Formula in MySQL basiert. Dies ist eine vollständige Lösungsbeschreibung mit Theorie, Implementierung und weiterer Leistungsoptimierung. Obwohl der räumliche Optimierungsteil in meinem Fall nicht richtig funktioniert hat.
Ich habe dabei zwei Fehler bemerkt:
die Verwendung von
abs
in der select-Anweisung auf Seite 8. Ich habe es einfach weggelassenabs
und es hat funktioniert.Die räumliche Suchentfernungsfunktion auf p27 konvertiert nicht in Bogenmaß oder multipliziert den Längengrad mit
cos(latitude)
, es sei denn, seine räumlichen Daten werden mit dieser Berücksichtigung geladen (kann nicht aus dem Kontext des Artikels entnommen werden), aber sein Beispiel auf p26 zeigt an, dass seine räumlichen DatenPOINT
nicht mit geladen sind Bogenmaß oder Grad.quelle
quelle
Mit MySQL
Siehe: https://andrew.hedges.name/experiments/haversine/
Siehe: https://stackoverflow.com/a/24372831/5155484
Siehe: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/
HINWEIS: Wird
LEAST
verwendet, um Nullwerte zu vermeiden, da ein Kommentar unter https://stackoverflow.com/a/24372831/5155484 vorgeschlagen wirdquelle