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

[Paul Ramsey]

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.