Infinite (?) loop in distance calculation

[pramsey]

For the pair of attached geometries, the standard distance code appears to go into an infinite (at least, very long) loop. Similarly sized geometries can run distance calculations in a few 10s of ms.

select 
  st_distance(a.geom, b.geom), 
  a.edabbr, b.edabbr,  
  st_memsize(a.geom), st_memsize(b.geom) 
from inf_distance a, inf_distance b;

[pramsey]

example data

[pramsey]

Oh, I should comment: the geometries (and their boxes) are disjoint. And I checked with a profiler, the execution path is the "fast" one, not the "brute force" one. So this isn't a brute force combinatorial explosion, it's something else going on.

[nicklas]

Interesting. I will look at it.

[pramsey]

Happily, looking at this problem exposed a key error in my indexed distance calculation code, and it now runs much closer to parity with the existing code on small objects, and much faster on large objects.

[nicklas]

Ok, I don't think this is a bug. This is just the nightmare situation for the "faster" code.

Actually in this case it was slightly faster to go the brute force way.

Your query finished in 2min 46 sec.

But I also compared it with brute force. I cheeted and just moved the northern geoemtry to south west to make the bounding boxes overlap and tested with just 1 calculation, not both ways like your query.

Then:

--"faster" code
select st_distance(a.geom, b.geom) from 
(select * from inf_distance where gid = 7) a,
(select * from inf_distance where gid = 37) b
1 min 25 sec

and

create table t as select gid, geom from inf_distance

update t set geom = ST_Translate(geom, -1, -1) where gid = 37;

--brute force code because overlapping bboxes
select st_distance(a.geom, b.geom) from 
(select * from t where gid = 7) a,
(select * from t where gid = 37) b
1 min 19 sec

Those geometries is a nightmare because the geometries is so close and most of the vertex-points is on the facing side to the other geometry. Then it takes a lot of iteration before it can be sure there is no other possible shorter combination.

That is why we want the tree-based code

[nicklas]

Just to further illustrate the characteristics of the algorithm

If you move the geometries further apart it will be faster because of the angels between different vertex-points. It makes it easier to order the points in a straight line:

drop table if exists t; create table t as select gid, geom from inf_distance;
update t set geom = ST_Translate(geom, -20, -20) where gid = 7;

select st_distance(a.geom, b.geom) from 
(select * from t where gid = 7) a,
(select * from t where gid = 37) b
3 sec

and when facing the opposite side of the geometries towards each other instead it starts to go really fast (brute force would still use 1 min 19 sec on this)

drop table if exists t; create table t as select gid, geom from inf_distance;
update t set geom = ST_Translate(geom, -20, -20) where gid = 37;

select st_distance(a.geom, b.geom) from 
(select * from t where gid = 7) a,
(select * from t where gid = 37) b
32 ms

This makes todays distance function very unpredictable from a user perspective. But that is limitations of the algorithm and I guess it anyway is preferable over brute force since it gives such a great boost in cases where it fits. About distance between the geometries it is the relation between the geometries related to the "width" of the geometries from the other geometries perspective that matters. So small geometries (not few points but small) requires a shorter distance to work well.

This makes sense if looking at the wiki-post about the method ​https://trac.osgeo.org/postgis/wiki/NewDistCalcGeom2Geom

[strk]

It is worst case that counts, IMHO. We need to use provide what is fastest in the worst case.

[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.