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

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

Oracle PGXでも同様の検証をしています。詳しくは、[こちらの記事](https://qiita.com/kk31108424/items/f6b8f76fe795a00a0509)をご覧ください。

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

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


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

サンプルデータのインポートは、以下の記事を参考にしてください。
https://qiita.com/kk31108424/items/715f82fa62db6040c805
###演算子の名称
ここで、この後の図で出てくる演算子の読み方をまとめておきます。

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

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


###幅優先探索

```sql
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/fed3d4ce-2382-efcf-55c4-fbb28ba2c59a.png)

結果が返ってくるまでは**4ms**でした。
グラフ形式で表示すると、以下のようになります。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/940842d2-696a-1e89-999e-443e55ea8b9d.png)

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

```sql
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/6d560554-3e6e-2554-883b-a8eebe68ead2.png)


```sql
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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/0bf80cb8-cfc3-b0f6-73ec-95170ab1022e.png)


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

###深さ優先探索（しらみつぶし探索）
```sql
MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WHERE length(p) > 1
RETURN p
```
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/346bec62-495c-32e8-77de-8ad9ea961464.png)



結果が返ってくるまで、**129ms**に延びていることがわかります。
結果をグラフ形式で表示すると、以下のようになります。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/90a5aa46-7d13-fd1d-319f-0669fe63eaae.png)


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

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

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/ceed1f00-208f-7f00-8107-9623036ae58f.png)

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

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/e55c58db-2bff-3c5d-4ebc-9a510ea1b1ad.png)

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

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

```sql
MATCH (s:Place{name:"Paris"}), (f:Place{name:"Roma"}), p = shortestPath((s)-[:EROAD*]-(f))
WITH p
WHERE length(p) > 1
RETURN p
```
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/2aa79df5-d095-6d4d-119c-ef0ecc610f92.png)

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

実行計画は、以下の通りです。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/190af0dc-71ca-f8c7-8175-f636c22a283b.png)

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/95ec2bf5-4f1e-5620-5ec4-6cc52e4d0402.png)

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

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

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

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

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

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

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/2ed7ebe5-f808-c788-1348-d98d6d994d3c.png)

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

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

![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/c3dd971f-584a-5982-a484-53ed0c43f3ff.png)

```sql
PROFILE MATCH (s:Place), (f:Place), p = shortestPath((s)-[:EROAD*]-(f))
WHERE s.name="Paris" AND f.name="Roma"
RETURN p
```
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/248756/d16e129b-e422-f248-f5ec-3cdbf2cbcc17.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