Estratégia mais rápida para pesquisas por proximidade no SQL Server 2012

8

Esta é a minha primeira pergunta aqui, então tenha paciência comigo!

Estou implementando um back-end para um aplicativo móvel que terá que fazer pesquisas de proximidade para encontrar POIs próximos (pontos de interesse). Sei que é um cenário muito comum e parece muito simples, mas há muitas maneiras diferentes de implementá-lo. Por isso, gostaria de ver como profissionais mais experientes estão implementando essas pesquisas espaciais simples.

Como um POI é apenas um PONTO, não precisamos de cálculos complexos envolvendo cruzamentos ou similares. Por isso, pensei inicialmente que o uso de colunas e índices espaciais GEOGRAPHY poderia ser um exagero ou até mais lento do que outras estratégias. Então, reduzi-o a três abordagens:

1) Coluna GEOGRAFIA + Índice Espacial

Essa talvez seja a solução de fato para esse problema. Como temos índices espaciais e colunas geográficas, podemos apenas usá-lo e pesquisar por distância. Algo assim.

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

Como temos um índice espacial no Loc, deve ser muito rápido.

2) Usando uma "caixa delimitadora" sobre as colunas Latitude e Longitude

Essa é a abordagem trivial sem envolver índices espaciais. Encontramos uma caixa delimitadora para nosso ponto e raio e, em seguida, basta pesquisar nas colunas Latitude e Longitude. Se ambos estiverem indexados, essa pesquisa deverá ser muito rápida. Teremos que aplicar a função de distância para filtrar alguns valores fora do "círculo", mas dentro da caixa delimitadora. Mas isso deve ser bem rápido. Esta ideia é melhor explicada aqui: http://www.movable-type.co.uk/scripts/latlong-db.html

Algo assim:

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 um GEOHASH integral armazenado em uma coluna indexada

Essa abordagem é muito interessante e é algo que as pessoas estão usando em conjunto com os conjuntos solicitados pelo REDIS para fazer pesquisas de proximidade. O princípio pode ser transposto para o SQL Server usando uma coluna indexada que armazena o GEOHASH integral.

Eu tenho essa ideia de Ardb: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Também é explicado de uma maneira um pouco mais amigável aqui: Usando o geohash para pesquisas por proximidade?

Em outras palavras, calcularíamos um GEOHASH com uma profundidade de bits correspondente ao raio da pesquisa que desejássemos, depois calcularíamos 8 geohashes nos arredores e finalmente enviaríamos uma pesquisa usando essas geohashs como caixas delimitadoras na coluna indexada. Serão 9 ENTRE operadores na cláusula WHERE do SQL ... Os resultados terão que ser filtrados devido ao retorno de um POI falso.

Mas parece que isso será mais lento que o método 2, pois a cláusula where será mais complexa, embora apenas faça uma consulta sobre uma única coluna em vez de duas.

Alguém tem alguma experiência para compartilhar sobre isso? Existe uma abordagem melhor / correta para isso?

sql-server spatial-index proximity geohash Loudenvier
fonte
Realmente é uma resposta 'Depende'. A quantidade de dados que você está consultando é definitivamente um fator. Como você está usando o SQL Server 2012, a consulta ao banco de dados deve ser bastante rápida. No entanto, certifique-se de seguir as regras msdn.microsoft.com/en-us/library/ff929109.aspx ou o índice espacial não será usado.
MickyT
@MickyT A consulta do vizinho mais próximo é otimizada de uma maneira diferente? Eu não tenho uma ordem por cláusula, nem uma cláusula TOP, pois estarei recebendo todos os pontos dentro do raio. Criei um banco de dados de teste com as colunas Lat, Long e Geometry, adicionei 4 milhões de registros e a pesquisa baseada em índice espacial com STDistance é instantânea, mas as colunas Lat e Long com caixa delimitadora também são muito rápidas. Vou tentar adicionar bilhões de pontos para ver se um funciona melhor que o outro. Caso contrário, continuarei com o índice espacial!
Loudenvier
Parece que sua consulta está usando o índice espacial. Eu não fiz muitos testes nesse particular, lembre-se de ler que havia condições. Como outra opção, se você quiser fazer pesquisas em caixas delimitadoras, tente o Filtro. msdn.microsoft.com/pt-br/library/cc645883.aspx
MickyT
O motivo pelo qual os bancos de dados implementam índices R-tree para espacial é porque eles são mais rápidos que geohashes ou pesquisas em índices x e y separados. O uso varia, mas não é um exagero usar o espaço apenas porque você só tem pontos. Você não perde nada usando um tipo de geometria e potencialmente ganha muito (não apenas em termos de velocidade), mas em provas futuras. E se você quiser adicionar buffer ou interseção de polígono posteriormente? Em última análise, a única maneira de saber é testar seu caso de uso, mas meu 2c é a abordagem utilização 1.
John Powell
@ JohnBarça Fiz mais alguns testes adicionando 50.000.000 de pontos e, após o cálculo do plano de consultas, as consultas usando o índice espacial ainda são quase instantâneas, enquanto as outras abordagens levam alguns segundos para serem concluídas. Farei mais alguns testes: como minhas consultas serão executadas em áreas urbanas, adicionarei um filtro de região / bairro / distrito / cidade (os locais já foram geocodificados anteriormente). Isso pode ou não melhorar a velocidade da pesquisa. Mas agora que tenho certeza de que o índice espacial tem esse desempenho com 50000000 pontos, tentarei otimizar apenas se houver necessidade real.
Loudenvier 5/10

Respostas:

2

O motivo pelo qual os bancos de dados implementam índices R-tree para espacial é porque eles são mais rápidos que geohashes ou pesquisas em índices x e y separados. O problema das geohashes é que você precisa pesquisar 9 quadrantes, e não apenas 1, para fazer pesquisas por tipo de proximidade - consulte as limitações de geohash . Eles são úteis em bancos de dados que não possuem árvores R, para permitir a expressão de um objeto com um intervalo 2D, em uma dimensão, que pode ser indexada com uma árvore B. Ter índices separados (ou compostos) em xey também será mais lento, pois você precisa digitalizar mais do índice para zerar sua área de interesse, enquanto que com as árvores R, a pesquisa de índice está na caixa delimitadora.

O uso varia, mas não é um exagero usar o espaço apenas porque você só tem pontos. Você não perde nada usando um tipo de geometria e potencialmente ganha muito (não apenas em termos de velocidade), mas em provas futuras. E se você quiser adicionar buffer ou interseção de polígono posteriormente? Por fim, a única maneira de saber é testar seu caso de uso, mas meu 2c é a abordagem de uso 1.

John Powell
fonte