Esta es mi primera pregunta aquí, ¡así que tengan paciencia conmigo!
Estoy implementando un back-end para una aplicación móvil que tendrá que hacer búsquedas de proximidad para encontrar PDI (puntos de interés) cercanos. Sé que es un escenario muy común y parece muy simple, pero hay muchas maneras diferentes de implementarlo, por lo que me encantaría ver cómo los profesionales más experimentados están implementando estas búsquedas espaciales simples.
Dado que un PDI es solo un PUNTO, no necesitamos cálculos complejos que involucren intersecciones o similares. Es por eso que inicialmente pensé que usar columnas GEOGRAPHY e índices espaciales podría ser excesivo o incluso más lento que otras estrategias. Así que lo reduje a 3 enfoques:
1) columna GEOGRAFÍA + índice espacial
Esta es quizás la solución de facto a este problema. Como tenemos índices espaciales y columnas de geografía, podríamos usarlo y buscar por distancia. Algo como esto.
SELECT * FROM POIs WHERE Loc.STDistance(@radius) <= @distance;
Como tenemos un índice espacial en Loc, debería ser muy rápido.
2) Uso de un "cuadro delimitador" sobre las columnas Latitud y Longitud
Este es el enfoque trivial sin involucrar índices espaciales. Encontramos un cuadro delimitador para nuestro punto y radio, luego simplemente buscamos en las columnas Latitud y Longitud. Si ambos están indexados, esta búsqueda debería ser muy rápida. Tendremos que aplicar la función de distancia para filtrar algunos valores fuera del "círculo" pero dentro del cuadro delimitador. Pero eso debería ser bastante rápido. Esta idea se explica mejor aquí: http://www.movable-type.co.uk/scripts/latlong-db.html
Algo como esto:
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) Use un GEOHASH integral almacenado en una columna indexada
Este enfoque es muy interesante y es algo que la gente usa junto con los conjuntos ordenados de REDIS para realizar búsquedas de proximidad. El principio se puede transponer a SQL Server mediante el uso de una columna indexada que almacena el GEOHASH integral.
Tengo esta idea de Ardb: https://github.com/yinqiwen/ardb/wiki/Spatial-Index
También se explica de una manera más amigable aquí: ¿ Usa geohash para búsquedas de proximidad?
En otras palabras, uno calcularía un GEOHASH con una profundidad de bits correspondiente al radio de la búsqueda que se desea, luego calcularía 8 geohashes de vecinos y finalmente enviaría una búsqueda usando estos geohashs como cuadros delimitadores en la columna indexada. Estos serán 9 ENTRE operadores en la cláusula WHERE del SQL ... Los resultados tendrán que filtrarse debido a la devolución de un POI espurio.
Pero parece que esto será más lento que el método 2, ya que la cláusula where será más compleja, aunque solo consultará en una sola columna en lugar de dos.
¿Alguien tiene alguna experiencia para compartir sobre esto? ¿Hay un enfoque mejor / correcto para esto?
fuente
Respuestas:
La razón por la que las bases de datos implementan índices R-tree para espacial es porque son más rápidas que las geohashes o búsquedas en índices x e y separados. El problema con las geohashes es que debe buscar 9 cuadrantes, no solo 1, para realizar búsquedas de tipo de proximidad; consulte las limitaciones de geohash . Son útiles en bases de datos que carecen de árboles R, para permitir la expresión de un objeto con un rango 2D, en una dimensión, que luego puede indexarse con un árbol B. Tener índices separados (o compuestos) en x e y también será más lento, ya que necesita escanear más del índice para centrarse en su área de interés, mientras que con los árboles R, la búsqueda de índice está en el cuadro delimitador.
El uso variará, pero no es excesivo usar espacial solo porque solo tiene puntos. No pierde nada al usar un tipo de geometría y potencialmente gana mucho (no solo en términos de velocidad), sino en pruebas futuras. ¿Qué sucede si desea agregar almacenamiento intermedio o intersección de polígono en una fecha posterior? En última instancia, la única forma de saber es probar su caso de uso, pero mi 2c es el enfoque de uso 1.
fuente