Why is any pgr_* routing function taking forever based on OSM data in an pgrouting enabled DB

Question

I loaded the German OSM dataset into the pgrouting DB by using osm2po 4.7.7. Everything works fine i have osm2po set up via it's config and it's working like a charm through it's Java part.

I had the *_2po_4pgr table imported without any problems. Even the *2po_v table gets imported, though I don't completely understand the relation of this table.

I executed the pgr_createTopology function which ran for quite a while (12000secs) while calculating all 6m edges. I thought this would do the deal, but still it's unbearably slow.

I would like to know if i forgot something. I was thinking of using pgRouting instead of the java library but at the moment its performance-wise just out of comparison.

Answer 1

Problem with pgRouting performance seems to be that new pgr_astar and pgr_dijkstra use whole graph (which guarantees solution if there is one). Simple solution to get better performance is limit used graph to smaller area. It has it own problems like sometimes it may create graphs that cannot be solved

 (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1 WHERE l1.source =7 OR l1.target = 12) 

Creates BBOX over source and target collection and expands it 0.1 degrees, then same query is used to limit graph size in pgr_ query

Dijkstra from 1.2s to ~65ms

SELECT  seq, id1 AS node, id2 AS edge, g.geom_way as the_geom
    FROM pgr_dijkstra(
            'SELECT id, source, target, cost FROM hh_2po_4pgr as r, 
            (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1    WHERE l1.source =7 OR l1.target = 12) as box
            WHERE r.geom_way && box.box',
            7, 12, false, false
    ) as r INNER JOIN hh_2po_4pgr as g ON r.id2 = g.id ;

A* from 2s to ~50ms

SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_astar(
           'SELECT id, source, target, cost, x1,y1,x2,y2 FROM hh_2po_4pgr as r, 
             (SELECT ST_Expand(ST_Extent(geom_way),0.1) as box  FROM hh_2po_4pgr as l1    WHERE l1.source =7 OR l1.target = 12) as box
            WHERE r.geom_way && box.box',
            7, 12, false, false
    );

osm2po was used to import data (finland-latest) into postgis table. gist index added to geom_way column and full vacuum analyze run for database. shared memory 1G . workmem 512M

Answer 2

Use this guide to set up indexes for a spatial database. Here is the gist of it:

 1. create indexes on ID, source and target columns.
 2. create index using GIST on geom column.
 3. vacuum
 4. cluster on geom column
 5. analyze

for my _4pgr and _vertex tables, only the source and target columns had indexes after the import (osm2po-core-5.1.0).

Answer 3

I finally came to the conclusion that it's best to put the whole graph (including indices) on a separate tablespace which permanently resides in memory using a ramdisk.

For setting up the ramdisk on Ubuntu 13.04 I used the following instructions and must say it's working pretty good (it's includes instructions for reloading the data into memory after a restart/reboot).

Next week I will get a hand on new SSD's (1GB/s read) and try to compare the performance.

As far as I see it's the only solution for keeping a 1M+ rows graph permanently accessible, since there a continuous random reads happening.