4

I have two sets of polygons. One is representing populated areas and it contains about 30k of polygons. Other set contains smaller polygons. I want to count how many smaller polygons are within populated areas. I made a query and run it but it is running for 24 house now. Second dataset is very large, about 120 million polygons.

select count(*) 
from public.pop_areas pa 
left join public.polys p
    on st_contains(pa.geom, p.wkb_geometry);

Is there any way to speed this up? Also, I have indices on geometry fields.

4
  • 1
    Index of the populated areas is probably not very selective because the areas are large. Large number of vertices in the geometries make also ST_Contains slow. ST_Subdivide should help with both issues postgis.net/docs/ST_Subdivide.html.
    – user30184
    Jul 21 at 10:26
  • @user30184 subdividing does not really work well with Polygon containment. Gridding might, but then you'd be stuck with gridding 120 million Polygons...
    – geozelot
    Jul 21 at 10:42
  • Hmm, I noticed also that a small polygon can belong to several subdivided polygons of populated areas and ST_Contains would give wrong results. Pre-checking centroids against subdivided polygons might still get some benefit.
    – user30184
    Jul 21 at 10:52
  • @user39184 yet it would require a second table to pre-filter, or a costly correlated/LATERAL subquery to then check for containment of a union by id or sth.
    – geozelot
    Jul 21 at 10:58
10

True Polygon containment is a costly operation; not only does a containment check have to run intersection computations between each pair of vertices in one polygon for each pair of vertices in the other, but is it also impossible to improve by subdividing any of them.

That being said, your query is also not going to return the desired result; you are counting any non-containing Polygons in public.pop_areas, plus one row for each of them containing one Polygon of public.polys; remove the LEFT JOIN, and COUNT only matching rows in public.polys:

SELECT COUNT(ply.*)
FROM   public.polys AS ply
JOIN   public.pop_places AS pop
  ON   pop.geom ~ ply.wkb_geometry 
WHERE  ST_Contains(pop.geom, ply.wkb_geometry)
;

The ~ condition may seem superfluous (it is implemented in ST_Contains), but might force a faster index lookup nonetheless.


Depending on the average shape of those Polygons you may see a boost in performance when pre-filtering by the ST_PointOnSurface of your public.polys.wkb_geometry:

SELECT COUNT(ply.*)
FROM   public.polys AS ply
JOIN   public.pop_places AS pop
  ON   pop.geom ~ ply.wkb_geometry 
 AND   ST_Intersects(pop.geom, ST_PointOnSurface(ply.wkb_geometry))
WHERE  ST_Contains(pop.geom, ply.wkb_geometry)
;

The idea is to limit the containment check to only those Polygons where at least the ST_PointOnSurface intersects the larger Polygon.

8
  • Second query took about 5 hours to calculate but it worked. Please correct ST_Contains(ply.wkb_geometry, pop.geom) to ST_Contains(pop.geom, ply.wkb_geometry).
    – DrJacoby
    Jul 22 at 8:15
  • 2
    @DrJacoby corrected, thx.! 5h is nothing I would be surprised about. Note that CREATE TABLE <name> AS SELECT ply.* FROM ... ; might be significantly faster, and leaves you with lasting options for that data. Or an UPDATE on an added column (e.g. isContained BOOL) even, though this would likely take about the same time.
    – geozelot
    Jul 22 at 8:37
  • This should use ST_PointOnSurface. Polygon centroids do not always lie inside the polygon.
    – dr_jts
    Jul 22 at 17:05
  • 1
    @dr_jts I used ST_Centroid on purpose, though, with my point being that its significantly lower complexity is adequate for a fast pre-filter, considering that this approach only ever really mskes sense for cases where the checked polygon is small enough to pass the bbox containment, but outside the actual bounds.
    – geozelot
    Jul 22 at 17:36
  • 1
    Good point. ST_PointOnSurface is about as fast as ST_Centroid, though, so seems better to promote its use, even in this case.
    – dr_jts
    Jul 22 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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