Why my mobile GPS routing calculates routes almost instantly and using pgRouting in my robust PC is so time costly ?


My test:

In my cellphone (Android 4.2.2 - 1G RAM - Dual core - Arm v9) I have iGo Primo. In my PC ( 8G RAM - Core i5 ) I have Postgre + PostGIS + pgRouting

Table OSM Planet "planet_osm_line" with previous work:

alter table planet_osm_line add column source integer;
alter table planet_osm_line add column target integer;
select pgr_createTopology('planet_osm_line', 0.0001, 'way', 'osm_id');

select * from planet_osm_line where name like '%BR-040%' // (source : 2751784)
select * from planet_osm_line where name like '%BR-101%' // (target : 2040999)

SELECT seq, id1 AS node, id2 AS edge, cost, name, way
  FROM pgr_dijkstra('SELECT osm_id as id, source, target, st_length(way) as cost FROM planet_osm_line',  2751784, 2040999, false, false  ) as di 
  JOIN planet_osm_line pt
  ON di.id2 = pt.osm_id ;

The route is (both Brazil Highway):

Source: BR-040

Target: BR-101

My cellphone do the job in less than two seconds and my PC takes more than 3 minutes (only the SELECT route - pgr_dijkstra - part).

  • 4
    Because your mobile routing is being done on google's cloud (or similar infrastructure)? Could your 'robust PC' search something the size of the internet as quickly as google?
    – Spacedman
    Commented Jan 22, 2014 at 13:49
  • I don't think so. Even I'm not connected (like iGo Amigo/Primo Maps/Routing GPS), the route calculation is much more faster than my PC.
    – Magno C
    Commented Jan 22, 2014 at 14:01
  • Does your mobile app have a simpler data set than your pgRouting data? Or maybe you need some optimisations/spatial indexing. Oh well...
    – Spacedman
    Commented Jan 22, 2014 at 14:05
  • 1
    Have you tried various things? eg: gis.stackexchange.com/questions/16886/…
    – Spacedman
    Commented Jan 22, 2014 at 14:06
  • 2
    Please people, STOP upvoting google's cloud comment. I'm OFFLINE for sure!
    – Magno C
    Commented Jan 22, 2014 at 15:42

3 Answers 3


Probably because it uses pre-calculated routes.

As an example of an open source routing app with pre-calculated routes, OSRM uses contraction hierarchies to create shortcuts: http://algo2.iti.kit.edu/routeplanning.php

PgRouting just creates the relations between source and target with the pgr_network_topology function. http://workshop.pgrouting.org/chapters/topology.html

pgRouting allows you to change conditions in real time. Does your phone app allow you to do that? Like, for example, add traffic data and recalculate the route depending on this new data?

  • 1
    I think Waze do that. waze.com
    – Magno C
    Commented Jan 22, 2014 at 15:24
  • 1
    Nowadays, almost all routing apps do it offline with a pre-calculated graph. Like OsmAnd too. Commented Jan 22, 2014 at 15:25
  • 2
    IMO, pre-calculated graph in one thing and pre-calculated route is another thing. pgr_createTopology creates a pre-calculated graph (source and target columns connects the points). A pre-calculated route needs to "guess" where I want to go.
    – Magno C
    Commented Jan 22, 2014 at 15:31
  • 1
    I'm sure iGo is offline. Here in Brasil 3G is expensive and low quality (if you coming for World Cup don't try to use it!) and I must keep my mobile offline almost all the time.
    – Magno C
    Commented Jan 22, 2014 at 15:34
  • Then it should be something related to pre-calculated graphs. If you are looking for something faster on the server side, take a look at project-osrm.org Commented Jan 22, 2014 at 15:42

I think the best answer was pointed by @Spacedman here in this post:

How can I optimize pgrouting for speed?

Mario Miler says:

In my experience, if using pgrouting on all dataset (table) then there is no great benefit from Postgres engine. Index is not even used so its useless. On every query whole table is loaded into memory. shared buffers and caches also didn't give any performance benefit because every query loads all the table into memory. If anyone has succeed to reuse loaded data in memory for subsequent queries, please tell us. Only possible performance increase I see in SDD drives, but I have never tested it. More memory only allows more concurrent queries, not performance. – Mario Miler Nov 15 '11 at 16:27

pgRouting "modus operandi" (pgr_dijkstra function) is the source of bad performance.

  • 2
    A couple of years ago I tried to improve pgRouting performance. We improved it a little with a custom algorithm that relied on pgRouting (Shooting Star) as background. The documentation is in Spanish, but maybe it can be useful for you: delawen.github.io/Taller-Routing On slide 7 you can see that Dijkstra is not even the best of pgRouting. (From slide 36 on is the idea we tried to implement) Commented Jan 22, 2014 at 16:04
  • Thank you so much for your effort. I need to find new ways to improve my application and you help a lot.
    – Magno C
    Commented Jan 22, 2014 at 16:06

It takes a long time to solve the network, but once it is done you "just" need to query the graph. Finding the route is thus very fast if you store the graph of your network and it is well indexed.

  • Indeed. Graph creation consumes a huge amount of time, but even this, the routing calculation is too slow.
    – Magno C
    Commented Jan 22, 2014 at 14:03
  • I've edited my question. Give a look.
    – Magno C
    Commented Jan 22, 2014 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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