pg_ksp is extremely memory intensive for k>1
メンテナーはふだん 3 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 初心者へのやさしさ
- 35/100
調査の方向性
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.
索引モデルが issue の本文から書いたものです。
説明
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)
- 主要言語
- C++
- スター
- 1.4k
- フォーク
- 397
- 平均マージ
- 2日 23時間
- マージ済み PR（30日）
- 7
環境構築
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
pgRouting/pgrouting のほかの issue
-
Administrative Enhancement
難易度 1/5 1時間未満 初心者へのやさしさ 80/100
メンテナーはふだん 3 日以内に返信
-
points_input Developers doc対応中かも @withaman69 が 94 日前に担当しました。 オープンC/C++ Developers Doc. good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
pgRouting/pgrouting#973 · コメント 10 件 ·
メンテナーはふだん 3 日以内に返信
-
get_check_data developers doc対応中かも @withaman69 が 96 日前に担当しました。 オープンC/C++ Developers Doc. good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
pgRouting/pgrouting#972 · コメント 7 件 ·
メンテナーはふだん 3 日以内に返信
-
bug Looks AI valid
難易度 4/5 3〜5日 初心者へのやさしさ 30/100
pgRouting/pgrouting#3180 · コメント 2 件 ·
メンテナーはふだん 3 日以内に返信
-
pgr_drivingDistance: get_depth() is O(reached × V) and dominates runtime on large graphs対応中かも @jflangenbach-casageo が 10 日前に担当しました。 オープンbug
難易度 3/5 1〜2日 初心者へのやさしさ 62/100
メンテナーはふだん 3 日以内に返信
pgRouting/pgrouting の issue をすべて見る
似ている issue
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 85/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
Niko1221/Strata#5560 · コメント 2 件 ·
メンテナーはふだん 4 日以内に返信
-
NVIDIA windows
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
メンテナーはふだん 1 日以内に返信
-
要トリアージ 辞書
難易度 1/5 1〜3時間 初心者へのやさしさ 86/100
yksr-melt/Meltype#1625 · リアクション 1 件 ·
メンテナーはふだん 1 日以内に返信
-
kind/bug priority/medium qa_automation
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
yugabyte/yugabyte-db#37324 ·
メンテナーはふだん 1 日以内に返信