[pgrouting-users] Speed when using big maps

pgRouting pgrouting-users
1

Hi everyone,

I’ve just started testing pgRouting on a big network (Germany) and want to use the whole Europe map later, but it’s pretty slow.
I takes around 2,5 min to calculate one route and it makes no difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up?
I have already indices to ‘source’ and ‘target’ and id is primary key, but I don’t know how to use bounding boxes.

Furthermore I’ve noticed: when selecting only a part of the graph (keeping in mind that the area of the dijkstra expansion is loaded) it gets much faster.
Is this similar to what the bounding box would do?

To understand this I have some questions about how pgRouting works:
Does pgRouting reloads the road data on every request and does the slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse it for further requests?

As I want to execute a lot of kDijkstras consecutively I guess only bounding boxes won’t make it fast enough.

Thanks in advance!

2

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I’ve just started testing pgRouting on a big network (Germany) and want
to use the whole Europe map later, but it’s pretty slow.
I takes around 2,5 min to calculate one route and it makes no difference
if the route distance is 7km or 700km.

Is there anything I can do to speed it up?
I have already indices to ‘source’ and ‘target’ and id is primary key,
but I don’t know how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I’ve noticed: when selecting only a part of the graph
(keeping in mind that the area of the dijkstra expansion is loaded) it
gets much faster.
Is this similar to what the bounding box would do?

Then only load the part of the roads needed to solve the graph. The more roads you load the long it takes to load the data and to solve the problem. Also astar and trsp are both faster then Dijkstra.

To understand this I have some questions about how pgRouting works:
Does pgRouting reloads the road data on every request and does the slow
calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse it for
further requests?

No, not currently because there is no place to load the graph into memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess only
bounding boxes won’t make it fast enough.

If you need many routes from a single start point, then you should look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can load data like a barbell using three bbox queries and union the results together. So, query 1, gets all roads for some radius around the start point, query2, gets all roads for some radius around the end point, and query 3, gets all the highways only in the bounding box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

3

Thanks Steve!
But I still have some questions:

To understand this I have some questions about how pgRouting works:
Does pgRouting reloads the road data on every request and does the
slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse it
for further requests?

No, not currently because there is no place to load the graph into memory in the database that is persistent.

What do you mean? Is there not enough space on the RAM for the whole road network?
And does "not currently" mean that someone is working on that? :wink: Or are there any ideas and hints to achieve that?
Because the most recent posting I've found about that is this one: http://lists.osgeo.org/pipermail/pgrouting-users/2012-December/001379.html

As I want to execute a lot of kDijkstras consecutively I guess only
bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should look at pgr_kdijkstra().

Yes, this is what I am going to do. But in fact I want to calculate a many-to-many matrix.
So I have to run the one-to-many Dijkstra n times, which would cause a huge waste of time when rebuilding the graph n times

Regards,
Philipp

-----Ursprüngliche Nachricht-----
Von: pgrouting-users-bounces@lists.osgeo.org [mailto:pgrouting-users-bounces@lists.osgeo.org] Im Auftrag von Stephen Woodbridge
Gesendet: Donnerstag, 24. Oktober 2013 15:04
An: pgrouting-users@lists.osgeo.org
Betreff: Re: [pgrouting-users] Speed when using big maps

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I've just started testing pgRouting on a big network (Germany) and
want to use the whole Europe map later, but it's pretty slow.
I takes around 2,5 min to calculate one route and it makes no
difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up?
I have already indices to 'source' and 'target' and id is primary key,
but I don't know how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I've noticed: when selecting only a part of the graph
(keeping in mind that the area of the dijkstra expansion is loaded) it
gets much faster.
Is this similar to what the bounding box would do?

Then only load the part of the roads needed to solve the graph. The more roads you load the long it takes to load the data and to solve the problem. Also astar and trsp are both faster then Dijkstra.

To understand this I have some questions about how pgRouting works:
Does pgRouting reloads the road data on every request and does the
slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse it
for further requests?

No, not currently because there is no place to load the graph into memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess only
bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can load data like a barbell using three bbox queries and union the results together. So, query 1, gets all roads for some radius around the start point, query2, gets all roads for some radius around the end point, and query 3, gets all the highways only in the bounding box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

4

On 10/25/2013 4:49 AM, Philipp Hamm wrote:

Thanks Steve! But I still have some questions:

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse
it for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

What do you mean? Is there not enough space on the RAM for the whole
road network?

pGRouting runs as a postgresql database extension, which means we have to play within the rules and constraints of extensions to the database.

The database lives effectively forever in memory and it would not be nice to other users if we just grabbed a huge chunk of memory. What would happen if 10 or 100 users all grabbed a huge chunk. Then there is another issue of how long do we hold the memory?, what if the user forgets to free the memory? what happens if someone restarts the database how do we know if we have to reload the graph, etc, etc, etc

All of the current commands have a lifespan of the query. everything gets done in a single query and everything is released at the end of the query.

And does "not currently" mean that someone is working
on that? :wink: Or are there any ideas and hints to achieve that? Because
the most recent posting I've found about that is this one:
http://lists.osgeo.org/pipermail/pgrouting-users/2012-December/001379.html

No, there are some ideas bouncing around, but mostly these focus on things like the kdijkstra one to many. It would be possible to do a many to many, using kdijstra like code the builds the graph once, and then solve multiple kdijkstra solutions on it. This would be a good project for a programmer that want to contribute to pgRouting with a pull request. Or if there is some funding we would be happy to tackle something like this.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

Yes, this is what I am going to do. But in fact I want to calculate a
many-to-many matrix. So I have to run the one-to-many Dijkstra n
times, which would cause a huge waste of time when rebuilding the
graph n times

Yes, I understand as I mentioned above and opened:
https://github.com/pgRouting/pgrouting/issues/205

Regards,
   -Steve

Regards, Philipp

-----Ursprüngliche Nachricht----- Von:
pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] Im Auftrag von
Stephen Woodbridge Gesendet: Donnerstag, 24. Oktober 2013 15:04 An:
pgrouting-users@lists.osgeo.org Betreff: Re: [pgrouting-users] Speed
when using big maps

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I've just started testing pgRouting on a big network (Germany) and
want to use the whole Europe map later, but it's pretty slow. I
takes around 2,5 min to calculate one route and it makes no
difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up? I have already indices
to 'source' and 'target' and id is primary key, but I don't know
how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I've noticed: when selecting only a part of the graph
(keeping in mind that the area of the dijkstra expansion is loaded)
it gets much faster. Is this similar to what the bounding box would
do?

Then only load the part of the roads needed to solve the graph. The
more roads you load the long it takes to load the data and to solve
the problem. Also astar and trsp are both faster then Dijkstra.

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph? If
so, is it possible to load the graph into the memory and reuse it
for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can
load data like a barbell using three bbox queries and union the
results together. So, query 1, gets all roads for some radius around
the start point, query2, gets all roads for some radius around the
end point, and query 3, gets all the highways only in the bounding
box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

5

In our experience with this, just getting a few SSDs in a RAID solves the performance issues of large networks, but it may be similar cost to pay for the dev work Stephen highlights below, and would benefit everyone.

In theory, on the OS level, you could have the database pointed at a logical disk which is really just memory, but then you need to deal with persistence issues, and reboot, etc., but it's not a difficult problem space. I can't find it at the moment, but I think we had a pgRouting mailing list discussion about this within the last year, so you might look to that as well.

Best,
Steve

  Stephen V. Mather
GIS Manager
(216) 635-3243 (Work)
clevelandmetroparks.com

________________________________________
From: pgrouting-users-bounces@lists.osgeo.org [pgrouting-users-bounces@lists.osgeo.org] on behalf of Stephen Woodbridge [woodbri@swoodbridge.com]
Sent: Friday, October 25, 2013 10:08 AM
To: pgrouting-users@lists.osgeo.org
Subject: Re: [pgrouting-users] Speed when using big maps

On 10/25/2013 4:49 AM, Philipp Hamm wrote:

Thanks Steve! But I still have some questions:

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse
it for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

What do you mean? Is there not enough space on the RAM for the whole
road network?

pGRouting runs as a postgresql database extension, which means we have
to play within the rules and constraints of extensions to the database.

The database lives effectively forever in memory and it would not be
nice to other users if we just grabbed a huge chunk of memory. What
would happen if 10 or 100 users all grabbed a huge chunk. Then there is
another issue of how long do we hold the memory?, what if the user
forgets to free the memory? what happens if someone restarts the
database how do we know if we have to reload the graph, etc, etc, etc

All of the current commands have a lifespan of the query. everything
gets done in a single query and everything is released at the end of the
query.

And does "not currently" mean that someone is working
on that? :wink: Or are there any ideas and hints to achieve that? Because
the most recent posting I've found about that is this one:
http://lists.osgeo.org/pipermail/pgrouting-users/2012-December/001379.html

No, there are some ideas bouncing around, but mostly these focus on
things like the kdijkstra one to many. It would be possible to do a many
to many, using kdijstra like code the builds the graph once, and then
solve multiple kdijkstra solutions on it. This would be a good project
for a programmer that want to contribute to pgRouting with a pull
request. Or if there is some funding we would be happy to tackle
something like this.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

Yes, this is what I am going to do. But in fact I want to calculate a
many-to-many matrix. So I have to run the one-to-many Dijkstra n
times, which would cause a huge waste of time when rebuilding the
graph n times

Yes, I understand as I mentioned above and opened:
https://github.com/pgRouting/pgrouting/issues/205

Regards,
   -Steve

Regards, Philipp

-----Ursprüngliche Nachricht----- Von:
pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] Im Auftrag von
Stephen Woodbridge Gesendet: Donnerstag, 24. Oktober 2013 15:04 An:
pgrouting-users@lists.osgeo.org Betreff: Re: [pgrouting-users] Speed
when using big maps

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I've just started testing pgRouting on a big network (Germany) and
want to use the whole Europe map later, but it's pretty slow. I
takes around 2,5 min to calculate one route and it makes no
difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up? I have already indices
to 'source' and 'target' and id is primary key, but I don't know
how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I've noticed: when selecting only a part of the graph
(keeping in mind that the area of the dijkstra expansion is loaded)
it gets much faster. Is this similar to what the bounding box would
do?

Then only load the part of the roads needed to solve the graph. The
more roads you load the long it takes to load the data and to solve
the problem. Also astar and trsp are both faster then Dijkstra.

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph? If
so, is it possible to load the graph into the memory and reuse it
for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can
load data like a barbell using three bbox queries and union the
results together. So, query 1, gets all roads for some radius around
the start point, query2, gets all roads for some radius around the
end point, and query 3, gets all the highways only in the bounding
box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

6

Postgresql is very good at page management and caching pages which is why you are probably not seeing a huge performance pick up. Many of the newer raid controllers have the option of add SSD for caching to optimize reading and handling write backs to spinning disks. Since pgRouting is mostly a build once, then read mostly read it might benefit from this in the reading of the edges.

But, in addition to reading the edges, allocate huge arrays to load all the edges into memory, then we still have to build the graph with those edges which requires allocating more memory and writing all the edges into that, then free the edge array all of which is also a big cost.

So the ideal situation is to build it once and reuse it if possible.
This is a little complicated in that you have to make sure that the graph and intermediate structures all get reinitialized.

Or hold the array of edges if we have to rebuild the graph multiple time. This is fairly trivial to implement.

-Steve W

On 10/25/2013 10:26 AM, Stephen V. Mather wrote:

In our experience with this, just getting a few SSDs in a RAID solves
the performance issues of large networks, but it may be similar cost
to pay for the dev work Stephen highlights below, and would benefit
everyone.

In theory, on the OS level, you could have the database pointed at a
logical disk which is really just memory, but then you need to deal
with persistence issues, and reboot, etc., but it's not a difficult
problem space. I can't find it at the moment, but I think we had a
pgRouting mailing list discussion about this within the last year, so
you might look to that as well.

Best, Steve

Stephen V. Mather GIS Manager (216) 635-3243 (Work)
clevelandmetroparks.com

________________________________________ From:
pgrouting-users-bounces@lists.osgeo.org
[pgrouting-users-bounces@lists.osgeo.org] on behalf of Stephen
Woodbridge [woodbri@swoodbridge.com] Sent: Friday, October 25, 2013
10:08 AM To: pgrouting-users@lists.osgeo.org Subject: Re:
[pgrouting-users] Speed when using big maps

On 10/25/2013 4:49 AM, Philipp Hamm wrote:

Thanks Steve! But I still have some questions:

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request
and does the slow calculation results only from fetching the
graph? If so, is it possible to load the graph into the memory
and reuse it for further requests?

No, not currently because there is no place to load the graph
into memory in the database that is persistent.

What do you mean? Is there not enough space on the RAM for the
whole road network?

pGRouting runs as a postgresql database extension, which means we
have to play within the rules and constraints of extensions to the
database.

The database lives effectively forever in memory and it would not be
nice to other users if we just grabbed a huge chunk of memory. What
would happen if 10 or 100 users all grabbed a huge chunk. Then there
is another issue of how long do we hold the memory?, what if the
user forgets to free the memory? what happens if someone restarts
the database how do we know if we have to reload the graph, etc, etc,
etc

All of the current commands have a lifespan of the query. everything
gets done in a single query and everything is released at the end of
the query.

And does "not currently" mean that someone is working on that? :wink:
Or are there any ideas and hints to achieve that? Because the most
recent posting I've found about that is this one:
http://lists.osgeo.org/pipermail/pgrouting-users/2012-December/001379.html

No, there are some ideas bouncing around, but mostly these focus on
things like the kdijkstra one to many. It would be possible to do a
many to many, using kdijstra like code the builds the graph once, and
then solve multiple kdijkstra solutions on it. This would be a good
project for a programmer that want to contribute to pgRouting with a
pull request. Or if there is some funding we would be happy to
tackle something like this.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you
should look at pgr_kdijkstra().

Yes, this is what I am going to do. But in fact I want to calculate
a many-to-many matrix. So I have to run the one-to-many Dijkstra n
times, which would cause a huge waste of time when rebuilding the
graph n times

Yes, I understand as I mentioned above and opened:
https://github.com/pgRouting/pgrouting/issues/205

Regards, -Steve

Regards, Philipp

-----Ursprüngliche Nachricht----- Von:
pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] Im Auftrag von
Stephen Woodbridge Gesendet: Donnerstag, 24. Oktober 2013 15:04
An: pgrouting-users@lists.osgeo.org Betreff: Re: [pgrouting-users]
Speed when using big maps

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I've just started testing pgRouting on a big network (Germany)
and want to use the whole Europe map later, but it's pretty slow.
I takes around 2,5 min to calculate one route and it makes no
difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up? I have already
indices to 'source' and 'target' and id is primary key, but I
don't know how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I've noticed: when selecting only a part of the
graph (keeping in mind that the area of the dijkstra expansion is
loaded) it gets much faster. Is this similar to what the bounding
box would do?

Then only load the part of the roads needed to solve the graph.
The more roads you load the long it takes to load the data and to
solve the problem. Also astar and trsp are both faster then
Dijkstra.

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse
it for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won't make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can
load data like a barbell using three bbox queries and union the
results together. So, query 1, gets all roads for some radius
around the start point, query2, gets all roads for some radius
around the end point, and query 3, gets all the highways only in
the bounding box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

7

Hi Philipp ,

You can take a look at the link below .
https://github.com/pgRouting/pgrouting/wiki/Details-and-how-to-use-guide-.

The pgr_pastar function doesnt load the whole graph initially , instead it loads only the partition that is required by the path computation algorithm. This was developed as a gsoc project this year keeping in mind the problem related with very large network. The thing is that it hasn’t been tested very extensively so it hasn’t been yet included with the pgrouting package , you can still use it using the above link , it has all the useful infomation regarding its installation and other pre-processing stuffs.

Hope this helps .

···

On Fri, Oct 25, 2013 at 8:44 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Postgresql is very good at page management and caching pages which is why you are probably not seeing a huge performance pick up. Many of the newer raid controllers have the option of add SSD for caching to optimize reading and handling write backs to spinning disks. Since pgRouting is mostly a build once, then read mostly read it might benefit from this in the reading of the edges.

But, in addition to reading the edges, allocate huge arrays to load all the edges into memory, then we still have to build the graph with those edges which requires allocating more memory and writing all the edges into that, then free the edge array all of which is also a big cost.

So the ideal situation is to build it once and reuse it if possible.
This is a little complicated in that you have to make sure that the graph and intermediate structures all get reinitialized.

Or hold the array of edges if we have to rebuild the graph multiple time. This is fairly trivial to implement.

-Steve W

On 10/25/2013 10:26 AM, Stephen V. Mather wrote:

In our experience with this, just getting a few SSDs in a RAID solves
the performance issues of large networks, but it may be similar cost
to pay for the dev work Stephen highlights below, and would benefit
everyone.

In theory, on the OS level, you could have the database pointed at a
logical disk which is really just memory, but then you need to deal
with persistence issues, and reboot, etc., but it’s not a difficult
problem space. I can’t find it at the moment, but I think we had a
pgRouting mailing list discussion about this within the last year, so
you might look to that as well.

Best, Steve

Stephen V. Mather GIS Manager (216) 635-3243 (Work)
clevelandmetroparks.com

________________________________________ From:
pgrouting-users-bounces@lists.osgeo.org
[pgrouting-users-bounces@lists.osgeo.org] on behalf of Stephen
Woodbridge [woodbri@swoodbridge.com] Sent: Friday, October 25, 2013
10:08 AM To: pgrouting-users@lists.osgeo.org Subject: Re:
[pgrouting-users] Speed when using big maps

On 10/25/2013 4:49 AM, Philipp Hamm wrote:

Thanks Steve! But I still have some questions:

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request
and does the slow calculation results only from fetching the
graph? If so, is it possible to load the graph into the memory
and reuse it for further requests?

No, not currently because there is no place to load the graph
into memory in the database that is persistent.

What do you mean? Is there not enough space on the RAM for the
whole road network?

pGRouting runs as a postgresql database extension, which means we
have to play within the rules and constraints of extensions to the
database.

The database lives effectively forever in memory and it would not be
nice to other users if we just grabbed a huge chunk of memory. What
would happen if 10 or 100 users all grabbed a huge chunk. Then there
is another issue of how long do we hold the memory?, what if the
user forgets to free the memory? what happens if someone restarts
the database how do we know if we have to reload the graph, etc, etc,
etc

All of the current commands have a lifespan of the query. everything
gets done in a single query and everything is released at the end of
the query.

And does “not currently” mean that someone is working on that? :wink:
Or are there any ideas and hints to achieve that? Because the most
recent posting I’ve found about that is this one:
http://lists.osgeo.org/pipermail/pgrouting-users/2012-December/001379.html

No, there are some ideas bouncing around, but mostly these focus on
things like the kdijkstra one to many. It would be possible to do a
many to many, using kdijstra like code the builds the graph once, and
then solve multiple kdijkstra solutions on it. This would be a good
project for a programmer that want to contribute to pgRouting with a
pull request. Or if there is some funding we would be happy to
tackle something like this.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won’t make it fast enough.

If you need many routes from a single start point, then you
should look at pgr_kdijkstra().

Yes, this is what I am going to do. But in fact I want to calculate
a many-to-many matrix. So I have to run the one-to-many Dijkstra n
times, which would cause a huge waste of time when rebuilding the
graph n times

Yes, I understand as I mentioned above and opened:
https://github.com/pgRouting/pgrouting/issues/205

Regards, -Steve

Regards, Philipp

-----Ursprüngliche Nachricht----- Von:
pgrouting-users-bounces@lists.osgeo.org
[mailto:pgrouting-users-bounces@lists.osgeo.org] Im Auftrag von
Stephen Woodbridge Gesendet: Donnerstag, 24. Oktober 2013 15:04
An: pgrouting-users@lists.osgeo.org Betreff: Re: [pgrouting-users]
Speed when using big maps

On 10/24/2013 6:16 AM, Philipp Hamm wrote:

Hi everyone,

I’ve just started testing pgRouting on a big network (Germany)
and want to use the whole Europe map later, but it’s pretty slow.
I takes around 2,5 min to calculate one route and it makes no
difference if the route distance is 7km or 700km.

Is there anything I can do to speed it up? I have already
indices to ‘source’ and ‘target’ and id is primary key, but I
don’t know how to use bounding boxes.

You need to create a spatial index:

create index myroads_gidx on myroads using gist (the_geom);

Furthermore I’ve noticed: when selecting only a part of the
graph (keeping in mind that the area of the dijkstra expansion is
loaded) it gets much faster. Is this similar to what the bounding
box would do?

Then only load the part of the roads needed to solve the graph.
The more roads you load the long it takes to load the data and to
solve the problem. Also astar and trsp are both faster then
Dijkstra.

To understand this I have some questions about how pgRouting
works: Does pgRouting reloads the road data on every request and
does the slow calculation results only from fetching the graph?
If so, is it possible to load the graph into the memory and reuse
it for further requests?

No, not currently because there is no place to load the graph into
memory in the database that is persistent.

As I want to execute a lot of kDijkstras consecutively I guess
only bounding boxes won’t make it fast enough.

If you need many routes from a single start point, then you should
look at pgr_kdijkstra().

If your routes are long and you want to use highways, then you can
load data like a barbell using three bbox queries and union the
results together. So, query 1, gets all roads for some radius
around the start point, query2, gets all roads for some radius
around the end point, and query 3, gets all the highways only in
the bounding box between the start and end points.

-Steve

Thanks in advance!

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

_______________________________________________ Pgrouting-users
mailing list Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users