Dies ist meine allererste Frage hier, also nimm sie mit!
Ich implementiere ein Back-End für eine mobile App, die Proximity-Suchen durchführen muss, um POIs in der Nähe zu finden (Punkte von Interesse). Ich weiß, dass es ein sehr häufiges Szenario ist und sehr einfach aussieht, aber es gibt viele verschiedene Möglichkeiten, es zu implementieren. Daher würde ich gerne sehen, wie erfahrene Fachleute diese einfachen räumlichen Suchen implementieren.
Da ein POI nur ein PUNKT ist, benötigen wir keine komplexen Berechnungen mit Schnittpunkten oder dergleichen. Aus diesem Grund dachte ich anfangs, dass die Verwendung von GEOGRAPHY-Spalten und räumlichen Indizes übertrieben oder sogar langsamer sein könnte als andere Strategien. Also habe ich es auf 3 Ansätze eingegrenzt:
1) Spalte GEOGRAPHIE + Raumindex
Dies ist vielleicht die tatsächliche Lösung für dieses Problem. Da wir räumliche Indizes und geografische Spalten haben, können wir diese einfach verwenden und nach Entfernung suchen. Etwas wie das.
SELECT * FROM POIs WHERE Loc.STDistance(@radius) <= @distance;
Da wir einen räumlichen Index für Loc haben, sollte dieser sehr schnell sein.
2) Verwenden eines "Begrenzungsrahmens" über Breiten- und Längengradspalten
Dies ist der triviale Ansatz ohne räumliche Indizes. Wir finden einen Begrenzungsrahmen für unseren Punkt und Radius und suchen dann einfach in den Spalten Latitude und Longitude. Wenn beide indiziert sind, sollte diese Suche sehr schnell sein. Wir müssen die Distanzfunktion anwenden, um einige Werte außerhalb des "Kreises" herauszufiltern, jedoch ohne Begrenzungsrahmen. Das sollte aber ziemlich schnell gehen. Diese Idee wird hier besser erklärt: http://www.movable-type.co.uk/scripts/latlong-db.html
Etwas wie das:
DECLARE @lat float
DECLARE @lon float
SET @lat = -23.001029
SET @lon = -43.328422
DECLARE @maxLat float, @minLat float, @maxlon float, @minLon float
DECLARE @R float
DECLARE @distance FLOAT = 100 -- A distance in meters
SET @R = 6378137 -- Earth
SET @maxLat = @lat + DEGREES(@distance/@R)
SET @minLat = @lat - DEGREES(@distance/@R)
SET @maxLon = @lon + DEGREES((@distance/@R/COS(RADIANS(@lat))))
SET @minLon = @lon - DEGREES((@distance/@R/COS(RADIANS(@lat))))
SELECT * from POIs
WHERE
Lat Between @minLat And @maxLat
And Lng Between @minLon And @maxLon
3) Verwenden Sie einen integralen GEOHASH, der in einer indizierten Spalte gespeichert ist
Dieser Ansatz ist sehr interessant und wird von Menschen zusammen mit von REDIS bestellten Sets verwendet, um Näherungssuchen durchzuführen. Das Prinzip kann mithilfe einer indizierten Spalte, in der das integrale GEOHASH gespeichert ist, auf SQL Server übertragen werden.
Ich habe diese Idee von Ardb: https://github.com/yinqiwen/ardb/wiki/Spatial-Index
Hier wird es auch etwas freundlicher erklärt: Geohash für Proximity-Suchen verwenden?
Mit anderen Worten, man würde einen GEOHASH mit einer Bittiefe berechnen, die dem gewünschten Radius der Suche entspricht, dann 8 Geohashes von Nachbarn berechnen und schließlich eine Suche unter Verwendung dieser Geohashs als Begrenzungsrahmen in der indizierten Spalte einreichen. Dies sind 9 ZWISCHEN Operatoren in der WHERE-Klausel des SQL ... Die Ergebnisse müssen herausgefiltert werden, da ein falscher POI zurückgegeben wird.
Es sieht jedoch so aus, als wäre dies langsamer als Methode 2, da die where-Klausel komplexer ist, obwohl nur eine einzelne Spalte anstelle von zwei abgefragt wird.
Hat jemand Erfahrung, um dies zu teilen? Gibt es einen besseren / richtigen Ansatz dafür?
quelle
Antworten:
Der Grund, warum Datenbanken R-Tree-Indizes für räumliche Indizes implementieren, liegt darin, dass sie schneller sind als Geohashes oder Suchen in separaten x- und y-Indizes. Das Problem bei Geohashes besteht darin, dass Sie 9 Quadranten durchsuchen müssen, nicht nur 1, um Proximity-Typ-Suchen durchzuführen - siehe Geohash-Einschränkungen . Sie sind in Datenbanken ohne R-Bäume nützlich, um den Ausdruck eines Objekts mit einem 2D-Bereich in einer Dimension zu ermöglichen, das dann mit einem B-Baum indiziert werden kann. Separate (oder zusammengesetzte) Indizes für x und y sind ebenfalls langsamer, da Sie mehr Index in Ihrem Interessenbereich auf Null scannen müssen, während sich bei R-Bäumen die Indexsuche im Begrenzungsrahmen befindet.
Die Verwendung variiert, aber es ist nicht übertrieben, räumlich zu verwenden, nur weil Sie nur Punkte haben. Sie verlieren nichts, wenn Sie einen Geometrietyp verwenden, und gewinnen möglicherweise viel (nicht nur in Bezug auf die Geschwindigkeit), sondern auch bei der zukünftigen Prüfung. Was ist, wenn Sie zu einem späteren Zeitpunkt Pufferung oder Polygonschnitt hinzufügen möchten? Letztendlich ist der einzige Weg zu wissen, Ihren Anwendungsfall zu testen, aber mein 2c ist Anwendungsansatz 1.
quelle