[postgis-devel] [PostGIS] #3949: Infinite (?) loop in distance calculation

Paul Ramsey pramsey at cleverelephant.ca
Fri Dec 22 06:43:44 PST 2017


On Fri, Dec 22, 2017 at 5:46 AM, Nicklas Avén
<nicklas.aven at jordogskog.no> wrote:
> Sounds very good.
>
> And I think it is worth to sacrify 10 % speed in some occations for the
> predictability.
>
> And caching the tree must be a very good thing.
>
> When you say 100x faster, do you then mean in cases like the one in the
> ticket?

No 100x faster for objects of that size (thousands of edges), but
without the total awfulness. A set of 10 comparisons that take 14s in
aggregate for current take 140ms for the tree.

> If so, it isn't primary the amount of vertes points that is the bottle
> neck for todays code but other things like distance between the
> geometries and if there is a lot of vertex points in the part of the
> border that is hard for the algorithm to filter on (the part facing the
> other geometry, specially concave cases)
>
> But I think it doesn't matter if todays code performs on pair or even
> better in some cases. Predictability is more important.

I'm less sanguine. Lots-of-small-pairings is a more common case than a
few large ones, so we have to not lose performance in that baseline
case.

P

>
> I will give it a test run if the code is ready for that.
>
> /Nicklas
>
>
>
> On Fri, 2017-12-22 at 05:35 -0800, Paul Ramsey wrote:
>> So, I now have tree distance code that seems to work, thanks to this
>> little bug, which caused me to find the error in my tree code. I'd
>> given up on it, figured the tree approach was a dead end.
>>
>> https://github.com/pramsey/postgis/tree/svn-trunk-distance
>>
>> In very limited testing, I see it running quite a bit faster (100x)
>> than the existing code on large objects, but slightly slower on small
>> objects (10%). I was thinking on merging it to trunk but as a
>> completely independent function for now (ST_DistanceRectTree()) so
>> that it can be tested and the functional limits of it determined.
>> Then
>> we can discuss how we want to integrate it into generic
>> ST_Distance(),
>> maybe with a object size test, or maybe as a cached approach
>> (skipping
>> the tree built step in cases with repeated inputs would probably be a
>> win).
>>
>> Thoughts?
>>
>> P
>>
>>
>> On Fri, Dec 22, 2017 at 4:15 AM, PostGIS <trac at osgeo.org> wrote:
>> >
>> > Comment (by nicklas):
>> >
>> >  I agree.
>> >
>> >  But worst case is different for different methods.
>> >  The example Paul provided here is among the worst cases for the
>> > algorithm
>> >  we use now (when bboxes doesn't overlap, then it falls back to
>> > brute
>> >  force)
>> >
>> >  If the shoreline of both geometries would have been convex it
>> > would have
>> >  been quite a lot faster, but now one is concave and all points in
>> > the
>> >  concave part needs to be tested more or less.
>> >
>> >  So for this case that is a pain for that algorithm it loses the
>> > battle
>> >  with about 1.08 (79 sec vs 85 sec)
>> >
>> >  But for the case with the same geometries further away it wins by
>> > using
>> >  approx 0.04 of the time brute force method uses. And with the case
>> > when we
>> >  turn the other side of the geometries against each other it wins
>> > by using
>> >  approx 0.0005 of the brute force method.
>> >
>> >  So in this case I think the 8 % worse result in some cases is ok.
>> > BUT, the
>> >  problem is that it is unpredictable. Users will like Paul think
>> > that
>> >  something is wrong.
>> >
>> >  But we have lived with this code now since 2010 and I don't think
>> > there
>> >  have been many posts on the list about that issue. But I have hit
>> > that
>> >  wall a few times myself making queries much slower than I expect.
>> > And it
>> >  can be very frustrating when testing a sample to get an idea of
>> > the query
>> >  time and then it takes 100 times longer.
>> >
>> > --
>> > Ticket URL: <https://trac.osgeo.org/postgis/ticket/3949#comment:9>
>> > PostGIS <http://trac.osgeo.org/postgis/>
>> > The PostGIS Trac is used for bug, enhancement & task tracking, a
>> > user and developer wiki, and a view into the subversion code
>> > repository of PostGIS project.
>>
>> _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/postgis-devel
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel


More information about the postgis-devel mailing list