[pgrouting-users] Newbie pgr_dijkstra performance question

Andrew_Harfoot · January 24, 2014, 3:45pm

Hi there,

I have been looking at pgrouting in the past week, and have a test installation using the following:

Win7 64bit on an i7 processor with 8Gb RAM
Postgres 9.2.4 64bit
Postgis 2.0.3-2 64bit
pgrouting 2.0 64bit

My test dataset is the Ordnance Survey Meridian roads dataset for Great Britain which has ~1.2 million edges.

I can successfully use the pgr_dijkstra function to generate routing, but the performance seems a little slow. My test route takes around 10 seconds to return in pgAdminIII, and so my first question is whether this is about what I should be expecting. I am not pre-filtering the ways being passed to pgr_dijkstra using a bounding box or such like

The second question is that whilst exploring the performance, I removed the indexes that pgr_createtopology had built on the source and target fields of the road data. To my surprise, this had no effect whatsoever on the performance of pgr_dijkstra, and after rebuilding them and looking at the index stats in pgAdminIII, this is reporting no usage of the indexes at all (I did rerun some routing queries after rebuilding the indexes!). Again, is this expected? It seems to contradict the recommendation to build the indexes in the pgr workshop:
http://workshop.pgrouting.org/chapters/topology.html#add-indices

Any thoughts appreciated,

Cheers,

Andy

--
Andy Harfoot

GeoData Institute
University of Southampton
Southampton
SO17 1BJ

Tel: +44 (0)23 8059 2719
Fax: +44 (0)23 8059 2849

www.geodata.soton.ac.uk

Stephen_Woodbridge1 · January 24, 2014, 4:21pm

On 1/24/2014 10:45 AM, Andrew Harfoot wrote:

Hi there,

I have been looking at pgrouting in the past week, and have a test
installation using the following:

Win7 64bit on an i7 processor with 8Gb RAM
Postgres 9.2.4 64bit
Postgis 2.0.3-2 64bit
pgrouting 2.0 64bit

My test dataset is the Ordnance Survey Meridian roads dataset for Great
Britain which has ~1.2 million edges.

I can successfully use the pgr_dijkstra function to generate routing,
but the performance seems a little slow. My test route takes around 10
seconds to return in pgAdminIII, and so my first question is whether
this is about what I should be expecting. I am not pre-filtering the
ways being passed to pgr_dijkstra using a bounding box or such like

You should definitely use the bbox filtering of the ways, otherwise you are loading ALL ways for every query. The way pgrouting works is on each query, it reads the ways, builds a graph and solves the graph to give you your results. The smaller the graph and number of ways need the faster it is.

The second question is that whilst exploring the performance, I removed
the indexes that pgr_createtopology had built on the source and target
fields of the road data. To my surprise, this had no effect whatsoever
on the performance of pgr_dijkstra, and after rebuilding them and
looking at the index stats in pgAdminIII, this is reporting no usage of
the indexes at all (I did rerun some routing queries after rebuilding
the indexes!). Again, is this expected?

Those indexes are not used when computing a route, they are only used to compute the topology and potentially during any post-processing you might decide to do to analyze the resultant path.

It seems to contradict the
recommendation to build the indexes in the pgr workshop:
http://workshop.pgrouting.org/chapters/topology.html#add-indices

Right, needed to compute the topology.

pgRouting is extremely flexible because we dynamically build the graph so we can easily do things like change the runtime solutions based on integrating traffic data, or eliminating edges in a disaster area, or changing the vehicle type or road preferences, etc. This comes at the cost of being the fastest possible solution.

If performance is more important than this flexibility, then you might want to look at Project-OSRM and osrm-tools as an alternative or to augment pgRouting.

Thanks,
-Steve

Any thoughts appreciated,

Cheers,

Andy

dkastl · January 24, 2014, 4:23pm

Hi Andrew,

See answers inline:

My test dataset is the Ordnance Survey Meridian roads dataset for Great
Britain which has ~1.2 million edges.

I can successfully use the pgr_dijkstra function to generate routing, but
the performance seems a little slow. My test route takes around 10 seconds
to return in pgAdminIII, and so my first question is whether this is about
what I should be expecting. I am not pre-filtering the ways being passed to
pgr_dijkstra using a bounding box or such like

This might be realistic, if you don't restrict your data by bbox
extent for example. pgRouting gets faster in general as less data you
select.

The second question is that whilst exploring the performance, I removed the
indexes that pgr_createtopology had built on the source and target fields of
the road data. To my surprise, this had no effect whatsoever on the
performance of pgr_dijkstra, and after rebuilding them and looking at the
index stats in pgAdminIII, this is reporting no usage of the indexes at all
(I did rerun some routing queries after rebuilding the indexes!). Again, is
this expected? It seems to contradict the recommendation to build the
indexes in the pgr workshop:
http://workshop.pgrouting.org/chapters/topology.html#add-indices

Did you run "VACUUM ANALYZE" afterwards?
If that information is missing in the workshop, then it should be added.

Regards,
Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

Andrew_Harfoot · January 24, 2014, 4:59pm

Thanks very much for the swift responses and clear explanations. I'll explore the BBOX filtering in more detail.