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

Tue Aug 5 14:05:45 PDT 2008

My C++ is no good.  My C# skills I think are decent but my C++ haven't
done any in a long long time and even then I was a best mediocre.

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

No big issues. How's your C++? Basically you can take the cascaded
union from JTS, port it to GEOS and then add a C-API facade. Then move
the PostGIS ST_Union code from the current place to the new place.

P.

On Tue, Aug 5, 2008 at 1:44 PM, Obe, Regina <robe.dnd at cityofboston.gov>
wrote:
> 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
> _______________________________________________
> 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