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?
la source
Réponses:
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.
la source