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

[Obe, Regina]

Kevin,

I remember that thread too and was thinking if that was along the lines of how the cascaded union thing would work.  In the cascaded case I presume we would still want to order the geometries.  I also wasn't quite clear how this is different from using

ST_MemCollect or ST_MemUnion - except it probably bunches more than 2 at a time.

Looking at the example I did where I was puzzled about why ordering made things slightly worse, I discovered I had the table clustered on the geometry so that's probably why - it was already naturally sorted so sorting again added a bit more processing - granted it seemed to add more than it should have.  I'll have to revisit that one again.

Thanks,
Regina

-----Original Message-----
From: postgis-devel-bounces at postgis.refractions.net on behalf of Kevin Neufeld
Sent: Tue 8/5/2008 2:39 PM
To: PostGIS Development Discussion
Subject: Re: [postgis-devel] Ordering of geometries in multipolygons, preparedgeometries
 
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
_______________________________________________
postgis-devel mailing list
postgis-devel at postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-devel


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20080805/60140a51/attachment.html>