neo4j で出力される warning について(builds a cartesian product)

はじめに

適当にクエリを作成していると以下の警告を受けた

This query builds a cartesian product between disconnected patterns.

未接続のパターンでデカルト積を構築するクエリだけど本当にいいの? という警告である. 意味が分からなかったので調べてみたことを記載しておく.

事象

下記クエリを実行しようとすると冒頭に述べた警告を受けた.
クエリ自体は問題なく実行される.

match (tag1:tag), (tag2:tag)
where id(tag1) = 26995 and tag2.name = "test-tag"
MERGE (tag1) - [:rel] -> (tag2)
return tag1,tag2

原因と処置

stackoverflow に説明があった.

要約すると計算時間が非効率だからやめとこうよという話のようである.
上記クエリの場合は WHERE 句において tag1 と tag2 に入り得る全てのパターンを精査する処理となる.
結果として計算量が tag1 と tag2 に入るノード数の直積となる.今回の場合は tag ラベルの付与されたノード数の二乗の計算量が発生する.
O(n^2) はあまりよろしくない計算量であり, ノード数が増えるほどパフォーマンスの低下が顕著になる.

このデカルト積が生じるパターンはアンチパターンとしてSQL界隈では有名なものらしい.

解決策としては MATCH 句を分割するのが手っ取り早い.

MATCH (tag1:tag)
WHERE id(tag1) = 26995
MATCH (tag2:tag)
WHERE ag2.name = "test-tag"
MERGE (tag1) - [:rel] -> (tag2)
return tag1,tag2

おわりに

RDBにおいてもクエリ実行時の意図しないデカルト積の発生は問題のあるものであるらしい.
この記事のおかげで自分がデータベースについて何も知らないことが露見してしまった.
もう少し精進することとしよう.