記事を書いた理由
『Neo4j の最短経路クエリの実行計画についてまとめてみた』という記事を書いて、Oracle PGXでは最短経路を取得するとき、どのように実行計画が動いているのか気になったので、まとめてみました。
Oracle PGXとは
Oracleが出しているインメモリのグラフ分析フレームワークです。ページランクや次数中心性等々のグラフを分析するアルゴリズムが多数組み込まれています。
動画のレコメンデーションや異常検出、タンパク質の相互作用の研究など、様々な分野への活用が期待されています。
こちらの記事でわかりやすくまとめられているので、是非参照してみてください。
より深く知りたい方は、OracleのHPへどうぞ。
Oracle PGXの環境構築については、Macを使用している方はこちら、Windowsを使用している方はこちらをご覧ください。
最短経路探索とは
各ノード間を移動するのにかかるコストを考慮して、最短であるノードまでに移動することができる経路を探索することです。
グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。
（Wikipediaより）https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C
テストデータ
今回は、\pgx-19.1.0\examples\graphsにある以下のデータを拝借します。
・connections.nodes.csv
・connections.edges.csv
・connections.csv.json
{
"format": "two_tables",
"datastore": "file",
"header": true,
"separator": ",",
"vertex_uris": ["connections.nodes.csv"],
"edge_uris": ["connections.edges.csv"],
"vertex_props": [{
"name": "label",
"type": "string"
}, {
"name": "name",
"type": "string"
}, {
"name": "country",
"type": "string"
}, {
"name": "occupation",
"type": "string"
}],
"edge_props": [{
"name": "label",
"type": "string"
}, {
"name": "weight",
"type": "double"
}]
}
補足：Neo4jでの検証結果
こちらの記事で検証した結果、Neo4jでは、経路探索時にパス全体をチェックする必要がある場合は深さ優先探索（しらみつぶし探索）が動くという結論に達しました。
（例：パスの中にname='Charlie Sheen'というプロパティをもつノードが存在する必要がある場合）
Oracle PGXで条件付き最短経路探索をした場合、内部的にはどのような実行計画が動くのでしょうか。
Oracle PGXでの検証
実際に検証してみました。
pgx> G = session.readGraphWithProperties("connections.csv.json");
今回は、Angela Merkelさんから辿ることができる最短経路を求めるクエリを実行してみます。
結果は以下のようになります。
pgx> result = G.queryPgql("SELECT a.name, b.name MATCH SHORTEST((a)-[]->*(b)) WHERE a.name='Angela Merkel' ");
==> oracle.pgx.api.ResultImpl@16d0e521
==> oracle.pgx.api.ResultImpl@634ca3e7
==> oracle.pgx.api.ResultImpl@ab4aa5e
==> oracle.pgx.api.ResultImpl@b14b60a
==> oracle.pgx.api.ResultImpl@1a7cb3a4
==> oracle.pgx.api.ResultImpl@1c297897
==> oracle.pgx.api.ResultImpl@33e0c716
==> oracle.pgx.api.ResultImpl@1d6a8386
==> oracle.pgx.api.ResultImpl@6274f21c
==> oracle.pgx.api.ResultImpl@35cec305
[rest of output truncated]
pgx> result.print();
+---------------------------------------------+
| a.name | b.name |
+---------------------------------------------+
| Angela Merkel | Angela Merkel |
| Angela Merkel | Barack Obama |
| Angela Merkel | Hillary Clinton |
| Angela Merkel | John Kerry |
| Angela Merkel | Vladimir Putin |
| Angela Merkel | Beyonce |
| Angela Merkel | Charlie Rose |
| Angela Merkel | Janet Yellen |
| Angela Merkel | Pope Francis |
| Angela Merkel | Jordan Peele |
| Angela Merkel | Keegan-Michael Key |
| Angela Merkel | David Koch |
| Angela Merkel | Charles Koch |
| Angela Merkel | Rand Paul |
| Angela Merkel | Eric Holder |
| Angela Merkel | House of Cards |
| Angela Merkel | Kirsten Gillibrand |
| Angela Merkel | Tom Steyer |
| Angela Merkel | Edward Snowden |
| Angela Merkel | Shinzo Abe |
| Angela Merkel | Hassan Rouhani |
| Angela Merkel | Mary Barra |
| Angela Merkel | Kim Jong Un |
| Angela Merkel | Abdel Fattah eL-Sisi |
| Angela Merkel | Serena Williams |
| Angela Merkel | Pharrell Williams |
| Angela Merkel | Amazon |
| Angela Merkel | CBS |
| Angela Merkel | Steve McQueen |
| Angela Merkel | H.R. McMaster |
| Angela Merkel | Omar Kobine Layama |
| Angela Merkel | Dieudonne Nzapalainga |
| Angela Merkel | Nicolas Guerekoyame Gbangou |
| Angela Merkel | The Vatican |
| Angela Merkel | Netflix |
| Angela Merkel | Robin Wright |
| Angela Merkel | Jason Collins |
| Angela Merkel | Xi Jinping |
| Angela Merkel | Abdullah Gul |
| Angela Merkel | Miley Cyrus |
| Angela Merkel | Alibaba |
| Angela Merkel | eBay |
| Angela Merkel | Google |
| Angela Merkel | ABC |
| Angela Merkel | NBC |
| Angela Merkel | Benedict Cumberbatch |
| Angela Merkel | Nicolas Maduro |
| Angela Merkel | Jenji Kohan |
| Angela Merkel | Tencent |
| Angela Merkel | Carl Icahn |
| Angela Merkel | Facebook |
| Angela Merkel | Nest |
| Angela Merkel | Kerry Washington |
| Angela Merkel | Carrie Underwood |
| Angela Merkel | Alfonso Cuaron |
| Angela Merkel | Seth Meyers |
| Angela Merkel | Michelle Bachelet |
| Angela Merkel | Snapchat |
+---------------------------------------------+
==> oracle.pgx.api.ResultImpl@d653e41
==> oracle.pgx.api.ResultImpl@3b78c683
==> oracle.pgx.api.ResultImpl@7f5614f9
==> oracle.pgx.api.ResultImpl@480cbe2e
==> oracle.pgx.api.ResultImpl@6c3f1658
==> oracle.pgx.api.ResultImpl@110e9982
==> oracle.pgx.api.ResultImpl@5eb0a686
==> oracle.pgx.api.ResultImpl@73608eb0
==> oracle.pgx.api.ResultImpl@67f9cb52
==> oracle.pgx.api.ResultImpl@2de9ca6
[rest of output truncated]
それでは、上記のクエリはどのように処理されているのでしょうか？PGXで実行計画を確認するには、explainPgql関数を使用します。
queryPgql関数の部分をexplainPgqlに置き換えるイメージです。
pgx> G.explainPgql("SELECT a.name, b.name MATCH SHORTEST((a)-[]->*(b)) WHERE a.name='Angela Merkel' ");
==> \--- (a) SHORTEST( (a) ->* (b) ) (b) Reachability {"cardinality":"10", "cost":"10", "accumulatedCost":"11"}
\--- (a) RootVertexMatch {"cardinality":"1", "cost":"1", "accumulatedCost":"1"}
このように、最初に最短経路を返すshortest関数が実行され、評価すべき経路は最短経路のみに絞り込まれます。
Neo4jでは場合、WITH句を使ってクエリの実行を早める必要がありましたが、
↑上記の表現は不適切であることが判明いたしました。こちらの記事で検証を行っています。
Neo4jでは、最短経路以外の経路も取得する条件をかけるクエリを実行する場合は、WITH句を使うことを考慮する必要がありますが、Oracle PGXではWHERE句があってもはじめに内部的に評価すべき経路の絞り込みを行ってくれます。
Oracle PGXでも、経路全体に条件をかけるクエリを実行した場合、深さ優先探索が動いてしまうことがわかりました（下記参照）。
まとめ
Oracle PGXは、WHERE句があっても、まず評価すべき経路の絞り込みを行ってくれるということがわかりました。条件付き最短経路探索を行う場合でも、実行計画を気にせずにWHERE句を使うべきですね。
追記(2019/06/13)
Oracle PGXでも、最短経路以外のパスの長さを調べる必要がある場合は、深さ優先探索（しらみつぶし探索）が動いてしまうということがわかりました。
以下のクエリを実行します。
pgx> result=G.queryPgql("PATH p AS (a)-[]-() WHERE a.name='Angela Merkel' SELECT b.name MATCH(a)-/:p +/->(b)");
==> oracle.pgx.api.ResultImpl@7a687d8d
==> oracle.pgx.api.ResultImpl@4c82b5df
==> oracle.pgx.api.ResultImpl@67eec8e1
==> oracle.pgx.api.ResultImpl@4214ae8f
pgx> result.print();
+-----------------+
| b.name |
+-----------------+
| Vladimir Putin |
| Hillary Clinton |
| Barack Obama |
| John Kerry |
+-----------------+
==> oracle.pgx.api.ResultImpl@63f6bed1
==> oracle.pgx.api.ResultImpl@7ef8eda7
==> oracle.pgx.api.ResultImpl@115ca7de
==> oracle.pgx.api.ResultImpl@29fe4840
上記のクエリは、PATHクエリでAngela Merkelさんを始点とする経路を、エイリアスpとして指定しています。
その経路pの長さが1以上である経路を指定し、経路の終点ノードのnameの値を取得しています。
このような、経路全体に条件をかけたクエリを実行する場合の実行計画を確認してみます。
pgx> G.explainPgql("PATH p AS (a)-[]-() WHERE a.name='Angela Merkel' SELECT b.name MATCH(a)-/:p +/->(b)").print();
\--- (a) -/:p+/-> (b) Reachability {"cardinality":"780", "cost":"780", "accumulatedCost":"858"}
\--- (a) RootVertexMatch {"cardinality":"78", "cost":"78", "accumulatedCost":"78"}==> null
上記の実行計画ともう一度比較してみてください。
経路全体に条件をかけた場合、まず始めに経路全体をみていることがわかります。
このように、経路全体に条件をかけた場合、Oracle PGXでも深さ優先探索が動いてしまうことがわかりました。
Neo4jもOracle PGXも、経路全体に対して条件をかけた場合、深さ優先探索が動いてしまうのですね。
参考資料
https://docs.oracle.com/cd/E56133_01/2.7.0/reference/api/graph-pattern-matching.html
https://docs.oracle.com/cd/E56133_01/latest/reference/pgql-specification.html#shortest-path
https://www.slideshare.net/YukiTagami1/pgx7pgql11