1

I am running a point in polygon test for close to one billion points. The size of my polygons are very small (at about 12 vertices each polygon). Therefore, I would be satisfied even with a bounding box intersect test. However, when I checked,point_geom && polygon_geom (bounding box test) and ST_Contains(point_geom, polygon_geom) (polygon contains test) yield the same amount of time. Rather, I expected the bounding box test to be much faster than the polygon contains test.

  • 2
    May be that with 12 vertices it is pretty fast to do the final intersects test. The preselection by bounding boxes is done first in any case and it is probably very selective so that the second intersects test is done only for few polygons. – user30184 Apr 6 '16 at 18:20
  • Following the smart user30184 's ideia, would be nice to have the exact time of both queries... – WKT Apr 6 '16 at 21:20
  • Thanks. You are correct. However, I expected the time to be still significantly different. I did the same in python and the time difference is noticeable. The difference is traversing a tree vs doing a ray cast/ winding number. Even if you have to do the latter for a significantly lower number of polygons, still the time is expected to be larger I guess. – picmate Apr 6 '16 at 21:21
3

You'll want to look inside the definition of ST_Contains, which is this:

CREATE OR REPLACE FUNCTION ST_Contains(geom1 geometry, geom2 geometry)
    RETURNS boolean
    AS 'SELECT $1 ~ $2 AND _ST_Contains($1,$2)'
    LANGUAGE 'sql' IMMUTABLE;

See what's going on? The function wraps a call to the box containment operator, ~, and the explicit polygon containment function after that. So since your query boxes are small, they are both winnowing most of the possible points using an index search (tree traversal), and only once that's done is the polygon query having to test the very small number of candidate points.

If you ran the polygon test using _ST_Contains(), which has no inlined index operator, you'd find it took very very long indeed. But why would you want to do that? :)

  • Thanks for pointing out the function Paul. My question is rather about doing only a bounding box test without doing the _ST_Contains($1,$2) at all. I was hoping if I run only the bounding box test the query would run much faster. For example, it takes 98 seconds to process 1million points with the bb test and 99 secs with the ST_Contains. In this case, the _ST_Contains($1,$2) should run once for a point and a polygon. My question is, is the difference in time for running _ST_Contains($1,$2) a million times 1 second? When I did the same thing on Python there was a significant difference – picmate Apr 7 '16 at 13:05

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.