Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am using pgrouting on a postgis database created through osm2pgrouting. It performs very good on a limited dataset (3.5k ways, all shortest path A* searches < 20 ms).

However since I have imported a bigger bounding box (122k ways) from europe.osm the performance went down a lot (a shortest path costs around 900ms).

I would think that using A* most of those edges will never be visited as they are out of the way.

What I have done so far in an attempt to improve the speed:

  • Put an index on the geometry column (no noticeable effect)
  • Increased my memory from 8GB to 16GB
  • Change the postgresql memory settings (shared_buffers, effective_cache_size) from (128MB, 128MB) to (1GB, 2GB) (no noticeable effect)

I have a feeling that most of the work is being done in the C Boost library where the graph is being made so optimizing postgresql will not give me much better results. As I do minor changes to the set of rows I select for A* for every search I am a bit afraid that the boost library cannot cache my graph and has to rebuild all the 122k edges every time (even though it will only use a very limited subset every query). And I have no idea how much is spent doing that compared to the actual shortest path search.

Does any of you use pgrouting on a 122k or greater OSM dataset? What performance should I expect? What settings affect the performance most?

share|improve this question
1  
I'm not a pgrouting expert, but can you cache results, for example, if you know a common sub route is always used, can you precache it? therefore, you have to do less searches? Also, van you limit searches to Arterials and collectors? –  dassouki Nov 15 '11 at 11:27
1  
I allow free search atm, so i don think i can assume much for sub routes. Also I am caching the result of searches of the last x minutes, but that doesn't help me for new searches. I have a feeling that A* on this size should still be really fast as long as i can keep the entire graph static in memory. There must be people who route this way on a whole country who know how to improve the performance. –  mrg Nov 15 '11 at 12:10
1  
Another option would be to build an O/D matrix (origin/destination matrix). This is a technique we use in traffic engineering. split the network into zones, so let's say a large city could have 100 zones. Each zone would have a dummy centroid. Connect the centroid to your network via a dummy link. Then you can remodel your whole network as 100 x 100 trips (10,000 trips in total). When a user does a search, pgrouting has to find a route closed to the centroid or dummy link on the origin and destination side. –  dassouki Nov 15 '11 at 12:38
1  
Don't you get weird results if someone wants to go from 1 zone to the next but they get routed through their centroids? Or do you only use this when the zones are further apart? Your solution makes the most sense if customers want to get fastest from A to B, but in my case i have to deal with customers who want to walk,cycle,etc for leisure and would like to pick unique routes and not be forced to go via the standard route. –  mrg Nov 15 '11 at 13:41
2  
If you are looking for a multimodal solution (bike, walk, public tranportation, drive), you should really take a look at Portland, Oregon's TriMet multimodal routing site, which uses OpenTripPlanner: trimet.org/news/releases/oct15-rtp.htm –  RyanDalton Nov 15 '11 at 16:37

3 Answers 3

up vote 7 down vote accepted

When faced with tasks like this your primary objective is to be rational. Don't change params based on 'gut feeling'. While the gut seems to works for Hollywood it does not for us who live in the real world. Well, at least not my gut ;-).

You should:

  1. establish a usable and repeatable metric (like the time required by a pgrouting query)

  2. save metric results in a spreadsheet and average them (discard best and worst). This will tell you if the changes you are making are going in the right direction

  3. monitor your server using top and vmstat (assuming you're on *nix) while queries are running and look for significant patterns: lots of io, high cpu, swapping, etc. If the cpu is waiting for i/o then try to improve disk performance (this should be easy, see below). If the CPU is instead at 100% without any significant disk acticity you have to find a way to improve the query (this is probably going to be harder).

For the sake of simplicity I assume network is not playing any significant role here.

Improving database performance

Upgrade to the latest Postgres version. Version 9 is so much better that previous versions. It is free so you have no reason not not.

Read the book I recommended already here.

You really should read it. I believe the relevant chapters for this case are 5,6,10,11

Improving disk performance

  1. Get an SSD drive and put the whole database on it. Read performance will most-likely quadruple and write performance should also radically improve

  2. assign more memory to postgres. Ideally you should be able to assign enough memory so that the whole (or the hottest part) can be cached into memory, but not too much so that swapping occurs. Swapping is very bad. This is covered in the book cited in the previous paragraph

  3. disable atime on all the disks (add the noatime options to fstab)

Improving query perfomance

Use the tools described in the book cited above to trace your query/ies and find stops that are worth optimizing.

Update

After the comments I have looked at the source code for the stored procedure

https://github.com/pgRouting/pgrouting/blob/master/core/src/astar.c

and it seems that once the query has been tuned there is not much more room for improvement as the algorithm runs completely in memory (and, unfortunately on only one cpu). I'm afraid your only solution is to find a better/faster algorithm or one that can run multithreaded and then integrate it with postgres either by creating a library like pgrouting or using some middleware to retrieve the data (and cache it, maybe) and feed it to the algorithm.

HTH

share|improve this answer
    
I have read parts of the book you recommend. My dataset is still small enough to fit entirely into memory so i think disk performance shouldn't be a bottleneck (i will better check my resources when testing to confirm this). I think Postgresql only comes into play in the pgrouting process when it does a simple select * from table to feed the C Boost library with row/tuples to perform the real search ((can someone confirm this) so i fear that there isn't much to gain in Postgresql itself. Your answer seems very good for Postgresql performance but maybe not so for pgrouting specific performance. –  mrg Nov 15 '11 at 14:02
    
@mrg I actually had thought of that, but I wanted to be sure that you didn't leave out the low-hanging-fruit. Thinking of it you went from 20ms for 3.5k to 900ms for 122k which is, imho, not entirely bad. Good luck –  unicoletti Nov 15 '11 at 14:24
    
Solid State Drives do increase performance (similar speeds to what caching) –  Mapperz Nov 15 '11 at 14:57
    
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

I have just the same problem and was about to ask on mailing lists, so thanks to everybody!

I am using Shooting Star with a million and a half rows on the routing table. It takes almost ten seconds to calculate it. With 20k rows it takes almost three seconds. I need Shooting Star because I need the turn restrictions.

Here are some ideas I'm trying to implement:

  • On the SQL where pgRouting get the ways, use a st_buffer so it don't get all ways, but just the "nearby" ways:

    select * from shortest_path_shooting_star( 'SELECT rout.* FROM routing rout, (select st_buffer(st_envelope(st_collect(geometry)), 4) as geometry from routing where id = ' || source_ || ' or id = ' || target || ') e WHERE rout.geometry && e.geometry', source, target, true, true);

It improved the performance, but if the way needs to go outside the buffer, it can return a "no path found" error, so... big buffer? several calls increasing the buffer until it finds a way?

  • Fast routes cached

Like dassouki suggested, I will cache some "useful" routes so if the distance is too long, it can go through these fast routes and just have to find the way in and out of them.

  • Partition table by gis index

But I suppose that, if it goes to memory, it doesn't really matter... Should test it, anyway.

Please, keep posting if you find another idea.

Also, do you know if there is some compiled pgRouting for Postgres9?

share|improve this answer
    
+1 There appear to be some useful and constructive ideas here. Please note that if you would like your questions to be answered, then it's best to formulate them as a new question. Our FAQ will tell you how to proceed. –  whuber Nov 16 '11 at 14:59
    
Délawen, i have also been thinking about your first idea (ST_Buffer) and foresee the same problem. The advantage however could be 2 way: the dataset is smaller and thus faster and as more of the processing is being done in Postgresql you have ways again to optimize it. Atm i am using Ubuntu 11 where postgresql 8.4 is the latest version. –  mrg Nov 16 '11 at 15:42
    
mrg, I compiled pgRouting on a Ubuntu Maverick for PostgreSQL 9.0 without much problem. Postgis for PostgreSQL 9.0 can be found here: ppa.launchpad.net/pi-deb/gis/ubuntu maverick/main amd64 Packages –  Délawen Nov 16 '11 at 17:10
    
I came up with 2 ideas. 1) A combination of 'fast routes cached' and 'st_buffer'. That way you guarantee finding a route and people will not all be forced on the same route. 2) Only use postgis to fill a static graph (with either Boost (C), nx_spatial (Python), neo4j (Java), etc) and reuse that graph for every search query. –  mrg Nov 16 '11 at 17:49
    
What about lowering the cost (ie boosting the preference) for 'fast' edges like highways when the distance between start and end is bigger than a threshold? The boost factor could also be related to distance: larger for longer distances, smaller for shorter. –  unicoletti Nov 18 '11 at 8:48

We have just created a branch in git for a turn restricted shortest path @ https://github.com/pgRouting/pgrouting/tree/trsp

Sorry no documentation yet, but but if you ask questions on the pgRouting list I hang out there and will respond. This code runs much faster than shooting star and is based on Dijkstra algorithm.

-Steve

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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