Stratégie la plus rapide pour les recherches de proximité dans SQL Server 2012

8

Ceci est ma toute première question ici, alors restez avec moi!

J'implémente un back-end pour une application mobile qui devra faire des recherches de proximité pour trouver les POI à proximité (points d'intérêt). Je sais que c'est un scénario très courant et semble très simple, mais il existe de nombreuses façons différentes de le mettre en œuvre, donc j'aimerais voir comment des professionnels plus expérimentés mettent en œuvre ces recherches spatiales simples.

Puisqu'un POI n'est qu'un POINT, nous n'avons pas besoin de calculs complexes impliquant des intersections ou similaires. C'est pourquoi j'ai d'abord pensé que l'utilisation des colonnes et des index spatiaux GEOGRAPHIE pouvait être exagéré ou même plus lent que d'autres stratégies. Je l'ai donc réduit à 3 approches:

1) Colonne GEOGRAPHIE + Index Spatial

C'est peut-être la solution de facto à ce problème. Comme nous avons des index spatiaux et des colonnes géographiques, nous pourrions simplement l'utiliser et rechercher par distance. Quelque chose comme ça.

SELECT * FROM POIs WHERE Loc.STDistance(@radius) <= @distance;

Puisque nous avons un indice spatial sur Loc, il devrait être très rapide.

2) Utilisation d'une "boîte englobante" sur les colonnes Latitude et Longitude

C'est l'approche triviale sans impliquer d'index spatiaux. Nous trouvons un cadre de délimitation pour notre point et notre rayon, puis nous recherchons simplement dans les colonnes Latitude et Longitude. Si les deux sont indexés, cette recherche devrait être très rapide. Nous devrons appliquer la fonction de distance pour filtrer certaines valeurs en dehors du "cercle" mais avec le cadre de délimitation. Mais cela devrait être assez rapide. Cette idée est mieux expliquée ici: http://www.movable-type.co.uk/scripts/latlong-db.html

Quelque chose comme ça:

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) Utilisez un GEOHASH intégré stocké sur une colonne indexée

Cette approche est très intéressante et c'est quelque chose que les gens utilisent avec des ensembles ordonnés REDIS pour effectuer des recherches de proximité. Le principe peut être transposé à SQL Server en utilisant une colonne indexée qui stocke l'intégralité de GEOHASH.

J'ai cette idée d'Ardb: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

C'est aussi expliqué de manière un peu plus conviviale ici: Utiliser geohash pour les recherches de proximité?

En d'autres termes, on calculerait un GEOHASH avec une profondeur de bits correspondant au rayon de la recherche que l'on désire, puis calculer 8 géohashs voisins et enfin soumettre une recherche en utilisant ces geohashs comme boîtes de délimitation sur la colonne indexée. Ce sera 9 opérateurs BETWEEN sur la clause WHERE du SQL ... Les résultats devront être filtrés en raison du retour de POI parasites.

Mais il semble que cela sera plus lent que la méthode 2 car la clause where sera plus complexe bien qu'elle ne questionne que sur une seule colonne au lieu de deux.

Quelqu'un at-il une expérience à partager à ce sujet? Existe-t-il une approche meilleure / correcte à cela?

Loudenvier
la source
C'est vraiment une réponse «ça dépend». La quantité de données que vous interrogez est certainement un facteur. Étant donné que vous utilisez SQL Server 2012, la requête de base de données devrait être assez rapide. Assurez-vous cependant de suivre les règles msdn.microsoft.com/en-us/library/ff929109.aspx sinon l'index spatial ne sera pas utilisé.
MickyT
@MickyT La requête du plus proche voisin est-elle optimisée d'une manière différente? Je n'ai pas de clause order by, ni de clause TOP, car j'obtiendrai tous les points dans le rayon. J'ai créé une base de données de test avec Lat, Long et une colonne Geometry, y ajouté 4 millions d'enregistrements, et la recherche basée sur l'index spatial avec STDistance est instantanée, mais les colonnes Lat et Long avec boîte englobante sont également très rapides. J'essaierai d'ajouter des milliards de points pour voir si l'un fonctionne mieux que l'autre. Sinon, je m'en tiendrai à l'index spatial!
Loudenvier
Il semble que votre requête utilise l'index spatial. Je n'ai pas fait beaucoup de tests sur celui-ci, rappelez-vous simplement qu'il y avait des conditions. Comme autre option, si vous souhaitez effectuer des recherches de zone de délimitation, vous pouvez essayer de filtrer. msdn.microsoft.com/en-us/library/cc645883.aspx
MickyT
La raison pour laquelle les bases de données implémentent les index R-tree pour l'espace est parce qu'elles sont plus rapides que les géohash ou les recherches sur des index x et y distincts. L'utilisation variera, mais il n'est pas exagéré d'utiliser l'espace simplement parce que vous n'avez que des points. Vous ne perdez rien en utilisant un type de géométrie et gagnez potentiellement beaucoup (pas seulement en termes de vitesse), mais dans l'épreuvage futur. Que faire si vous souhaitez ajouter un tampon ou une intersection de polygones à une date ultérieure? En fin de compte, la seule façon de savoir est de tester votre cas d'utilisation, mais mon 2c est l'utilisation de l'approche 1.
John Powell
@ JohnBarça J'ai fait plus de tests en ajoutant 50 000 000 de points et après le calcul du plan de requête, les requêtes utilisant l'index spatial sont toujours presque instantanées, tandis que les autres approches prennent quelques secondes pour terminer. Je ferai quelques tests supplémentaires: comme mes requêtes s'exécuteront dans les zones urbaines, j'ajouterai un filtre région / quartier / quartier / ville (les emplacements auront été précédemment géocodés inversement). Cela peut ou non améliorer la vitesse de recherche. Mais maintenant que je suis sûr que l'indice spatial fonctionne aussi bien avec 50000000 points, je n'essaierai d'optimiser que s'il y a un réel besoin.
Loudenvier

Réponses:

2

La raison pour laquelle les bases de données implémentent les index R-tree pour l'espace est parce qu'elles sont plus rapides que les géohash ou les recherches sur des index x et y distincts. Le problème avec les geohashes, c'est que vous devez rechercher 9 quadrants, pas seulement 1, pour faire des recherches de type proximité - voir les limitations de geohash . Ils sont utiles dans les bases de données qui manquent d'arbres R, pour permettre l'expression d'un objet avec une plage 2D, dans une dimension, qui peut ensuite être indexé avec un arbre B. Avoir des index séparés (ou composés) sur x et y sera également plus lent, car vous devez numériser davantage d'index à zéro dans votre zone d'intérêt, tandis qu'avec les arbres R, la recherche d'index est dans la zone de délimitation.

L'utilisation variera, mais il n'est pas exagéré d'utiliser l'espace simplement parce que vous n'avez que des points. Vous ne perdez rien en utilisant un type de géométrie et gagnez potentiellement beaucoup (pas seulement en termes de vitesse), mais dans l'épreuvage futur. Que faire si vous souhaitez ajouter un tampon ou une intersection de polygones à une date ultérieure? En fin de compte, la seule façon de savoir est de tester votre cas d'utilisation, mais mon 2c est l'approche d'utilisation 1.

John Powell
la source