ST_Distance for geography should be cancellable

[robe]

My server seems pretty frozen computing these and it's still trying to compute the distance between these two countries and it's been 15 minutes already.

After about 17 minutes of waiting I decided to just cancel the query and the query would not cancel even after 7 minutes of waiting. Then I tried to pg_terminate_backend it, and that still did not work. So I had to finally end up killing my service entirely.

I know they are big but really? I should at least be able to cancel.

We were testing on 2.2.1, but decided to also test on 2.1.8 (postgresql 9.4). Same issue on both.

Us has 36054 points and Russia has 36352

Query is as follows:

SELECT ST_Distance(a.geog, b.geog)
FROM   (SELECT geom::geography As geog, ST_NPoints(geom) As npoints FROM ur_test WHERE name = 'United States') AS a
,  (SELECT geom::geography AS geog, ST_NPoints(geom) As npoints FROM ur_test WHERE name = 'Russia') AS b

Casting to geography is quick. Doing distance on geometry I think was about 2 seconds.

[robe]

For more fun, I decided to see what would happen if I simplified. Took 15:31 minutes to complete and returned an answer of 4434.16000.

-- US 12215 pts; Russia 14686
SELECT ST_Distance(ST_Simplify(a.geom,0.01)::geography, ST_Simplify(b.geom,0.01)::geography) --::geography, ST_Simplify(b.geog::geometry,0.8)::geography)
FROM   (SELECT  geom FROM ur_test WHERE name = 'United States') AS a
,  (SELECT  geom FROM ur_test WHERE name = 'Russia') AS b;

I also started the old unsimplified running, after 1 hr, 38 minutes and 36 seconds, I still have no idea how far Russia is from US. I'll keep it running because I really want to know now.

[robe]

Okay it finally returned an answer, so I guess it really does take that long to figure out how far these political boundaries are. Still it should be a cancellable/interruptable operation.

Final answer - 3987.91690476 in (1 hr, 54 minutes, 36 seconds)

[pramsey]

So, "yes" to interruptible, I'll do that right away. It's easy to see why it takes forever: with the first, uncached call happening in the "brute force" algorithm, you get 36K x 36K edge-edge distance calculations, which is… a lot 1.2B. So it takes a while. Running the tree-based calculation, I get a result in a under a second (and that's with four calculations!):

postgis23=# select _st_distancetree(a.geog, b.geog) from ur_test_g a, ur_test_g b;
 _st_distancetree 
------------------
                0
   3987.916904757
   3987.916904757
                0
(4 rows)

Time: 801.691 ms

So that maybe argues for forgoing the brute force calculation altogether and just using the tree every time. (Although we have other tickets that still show failure cases in the tree, compared to the brute force, in terms of correct results.)

[robe]

Wow that's a big improvement. Is there the same issue with the geometry ST_Distance? My ST_Distance on geometry was 2 seconds (I think 1.8 to be exact) which is even slower than your new geography answer.

[pramsey]

Well, if we *had* a tree-based distance query for geometry (I still have my ½ built one) it could be quite a bit faster too, at least for these really large inputs.

[pramsey]

OK, in 2.2 (r14821) and trunk (r14821) the brute force calculation is now interruptible. For 2.1, I could not easily add it, as the interruption framework for liblwgeom only dates to 2.2+. Not sure how critical this is considered in that regard. See #3528 for follow-on work.

[robe]

np 2.1 is dead to me

So I will consider this closed and move on.