pg_ksp is extremely memory intensive for k>1

[ZaninAndrea]

Expected behavior and actual behavior

I am using pg_ksp on a subset of the OpenStreetMap database with 270.000 roads and 200.000 vertices, if I set k=1 to find the best path the query takes about a second and around 100 MB of RAM

SELECT * FROM pgr_ksp('SELECT gid as id, source, target, cost FROM ways',12,7,1)

If I set k=2 or greater the ram usage skyrockets to over 100 GB and goes out of RAM before completing.

SELECT * FROM pgr_ksp('SELECT gid as id, source, target, cost FROM ways',12,7,2)

Am I using the command pgr_ksp incorrectly or is this drastic difference between k=1 and k=2 expected (if so why?) ?

Steps to reproduce the problem

Crop OSM graph to the bounding box 9.91,45.5721,12.5,46.54 then load it in postgis using the osm2pgrouting tool.

Specifications like the version of pgRouting/PostGIS and PostgreSQL as well as Operating System

PostgreSQL 10.7 (Debian 10.7-1.pgdg90+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516, 64-bit

POSTGIS="2.5.2 r17328" [EXTENSION] PGSQL="100" GEOS="3.5.1-CAPI-1.9.1 r4246" PROJ="Rel. 4.9.3, 15 August 2016" GDAL="GDAL 2.1.2, released 2016/10/24" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.2.1" TOPOLOGY RASTER

pgr_version = (2.6.2,v2.6.2,b14f4d56b,master,1.62.0)

[ZaninAndrea]

Solved the issue: the OSM graph had some edges where source=target, I think this made the algorithm go into infinite recursion. Dropping these edges fixed the issue.

[woodbri]

On 12/2/2019 5:34 PM, Zanin Andrea wrote: Solved the issue: the OSM graph had some edges where source=target, I think this made the algorithm go into infinite recursion. Dropping these edges fixed the issue. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1319?email_source=notifications&email_token=AAGETATESLADEQCYTQPOGDLQWWEORA5CNFSM4JTUMLG2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEFWLCAA#issuecomment-560771328>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGETAX7JD4WOYYWGQQIKO3QWWEORANCNFSM4JTUMLGQ>.

This is a bug, we should check for this condition and eliminate those edges or put up an appropriate error message directing the user to remove them. Crashing the server is BAD ;)