[postgis-devel] Ordering of geometries in multipolygons, prepared geometries

[Kevin Neufeld]

Yes, specifying a custom ordering for collect often makes a huge 
difference when performing certain operations, but PostGIS does not do 
anything special internally with the ordering of a collection ... yet.

I recall back in Nov.2007 that Lee Keel was trying to union ~33000 
polygons together that was taking over 5 hours to compute.  (See the 
"geomunion revisited..." thread in postgis-users).

Using a technique called cascaded union, Martin Davis and I were able to 
drop the computation to half a minute by simply ordering the geometries 
so that they were spatially close to eachother and then unioning small 
collections at a time. 
(http://postgis.refractions.net/pipermail/postgis-users/2007-November/017696.html)

Martin, what's the status of your CascadedUnion class in JTS?  Do you 
know if it ever made its way into GEOS yet?

Cheers,
-- Kevin


Obe, Regina wrote:
> Do PostGIS functions take advantage of the internal ordering of
> geometries in a Multi geometry?
> 
> The reason I ask is that since ST_Collect just collects geometries in
> the order they are fed in, I'm wandering if its better to advice to
> first order the geometries before collecting.
> 
> Something along the line of 
> 
> SELECT stusps, 
> 	   ST_Collect(f.the_geom) as singlegeom  
> 	 FROM (SELECT stusps, (ST_Dump(the_geom)).geom As the_geom 
> 				FROM
> 				somestatetable
> 			ORDER BY stusps, somestatetable.the_geom ) As f
> GROUP BY stusps
> 
> or maybe it doesn't make a difference.
> 
> Also I've noticed when using ST_Union if I order the geometries first
> before passing them to ST_Union, it is anywhere from 20-30% faster.  On
> some occasions though - its actually slower by about 10% (even when my
> ordering doesn't add any significant time).  I'm still trying to figure
> this out.
> 
> Case in point - runs in 359-360 ms
> SELECT ST_Union(the_geom)
> from (SELECT * from neighborhoods ORDER BY the_geom)  as foo
> 
> Vs - runs between 530 - 550 ms
> SELECT ST_Union(the_geom)
> from (SELECT * from neighborhoods ) as foo
> 
> This is all running on - "POSTGIS="1.3.3" GEOS="3.0.0-CAPI-1.4.1"
> PROJ="Rel. 4.6.0, 21 Dec 2007" USE_STATS"
> 
> Thanks,> Regina
> 
> 
> -----------------------------------------
> The substance of this message, including any attachments, may be
> confidential, legally privileged and/or exempt from disclosure
> pursuant to Massachusetts law. It is intended
> solely for the addressee. If you received this in error, please
> contact the sender and delete the material from any computer.
> 
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel