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

[Kevin Neufeld]

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