# Looking for boolean intersection of small table with huge table

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)

• I should add, I am already using a spatial index on the large table. – Nate Wessel Sep 11 '15 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 Sep 11 '15 at 22:40
• @RobSkelly done! – Nate Wessel Sep 12 '15 at 1:11

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

``````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!! – Nate Wessel Sep 12 '15 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 Sep 12 '15 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 Sep 12 '15 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 Sep 12 '15 at 0:33
• No, the index of the polygon table wouldn't be used to find lines which overlap the polygon query shape. – Vince Sep 12 '15 at 1:05
• Yeah, exactly what I meant. – bosth Sep 12 '15 at 2:00