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

Tue Aug 5 13:19:05 PDT 2008

I would agree.  I suspect that the hierarchical nature of the Cascaded 
Union provides more of a performance boost than the ordering (although 
the ordering is essential to make it work).

This is probably heavily dataset dependent.  It would be interesting to 
see some performance testing.

Kevin Neufeld wrote:
> Interesting. I like it.
>
> But isn't ordering the geometries just the first step of a true 
> cascaded union?  In my experiments, it's significantly faster to union 
> small spatially-close collections together and build up to larger 
> unions.  IE. if you wanted to union 1000 geometries together, it's 
> faster to first create 10 groups of 100 spatially close geometries and 
> then union the 10 groups together than it is to simply union 1000 
> geometries together that are optimally ordered.
>
> -- Kevin
>
> Paul Ramsey wrote:
>> Perhaps it is time to add a geohash generation function to PostGIS,
>> for these kinds of problems. (Also to simply back ST_Union() into a
>> cascaded implementation :). But an order by ST_GeoHash(geom) should
>> provide a pretty optimal input to the standard union function.
>>
>> This is something that could even be done in plpgsql, I bet. Take the
>> centroid of the geometry and apply an interleave to the coordinates.
>>
>> P.
>>
>> On Tue, Aug 5, 2008 at 11:58 AM, Martin Davis 
>> <mbdavis at refractions.net> wrote:
>>> CascasedUnion in JTS works great - for independent feedback see this 
>>> post:
>>>
>>> http://lists.jump-project.org/pipermail/jts-devel/2008-July/002587.html
>>>
>>> Unfortunately this code hasn't been ported to GEOS yet.
>>>
>>> In the meantime, the "order-by-x" technique will help.
>>>
>>>
>>>
>>> Kevin Neufeld wrote:
>>>> 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
>>>>
>>> -- 
>>> Martin Davis
>>> Senior Technical Architect
>>> Refractions Research, Inc.
>>> (250) 383-3022
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022