[postgis-users] Finding Islands

[Lee Hachadoorian]

I am trying to find "islands", polygons in a (multi)polygon layer which 
are not connected to any other polygons in the same layer. What I came 
up with runs in a couple of seconds on a layer with ~1000 geometries, 
and a couple of minutes on a layer with ~23,000 geometries, but I want 
to run it on a layer of 2 million+ and it's taking a L-O-O-O-NG time, 
presumably because it's making (2 million)^2 comparisons.

What I came up with is:

SELECT a.*
FROM table a LEFT JOIN table b
     ON (ST_Touches(a.geom, b.geom))
WHERE b.gid is null

or

SELECT *
FROM table
WHERE gid NOT IN (
     SELECT DISTINCT a.gid
     FROM table a JOIN table b
         ON (ST_Intersects(a.geom, b.geom) AND a.gid != b.gid)
     )

The first variant raises "NOTICE:  geometry_gist_joinsel called with 
incorrect join type". So I thought I could improve performance with an 
INNER JOIN instead of an OUTER JOIN, and came up with the second 
variant, and it does seem to perform somewhat better. Any suggestions 
for how to speed up either approach?

Best,
--Lee

-- 
Lee Hachadoorian
Assistant Professor in Geography, Dartmouth College
http://freecity.commons.gc.cuny.edu