-
-
Notifications
You must be signed in to change notification settings - Fork 364
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
database crashes when a large number was entered as target id #32
Comments
I think I've found the same issue, I can reproduce a crash with the following line: for driving_distance, at least, the issue is that the boost graph library's adjancey_list, vector implementation, is allocating way too much memory. on the large numbers where it goes slow, what does your memory usage look like? |
This should be made into a test case for branch sew-devel-2_0 |
I can confirm this crashes 2.0 or pg 9.2. |
This does not crash trsp.
This will probably crash any of our boost implementations based on the way a graph is defined, because if I remember correctly, boost uses the vertex id to index into an array. I'll ask for more info on the boost list. |
Response from Boost list. On Wed, 15 May 2013, Stephen Woodbridge wrote:
For adjacency lists with vecS as the vertex container type (the default), there is an assumption that vertex numbers are in the range 0...num_vertices(g)-1 (inclusive). Thus, if you want to use a vertex number 10000, your graph will need to have at least 10001 vertices (before you add the edge). There are several data structures in the graph class that whose sizes are proportional to the number of vertices, so using very large vertex numbers can end up eating large amounts of memory. There should not be any limits on vertex counts other than available memory; the vertex index type is usually size_t or some other large-enough type if I remember correctly.
We have run it with larger numbers of vertices before (but more often with compressed_sparse_row_graph), so it should not be a limitation.
Are you using widely separated vertex numbers (i.e., you use large numbers as vertex IDs but don't actually have a large number of vertices)? If so, you can try using labeled_graph. Otherwise,
I suspect you are hitting a buffer overflow here, so that won't be easy to trap. Compiling with _GLIBCXX_DEBUG defined (with GCC) will turn some of those problems into assertion failures, but that still won't help you get an error code. I think the best thing to try would be to fix any overflow issues; you are likely to get an exception if you try to add more vertices or edges than will fit into virtual memory (which probably won't happen, since you will most likely run out of physical memory first, and it's up to your OS what happens in that case).
I see a few potential improvements:
OK. You might be able to attach to the database server itself with gdb as well, but Valgrind might be a more useful tool for seeing what the problem is. -- Jeremiah Willcock |
I have create a command line test tools in "develop" branch in src/dijkstra/tester/ that can be run in gdb or valgrind to evaluate changes to the boost wrapper. |
Does this affect pgRouting 2.0? |
Yes, and it will have to wait for post 2.0 for a fix. |
pgr_dijstra, pgr_ksp and pgr_dirvingDistance should work with big numbers |
I was reading in detail this issue, it mentions functions that we do not support any more like:
Instead of shortest_path use pgr_dijkstra
Instead of driving_distance use pgr_drivingdistance
Instead of turn_restrict_shortest_path use pgr_trsp
For the queries posted on this issue the functions in V2.1 work. |
with a normal number it's fast 4860887 152ms
with a larger number it becomes slow 34860887 19435ms
with an even larger number it crashes the database 134860887 after 28 seconds it crashed the database
I could reproduce it both under linux/postgres9 and windows/postgres8.4
under windows the timings are different 300 ms ,1500 ms ,250 ms the first two gave a result and the third also caused the database to crash
The SQL of the network used for testing is below. For the first two tests the number 134860887 is changed
DROP TABLE IF EXISTS network;
CREATE TABLE network (id integer PRIMARY KEY, source integer, target integer, cost float);
INSERT INTO network(id,source,target,cost) VALUES
(134034453,4401484,4401467,1491.35562366006),
(134034463,4401489,4401485,12.1046145920234),
(134034458,4401487,4401477,177.374061187772),
(134095663,4401465,4401476,2014.71852797927),
(134034459,4401485,4401487,201.968135582698),
(134095834,4401478,4401465,293.089423713387),
(134034461,4401488,4401489,418.687894948968),
(629678698,4415069,134860887,3776.78929640359),
(134034456,4401477,4401481,491.242305990214),
(134095832,4401482,4401487,76.1157555542275),
(134034465,4401490,4401489,1956.98967514724),
(134034454,4401483,4401486,1356.25190452873),
(134034462,4401487,4401478,17.2205341642897),
(134095833,4401477,4401478,2014.66722340654),
(134034455,4401485,4401483,53.5613132396201),
(134034467,4401488,4417647,2597.20106449741),
(134034452,4401483,4401467,350.071683838508),
(134034446,4401481,4401476,568.270689073724),
(134072383,4416226,4401482,322.141177736713),
(134034447,4401482,4401481,1522.8331095897),
(134034466,4401486,4401490,610.880612548267),
(134034468,4417647,4401486,507.803184036552),
(134034464,4401490,4401485,149.914370088613);
DROP INDEX IF EXISTS idx_network_source;
DROP INDEX IF EXISTS idx_network_target;
CREATE INDEX idx_network_source ON network(source);
CREATE INDEX idx_network_target ON network(target);
SELECT * FROM shortest_path('SELECT id, source, target, cost FROM network', 4401489, 4401483, false, false)
The text was updated successfully, but these errors were encountered: