Help us understand the problem. What is going on with this article?

Neo4j の最短経路クエリの実行計画についてまとめてみた

記事を書いた理由

Neo4jで最短経路を取得するとき、どのように実行計画が動いているのか気になったので、まとめてみました。

Oracle PGXでも同様の検証をしています。詳しくは、こちらの記事をご覧ください。

Predicateによって実行計画が変わる

・経路探索中にPredicateが評価可能なとき⇒幅優先探索
例)対象の全てのノードが同じラベルを持っているときに最短経路を探索する場合

・経路探索時にパス全体をチェックする必要があるとき⇒深さ優先探索(しらみつぶし探索)
例)パスの中にname='Charlie Sheen'というプロパティをもつノードが存在する必要がある場合

実際に実行してみた

字面だけでは理解しづらいので、実際に実行してみました。

サンプルデータのインポートは、以下の記事を参考にしてください。
https://qiita.com/kk31108424/items/715f82fa62db6040c805

演算子の名称

ここで、この後の図で出てくる演算子の読み方をまとめておきます。

Estimated Rows
コストベースの実行計画で見積した予測の行数。

Rows
演算子によって絞り出された実際のデータの行数

幅優先探索

MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE ALL (r IN relationships(p) WHERE exists(r.distance))
RETURN p

無題.png

結果が返ってくるまでは4msでした。
グラフ形式で表示すると、以下のようになります。
無題.png

このクエリの実行計画は、以下のようになります。

EXPLAIN MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE ALL (r IN relationships(p) WHERE exists(r.distance))
RETURN p

無題.png

PROFILE MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE ALL (r IN relationships(p) WHERE exists(r.distance))
RETURN p

無題.png

実行計画の図は、上から読んでいってください。

深さ優先探索(しらみつぶし探索)

MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE length(p) > 1
RETURN p

無題.png

結果が返ってくるまで、129msに延びていることがわかります。
結果をグラフ形式で表示すると、以下のようになります。
無題.png

このクエリの実行計画は、以下のようになります。

EXPLAIN MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE length(p) > 1
RETURN p

無題.png

PROFILE MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE length(p) > 1
RETURN p

無題.png

WHERE句の評価がshortestPathの決定よりも先に評価されてしまいます。この結果、最短経路だけでなく、全てのパスを評価する必要があるため、このように長い時間がかかってしまいます。

WITHを使ったクエリ

上記のクエリの実行を早めるには、WITH句を使います。MATCH句で取得した値をフィルターにかけるイメージです。

MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WITH p
WHERE length(p) > 1
RETURN p

無題.png

結果が返ってくるまで、たったの8msしかかっていないことがわかります。

実行計画は、以下の通りです。
無題.png

無題.png

WITH句を使ったクエリでは、WHERE句ではMATCH句で取得した最短経路のみを評価すればよいので、結果を返すまでにかかる時間が大幅に減少します。

まとめ

WHERE句のPredicateはshortestPathの決定より先に評価されてしまうため、条件付きの最短経路探索を行う場合は、WITH句を使ったほうが処理が速くなることを念頭に入れておいたほうが良いです。

追記(2019/06/12)

WHERE句があるからといって、必ず深さ優先探索(しらみつぶし探索)が動くというわけではないようでした。上記のlength(p)>1という条件をかけると、最短経路以外のパスの長さを調べる必要があるため、深さ優先探索(しらみつぶし探索)が動いてしまうということがわかりました。

試しに始点ノード、終点ノードにのみ条件をかけるWHERE句を使ったクエリを投げてみます。

MATCH (s:Place), (f:Place), p = shortestPath((s)-[:EROAD*]-(f))
WHERE s.name="Paris" AND f.name="Roma"
RETURN p

結果はこのようになります。

無題.png

それでは、実行計画はどのようになっているでしょうか。

EXPLAIN MATCH (s:Place), (f:Place), p = shortestPath((s)-[:EROAD*]-(f))
WHERE s.name="Paris" AND f.name="Roma"
RETURN p

無題.png

PROFILE MATCH (s:Place), (f:Place), p = shortestPath((s)-[:EROAD*]-(f))
WHERE s.name="Paris" AND f.name="Roma"
RETURN p

無題.png

このように、始点ノード・終点ノードだけに条件をかけた場合は、WHERE句を使っても、幅優先探索が動いていることがわかります。

よって、最短経路以外の経路も取得する条件をかけるクエリを実行する場合は、WITH句を使うことを考慮する必要があるという結論に至りました。

参考

https://neo4j.com/docs/cypher-manual/current/execution-plans/shortestpath-planning/
https://neo4j.com/docs/cypher-manual/current/clauses/with/
https://books.google.co.jp/books?id=RSTLCgAAQBAJ&pg=PT27&lpg=PT27&dq=neo4j+%E5%AE%9F%E8%A1%8C%E8%A8%88%E7%94%BB&source=bl&ots=rU-r8PFYQa&sig=ACfU3U1JbZbf0l31GQ3r2i7LUQ9b6n5ZZg&hl=ja&sa=X&ved=2ahUKEwjRstrxgtTiAhUGEbwKHSr-AOwQ6AEwCXoECAkQAQ#v=onepage&q=neo4j%20%E5%AE%9F%E8%A1%8C%E8%A8%88%E7%94%BB&f=false

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした