<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7652.24">
<TITLE>RE: [postgis-devel] Ordering of geometries in multipolygons, preparedgeometries</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<BR>
<P><FONT SIZE=2>Kevin,<BR>
<BR>
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<BR>
<BR>
ST_MemCollect or ST_MemUnion - except it probably bunches more than 2 at a time.<BR>
<BR>
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.<BR>
<BR>
Thanks,<BR>
Regina<BR>
<BR>
-----Original Message-----<BR>
From: postgis-devel-bounces@postgis.refractions.net on behalf of Kevin Neufeld<BR>
Sent: Tue 8/5/2008 2:39 PM<BR>
To: PostGIS Development Discussion<BR>
Subject: Re: [postgis-devel] Ordering of geometries in multipolygons, preparedgeometries<BR>
<BR>
Yes, specifying a custom ordering for collect often makes a huge<BR>
difference when performing certain operations, but PostGIS does not do<BR>
anything special internally with the ordering of a collection ... yet.<BR>
<BR>
I recall back in Nov.2007 that Lee Keel was trying to union ~33000<BR>
polygons together that was taking over 5 hours to compute. (See the<BR>
"geomunion revisited..." thread in postgis-users).<BR>
<BR>
Using a technique called cascaded union, Martin Davis and I were able to<BR>
drop the computation to half a minute by simply ordering the geometries<BR>
so that they were spatially close to eachother and then unioning small<BR>
collections at a time.<BR>
(<A HREF="http://postgis.refractions.net/pipermail/postgis-users/2007-November/017696.html">http://postgis.refractions.net/pipermail/postgis-users/2007-November/017696.html</A>)<BR>
<BR>
Martin, what's the status of your CascadedUnion class in JTS? Do you<BR>
know if it ever made its way into GEOS yet?<BR>
<BR>
Cheers,<BR>
-- Kevin<BR>
<BR>
<BR>
Obe, Regina wrote:<BR>
> Do PostGIS functions take advantage of the internal ordering of<BR>
> geometries in a Multi geometry?<BR>
><BR>
> The reason I ask is that since ST_Collect just collects geometries in<BR>
> the order they are fed in, I'm wandering if its better to advice to<BR>
> first order the geometries before collecting.<BR>
><BR>
> Something along the line of<BR>
><BR>
> SELECT stusps,<BR>
> ST_Collect(f.the_geom) as singlegeom <BR>
> FROM (SELECT stusps, (ST_Dump(the_geom)).geom As the_geom<BR>
> FROM<BR>
> somestatetable<BR>
> ORDER BY stusps, somestatetable.the_geom ) As f<BR>
> GROUP BY stusps<BR>
><BR>
> or maybe it doesn't make a difference.<BR>
><BR>
> Also I've noticed when using ST_Union if I order the geometries first<BR>
> before passing them to ST_Union, it is anywhere from 20-30% faster. On<BR>
> some occasions though - its actually slower by about 10% (even when my<BR>
> ordering doesn't add any significant time). I'm still trying to figure<BR>
> this out.<BR>
><BR>
> Case in point - runs in 359-360 ms<BR>
> SELECT ST_Union(the_geom)<BR>
> from (SELECT * from neighborhoods ORDER BY the_geom) as foo<BR>
><BR>
> Vs - runs between 530 - 550 ms<BR>
> SELECT ST_Union(the_geom)<BR>
> from (SELECT * from neighborhoods ) as foo<BR>
><BR>
> This is all running on - "POSTGIS="1.3.3" GEOS="3.0.0-CAPI-1.4.1"<BR>
> PROJ="Rel. 4.6.0, 21 Dec 2007" USE_STATS"<BR>
><BR>
> Thanks,> Regina<BR>
><BR>
><BR>
> -----------------------------------------<BR>
> The substance of this message, including any attachments, may be<BR>
> confidential, legally privileged and/or exempt from disclosure<BR>
> pursuant to Massachusetts law. It is intended<BR>
> solely for the addressee. If you received this in error, please<BR>
> contact the sender and delete the material from any computer.<BR>
><BR>
> _______________________________________________<BR>
> postgis-devel mailing list<BR>
> postgis-devel@postgis.refractions.net<BR>
> <A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
_______________________________________________<BR>
postgis-devel mailing list<BR>
postgis-devel@postgis.refractions.net<BR>
<A HREF="http://postgis.refractions.net/mailman/listinfo/postgis-devel">http://postgis.refractions.net/mailman/listinfo/postgis-devel</A><BR>
<BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>