グラフクエリ言語（Cypher・Gremlin）

SQLでグラフを書くと何が辛いのか

「友人の友人の友人」を SQL で書くと、自己結合が3段重なります。

SELECT DISTINCT f3.user_id
FROM friends f1
JOIN friends f2 ON f1.friend_id = f2.user_id
JOIN friends f3 ON f2.friend_id = f3.user_id
WHERE f1.user_id = 123;

ホップ数が増えるたびに JOIN が増え、結合順序をオプティマイザが誤ると中間結果が爆発します。SQLのJOINは本来「2つの集合から条件に合う組を全部作る」無方向の集合演算であり、グラフの「ある頂点から辺を辿って次の頂点へ」という有向・逐次的な移動とは発想の型が違います。グラフクエリ言語はこの移動そのものを一級市民として言語に組み込みます。代表が宣言型の Cypher と命令型の Gremlin です。

Cypher：グラフの形をパターンとして書く

Cypher（Neo4j が開発し openCypher として標準化）は、探したいグラフの形を ASCII アート風のパターンとして書く宣言型言語です。

MATCH (a:Person {name: "Alice"})-[:FRIEND]->(b)-[:FRIEND]->(c)
WHERE a <> c
RETURN DISTINCT c.name

丸括弧がノード、角括弧付きの矢印が辺を表し、(a)-[:FRIEND]->(b) は「a から FRIEND 辺で b へ」という向きを持つ隣接そのものです。宣言型なので、どの順にどう辿るかはユーザーが書かず、クエリオプティマイザが決めます。

内部では、この MATCH パターンはまず論理演算子のグラフ（Expand、NodeByLabelScan、Filter など）に変換され、実行計画へ落とされます。鍵となるのが Expand 演算子で、これは「ある頂点集合から特定方向・特定ラベルの辺をすべて展開する」操作です。ネイティブグラフDBでは各ノードが隣接エッジへの物理ポインタを持つ index-free adjacency の構造そのものを使って Expand を実行するため、1ホップの展開コストはグラフ全体の件数に依存せず、そのノードの次数（隣の数）だけに比例します。

オプティマイザの主な仕事は開始点（アンカー）の選択です。MATCH パターン中でラベルやプロパティ条件が最も絞り込める頂点をまず見つけ（例では name: "Alice" を持つ Person ラベル）、そこから Expand を連鎖させます。これは SQLオプティマイザがカーディナリティ推定で選択性の高いテーブルから結合を始めるのと同じ発想で、開始点を誤ると「全ノードから3ホップ展開」のような爆発が起きます。

Gremlin：辿る手順そのものを組み立てる

Gremlin（Apache TinkerPop）は対照的に、トラバーサル（辿る操作）を関数呼び出しの連鎖として明示的に書く命令型・関数型言語です。

g.V().has('name', 'Alice').as('start')
 .out('FRIEND')
 .out('FRIEND')
 .where(neq('start'))
 .dedup()
 .values('name')

g.V() が全頂点集合から出発し、has(...) で絞り込み、out('FRIEND') で「FRIEND辺を辿って先の頂点集合へ移る」を明示的に2回書いています。実行順序が構文の並び順とほぼ一致するため、書いた通りに実行されるのが命令型の特徴です。裏を返せば、どの順で辿るかの最適化責任の多くが書き手側にあるということでもあります。

Gremlin の実行モデルはパイプライン（ストリーム）評価です。g.V().has(...).out(...).out(...) の各ステップは、前段が1件生成するたびに後段へ即座に流すイテレータの連鎖として動きます。全頂点をいったん配列に集めてから次のステップへ渡すのではなく、1つの「トラバーサ（traverser、探索中の1本の経路情報を持つトークン）」がパイプラインを流れていくイメージです。

トラバーサの流れ（概念）
  V() → 1件ずつ生成 ──┐
  has(...)で通過/破棄 ──┤ 1件ずつ次段へ
  out('FRIEND')で分岐 ──┤ （中間結果を全件バッファしない）
  dedup()で重複除去 ────┘

この方式の利点は、limit(10) のような打ち切りがあるとパイプライン全体が早期終了できる点です。欠点は、has('name','Alice') を先に置くか out('FRIEND') の後に置くかで中間集合のサイズが桁違いに変わることで、絞り込み条件をできるだけ早いステップに書くのが定石になります。これは SQLで WHERE 条件をどのJOIN段で評価するかによって結合アルゴリズムの中間結果サイズが変わるのと同じ理屈で、Gremlinではオプティマイザ任せにできない分、書き手の責任がより重くなります。

パターンマッチングの最適化：どちらも「開始点探し」に帰着する

宣言型と命令型は書き味が正反対でも、内部最適化のコア課題は共通しています。

Cypherの MATCH パターンは複数の開始候補（ラベル付き頂点のどれから始めるか）を持ちうるため、オプティマイザはカーディナリティ推定に基づき最も件数の絞れる頂点ラベル・プロパティ条件からアンカーを選び、そこから Expand を連鎖させる計画を立てます。これは複数テーブルの結合順序を探索するのと同型の問題で、探索空間が組み合わせ的に増えるため、多くの実装はヒューリスティクス（最も選択的な述語を持つパターン要素を優先するなど）で妥協します。

Gremlinには対応するオプティマイザ層が薄いため、同じ最適化判断をクエリの書き方自身に埋め込むことになります。g.V().hasLabel('Person').out('FRIEND') と g.V().out('FRIEND').where(hasLabel('Person')) は論理的に近くても、前者はフィルタ後にExpandする分だけ中間トラバーサ数を抑えられ、実務上はっきり速くなることがあります。

まとめ