Why mobile routing is so fast?

Question

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

EDIT:

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).

Answer 1

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?

Answer 2

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.

Answer 3

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.