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

Tue Aug 5 13:44:47 PDT 2008

So whats the issue with getting it in Geos?  Is it a memory leak issue? 

If it is a big improvement of regrouping into smaller ordered data sets,
I still think this kind of grouping can be done in plpgsql function
without too much effort at the final func step.  

So final func -->  sorts array by this magical geohash function 
split array into some magical number of groups each having a magical
number of elements
unite_array(each group)

unit_array(dissolved groups)

So instead of one unite array call we do a couple.

I'm sure I'm missing something here though. There is just way too much
magic happening in the above.

-----Original Message-----
From: postgis-devel-bounces at postgis.refractions.net
[mailto:postgis-devel-bounces at postgis.refractions.net] On Behalf Of
Martin Davis
Sent: Tuesday, August 05, 2008 4:19 PM
To: PostGIS Development Discussion
Subject: Re: [postgis-devel] Ordering of geometries in multipolygons,
preparedgeometries

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/01
7696.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

_______________________________________________
postgis-devel mailing list
postgis-devel at postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-devel