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

[Paul Ramsey]

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
>