Den nächsten (Entfernungs-) Datensatz aus einer Datenbank effektiv auswählen
Ich habe eine Datenbank mit 40.000 Orten und wächst gerade.
Angenommen, ich bin der rote Punkt
Ich möchte den nächsten Datensatz so schnell wie möglich abrufen können.
Aber die Entfernung zu dem nächsten Gegenstand könnte alles sein. Und es könnte auch 0-n Übereinstimmungen geben. Aber muss ich alle 40000 Ergebnisse laden, wenn ich nur nach 1 suche?
Wie kann ich die Datensätze nach Entfernung sortieren? Sollte es in MYSQL oder PHP gemacht werden? Diese Berechnung erfolgt bei fast jeder Anfrage, pro Benutzer und pro Seite, daher muss die Lösung schnell sein.
Bearbeiten Vielen Dank für die schnellen und vielversprechenden Antworten. Ich muss diese Ressourcen überprüfen und die Antworten innerhalb weniger Tage akzeptieren / kommentieren.
4 Antworten
Dieses Problem wird in dieser Scribd-Präsentation behandelt (Theorie + mathematische Formeln + Mysql): Geo Distance mit MySQL
Ich hoffe, es deckt alles ab, was Sie brauchen
Die einfachste Lösung besteht darin, die Entfernung für jeden Datensatz einfach zu berechnen und nach diesem Wert zu sortieren. Das Problem ist: Dies ist sehr teuer und Sie können dafür keinen Index verwenden . Sie können die Kosten senken, indem Sie nur eine Teilmenge Ihrer Aufzeichnungen betrachten, vielleicht durch eine Begrenzungsbox begrenzen, wie einige Poster hier vorschlagen.
Wenn Sie eine klare und schnelle Lösung wünschen, sehen Sie sich die an Räumliche Erweiterungen von MySQL . Diese sind genau für was Sie machen möchten. Diese unterstützen:
- Ein neuer Spalten-Typ "Point"
- Ein spezieller Indextyp, der für Distanzabfragen optimiert ist
- Ein Distanzoperator.
Dieser Howto bietet einige Beispiele:
%Vor%Erstellen Sie eine "Begrenzungsbox" zur Verwendung in einer WHERE-Klausel in Ihrer SQL-Abfrage, wie in dieser Artikel über Movable Type (mit PHP-Codebeispielen), dann fügen Sie die Haversine-Formel in Ihre Abfrage ein, um die tatsächlichen Entfernungen zu berechnen und das Ergebnis nach Entfernung ASC zu sortieren. Der nächstgelegene Veranstaltungsort ist dann die erste Rückkehr in der Ergebnismenge.
Es ist die Bounding Box, die Ihre Leistung unterstützt, weil Sie nur die teure Distanzberechnung für eine kleine Teilmenge Ihrer Daten durchführen müssen
Wenn die anfängliche Abfrage keine Datensätze zurückgibt, erweitern Sie die Begrenzungsbox, und führen Sie die Abfrage erneut aus, bis Sie eine Antwort erhalten.
Es gibt keine effektive Möglichkeit, die Entfernung zu finden, außer durch Versuch und Irrtum. Das heißt, mit MySQL können Sie die Datensätze nicht nach Entfernung vom Ziel sortieren und dann die oberste auswählen. Der beste Weg ist, eine Entfernung zu wählen, von der Sie denken, dass die nächste Aufzeichnung darin enthalten ist. Eine zu große Zahl und Sie erhalten zu viele Datensätze, zu kleine Nummern und Sie werden keine erhalten. Nehmen wir an, Sie wählen 40 Einheiten.
%Vor%Jetzt haben Sie alle Datensätze mit Koordinaten in einer 80 x 80 Box, mit Ihrem Ziel als Mittelpunkt (die Box wird ein wenig schief, wenn Sie in Längen- und Breitengrad arbeiten, aber das tut nicht t wirklich wichtig). Verwenden Sie jetzt die Haversine-Gleichung, wenn Sie mit Längen- und Breitengrad arbeiten, oder Pythagoras, wenn es nur kartesisch ist, um den Abstand zwischen dem Ziel und jedem der Punkte zu berechnen.