Schnellste Strategie für Proximity-Suchen in SQL Server 2012

8

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?

Loudenvier
quelle
Wirklich, es ist eine "Es kommt darauf an" Antwort. Die Datenmenge, gegen die Sie abfragen, ist definitiv ein Faktor. Da Sie SQL Server 2012 verwenden, sollte die Datenbankabfrage recht schnell sein. Stellen Sie jedoch sicher, dass Sie die Regeln msdn.microsoft.com/en-us/library/ff929109.aspx befolgen. Andernfalls wird der räumliche Index nicht verwendet.
MickyT
@MickyT Wird die Abfrage für den nächsten Nachbarn auf andere Weise optimiert? Ich habe weder eine Order-by-Klausel noch eine TOP-Klausel, da ich alle Punkte innerhalb des Radius erhalte. Ich habe eine Testdatenbank mit Lat, Long und einer Geometry-Spalte erstellt, 4 Millionen Datensätze hinzugefügt und die auf räumlichen Indizes basierende Suche mit STDistance erfolgt sofort, aber die Lat- und Long-Spalten mit Begrenzungsrahmen sind auch sehr schnell. Ich werde versuchen, Milliarden von Punkten hinzuzufügen, um zu sehen, ob einer besser abschneidet als der andere. Wenn nicht, bleibe ich beim räumlichen Index!
Loudenvier
Es hört sich so an, als würde Ihre Abfrage den räumlichen Index verwenden. Ich habe nicht viele Tests an diesem bestimmten durchgeführt. Denken Sie daran, dass es Bedingungen gab. Wenn Sie eine Begrenzungsrahmensuche durchführen möchten, können Sie auch Filter ausprobieren. msdn.microsoft.com/en-us/library/cc645883.aspx
MickyT
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. 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.
John Powell
@ JohnBarça Ich habe einige weitere Tests durchgeführt, bei denen 50.000.000 Punkte hinzugefügt wurden. Nach der Berechnung des Abfrageplans sind Abfragen unter Verwendung des räumlichen Index immer noch fast augenblicklich, während die anderen Ansätze einige Sekunden dauern. Ich werde noch einige Tests durchführen: Da meine Abfragen in städtischen Gebieten ausgeführt werden, füge ich einen Filter für Region / Nachbarschaft / Bezirk / Stadt hinzu (die Standorte wurden zuvor umgekehrt geokodiert). Dies kann die Suchgeschwindigkeit verbessern oder nicht. Aber jetzt, da ich sicher bin, dass der räumliche Index mit 50000000 Punkten so gut abschneidet, werde ich nur versuchen, ihn zu optimieren, wenn tatsächlich Bedarf besteht.
Loudenvier

Antworten:

2

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.

John Powell
quelle