# How can I optimize a Point in Polygon query for millions of points when most of the points lie within the polygon?

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)

• 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. Commented 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. Commented 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.) Commented 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. Commented 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. Commented Dec 17, 2018 at 21:52