How can I quickly check to see if a polygon(or whatever) intersects anything in a massive table? I'm trying to find polygons that don't intersect with the North American street network at any point. Most of my polygons do intersect. My street network (a routeable edge table) has almost 50 million edges, and obviously, I shouldn't have to check each polygon for intersection with each of them. If any street at all intersects a polygon, there is no need to keep checking that polygon and the intersect operation should return true.

Is there any postgis function that can prevent this query from taking time on the order of N(table1) X N(table2) ?

Here is the query as I currently have it:

    msa.uid, -- unque identifier for grid cells
    bool_or( ST_Intersects( msa.the_geog::geometry,na.way ) )
    na_network AS na, -- ~ 50,000,000 lines 
    msa_grids AS msa
WHERE msa.msaid = 10180 -- limits to ~ 500 grid cells
GROUP BY msa.uid

EXPLAIN gives:

HashAggregate (cost=7911120376.04..7911120382.88 rows=684 width=256) -> Nested Loop (cost=0.00..361428549.44 rows=28760730768 width=256) -> Seq Scan on na_network na (cost=0.00..1903179.52 rows=42047852 width=124) -> Materialize (cost=0.00..16237.03 rows=684 width=132) -> Seq Scan on msa_grids msa (cost=0.00..16233.61 rows=684 width=132) Filter: (msaid = 10180) (6 rows)

  • I should add, I am already using a spatial index on the large table. Commented Sep 11, 2015 at 22:29
  • If you're using an index, the query shouldn't be n^2. Maybe post your query and the output of EXPLAIN.
    – Rob Skelly
    Commented Sep 11, 2015 at 22:40
  • @RobSkelly done! Commented Sep 12, 2015 at 1:11

2 Answers 2


You can use an EXISTS subquery expression to accomplish this (see Postgres docs).

In your case, your query might look something like

SELECT * FROM polygons
WHERE NOT EXISTS (SELECT 1 FROM streets WHERE ST_Intersects(polygons.geom, streets.geom))
  • Yes!! From over an hour without completing to under two seconds. I knew there must be a way. Thanks!! Commented Sep 12, 2015 at 1:33

You could do an ST_Union on your polygon table first and then push that down to the actual intersection query. If your polygon table is very large, however, the ST_Union will take a long time and this might not be any better than just doing a regular JOIN.

It could look something like this:

WITH polygon AS (SELECT ST_Union(geom) AS union FROM my_polygon_table) SELECT routes.* FROM routes, polygon WHERE ST_Intersects(routes.geom, union);

The performance benefit all depends on how slow that original ST_Union is.

  • Performance will also depend on the relative extent of the my_polygon_table union (if it covers the entire line table, there's no benefit to doing the union at all)
    – Vince
    Commented Sep 12, 2015 at 0:18
  • It depends on the nature of the polygon table... If it were two large polygons that covered the entire line table, it could be faster to take the union (which would be fast in this case) and then do a single intersection with each line.
    – bosth
    Commented Sep 12, 2015 at 0:32
  • The main disadvantage my approach is that you lose the benefit of an index that was created on the original polygon table.
    – bosth
    Commented Sep 12, 2015 at 0:33
  • No, the index of the polygon table wouldn't be used to find lines which overlap the polygon query shape.
    – Vince
    Commented Sep 12, 2015 at 1:05
  • Yeah, exactly what I meant.
    – bosth
    Commented Sep 12, 2015 at 2:00

Your Answer

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

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