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

[Paul Ramsey]

You're correct. We should be doing things a node at a time up the
tree. Ordering is better, but not best.

P

On Tue, Aug 5, 2008 at 1:09 PM, Kevin Neufeld <kneufeld at refractions.net> 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
>