まえがき
この記事は、Sansan Data Intelligence開発Unitブログリレーの第9弾です。
こんにちは、技術本部Data Intelligence Engineering Unitの滑川です。
本記事ではSansan Data Intelligenceの中で動くMaster Data Systemに採用されている「グラフ構造」と「Cloud Spanner」を題材に、Spanner Graphがどのように活用できるのか、またそのパフォーマンスについて検証してみたのでご紹介したいと思います。
本記事では、Master Data Systemで扱うグラフ構造をシンプルに表現し、グラフの形状（サイズ・幅・経路数など）がSpanner Graphのパフォーマンスにどのように影響するかを検証します。合わせて従来のSQLとの特性の違いにも触れていきます。
※ グラフ理論について知らない方でもわかるような表現や補足を書くようにしています。
ただし、2026/3/4（水）現在はSpanner GraphはEnterprise エディションまたはEnterprise Plus エディションでのみ利用可能です。あらかじめご了承ください。
- まえがき
- Sansan Data Intelligence・Master Data Systemとは
- Master Data Systemのデータ構造
- なぜSpanner Graphなのか
- Spanner Graphのパフォーマンス検証
- 考察
- あとがき
- カジュアル面談
- 採用イベント
Sansan Data Intelligence・Master Data Systemとは
まず本題に入る前にSansan Data Intelligenceについて軽く説明します。
Sansan Data Intelligence とは企業の持つ取引先データの最新化や正規化を行うことで、データの品質に関する課題を解決するデータクオリティマネジメントサービスです。
Sansan Data Intelligenceについては以下の記事で詳しく紹介しておりますので、ぜひご覧ください。
そしてSansan Data Intelligenceの裏側では、Master Data Systemが動いています。このシステムは、企業や事業所の名前や住所などのマスタデータを管理し、時間変化（社名変更、本社移転、合併など）を含むグラフモデルで表現することで、企業の最新状態を容易に辿ることを可能にしています。
Master Data Systemについては以下の記事で詳しく紹介しておりますので、ぜひご覧ください。
Master Data Systemのデータ構造
Master Data Systemでは企業や事業所のマスタデータをグラフ構造で管理しています。実際には以下のようなノード1とエッジ2を持ちます。
ノード
- 企業: 企業の各時点での状態を表します。企業は商号変更、本社移転などのイベントが発生するたびに、新しいバージョンのノードとして記録されます。
- 事業所: 企業が持つ事業所（支店、営業所、工場など）の各時点での状態を表します。事業所の新設、移転、閉鎖などのイベントごとに新しいノードが作成されます。
エッジ
- 企業-企業: 企業ノード間の関係性を表し、合併による吸収関係、商号変更のような企業情報の属性変更、親子関係などを示します。
- 企業-事業所: 企業と事業所の所属関係を表し、どの企業がどの事業所を持っているかを示します。
- 事業所-事業所: 主に事業所情報の属性変更や移転などを示します。
これらに加えてエッジに有効期間を組み合わせることで、企業の時間的変化や組織構造を柔軟に表現できます。この仕組みにより時系列を交えた企業関係が整理可能になっています。
このシステムは例えば以下のようなシーンに活用することができます。
- 古くに作られた取引先データを最新化したい
- 新旧データが入り混じったデータ群から重複を取り除きたい
- 子会社と親会社が入り混じったリストから親会社だけに絞りたい
- 事業所の新設や合併などの事業拡大イベントをキャッチし、新たなサービスの提案に繋げたい
なぜSpanner Graphなのか
Spanner Graph は Google Cloud Spanner の機能の一つで、グラフ構造のデータに対して専用のクエリ言語（GQL: Graph Query Language）でクエリを書くことができます。
通常のSQLではグラフのチェーンをN段辿ろうとするとN回のJOINや再帰が必要になりますが、GQLでは「エッジを0〜100回辿る」という操作を-[:edge]->{0,100} のように簡単な1クエリで表現できます。
Master Data System が扱う「合併・移転・親子関係のつながり」などを辿ることはまさにグラフ探索そのものであり、Spanner Graphとは相性が良いです。
そこで本記事の主題、実際にMaster Data Systemを例にSpanner Graphがどのように使えるのか、またそのパフォーマンスをいくつかのパターンを用意して実験してみたいと思います。
Spanner Graphのパフォーマンス検証
Master Data Systemをそのまま利用すると複雑なため、今回は簡単な例として、「企業」の「合併」と「分割」のみを扱ってパフォーマンスを計測してみたいと思います。
検証に利用したSpannerインスタンスのProcessingUnitsは3000に設定しています。
検証データ
ノード
- 企業: 企業を表します。商号のみを持ち、1企業1ノードとします。
エッジ
- 企業-企業: 合併と分割のイベントを表します。複数の企業が一つの企業に合併されることもあれば、一つの企業が複数の企業に分割されることもあるとします。
パフォーマンスを計測するにあたって、DB上にデータ量を確保する目的で以下の条件でベースとなるデータを作成します。
- 総企業数は1000万件
- 全体の10%の企業は、ランダムに選ばれた1つの企業と合併されている
- 合併により存続した企業が別企業に合併されることがある
- 一度合併して消滅した企業が合併先になることはない（合併先が循環しない）
- 一つの企業が複数回企業を合併することがある
- 合併により存続した企業が別企業に合併されることがある
- 全体の1%の企業は、ランダムに選ばれたいずれか2つの企業に分割されている
これらに加えて、検証したいケースに沿ったデータを追加してパフォーマンスを検証したいと思います。
テーブル定義
-- node CREATE TABLE corporations ( corporation_id INT64 NOT NULL, name STRING(256) NOT NULL, ) PRIMARY KEY (corporation_id); -- edge CREATE TABLE corporation_corporation_edges ( edge_id INT64 NOT NULL, from_id INT64 NOT NULL, -- corporations.corporation_id to_id INT64 NOT NULL, -- corporations.corporation_id ) PRIMARY KEY (edge_id); CREATE INDEX cc_edges_from ON corporation_corporation_edges(from_id); CREATE INDEX cc_edges_to ON corporation_corporation_edges(to_id); -- Spanner Graph用の定義。合併や分割元から先を辿れるようにする。 CREATE PROPERTY GRAPH corporation_graph NODE TABLES (corporations) EDGE TABLES ( corporation_corporation_edges SOURCE KEY (from_id) REFERENCES corporations (corporation_id) DESTINATION KEY (to_id) REFERENCES corporations (corporation_id) LABEL corp_from_corp_to, );
検証ケースと結果
検索のパフォーマンスに影響を与える要因として、グラフ構造のパスの長さ（合併・分割チェーンの長さ）、幅（分割数）、経路数（同一ノードへ至る経路の本数）の3つが考えられます。これらの影響を個別・組み合わせで検証するために、極端な例も交えて検証したいと思います。
検索したいケースとして「ある企業名から最新の企業を取得したい」場合を考えます。ただし分割があった場合は分割先の企業すべての一覧を取得したいものとします。
それを表現した各ケースで実行するSpanner GraphのGQLは以下のクエリです。
-- グラフを指定 GRAPH corporation_graph -- 始点になるノードを検索 MATCH (s WHERE s.name = @name) -- 始点になるノードからcorp_from_corp_toを再帰的に辿る -[:corp_from_corp_to]->{0,100} (dest) -- 先がないノードのみに絞る WHERE NOT EXISTS { MATCH (d WHERE d.corporation_id = dest.corporation_id)-[:corp_from_corp_to]->(successor) } RETURN DISTINCT dest.corporation_id ORDER BY dest.corporation_id
また、参考までに以下のSQLを再帰的に発行して同じ結果を得た時の結果も載せておきます。（ケースごとにクエリの最適化はしていないのであくまで参考値と捉えてください。）
-- 再帰CTEはサポートされておらず、同時にJOINできる数は20までのため100回実行して末端まで辿る SELECT DISTINCT e.to_id AS corporation_id, c.name FROM corporations start JOIN corporation_corporation_edges e ON e.from_id = start.corporation_id JOIN corporations c ON c.corporation_id = e.to_id WHERE start.name = @name;
なお、計測値はウォームアップで1回クエリを実行し、その後の3回から中央値を取った値を記載しています。
ケース1: 1つの企業にN回合併された企業である
| 形状 | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|
| 線形チェーン | 1 | N | N+1 |
結果
| N | GQL (ms) | SQL (ms) | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|---|---|
| 1 | 29 | 107 | 1 | 1 | 2 |
| 5 | 39 | 231 | 1 | 5 | 6 |
| 10 | 29 | 420 | 1 | 10 | 11 |
| 100 | 43 | 3,360 | 1 | 100 | 101 |
ケース2: N個の企業に1回分割された企業である
| 形状 | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|
| 放射構造 | N | 1 | N+1 |
結果
| N | GQL (ms) | SQL (ms) | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|---|---|
| 2 | 31 | 97 | 2 | 1 | 3 |
| 5 | 29 | 89 | 5 | 1 | 6 |
| 10 | 30 | 89 | 10 | 1 | 11 |
| 100 | 30 | 89 | 100 | 1 | 101 |
ケース3: 1000社に分割後、各社がN回合併される
| 形状 | 経路数 | ノード数 | |
|---|---|---|---|
| 1000本の並列線形チェーン | 1,000 | N+1 | 1+1,000(N+1) |
結果
| N | GQL (ms) | SQL (ms) | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|---|---|
| 2 | 108 | 173 | 1,000 | 3 | 3,001 |
| 10 | 126 | 534 | 1,000 | 11 | 11,001 |
| 20 | 180 | 1,350 | 1,000 | 21 | 21,001 |
| 50 | 411 | 2,419 | 1,000 | 51 | 51,001 |
| 99 | 647 | 4,689 | 1,000 | 100 | 100,001 |
ケース4: 2のN乗に分割後、2社ずつ合併していき、1社に収束する
| 形状 | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|
| バイナリ合併ツリー | 2N | N+1 | 2N+1 |
結果
| N | GQL (ms) | SQL (ms) | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|---|---|
| 1 | 30 | 130 | 2 | 2 | 4 |
| 5 | 38 | 255 | 32 | 6 | 64 |
| 10 | 355 | 469 | 1,024 | 11 | 2,048 |
| 11 | 696 | 527 | 2,048 | 12 | 4,096 |
| 12 | 1,542 | 731 | 4,096 | 13 | 8,192 |
| 13 | 2,402 | 759 | 8,192 | 14 | 16,384 |
| 14 | 7,012 | 1,170 | 16,384 | 15 | 32,768 |
| 15 | 13,733 | 1,865 | 32,768 | 16 | 65,536 |
ケース5: N社への分割と全社合併を5回繰り返して1社に収束する
| 形状 | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|
| (N分割→1つに収束)×5段 | N5 | 10 | 5N+6 |
結果
| N | GQL (ms) | SQL (ms) | 経路数 | パスの長さ | ノード数 |
|---|---|---|---|---|---|
| 2 | 38 | 390 | 32 | 10 | 16 |
| 6 | 479 | 390 | 7,776 | 10 | 36 |
| 7 | 829 | 409 | 16,807 | 10 | 41 |
| 8 | 1,302 | 433 | 32,768 | 10 | 46 |
| 9 | 2,630 | 400 | 59,049 | 10 | 51 |
| 10 | 4,321 | 398 | 100,000 | 10 | 56 |
| 11 | 6,799 | 422 | 161,051 | 10 | 61 |
| 12 | 10,919 | 469 | 248,832 | 10 | 66 |
| 13 | 15,521 | 380 | 371,293 | 10 | 71 |
| 14 | 22,099 | 370 | 537,824 | 10 | 76 |
| 15 | 32,800 | 400 | 759,375 | 10 | 81 |
| 16 | 42,148 | 372 | 1,048,576 | 10 | 86 |
| 17 | 47,962 | 381 | 1,419,857 | 10 | 91 |
| 18 | 75,209 | 370 | 1,889,568 | 10 | 96 |
| 19 | 99,211 | 380 | 2,476,099 | 10 | 101 |
| 20 | 106,107 | 391 | 3,200,000 | 10 | 106 |
考察
パスの長さについて
ケース1でパスの長さのみを変える実験を行いましたが、1~100まで伸ばしても30ms→40msと結果はほぼ変わらずでした。
また、ケース3のように1000分割からチェーンを伸ばしていく実験においても、パスの長さを2→100に増加させても108ms→647ms程度の差しか確認できませんでした。
このことから、Spanner Graphにおいてパスの長さがパフォーマンスに及ぼす影響は軽微のようです。
一方、従来のSQLは合併のチェーンが長くなるにつれて参照やJOINの必要数が増えるため、レイテンシーが伸びる傾向にありました。長いチェーン構造でも数十msで辿れるのはSpanner Graphの大きな利点と言えそうです。
幅について
ケース2では企業の分割数を増やす実験を行いましたが、単純に分割数を増やして終点のノード数が増えても、パフォーマンスへの影響は軽微のようです。
経路数について
パフォーマンスが急激に悪化したのは、複数の経路が同一のノードに収束するケースでした。
バイナリの合併ツリーで検証したケース4においては、N=10（経路数1,024）では355msと実用的な速度でしたが、N=11（経路数2,048）で696ms、N=15（経路数32,768）では13,733msまで増大しました。
経路数が倍増するにつれて応答時間も倍増していて、このグラフ構造では経路数に対して線形にスケールしていることもわかりました。
多くのエッジが一つに収束したノードが連なった構造で検証したケース5においては、経路数がN5で増加するため、10個のエッジが収束したノードが5つ連なっただけで4秒以上のレイテンシーになることが確認できました。
経路数が 50 万あたりで既に20秒程度かかっていることから、実際にSpanner Graphの採用を検討するときはこの規模の経路数の爆発が頻繁に起きるかどうかが主な論点になりそうです。
一方で従来のSQLは1秒もかからないことから、頻繁に合流が起きるようなケースではSQLを利用してあげるのも一つの選択肢になりそうです。
また今回の検証では扱いませんでしたが、Spanner Graphのクエリチューニングのガイドによると走査対象のエッジを制限することも有効とされているため、利用できる場面ではこちらも検討してみると良いかもしれません。
同一経路数にも関わらず実行速度が約10倍違うケースについて
ケース4のN=15とケース5のN=8では経路数は同じ32,768ですが、ケース4は13sかかり、ケース5は1.3s程度で完了しています。よって、実行速度はケース5の方が約10倍早いため、同じ経路数だとしてもグラフの形状によって速度が変わることもわかりました。
（表を抜粋して再掲）
| ケース | 概要 | GQL (ms) | SQL (ms) | 経路数 | ノード数 |
|---|---|---|---|---|---|
| 4 | 215分割→1つに収束 | 13,733 | 1,865 | 32,768 | 65,536 |
| 5 | 8つに分割→収束 × 5 | 1,302 | 433 | 32,768 | 46 |
実際にSpanner Studioの実行計画を確認すると、エッジスキャンの実行回数に差があることがわかりました。
| 指標 | ケース4 N=15（13,733ms） | ケース5 N=8（1,302ms） |
|---|---|---|
| エッジスキャン実行回数 | 524,289 回 | 74,897 回 |
| 読み込みデータ量 | 2.47 GB | 4.4 MB |
この差が生まれる理由はおそらく、Spanner Graphが内部で「ノード＋そこに至る経路の組み合わせ」単位で状態を管理しているからと思われます。つまりあるノードに2本の経路が到達していれば、そのノードへのスキャンが2回実行されていると見られます。
ケース4のN=15 のグラフは source → 32,768 → 16,384 → 8,192 → … → 1最終ノード という構造であり、各ステップのスキャン回数を追うと次のようになります。
| ステップ | 各ステップのノードと入力経路数 | スキャン回数 |
|---|---|---|
| 1（分割） | 32,768ノード × 各1経路 | 32,768回 |
| 2（合併1） | 16,384ノード × 各2経路 | 32,768回 |
| 3（合併2） | 8,192ノード × 各4経路 | 32,768回 |
| ⋮（全16） | ⋮ | 32,768回 |
| 合計 | - | 1 + 16 × 32,768 = 524,289回 |
一方ケース5は、最初の分割では8経路のみでグラフの出口付近で経路の爆発が起きるため序盤のコストが低く、スキャン回数の合計は1/8程度に抑えられています。
| ステップ | 各ステップのノードと入力経路数 | スキャン回数 |
|---|---|---|
| R1・分割 | 8ノード × 各1経路 | 8回 |
| R1・合併 | 1ノード × 8経路 | 8回 |
| R2・分割 | 8ノード × 各8経路 | 64回 |
| R2・合併 | 1ノード × 64経路 | 64回 |
| ... | ... | ... |
| R5・分割 | 8ノード × 各4,096経路 | 32,768回 |
| R5・合併 | 1ノード × 32,768経路 | 32,768回 |
| 合計 | - | 1 + 2×(8+64+512+4,096+32,768) = 74,897回 |
このように、経路のうち浅い箇所で経路数が爆発している場合は、データのスキャン回数もボトルネックになっていました。
以上より、辿る経路の数だけでなく間のノードと経路のパターンも、スキャンコストの観点でパフォーマンスに影響していることがわかりました。
※ 厳密には、ケース4の13sの大半はスキャン処理そのものではなく、52万回のスキャン結果を都度結合する処理が支配的でした。スキャン1回あたりは約1〜2マイクロ秒ですが、「スキャン回数が多い→中間結果が増える→結合コストも増える」という連鎖により、スキャン回数の多さがボトルネックにつながっています。
※ Spanner Graphのスキーマガイドによると、interleaveも有効である旨が記載されていました。今回のようにスキャンがボトルネックになっているケースの最適化時はこちらのガイドも参考にしてみると良いと思います。
あとがき
今回の検証ではグラフデータの「パスの長さ」「幅」「経路数」の三つに焦点を当てて検証を行いました。
結論として、Spanner Graphのパフォーマンスを左右する要因として経路数が支配的であることがわかりました。パスの長さ・分割数は単体ではほとんど影響せず、経路数が急増する構造（エッジが収束する構造）の有無が鍵になることがわかりました。
また、エッジスキャンのデータ量も無視できないため、経路数の増大タイミングもパフォーマンスに影響を及ぼすことも確認できました。
先のシンプルな例でもわかるように、企業や事業所を時間軸で状態管理するMaster Data Systemにおいて、Spanner Graphは従来のSQLでは複雑なJOINや再帰が必要だった箇所を、直感的なグラフクエリで表現できる強力なツールです。
ただ今回の検証からわかるように一部の経路数が増大するケースではパフォーマンスの劣化が顕著になります。
例:
- 多数の企業が段階的に合併を繰り返すような複雑な組織再編
- 一つの企業に多数の企業が収束するような構造が連鎖する場合
今回の検証のような経路数が爆発する企業が出てきた場合には、適度なクエリ分割やSQLとのハイブリッドな運用、ショートカットを作る設計などが求められることになります。
よって結論としてはグラフ構造のデータだからSpanner Graphだけで良い、とはならずGQL・SQL双方のクエリパターンが持つ特性を理解して使い分ける必要がありそうです。
ぜひ本検証を参考にグラフ構造データを扱う際には、Spanner Graphを選択肢の一つとして検討してみてください。
最後までお読みいただき、ありがとうございました。
カジュアル面談
Sansan技術本部では中途の方向けにカジュアル面談を実施しています。Sansan技術本部での働き方、仕事の魅力について、現役エンジニアの視点からお話しします。「実際に働く人の話を直接聞きたい」「どんな人が働いているのかを事前に知っておきたい」とお考えの方は、ぜひエントリーをご検討ください。
採用イベント
3月31日（火）に採用説明会を行います。 Sansan Data IntelligenceのProduct Ownerやエンジニアから「新規プロダクト立ち上げフェーズの開発や組織づくり」や「どんなメンバーが働いていてどんな課題に挑戦できるのか」などの話が聞けるイベントになっています。興味のある方は以下のリンクよりエントリーの上ぜひご参加下さい。
