Crash with simple A* query on European cartography

[drllanos]

Dear developers,

This is Diego R. Llanos, Professor of Computer Science at the University of Valladolid. We have installed pgRouting to perform Dijkstra searches on the European cartography (europe-latest.osm.pbf, January 28th 2015). After successfully installing the software and the cartography (version details below), we perform a simple query using the A* algorithm to find the shortest path between two adjacent nodes. Unfortunately, it crashed. The query follows:

select seq, id1 AS node, id2 AS edge, cost from pgr_astar('select id, source, target, cost, x1, y1, x2, y2 from eu_2po_4pgr', 8324560, 8324561, false, false);

The result is always:

ERROR: invalid memory alloc request size 1073792000

The same problem appears with bidirectional A*, but not with Dijkstra or bidirectional Dijkstra.

We are using Ubuntu 14, with PostgreSQL 9.3.6, postgis 2.1.2, and pgrouting 2.0.0. Our system has 32Gb of RAM, and the configuration file for PostgreSQL has been created using pgtune.

It is very important for our research to solve this issue. Any help will be greatly appreciated.

Best regards,

            diego

[woodbri]

You are trying to load all the edges in table eu_2po_4pgr and you do not have enough memory. You should be loading only the edges in a bounding box about your start and end points. Try something like:

select id, source, target, cost, x1, y1, x2, y2 from eu_2po_4pgr where st_dwithin(geom, (select st_makeLine(geom) from vertice_table where id in (8324560, 8324561)), radius);

where radius is some distance in the units of the vertices_table srid
and vertice_table has each vertex and its location.

[drllanos]

Dear Mr. Woodbridge,

Thank you very much for your quick answer. One last thing. Could you please indicate us how should we set the "geom" parameter mentioned above? A quick search on the Internet makes me think that this is not straightforward. Thank you again for your support.

With very best regards,

            diego

[woodbri]

The "geom" should be a column in your table (it might be called "the_geom") that is created when the data is loaded. If you have not run through the pgrouting workshop, I strongly recommend doing that as it explains much of the basic concepts and terms that we use to describe the data and work with the data. pgrouting is dependent on postgis and we use lots of the postgis functions to manipulate the data.

[drllanos]

We will definitely attend the workshop. Thank you again!

[cvvergara]

It is clear to me that there is a problem that has to be solved:

1. ERROR: invalid memory alloc request size 1073792000 should not happen
2. A* and bidirectional A* has the problem
3. But not with Dijkstra or bidirectional Dijkstra. clearly he tried other algorithms

Maybe this issue is related to this other issue:
#288

I want to reproduce his error, but Europe is too big, so instead of Europe
I want to use 2 different sources:
open source data: mexico-latest.osm.pbf (82.9MB),
Government data: inegi data

1. Start from scratch. osm data first.

• use osm data directly
• check the column data types I get
• what are the steps to make the data work with pgRouting without using osm2pgrouting?
• try the 4 functions mentioned in the issue

2. start again:

• use osm data but with osm2pgrouting
• do I get the same columns (where it applies) ?
• are the data types the same as the raw osm data ?
• try the 4 functions again

3. Start again

• use inegi data
• what are the steps to make the data work with pgRouting?
• are the data types compatible
• try the 4 functions mentioned in the issue

If with that I cant reproduce the error, then I'll do 1) and 2) for Europe

[drllanos]

May I remark that the problem appears even when we try to find the shortest path between two adjacent nodes in the European cartography.

Thanks to all of you for your help.

          diego

[cvvergara]

I am putting on my "economics" backgroud shoes, that is ignore what I know about anything on this topic.
I just created this Log page, of my process
https://github.com/pgRouting/pgrouting/wiki/Log-of-setps-to-reproduce-%23291

[cvvergara]

Corrected a typo in the title of the log
https://github.com/pgRouting/pgrouting/wiki/Log-of-steps-to-reproduce-%23291

[cvvergara]

When loading all Europe's data I was able to reproduce the error: but I have also on pgr_dijkstra.
select seq, id1 AS node, id2 AS edge, cost from pgr_astar('select id, source, target, cost, x1, y1, x2, y2 from eu_2po_4pgr', 8324560, 8324561, false, false);
ERROR: invalid memory alloc request size 1073792000
Time: 62422.160 ms
osm_europe=# select seq, id1 AS node, id2 AS edge, cost from pgr_dijkstra('select id, source, target, cost from eu_2po_4pgr', 8324560, 8324561, false, false);
ERROR: invalid memory alloc request size 1073760000

[woodbri]

As I mentioned in the first comment above, you should be using a bbox query. This table has something like 46M edges and you need about 104 bytes per edge so that translates into more than 5 GB of memory just to hold the data, and that doesn't include any temporary data structures that might be needed. So depending on how much memory and swap space are available it could easily run out of memory. This will also be very dependent on the hardware and how much physical ram and swap the system has.

[cvvergara]

On the documentation on performance tips I added a comment about the size of the data.