1

I have been following this article to find shortest path in vector data. I can already find shortest path between 2 OSM nodes using Dijkstra algorithm in pgrouting. My working query is as below:

SELECT seq, id1 AS node, id2 AS edge, di.cost, ST_AsText(ST_Transform(geom_way, 4326)) 
FROM pgr_dijkstra('SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr', 21000, 1855, false, false) as di
JOIN hh_2po_4pgr
ON di.id2 = hh_2po_4pgr.id

The OSM data that I am using is of Trieste (Italy). The above query executes in roughly 3.5 seconds. In order to decrease its execution time (roughly around 30 milliseconds), I want to write a similar query using a bounding box. The query will be executed only in a bounding box instead of executing on the whole city of Trieste. As a result of this the execution time should also be decreased.

Selection of Bounding Box: Since I already know the latitude/longitude of source and target nodes, I have simply calculated the bounding box of 3.0 km around the source node, as source node and target nodes are at most 1 km away from each other. Therefore, any one of them can be chosen to calculate the bounding box.

The query that I have designed is as below:

SELECT seq, id1 AS node, id2 AS edge, di.cost, ST_AsText(ST_Transform(geom_way, 4326)) 
FROM pgr_dijkstra('SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr WHERE  geom_way && ST_Transform(ST_MakeEnvelope(13.794389, 45.636805, 13.775791, 45.638375, 4326), 3857)', 21000, 1855, false, false) as di
JOIN hh_2po_4pgr
ON di.id2 = hh_2po_4pgr.id

But this query results in an empty table every time. I have spent a lot of time on it and cannot figure out where I am getting it wrong.


As instructed in the answer by @Jendrusk and comments by @ylka, I have thoroughly debugged the query. The problem was in the subquery. The projections were not correct. Now the following subquery with the bounding box returns me results in roughly 15ms. Previously, it was around 3.5 seconds (without the bounding box). The bounding box subquery with correct projections is as below:

SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr 
WHERE geom_way && ST_MakeEnvelope(13.794389, 45.636805, 13.775791, 45.638375, 4326)

@Jendrusk: I am already using indexing. The columns id, source and target have BTREE index, whereas, geom_way column has gist type of index.

THE PROBLEM: Now, when I contruct back the full query, then I do not get any results. I get an empty table. The full query is as below:

SELECT seq, id1 AS node, id2 AS edge, di.cost, ST_AsText(ST_Transform(geom_way, 4326)) 
FROM pgr_dijkstra('SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr 
        WHERE geom_way && ST_MakeEnvelope(13.794389, 45.636805, 13.775791, 45.638375, 4326)',
        21000, 1855, false, false ) as di 
JOIN hh_2po_4pgr 
ON di.id2 = hh_2po_4pgr.id

So far, I tried the following query:

select * FROM pgr_dijkstra('SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr 
        WHERE geom_way && ST_MakeEnvelope(13.794389, 45.636805, 13.775791, 45.638375, 4326)',
        21000, 1855, false, false ) as di 

This gives back an empty table and in result of this the whole query gives an emtpy table. Therefore, now the problem is in pgr_dijkstra() function. Without the boundingbox subquery, it gives back results but with the boundingbox query it gives back an empty table.

SOLUTION The first problem was with the projections. After solving it the problem was with the boundingbox. It was not big enough. The correct query is as below:

SELECT seq, id1 AS node, id2 AS edge, di.cost, ST_AsText(ST_Transform(geom_way, 4326)) 
FROM pgr_dijkstra('SELECT id, source, target, st_length(geom_way) as cost FROM hh_2po_4pgr 
        WHERE geom_way && ST_MakeEnvelope(13.754883,45.636547,13.801408,45.647708, 4326)',
        21000, 1855, false, false ) as di 
JOIN hh_2po_4pgr 
ON di.id2 = hh_2po_4pgr.id

The query roughly takes 16ms. If you have any idea to optimize it further, I would be happy to know it.

  • have you tried to visualize your working version in QGIS with your bounding box and checked if no route is outside the bbox? – ylka Nov 24 '16 at 15:22
  • No. Good suggestion and I will work on it now. – Amir Nov 24 '16 at 15:24
  • So I tried your query and couldn't replicate the problem. Try the query first with the bounding box of the whole dataset. If that returns the same result as in the working query, then its a problem with the extent of the bbox not the query – ylka Nov 24 '16 at 16:25
1

Since there is no data it's difficult to provide some ready-to-use solution, but:

  1. Check if your data is in EPSG:3857 - when good query with some spatial conditions is not returning records in 99% cases it's projection. Table names suggests you're using osm2po4pgr and it's default projection is 4326 (as I see in my data)
  2. Check your sub-query if it's returning records. If yes then trouble is with routing, if no it's about sub-query (e.g. projection from p.1)
  3. Don't use envelope on points of start and end - use some buffer around because route doesn't have to go straight from point A to B - sometimes roads forces driving opposite direction for some time.
  4. If you're searching for performance improvement try to search in union of 3 datasets - all roads in buffer 1km from start and end point + only main roads in envelope of this buffers
  5. Last but not least - of course, you read all materials about improving performance of pg_routing queries and you made all needed indexes? If I remember routing itself needs source and target fields, if you're using && some spatial index could be useful, if you'll use my sugestions from point 4 you also need index on clazz column.
  • Thanks allot for your time. I have updated my question after following these steps. – Amir Nov 28 '16 at 16:21
  • no problem, and I think in the join ... on clause should be id1, but not sure right now cause I have no place to check it... I'll check later – Jendrusk Nov 28 '16 at 16:40
  • Thanks. Now pgr_dijkstra() returns an empty table. I have updated it in the question. I am looking into this function and trying to figure out where I am getting it wrong. Thanks for your assistance :) – Amir Nov 28 '16 at 16:54
  • I found the problem. Now the boundingbox that I was selecting was not big enough, that is why I was getting an empty table. I am updating now the correct query in the question. Thanks allot for your help. I will be selecting your answer as you helped me find the projection issue. Thanks :) – Amir Nov 28 '16 at 17:04
  • 16ms is a good time... maybe too good - check if it's not returning from cache (restart postgres and check time of first run). Time of run also depends of numer of edges routing have to search in so it will significally grow for longer paths. 600km could take few seconds so I'm running different querries on different datasets for different eucledian distances and route types (quickest-shortest)... But that's story for another Q&A I think. – Jendrusk Nov 28 '16 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.