[pgrouting-users] Performance problems with pgr_dijkstra

Eric Scheibler email at eric-scheibler.de
Tue Feb 10 14:34:59 PST 2015


I have some problems with the performance of the dijkstra routing algorithm and I hope, that someone
can help me with that.

I started my routing experiments with the Openstreetmap database of Saxony (German state) and
created a routing table with the program osm2po. First tries with the whole routing table with
934102 rows took several seconds to finish. So I created a temporary routing table with much less
rows: I've extracted only a subset of rows around the start and destination vertex. This table only
contained about 5000 rows and the dijkstra routing algorithm took about 60 ms to complete. The route
is intended for walkers and approximately 1000 meters long. Very good result 

Now I upgraded to the whole osm map of Europe and again created the routing table with osm2po. This
table has about 78300000 rows. So I created the temp routing table again, filled it with almost the
same 5000 rows and took the same start and destination points. But when I run the dijkstra algorithm
on this table, it runs for about 2.1 seconds. That's also not so bad but much more then the 60 ms
from the Saxony map. Both tables got an index at the id, source and target fields. I've repeated the
routing query at the temp routing table but got always the same process time.

I don't understand, why the procedure lasts so much longer at the map of Europe although both
temporary routing tables are almost identical in size and don't depend on the rest of the databases
(no joins or other complicated stuff). Maybe someone has an idea and can point me in the right

Here is my routing query although there is nothing special on it:
SELECT seq, id1 AS node, id2 AS edge_id, cost FROM pgr_dijkstra('select id, source, target, cost from tmp_routing', 12345, 67890, false, false);
I use Postgresql 9.1, postgis 2.0 and pgrouting 2.0.

Thank you in advance
Best regards
Eric Scheibler
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: Digital signature
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20150210/4c55b394/attachment.pgp>

More information about the Pgrouting-users mailing list