Muitas das aplica\u00e7\u00f5es nos dias de hoje querem que saibamos o qu\u00e3o perto estamos das coisas:<\/p>\n
Outra maneira de fazer essas perguntas \u00e9 dizer \u201cQuem s\u00e3o meus vizinhos mais pr\u00f3ximos a mim?\u201d. <\/p>\n
Isso mapeia um problema algor\u00edtmico cl\u00e1ssico: encontrar com efici\u00eancia os vizinhos K<\/em> mais pr\u00f3ximos (ou K-NN)<\/a>, onde K \u00e9 uma constante. Por exemplo, a primeira quest\u00e3o seria um problema de 3-NN, j\u00e1 que estamos tentando encontrar os 3 caf\u00e9s mais pr\u00f3ximos.<\/p>\n (Se voc\u00ea estiver interessado em aprender mais sobre os problemas do K-NN em geral, eu recomendo fortemente voc\u00ea tentar resolver isso usando Diagrama de Voronoi<\/a>, uma maravilhosa estrutura de dados desenvolvida no campo da geometria computacional.)<\/p>\n Como podemos usar o PostgreSQL para nos ajudar a encontrar rapidamente nossos vizinhos mais pr\u00f3ximos?<\/p>\n 1. Construindo uma consulta<\/strong><\/p>\n Em um artigo anterior<\/a> foi utilizado um conjunto de dados das pessoas que visitaram cafeterias localizadas na \u00e1rea da cidade de Nova York. A nossa tabela se parece com isso:<\/p>\n Digamos que queremos descobrir os tr\u00eas amigos que estavam mais pr\u00f3ximos da nossa localiza\u00e7\u00e3o em uma determinada data e hora. Para construir essa consulta, precisamos saber:<\/p>\n O PostgreSQL define um operador de dist\u00e2ncia para tipos geom\u00e9tricos que se parecem com este \u201c<->\u201d que, no caso de pontos, calcula a dist\u00e2ncia euclidiana bidimensional<\/a>. Por exemplo:<\/p>\n Por uma quest\u00e3o de integralidade, quanto menor o n\u00famero, mais pr\u00f3ximos os dois pontos s\u00e3o um do outro, o que \u00e9 importante para a pr\u00f3xima etapa do processo.<\/p>\n Se quisermos encontrar os tr\u00eas amigos mais pr\u00f3ximos de n\u00f3s em 1\u00ba de outubro de 2012, entre as 7h e as 9h, podemos criar uma consulta como esta:<\/p>\n A parte \u201cK-vizinho mais pr\u00f3ximo\u201d da consulta pode ser vista em ORDER BY POINT (40.7127263, -74.0066592) <-> geocode LIMIT 3<\/em>, que est\u00e1 dizendo \u201cencontre pela menor dist\u00e2ncia entre a minha localiza\u00e7\u00e3o atual e todas as outras gravadas locais, mas encontre os 3 locais mais pr\u00f3ximos a mim.\u201d<\/p>\n Como isso funciona? <\/p>\n Observando esse plano de consulta, o PostgreSQL determinou que nenhum dos \u00edndices poderia ser usado, e faz uma varredura sequencial completa (paralelizada) na tabela de visitas para encontrar as 3 pessoas mais pr\u00f3ximas. Isso n\u00e3o \u00e9 muito eficiente, mas poder\u00edamos fazer melhor.<\/p>\n 2. KNN-GiST: Encontre vizinhos eficientemente<\/strong><\/p>\n O PostgreSQL 9.1 introduziu o \u00edndice KNN-GiST como uma maneira de acelerar a busca de vizinhos. Ele foi implementado em v\u00e1rios tipos de dados, incluindo pontos e trigramas, e tamb\u00e9m \u00e9 aproveitado pela extens\u00e3o espacial PostGIS.<\/p>\n Voc\u00ea pode usar um \u00edndice KNN-GiST simplesmente criando um \u00edndice GiST em um tipo de dados suportado, que, nesse caso, \u00e9 a coluna geocode:<\/p>\n Para demonstrar seu poder, vamos ver o que acontece se tentarmos encontrar os 3 pontos mais pr\u00f3ximos de um determinado local:<\/p>\n Impressionante! J\u00e1 podemos ver que o \u00edndice KNN-GiST em nosso tipo de ponto nos permite encontrar coisas que est\u00e3o perto de n\u00f3s incrivelmente r\u00e1pido! Agora, vamos tentar executar nossa consulta original para descobrir quem est\u00e1 mais pr\u00f3ximo de n\u00f3s em 1\u00ba de outubro de 2012, entre as 7h e as 9h e ver se esse \u00edndice acelera:<\/p>\n Sem sorte! Neste caso, porque tamb\u00e9m precisamos filtrar nossos dados para o intervalo de data e hora determinado, sen\u00e3o o PostgreSQL n\u00e3o pode tirar proveito do \u00edndice KNN-GiST.<\/p>\n 3. Usando o \u00edndice btree_gist<\/strong><\/p>\n Uma solu\u00e7\u00e3o poss\u00edvel \u00e9 criar um \u00edndice de v\u00e1rias colunas (visited_at, geocode), mas para fazer isso, precisamos configurar a extens\u00e3o \"btree_gist\". Em suma, a extens\u00e3o btree_gist permite que voc\u00ea use os operadores de qualidade padr\u00e3o da \u00e1rvore B com um \u00edndice GiST. Voc\u00ea pode instalar essa extens\u00e3o executando o seguinte:<\/p>\n Antes de tentarmos criar o \u00edndice de v\u00e1rias colunas, primeiro precisamos \"dropar\" o \u00edndice anterior:<\/p>\n Agora, vamos criar o \u00edndice de v\u00e1rias colunas em (visited_at, geocode):<\/p>\n O que acontece com o tempo de execu\u00e7\u00e3o?<\/p>\n Excelente! Parece que agora estamos aproveitando o \u00edndice KNN-GiST.<\/p>\n Uma pergunta que voc\u00ea pode ter: por que n\u00e3o apenas usar um \u00edndice B-tree na coluna visited_at? Essa solu\u00e7\u00e3o pode funcionar se voc\u00ea souber que eliminar\u00e1 a maioria das linhas antes da execu\u00e7\u00e3o. No entanto, se voc\u00ea come\u00e7ar a examinar uma faixa de data e hora maior ou se houver \"muitas\" linhas direcionalmente dentro da faixa de data e hora, ver\u00e1 um aumento significativo de desempenho usando este \u00edndice KNN-GiST de v\u00e1rias colunas.<\/p>\n 4. Conclus\u00e3o<\/strong><\/p>\n Uma das coisas maravilhosas do PostgreSQL \u00e9 que ele est\u00e1 repleto de \"ferramentas ocultas\" que podem ajudar significativamente na acelera\u00e7\u00e3o de suas cargas de trabalho. Quando usado apropriadamente, o \u00edndice KNN-GiST pode acelerar significativamente suas consultas onde voc\u00ea precisa encontrar coisas pr\u00f3ximas, o que \u00e9 uma necessidade comum de aplicativos. Eles n\u00e3o t\u00eam custo: os \u00edndices KNN-GiST s\u00e3o maiores do que os \u00edndices GiST regulares, mas os \u00edndices KNN-GiST de fornecem acelera\u00e7\u00e3o significativamente maiores que o espa\u00e7o adicional e devem estar em sua caixa de ferramentas para qualquer aplica\u00e7\u00e3o que voc\u00ea constr\u00f3i.<\/p>\n Este post foi traduzido e adaptado livremente do post originalmente escrito por Jonathan S. Katz, no Blog Crunchy Data.<\/em><\/p>\n Fonte: Blog Crunchy Data<\/a><\/p>\n","protected":false},"excerpt":{"rendered":" Muitas das aplica\u00e7\u00f5es nos dias de hoje querem que saibamos o qu\u00e3o perto estamos das coisas: Quais s\u00e3o os tr\u00eas caf\u00e9s mais pr\u00f3ximos da minha localiza\u00e7\u00e3o atual? Qual \u00e9 o aeroporto mais pr\u00f3ximo do escrit\u00f3rio? Quais s\u00e3o as duas paradas… Continue Reading →<\/a><\/p>\n","protected":false},"author":275,"featured_media":7582,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24],"tags":[212,230],"class_list":["post-7580","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-gis","tag-postgis","tag-postgresql"],"_links":{"self":[{"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/posts\/7580","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/users\/275"}],"replies":[{"embeddable":true,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/comments?post=7580"}],"version-history":[{"count":13,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/posts\/7580\/revisions"}],"predecessor-version":[{"id":7594,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/posts\/7580\/revisions\/7594"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/media\/7582"}],"wp:attachment":[{"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/media?parent=7580"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/categories?post=7580"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.fernandoquadro.com.br\/html\/wp-json\/wp\/v2\/tags?post=7580"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\r\nCREATE TABLE visits (\r\n id int GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,\r\n visitor UUID NOT NULL,\r\n visited_at timestamptz NOT NULL,\r\n geocode point NOT NULL\r\n);\r\n<\/pre>\n
\n
\r\nSELECT POINT(0,0) <-> POINT(1,1);\r\n\r\n ?column?\r\n-----------------\r\n 1.4142135623731\r\n<\/pre>\n
\r\nSELECT visitor, visited_at, geocode\r\nFROM visits\r\nWHERE\r\n visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'\r\nORDER BY POINT(40.7127263,-74.0066592) <-> geocode\r\nLIMIT 3;\r\n<\/pre>\n
\r\nEXPLAIN ANALYZE SELECT visitor, visited_at, geocode\r\nFROM visits\r\nWHERE\r\n visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'\r\nORDER BY POINT(40.7127263,-74.0066592) <-> geocode\r\nLIMIT 3;\r\n\r\nLimit (cost=53755.18..53755.54 rows=3 width=48) (actual time=120.890..128.781 rows=3 loops=1)\r\n -> Gather Merge (cost=53755.18..53794.45 rows=328 width=48) (actual time=120.889..128.778 rows=3 loops=1)\r\n Workers Planned: 4\r\n Workers Launched: 4\r\n -> Sort (cost=52755.12..52755.32 rows=82 width=48) (actual time=115.623..115.625 rows=2 loops=5)\r\n Sort Key: (('(40.7127263,-74.0066592)'::point <-> geocode))\r\n Sort Method: top-N heapsort Memory: 25kB\r\n Worker 0: Sort Method: top-N heapsort Memory: 25kB\r\n Worker 1: Sort Method: top-N heapsort Memory: 25kB\r\n Worker 2: Sort Method: top-N heapsort Memory: 25kB\r\n Worker 3: Sort Method: quicksort Memory: 25kB\r\n -> Parallel Seq Scan on visits (cost=0.00..52754.06 rows=82 width=48) (actual time=65.256..115.476 rows=50 loops=5)\r\n 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))\r\n Rows Removed by Filter: 805600\r\n\r\nPlanning Time: 0.112 ms\r\nExecution Time: 128.808 ms\r\n<\/pre>\n\r\nCREATE INDEX visits_geocode_gist_idx ON visits USING gist(geocode);\r\nVACUUM ANALYZE visits;\r\n<\/pre>\n
\r\nEXPLAIN ANALYZE SELECT visitor, visited_at, geocode\r\nFROM visits\r\nORDER BY POINT(40.7127263,-74.0066592) <-> geocode\r\nLIMIT 3;\r\n\r\nLimit (cost=0.41..0.73 rows=3 width=48) (actual time=0.237..0.244 rows=3 loops=1)\r\n -> 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)\r\n Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)\r\n\r\nPlanning Time: 0.089 ms\r\nExecution Time: 0.265 ms\r\n<\/pre>\n
\r\nEXPLAIN ANALYZE SELECT visitor, visited_at, geocode\r\nFROM visits\r\nWHERE\r\n visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'\r\nORDER BY POINT(40.7127263,-74.0066592) <-> geocode\r\nLIMIT 3;\r\n\r\n\r\nLimit (cost=0.41..4012.19 rows=3 width=48) (actual time=184.327..184.332 rows=3 loops=1)\r\n -> 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)\r\n Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)\r\n 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))\r\n Rows Removed by Filter: 499207\r\n\r\n\r\nPlanning Time: 0.140 ms\r\nExecution Time: 184.361 ms\r\n<\/pre>\n
\r\nCREATE EXTENSION btree_gist;\r\n<\/pre>\n
\r\nDROP INDEX visits_geocode_gist_idx;\r\n<\/pre>\n
\r\nCREATE INDEX visits_visited_at_geocode_gist_idx ON visits USING gist(visited_at, geocode);\r\nVACUUM ANALYZE visits;\r\n<\/pre>\n
\r\nEXPLAIN ANALYZE SELECT visitor, visited_at, geocode\r\nFROM visits\r\nWHERE\r\n visited_at BETWEEN '2012-10-01 07:00' AND '2012-10-01 09:00'\r\nORDER BY POINT(40.7127263,-74.0066592) <-> geocode\r\nLIMIT 3;\r\nLimit (cost=0.41..12.64 rows=3 width=48) (actual time=0.047..0.049 rows=3 loops=1)\r\n -> 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)\r\n 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))\r\n Order By: (geocode <-> '(40.7127263,-74.0066592)'::point)\r\nPlanning Time: 0.133 ms\r\nExecution Time: 0.068 ms\r\n<\/pre>\n