pg_ksp is extremely memory intensive for k>1

Đang mở
  • Có gì không ổn?
#1,319 2 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 3 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
35/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
postgresql
Lĩnh vực
backend, databases

Hướng nghiên cứu

The issue is in the pg_ksp algorithm implementation, likely in the C++ source code for k-shortest path routing. Start by examining the pgr_ksp function in the src/ksp directory. Reproduce the memory issue with a smaller dataset to understand the heap usage pattern. Look for data structures that scale poorly with k>1, such as priority queues or candidate path storage. Verify the fix by running the provided SQL queries and monitoring memory.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Bug Report KSP
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)

Ngôn ngữ chính
C++
Star
1.4k
Fork
397
Merge trung bình
2 ngày 23 giờ
Pull request đã merge (30 ngày)
7

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của pgRouting/pgrouting

Tất cả issue của pgRouting/pgrouting

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.