[pgrouting-users] Performance problems with pgr_dijkstra

Eric Scheibler email at eric-scheibler.de
Wed Feb 11 03:23:08 PST 2015

Hallo Daniel,

Daniel Kastl <daniel at georepublic.de> schrieb am 11.02.2015, 10:54 +0900:
>> 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
>> direction.
>First of all I'm not sure, if I really understand what you mean with
>"creating a temporary table". Did you run "CREATE TEMP TABLE ..."?

Okay, let me explain that shortly. Maybe you have another solution for my problem at all. I use
python to create a routing server application. I call the necessary SQL commands within python. So I
start by creating a normal table like this:
CREATE TABLE tmp_routing AS SELECT * FROM eu_2po_4pgr LIMIT 0;

Then I fill it with rows from the eu_2po_4pgr table until both start and destination points are
included. So I get the described temp table with about 5000 rows. Reason for that is, that I
need this table more than once, so it's more efficient to create it first and then take it as long
as required.

A major problem for routing are ways, which aren't connected to the main street network, for example
a way in the backyard or at a roof garden. Cause my router is for walkers, I can't only use streets
but all other tracks and paths. So the first step is to verify, that the closest way from route
start and destination is connected to the main street network. Otherwise the routing algorithm can't
find a solution.

To achieve that, I take the closest intersection with at least one big street and calculate a route
from the potential best starting way to that intersection. Cause it's very likely that an
intersection with a big road is connected to the main street network, I get the surety, that my
potential start way is also connected to the main network. After I've verified my starting and
destination way, I can run the actual routing query. When I'am done, I delete the created table

So I need at least 3 but often more routing queries and so the relatively long process time of 2.1
seconds bothers me. For only one routing query I would be fine but I don't know how to deal
with that dead way networks.

So I have two chances to improve my router:
1. I find a better solution for the dead way problem. Then I only would need one routing query.
2. I try to find out, why the routing query takes so much longer at the bigger database although
it's a routing table with almost the same size.

>You're right, that with pgRouting the amount of data selected from the
>network table matters. And the fastest way to select only a part of the
>network table is by selecting a bounding box. You should have an index on
>your geometry column as well. Then you don't need to create temporary

Do you have an example for a bounding box? How to determine the box size? I know the distance
between the starting and destination point in meters. Could that be used?

>Back to your question: as far as I remember, the size of ID's can matter. I
>experienced this when I used data, that had already source and target ID's
>in place, which all had the same number of digits. Renumbering (starting
>from 1) helped to improve the speed. Though I can't tell this is the reason
>in your case.

Very interesting. You could be right. I created a temp routing table in the Saxony database, took
start and destination vertex from my program and verified the process time and the result (4 rows
and 60 ms for a very short way, approximately 100 meters). Then I dumped the created table with
pg_dump and restored it into the Europe database. Now the same routing query runs as fast as in the
small database. So maybe the higher source and target id's are responsible for that. Do you have an
idea how to recreate the source and target id's, starting by 1?

>Have you also run VACUUM and ANALYZE on your table?


Best regards
-------------- 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/20150211/886c1687/attachment.pgp>

More information about the Pgrouting-users mailing list