pgRouting computation time & code efficiency

I am trying to find the closest landfill by distance from various locations, however, the computation time is 8 hr 36 min to find the shortest path from 3602 locations to 5 landfill locations.

Before using pgRouting I used QNEAT3 on another larger data set and it didn't take nearly as long.

As a test, I scaled down the data to 9 locations and 5 landfill locations and it completed the shortest path analysis in ~10 min.

Is there a problem with the code and its efficiency?

``````-- build road topology
SELECT pgr_createTopology('landfill.road', 0.001, 'geom', 'id'); -- prepare roads layer by building network topology based on geometry information.

UPDATE landfill.road SET length = ST_Length(geom::geography);

-- replace null values with 0
UPDATE landfill.road SET oneway=0 WHERE oneway IS null;

-- create cost and reverse costs for road network based on ONEWAY field
SET cost = ST_Length(geom::geography)
WHERE oneway IN ('0','FT'); -- both direction, road direction and the digitizing direction are the same

SET cost = 999999999
WHERE oneway = 'TF'; -- The road direction and the digitizing direction are opposite.

SET reverse_cost = ST_Length(geom::geography)
WHERE oneway IN ('0', 'TF');

SET reverse_cost = 999999999
WHERE oneway = 'FT';

-- Begin Dijkstra algorithm shortest path query
CREATE TABLE landfill.pgr_routes AS
WITH all_pairs AS (
-- all pairs of start and end geometries with IDs
-- that get carried through so the routing results
-- match with the pt IDs you know.
SELECT f.id AS fid, f.geom as fgeom,
t.id as tid, t.geom as tgeom
FROM public.from_pts AS f,
landfill.to_pts AS t
), vertices AS (
SELECT fid, tid,
(SELECT id -- proximity search for closest from vertex
ORDER BY the_geom <-> fgeom
LIMIT 1) as fv,
(SELECT id -- proximity search for closest to vertex
ORDER BY the_geom <-> tgeom
LIMIT 1) as tv
FROM all_pairs
), pgr_result AS (
SELECT fid, tid, pgr_Dijkstra(
'SELECT id, source, target, length AS cost, reverse_cost FROM landfill.road',
fv, tv,
directed := true
) from vertices
)
SELECT fid, tid, (pgr_dijkstra).* FROM pgr_result -- to unpack all fields in the composite column with each as a seperate column.
WHERE (pgr_dijkstra).edge = -1;

-- min distance value of agg_cost results
CREATE TABLE landfill.pgr_routes_min AS
SELECT DISTINCT ON (fid) fid, tid, agg_cost
FROM landfill.pgr_routes
WHERE agg_cost > 0  -- landfill must be greater than 0 m from location
ORDER BY fid, agg_cost;

-- Left join min distance results to locations and original landfill locations table
CREATE TABLE landfill.nearest_landfill AS
SELECT public.from_pts.*,landfill.pgr_routes_min.*,landfill.to_pts.name
FROM landfill.pgr_routes_min
LEFT JOIN public.from_pts
ON landfill.pgr_routes_min.fid = public.from_pts.id
LEFT JOIN landfill.to_pts
ON landfill.pgr_routes_min.tid = landfill.to_pts.id;
``````
• How many records does landfill_road have? In your proximity search - do you have a spatial index on the_geom ? May 25, 2022 at 6:58
• The time it is taking is definitely unusual. Before diving into further speedups, such as bounding box enhancements, let's try and eliminate the low hanging fruit first. The 45 queries I'd already expect to compute faster but then again, it depends how big the dataset is in the first place. Can you share a subset of the data? May 25, 2022 at 12:14
• pgRouting builds a network graph each time pgr_* function is executed. In your case (3602 * 5) times. Based on your network size, this can be unsustainable. You have to find a pgr function that calculates what you need in the least possible calls. I don't know if that function exists in pgRouting... You have to be creative or use something like pgrserver that can cache graph... May 25, 2022 at 13:13
• This is not true, pgr builds the topology once, the OP is doing that correctly. When the query is executed it loads the graph into memory and keeps it there until the call finishes. May 25, 2022 at 14:11
• @TimothyDalton yes and no... Topology structure in database is build only once, but SQL to query it and building internal in memory graph is performed each time you call a pgr function. If you call pgr_dijkstra 100 times, pgrouting executes topology SQL (passed as parameter) and build in memory graph 100 times... May 25, 2022 at 15:16

Instead of calling `pgr_dijkstra` multiple times you should be invoking it with 2 arrays for sources and targets and not single values (thank you @DavidP for highlighting this). This way the graph will be loaded into memory one time only. I tested the following many-to-many query on a 4 core and 16GB laptop on a topology containing 3.2M edges (OSM North California processed with osm2po) and it took 22 seconds to compute. The only difference is the `array_agg()` call. You can read more about it here. There are a few additional handy speedups you can implement listed here.

First of all I am creating some random points in the target area.

``````CREATE TABLE from_pts (
id serial primary key,
geom geometry(point, 4326)
);
INSERT INTO from_pts(geom)
VALUES
(ST_MakePoint(-122.62390136718749, 38.24842651622814)),
(ST_MakePoint(-122.684326171875, 38.285624966683756)),
(ST_MakePoint(-122.78114318847655, 38.25543637637947)),
(ST_MakePoint(-122.89512634277345, 38.313107227858914));

CREATE TABLE to_pts (
id serial primary key,
geom geometry(point, 4326)
);
INSERT INTO to_pts(geom)
VALUES
(ST_MakePoint(-121.58020019531249, 39.12792964388499)),
(ST_MakePoint(-121.38519287109375, 38.989302551359515)),
(ST_MakePoint(-121.56372070312499, 39.51887357127223)),
(ST_MakePoint(-122.00042724609374, 39.191819549771694));
``````

Afterwards I'm basically using your logic with the small change mentioned up top.

``````WITH all_pairs AS (
SELECT f.id AS fid, f.geom as fgeom,
t.id as tid, t.geom as tgeom
FROM from_pts AS f,
to_pts AS t
),
vertices AS (
SELECT fid, tid,
(SELECT id
FROM norcal_2po_4pgr
ORDER BY geom_way <-> fgeom
LIMIT 1) as fv,
(SELECT id
FROM norcal_2po_4pgr
ORDER BY geom_way <-> tgeom
LIMIT 1) as tv
FROM all_pairs
), pgr_result AS (
SELECT pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM norcal_2po_4pgr',
array_agg(fv), array_agg(tv),
directed := true
) from vertices
)
SELECT (pgr_dijkstra).* FROM pgr_result;
``````

To be able to obtain the user defined source and destination IDs, I would suggest to use a temporary lookup table and then join it with the pgr results.

``````CREATE TEMP TABLE vertices_lookup
AS
WITH all_pairs AS (
SELECT f.id AS fid, f.geom as fgeom,
t.id as tid, t.geom as tgeom
FROM from_pts AS f,
to_pts AS t
),
vertices AS (
SELECT fid, tid,
(SELECT id
FROM norcal_2po_4pgr
ORDER BY geom_way <-> fgeom
LIMIT 1) as fv,
(SELECT id
FROM norcal_2po_4pgr
ORDER BY geom_way <-> tgeom
LIMIT 1) as tv
FROM all_pairs
)
SELECT * FROM vertices;

WITH pgr_result AS (
SELECT pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM norcal_2po_4pgr',
array_agg(fv), array_agg(tv),
directed := true
) FROM vertices_lookup
)
SELECT (pgr_dijkstra).*, a.fid, a.tid FROM pgr_result
JOIN vertices_lookup a
ON (pgr_dijkstra).start_vid = a.fv
AND (pgr_dijkstra).end_vid = a.tv;
``````
• Didn't know that passing source and target as arrays is possible... Now I know 😏 This should help a lot... May 25, 2022 at 18:58
• It now works really fast, but how do I obtain the 'fid','tid' values from my shortest path table? I get the following error when I use SELECT fid, tid, pgr_Dijkstra & SELECT fid, tid, (pgr_dijkstra).* ERROR: column "vertices.fid" must appear in the GROUP BY clause or be used in an aggregate function LINE 54: SELECT fid, tid, pgr_Dijkstra(
– MJM
May 27, 2022 at 15:34
• One way to do this is to create vertices as a temporary table and after you have obtained the results from pgr join it back with the vertices table which will yield the fid and tid values. May 28, 2022 at 12:09
• @MJM I added a suggestion and updated the answer how you could do accomplish this. May 29, 2022 at 18:04
• @TimothyDalton thank you for your amazing help.
– MJM
May 30, 2022 at 14:38