PostgresをGraph DBとして使う: pgRoutingをAb(using)する — 活用か、それとも濫用か？

 (supabase.com)
10 ポイント 投稿者 GN⁺ 2025-03-04 | 2件のコメント | WhatsAppで共有
  • pgRoutingはPostgresの拡張機能で、主に地理情報システム（GIS）で2地点間の最短経路を見つけるために使用される
  • しかしpgRoutingは、地理空間データ以外にも、さまざまなグラフ構造のデータを処理する用途に活用できる
  • Apache AGEやNeo4jのような専用グラフデータベースの軽量な代替として利用可能

pgRoutingの紹介

  • pgRoutingはPostGISの拡張機能で、地理空間ルーティング機能を提供する
  • これにより、最短経路の計算、ネットワーク分析、複雑なルーティング問題の解決などが可能になる
  • 主に、2つの地点間の最短経路を見つけるといったGIS用途で活用される

グラフとの連携

  • pgRoutingの強みは、グラフとして構造化されたあらゆるデータと一緒に扱える点にある
  • グラフは相互接続された点のネットワークで構成され、ここで:
    • ノードはエンティティを表す
    • エッジはノード間の関係や経路を表す
  • 地図やGISではノードとエッジはそれぞれ交差点と道路を意味するが、ソーシャルネットワークのような抽象的なシステムにも適用できる

GIS以外でのpgRouting活用例

  • ジョブスケジューリング

    • プロジェクトではタスク間に依存関係が存在し、これは**有向非巡回グラフ（DAG）**を形成する
      • ノードはタスクを表す
      • エッジは依存関係を表す
    • プロジェクト管理における主要な課題の1つは、プロジェクト全体の期間を決定する「クリティカルパス」を見つけること
    • pgRoutingを使ってタスクの依存関係をモデル化し、グラフアルゴリズムによってクリティカルパスを見つけられる

  • リソース割り当てベースのリバースプロキシルーティング

    • 分散システムでは、ネットワークのノード間でリソースを効率的に割り当てることが重要
    • 各ノードは物理的な場所またはコンピューティングプロセスを表し、エッジはノード間でデータが移動する経路を表す
    • たとえばクラウドインフラでは、pgRoutingを使って分散サーバー間のデータや計算タスクを最も効率的な経路でルーティングできる

  • YouTubeのような推薦エンジン

    • 推薦エンジンやナレッジグラフを使う検索アルゴリズムでは、pgRoutingを活用してエンティティとイベント間の関係を構築できる
    • たとえばYouTubeの推薦アルゴリズムでは:
      • ノードはユーザー、動画、カテゴリなどのエンティティを表す
      • エッジはユーザーと動画の相互作用や、動画同士でカテゴリを共有しているといった関係を表す
    • こうしたグラフ構造を通じて、ユーザーにパーソナライズされた推薦を提供できる

pgRoutingの追加情報

  • pgRoutingはPostgresの強力な拡張機能であり、さまざまなグラフベースの問題を解決するために使える
  • 詳細はpgRouting公式ドキュメントで確認できる

関連記事

2件のコメント

 
curiosityprocessor 2025-03-05

Apache AGE や pgRouting を実際に導入してみた方はいらっしゃいますか？
会社でグラフDBの導入を進めているのですが、既存のRDBとして Postgres を使ってはいるものの、
plugin/extension で Postgres を「まるでグラフDBのように」使うことはできても、実際にはパフォーマンスが出ないと聞き、Neo4j を検討していました。ですが、Hacker News の意見を見ると、Neo4j にも不満が多いようですね。
 
GN⁺ 2025-03-04
Hacker Newsの意見

  • 5年前、Graphデータベースとライブラリに失望し、NetworkXに似たPythonインターフェースの背後に複数の非Graph DBMSを配置しようとしていた

    • Neo4Jはあらゆるグラフでクラッシュし、SQLiteとPostgresのほうがネットワーク処理タスクにより適した選択肢だった
    • Postgres互換性が高まる中で、プロジェクトを刷新する価値があるのか気になっている
    • MemGraphのようにCYPHER互換のGraph DBが増えており、Neo4Jよりもうまく動く可能性がある
    • pgroutingがAI/エージェント向けのメモリレイヤーを構築するのに良いツールかを確かめることが目的だった
    • 初期結果は有望で、近いうちに別の記事で続報を出す予定
    • SuiteSparseベースのonesparseのような興味深い拡張機能がある

  • SupabaseはPostGIS関連の優れたコンテンツを継続的に提供している

    • タイルを直接配信したり、PGの地理コンテキストで機能を（誤）用したりする話がある
    • 革新的でも複雑でもないが、面白く知的刺激がある
    • データベースで作業することへの興味をかき立てるコンテンツを頻繁に公開している点を評価している

  • 「グラフのためのSQLite」が存在しない理由をずっと不思議に思っていた

    • ディスクベースのストレージを持つインプロセスソリューションを妨げるような保存方式があるのか気になる

  • シンプルなPostgresグラフDBプロジェクトに取り組んでいる

    • クエリとテーブル構造は、同じ作業に対してはるかにシンプルだ

  • roaring bitmapをbyteaのpostgres列に保存して隣接行列を表現することについて意見を聞きたい

    • RDSがplrustとPostgreSQLのSPIをサポートしているので、croaring-rsを使って構築できそうだ
    • 多数のグラフを表現でき、それぞれのグラフはテナント（会社/B2B SaaSのユースケース）に割り当てられる
    • plrustを使ってroaring bitmapをDBサーバーのbyteaに保存し、SPIを使ってネットワークオーバーヘッドを最小化できる
    • PostgreSQLはトランザクション安全性を提供し、テナントID列や、関係メタデータを問い合わせるためのJSONBなど、他の列指向データへのサポートもある
    • 多数のテナントグラフをサポートする必要があり、すでにcitusを使っているので大規模でも可能そうだ
    • 関係をよりよくインデックスするために、いくつかの演算子クラスを作る必要がありそうだ
    • pg_roaringbitmapは知っているが、int64を使っており、RDSから始めるほうを好む
    • Neo4Jは使わず、PostgreSQLを深く活用している（20TB超のテーブル作業など）
    • ブログ投稿の著者に深く感謝している
    • pgRoutingをグラフDBとして使えそうなので、テストリストに追加する

  • 「Apache AGE」について意見があるか気になる

    • Apache AGE™はグラフデータベース機能を提供するPostgreSQL

  • データモデルだけを見た場合（たとえばクエリ言語ではなく）、「グラフ」データベースと「一般的なSQL」データベースの間に実際の違いがあるのか気になる

  • PgRoutingを使った等時線生成の経験があるか気になる

    • 徒歩や自転車などの等時線マップを生成するユースケースがある
    • 可能ならPostgresだけを使い、Valhalla、OpenTripPlanner、OpenRouteServiceのような他のインフラは避けたい

  • Postgresは常に新しいデータモデリングの機会を開く拡張を提供してくれる

    • CedarDB（Postgres互換）のグラフ機能と比べて、どのような位置づけになるのか気になる