8

I have 150 million points in a point table and would like to find the few points lying outside a given polygon geometry. I know that 99.9% of the points are within the polygon geometry. I am interested in finding the few points which lie outside the polygon.

My present best query using indexed PostGIS tables takes about 30 minutes to complete. Is there a way to optimize the following query knowing that most of the points are within the polygon (border)?

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

The polygon is basically the admin 0 border of Italy. Vertices - 405,000. Parts - 510. The envelope is much larger than the polygon (The polygon covers 24% of the envelope)

Improve this question
6
  • 2
    Please Edit the question to give an indication of the complexity of the polygon -- How many parts? How many vertices? What percentage of the envelope of the polygon is within the polygon. I've found that partitioning complex polygons can improve point-in polygon evaluation, but you need to handle the condition where a single point intersects more than one partition.
    – Vince
    Dec 17, 2018 at 17:02
  • The first optimization for this type of operation is commonly to check whether the point is in the bounding box of the polygon before carrying on to the full point-in-polygon operation. Point-in-box is a very efficient operation by comparison.
    – WhiteboxDev
    Dec 17, 2018 at 19:56
  • @Vince If duplicates are possible (the only case I think think of is when it falls exactly on the border of two partitions), this is trivially handled in PostGIS. You need only GROUP BY the primary key of the points. (PostgreSQL conveniently allows you to reference any columns in the SELECT clause that come from a table where the primary key is included in the GROUP BY clause.)
    – jpmc26
    Dec 17, 2018 at 21:02
  • @WhiteboxDev ST_Within already does a boundary box check that enables to use of the index. (Almost all of PostGIS's functions include this optimization.) If it's still slow, then clearly the problem is with the complexity of the polygon.
    – jpmc26
    Dec 17, 2018 at 21:05
  • @jpmc26 Certainly, but the SQL query would also need to be modified to use ST_Intersects, since ST_Within would not reliably match internal boundary conditions.
    – Vince
    Dec 17, 2018 at 21:52

1 Answer 1

Reset to default
10

Use ST_Subdivide to cut your polygon into smaller polygons, save them to a table and create a spatial index. Then do your query on the gridded polygons.

Without that, spatial indexing does not provide any advantages in your case (only 1 polygon of interest).

Improve this answer
3
  • 4
    Further to the ST_Subdivide() comment, you might find that using less than the default number of vertices yields further gains by increasing index leverage and decreasing geometry recovery time. Try 64 or even 32.
    – Paul Ramsey
    Dec 17, 2018 at 17:27
  • The query now completes in 5 minutes as opposed to 30! Thanks for the suggestion.
    – Prithvi
    Dec 17, 2018 at 22:28
  • Wow, this was an insanely good shout. My query was crashing a machine with 62Gb RAM in less than 2 min and then this ST_Subdivide made it not only not crash but execute in seconds. Just found my new best friend!
    – Momchill
    Oct 29, 2019 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.