2

I have to calculate the shortest path and corresponding distances for 300k+ origin-destination (OD) pairs. Using the query below it takes me around 0.3 sec to calculate one distance and therefore more than 24 hours to run the full query (still need to verify the total runtime). Is there a way to speed this up? Possibly using more RAM, fast CPU, possibly parallelizing?

This is my first attempt at a spatial sql query, so mostly wondering if there are any obvious speed-up possibilities.

-- Parameterized SQL function to take the OD ID as the parameter 
-- and lookup the corresponding origin and destination coordinates from 
-- all_trips_non_zero table. We then find the nearest point on the road  
-- network closest to our origin and destination and find the shortest 
-- path using pgr_dijkstra(). **OD ID goes from 1 to 300k+**
CREATE OR REPLACE FUNCTION shortest_path_id(IN od_id int)
RETURNS TABLE (shortest_distance double precision) as
$BODY$   

SELECT sum(cost) * 0.000621371 as shortest_distance
FROM pgr_dijkstra(
'SELECT id, source, target, st_length(geom, true) as cost FROM public."WA_roads"',
  (SELECT source FROM public."WA_roads" ORDER BY ST_StartPoint(geom) <->
    (select ST_SetSRID(ST_MakePoint(ocentx, ocenty), 4326) from all_trips_non_zero where id = od_id) ASC
LIMIT 1),
  (SELECT source FROM public."WA_roads"
ORDER BY ST_StartPoint(geom) <->
    (select ST_SetSRID(ST_MakePoint(dcentx, dcenty), 4326) from all_trips_non_zero where id = od_id) ASC
LIMIT 1), directed := false) as pt
JOIN public."WA_roads" rd ON pt.edge = rd.id;

$BODY$
LANGUAGE sql;

-- Create a new table containing the Origin, destination and 
-- shortest path using the sql function created above.
CREATE TABLE od_shortestpath AS 
SELECT origin, destination, shortest_path_id(id) from all_trips_non_zero;
  • generally, reduce iteration cost: don't call a function but use plain SQL, pre-compute NN source and cost value, join results to edges once at the end; highest impact would be to reduce graph loading: use many-to-one-dijkstra for a node that happens to get routed to from multiple start nodes – geozelot Aug 18 '19 at 6:48
0

If you are not really using the routes returned by the pgr_dijkstra, then simply use the pgr_dijkstraCost which is more efficient for your use case. And please don't use LIMIT 1, you can use many to many by passing every possible source and destination at once.

| improve this answer | |

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.