Como otimizar uma consulta Ponto no polígono para milhões de pontos quando a maioria dos pontos está dentro do polígono?

8

Eu tenho 150 milhões de pontos em uma tabela de pontos e gostaria de encontrar os poucos pontos fora de uma dada geometria de polígono. Eu sei que 99,9% dos pontos estão dentro da geometria do polígono. Estou interessado em encontrar os poucos pontos que estão fora do polígono.

Minha melhor consulta atual usando tabelas PostGIS indexadas leva cerca de 30 minutos para ser concluída. Existe uma maneira de otimizar a consulta a seguir sabendo que a maioria dos pontos está dentro do polígono (borda)?

SELECT COUNT(*) 
FROM italy_points pt
JOIN borders poly
ON ST_WITHIN (pt.the_geom, poly.geom)
WHERE poly.iso3 = 'ITA';

O polígono é basicamente a fronteira administrativa da Itália. Vértices - 405.000. Peças - 510. O envelope é muito maior que o polígono (o polígono cobre 24% do envelope)

postgis postgresql Prithvi
fonte
2
Agradar Editar a questão de dar uma indicação da complexidade do polígono - Quantas peças? Quantos vértices? Qual porcentagem do envelope do polígono está dentro do polígono. Descobri que o particionamento de polígonos complexos pode melhorar a avaliação de polígonos point-in , mas você precisa lidar com a condição em que um único ponto cruza mais de uma partição.
Vince
A primeira otimização para esse tipo de operação é geralmente verificar se o ponto está na caixa delimitadora do polígono antes de prosseguir para a operação completa do ponto no polígono. O point-in-box é uma operação muito eficiente em comparação.
WhiteboxDev
@Vince Se duplicatas são possíveis (o único caso em que penso é quando cai exatamente na borda de duas partições), isso é trivialmente tratado no PostGIS. Você precisa apenas GROUP BYda chave primária dos pontos. (PostgreSQL convenientemente permite fazer referência a quaisquer colunas na SELECTcláusula que vêm de uma tabela onde a chave primária está incluída na GROUP BYcláusula.)
jpmc26
O @WhiteboxDev ST_Withinjá faz uma verificação de caixa de limite que permite o uso do índice. (Quase todas as funções do PostGIS incluem essa otimização.) Se ainda estiver lento, então claramente o problema está na complexidade do polígono.
jpmc26
@ jpmc26 Certamente, mas a consulta SQL também precisaria ser modificada para ser usada ST_Intersects, pois ST_Withinnão corresponderia com segurança às condições de limite interno.
Vince

Respostas:

10

Use ST_Subdivide para cortar seu polígono em polígonos menores, salve-os em uma tabela e crie um índice espacial. Em seguida, faça sua consulta nos polígonos em grade.

Sem isso, a indexação espacial não oferece nenhuma vantagem no seu caso (apenas 1 polígono de interesse).

Mesa
fonte
4
Além do comentário ST_Subdivide (), você pode descobrir que o uso de menos do que o número padrão de vértices gera ganhos adicionais, aumentando a alavancagem do índice e diminuindo o tempo de recuperação da geometria. Tente 64 ou até 32.
Paul Ramsey
A consulta agora é concluída em 5 minutos, em vez de 30! Obrigado pela sugestão.
Prithvi
Uau, este foi um grito insanamente bom. Minha consulta estava travando uma máquina com 62 GB de RAM em menos de 2 minutos e, em seguida, esse ST_Subdivide fez com que não apenas falhasse, mas também executasse em segundos. Acabei de encontrar meu novo melhor amigo!
Momchill 29/10/19