[postgis-devel] Optimized ST_Union for polygon coverages

[Daniel Baston]

Is there any interest in a special-purpose union function for "dissolving"
topologically integrated polygon coverages?  I've used a simple algorithm
for a while on Java projects : extract the segments of your geometries,
discard any segments that are repeated, and polygonize.  I was curious
about the performance gain from a PostGIS implementation of this idea.  It
can be pretty significant.  Here's an example case, dissolving the TIGER
faces in Maricopa County, AZ (123k polygons, 3.5 million vertices):

SELECT ST_NPoints(ST_CoverageUnion(ST_Collect(geom))) FROM
tl_2015_04013_faces;
 st_npoints
------------
       6944
(1 row)

Time: 1835.423 ms

postgres=# SELECT ST_Npoints(ST_Union(geom)) FROM tl_2015_04013_faces;
 st_npoints
------------
       6944
(1 row)

Time: 94927.438 ms

Obviously this is a special case, but not necessarily an uncommon one, and
the performance blows away the general-purpose union.  From a user
standpoint, the main "gotcha" is that, if your inputs aren't topologically
integrated, you'll just get a garbage result.  But the operation should
conserve area, so you should at least be able to detect the problem.

The main defect with the implementation right now is memory usage.  If I
run it on a larger data set, I get an unhappy "ERROR:  invalid memory alloc
request size 1073741824"

Any thoughts?

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20160413/6ec07c6b/attachment.html>