Looking for boolean intersection of small table with huge table

Question

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:

SELECT
    msa.uid, -- unque identifier for grid cells
    bool_or( ST_Intersects( msa.the_geog::geometry,na.way ) )
FROM 
    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)

Answer 1

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))

Answer 2

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.