Muitas das aplicações nos dias de hoje querem que saibamos o quão perto estamos das coisas:

  • Quais são os três cafés mais próximos da minha localização atual?
  • Qual é o aeroporto mais próximo do escritório?
  • Quais são as duas paradas de metro mais próximas do restaurante?

Outra maneira de fazer essas perguntas é dizer “Quem são meus vizinhos mais próximos a mim?”.

Isso mapeia um problema algorítmico clássico: encontrar com eficiência os vizinhos K mais próximos (ou K-NN), onde K é uma constante. Por exemplo, a primeira questão seria um problema de 3-NN, já que estamos tentando encontrar os 3 cafés mais próximos.

(Se você estiver interessado em aprender mais sobre os problemas do K-NN em geral, eu recomendo fortemente você tentar resolver isso usando Diagrama de Voronoi, uma maravilhosa estrutura de dados desenvolvida no campo da geometria computacional.)

Como podemos usar o PostgreSQL para nos ajudar a encontrar rapidamente nossos vizinhos mais próximos?

1. Construindo uma consulta

Em um artigo anterior foi utilizado um conjunto de dados das pessoas que visitaram cafeterias localizadas na área da cidade de Nova York. A nossa tabela se parece com isso:

CREATE TABLE visits (
    id int GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
    visitor UUID NOT NULL,
    visited_at timestamptz NOT NULL,
    geocode point NOT NULL
);

Digamos que queremos descobrir os três amigos que estavam mais próximos da nossa localização em uma determinada data e hora. Para construir essa consulta, precisamos saber:

  • O intervalo de data e hora da consulta
  • A distância entre a nossa localização e a dos nossos amigos

O PostgreSQL define um operador de distância para tipos geométricos que se parecem com este “<->” que, no caso de pontos, calcula a distância euclidiana bidimensional. Por exemplo:

SELECT POINT(0,0) <-> POINT(1,1);

    ?column?
-----------------
 1.4142135623731

Por uma questão de integralidade, quanto menor o número, mais próximos os dois pontos são um do outro, o que é importante para a próxima etapa do processo.

Se quisermos encontrar os três amigos mais próximos de nós em 1º de outubro de 2012, entre as 7h e as 9h, podemos criar uma consulta como esta:

SELECT visitor, visited_at, geocode
FROM visits
WHERE
    visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'
ORDER BY POINT(40.7127263,-74.0066592) <-> geocode
LIMIT 3;

A parte “K-vizinho mais próximo” da consulta pode ser vista em ORDER BY POINT (40.7127263, -74.0066592) <-> geocode LIMIT 3, que está dizendo “encontre pela menor distância entre a minha localização atual e todas as outras gravadas locais, mas encontre os 3 locais mais próximos a mim.”

Como isso funciona? 

EXPLAIN ANALYZE SELECT visitor, visited_at, geocode
FROM visits
WHERE
    visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'
ORDER BY POINT(40.7127263,-74.0066592) <-> geocode
LIMIT 3;

Limit (cost=53755.18..53755.54 rows=3 width=48) (actual time=120.890..128.781 rows=3 loops=1)
   -> Gather Merge (cost=53755.18..53794.45 rows=328 width=48) (actual time=120.889..128.778 rows=3 loops=1)
        Workers Planned: 4
        Workers Launched: 4
        -> Sort (cost=52755.12..52755.32 rows=82 width=48) (actual time=115.623..115.625 rows=2 loops=5)
             Sort Key: (('(40.7127263,-74.0066592)'::point <-> geocode))
             Sort Method: top-N heapsort Memory: 25kB
             Worker 0: Sort Method: top-N heapsort Memory: 25kB
             Worker 1: Sort Method: top-N heapsort Memory: 25kB
             Worker 2: Sort Method: top-N heapsort Memory: 25kB
             Worker 3: Sort Method: quicksort Memory: 25kB
             -> Parallel Seq Scan on visits (cost=0.00..52754.06 rows=82 width=48) (actual time=65.256..115.476 rows=50 loops=5)
                Filter: ((visited_at >= '2012-10-01 07:00:00-04'::timestamp with time zone) AND (visited_at <= '2012-10-01 09:00:00-04'::timestamp with time zone))
                Rows Removed by Filter: 805600

Planning Time: 0.112 ms
Execution Time: 128.808 ms

Observando esse plano de consulta, o PostgreSQL determinou que nenhum dos índices poderia ser usado, e faz uma varredura sequencial completa (paralelizada) na tabela de visitas para encontrar as 3 pessoas mais próximas. Isso não é muito eficiente, mas poderíamos fazer melhor.

2. KNN-GiST: Encontre vizinhos eficientemente

O PostgreSQL 9.1 introduziu o índice KNN-GiST como uma maneira de acelerar a busca de vizinhos. Ele foi implementado em vários tipos de dados, incluindo pontos e trigramas, e também é aproveitado pela extensão espacial PostGIS.

Você pode usar um índice KNN-GiST simplesmente criando um índice GiST em um tipo de dados suportado, que, nesse caso, é a coluna geocode:

CREATE INDEX visits_geocode_gist_idx ON visits USING gist(geocode);
VACUUM ANALYZE visits;

Para demonstrar seu poder, vamos ver o que acontece se tentarmos encontrar os 3 pontos mais próximos de um determinado local:

EXPLAIN ANALYZE SELECT visitor, visited_at, geocode
FROM visits
ORDER BY POINT(40.7127263,-74.0066592) <-> geocode
LIMIT 3;

Limit (cost=0.41..0.73 rows=3 width=48) (actual time=0.237..0.244 rows=3 loops=1)
  -> Index Scan using visits_geocode_gist_idx on visits (cost=0.41..423200.97 rows=4028228 width=48) (actual time=0.236..0.242 rows=3 loops=1)
      Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)

Planning Time: 0.089 ms
Execution Time: 0.265 ms

Impressionante! Já podemos ver que o índice KNN-GiST em nosso tipo de ponto nos permite encontrar coisas que estão perto de nós incrivelmente rápido! Agora, vamos tentar executar nossa consulta original para descobrir quem está mais próximo de nós em 1º de outubro de 2012, entre as 7h e as 9h e ver se esse índice acelera:

EXPLAIN ANALYZE SELECT visitor, visited_at, geocode
FROM visits
WHERE
    visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'
ORDER BY POINT(40.7127263,-74.0066592) <-> geocode
LIMIT 3;


Limit (cost=0.41..4012.19 rows=3 width=48) (actual time=184.327..184.332 rows=3 loops=1)
  -> Index Scan using visits_geocode_gist_idx on visits (cost=0.41..433272.35 rows=324 width=48) (actual time=184.326..184.330 rows=3 loops=1)
      Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)
      Filter: ((visited_at >= '2012-10-01 07:00:00-04'::timestamp with time zone) AND (visited_at <= '2012-10-01 09:00:00-04'::timestamp with time zone))
      Rows Removed by Filter: 499207


Planning Time: 0.140 ms
Execution Time: 184.361 ms

Sem sorte! Neste caso, porque também precisamos filtrar nossos dados para o intervalo de data e hora determinado, senão o PostgreSQL não pode tirar proveito do índice KNN-GiST.

3. Usando o índice btree_gist

Uma solução possível é criar um índice de várias colunas (visited_at, geocode), mas para fazer isso, precisamos configurar a extensão "btree_gist". Em suma, a extensão btree_gist permite que você use os operadores de qualidade padrão da árvore B com um índice GiST. Você pode instalar essa extensão executando o seguinte:

CREATE EXTENSION btree_gist;

Antes de tentarmos criar o índice de várias colunas, primeiro precisamos "dropar" o índice anterior:

DROP INDEX visits_geocode_gist_idx;

Agora, vamos criar o índice de várias colunas em (visited_at, geocode):

CREATE INDEX visits_visited_at_geocode_gist_idx ON visits USING gist(visited_at, geocode);
VACUUM ANALYZE visits;

O que acontece com o tempo de execução?

EXPLAIN ANALYZE SELECT visitor, visited_at, geocode
FROM visits
WHERE
    visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'
ORDER BY POINT(40.7127263,-74.0066592) <-> geocode
LIMIT 3;
Limit (cost=0.41..12.64 rows=3 width=48) (actual time=0.047..0.049 rows=3 loops=1)
  -> Index Scan using visits_visited_at_geocode_gist_idx on visits (cost=0.41..1348.69 rows=331 width=48) (actual time=0.046..0.048 rows=3 loops=1)
      Index Cond: ((visited_at >= '2012-10-01 07:00:00-04'::timestamp with time zone) AND (visited_at <= '2012-10-01 09:00:00-04'::timestamp with time zone))
      Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)
Planning Time: 0.133 ms
Execution Time: 0.068 ms

Excelente! Parece que agora estamos aproveitando o índice KNN-GiST.

Uma pergunta que você pode ter: por que não apenas usar um índice B-tree na coluna visited_at? Essa solução pode funcionar se você souber que eliminará a maioria das linhas antes da execução. No entanto, se você começar a examinar uma faixa de data e hora maior ou se houver "muitas" linhas direcionalmente dentro da faixa de data e hora, verá um aumento significativo de desempenho usando este índice KNN-GiST de várias colunas.

4. Conclusão

Uma das coisas maravilhosas do PostgreSQL é que ele está repleto de "ferramentas ocultas" que podem ajudar significativamente na aceleração de suas cargas de trabalho. Quando usado apropriadamente, o índice KNN-GiST pode acelerar significativamente suas consultas onde você precisa encontrar coisas próximas, o que é uma necessidade comum de aplicativos. Eles não têm custo: os índices KNN-GiST são maiores do que os índices GiST regulares, mas os índices KNN-GiST de fornecem aceleração significativamente maiores que o espaço adicional e devem estar em sua caixa de ferramentas para qualquer aplicação que você constrói.

Este post foi traduzido e adaptado livremente do post originalmente escrito por Jonathan S. Katz, no Blog Crunchy Data.

Fonte: Blog Crunchy Data