読者です 読者をやめる 読者になる 読者になる

F@N Ad-Tech Blog

株式会社ファンコミュニケーションズ nend・nex8のエンジニア・技術ブログ

RDBとグラフDBは使いよう ~ MariaDB様がみてる vs. InnoDBさんとNeo4jさん

Cypher DataStore graph database InnoDB MariaDB MySQL Neo4j OQGRAPH k_oomori

 ごきげんよう。k_oomoriです。業務でデータノード間の関連性を追いかけるようなクエリが投げたくなったので、グラフデータベースについて調べてみました。ここではネイティブなグラフDBであるNeo4j、本来はRDBであるMariaDBのグラフ計算用エンジンとして開発されたOQGRAPH、それとお馴染みのInnoDBを直接グラフ問題に適用した例を試してみようと思います。
 なお、検証に用いたサーバは全てAWSのc3.large EC2インスタンス(CPU: Intel Xeonプロセッサ2.8GHz×2, メモリ: 4GB)で、OSはUbuntu 14.04になります。

Neo4j

インストール

 Neo4jNeo Technology社が開発しているJavaで実装されたグラフデータベースソフトウェアであり、NoSQLデータベースに分類されます。オープンソースのコミュニティ版と商用パッケージ版のデュアルライセンスで提供されていますが、ここではコミュニティ版を用いて検証します。Neo4jのインストールは、例えばDebian系Linuxでは以下の手順で行うことができます [公式]。

# wget -O - http://debian.neo4j.org/neotechnology.gpg.key| apt-key add -
# echo 'deb http://debian.neo4j.org/repo stable/' > /etc/apt/sources.list.d/neo4j.list
# aptitude update -y
# aptitude install neo4j -y

今回試したサーバーバージョンは2.1.2です。インストールすると自動でサービスが起動していると思いますが、手動で起動・停止するには以下のようにします。

# service neo4j-service start
# service neo4j-service stop

グラフ型データモデル

 準備が整ったところで実際のデータを扱ってみます。まずは例として、次のようなグラフを考えましょう。※1 f:id:fancs:20160502140501p:plain これは、プロパティグラフモデル(property graph model)と呼ばれるモデル化手法に基づいており、次のような特徴を持っています。

  • プロパティグラフはノード(node)、リレーションシップ(relationship)、プロパティ(property)によって構成される。
  • ノード及びリレーションシップは、属性名-属性値のキーバリューペアの形のプロパティを持つことができる。
  • リレーションシップは開始ノードと終端ノードの間の関係性を表し、向きとラベルを持つ。

ではこれをNeo4jに登録するため、Neo4jシェルを立ち上げます※2

$ neo4j-shell

データを操作するクエリ言語として、ここではCypherを用います※3。Neo4jはスキーマレスなのでデータ構造を事前に定義する必要はありません。データを登録するには次のようなCREATE文をNeo4jシェルに流します。

neo4j-sh (?)$ CREATE (a:Person {name:"A", age:30}), (b:Person {name:"B", age:25}), (c:Person {name:"C", age:40}), 
(inuhasa:Item {name:"犬とハサミは使いよう Blu-ray(1)", genre:"Anime"}), 
(marimite:Item {name:"マリア様がみてる 1stシーズン DVD-BOX", genre:"Anime"}), 
(inuneko:Item {name:"犬神さんと猫山さん [Blu-ray]", genre:"Anime"}), 
(graphdb:Item {name:"Graph Databases [ペーパーバック]", genre:"Technology"}), 
(neo4j:Item {name:"Neo4j in Action [ペーパーバック]", genre:"Technology"}), 
(mysql:Item {name:"実践ハイパフォーマンスMySQL 第3版", genre:"Technology"}), 
(a)-[:FRIEND]->(b), (b)-[:FRIEND]->(a), (a)-[:KNOWS]->(c), 
(a)-[:PURCHASE {date: "2014-01-01"}]->(graphdb),
(a)-[:PURCHASE {date: "2014-07-18"}]->(inuneko),
(a)-[:INTEREST]->(neo4j),
(b)-[:PURCHASE {date: "2013-09-20"}]->(inuhasa),
(b)-[:INTEREST]->(marimite),
(b)-[:PURCHASE {date: "2014-07-18"}]->(inuneko),
(c)-[:PURCHASE {date: "2013-06-17"}]->(graphdb),
(c)-[:RESERVE {release_date: "2014-08-31"}]->(neo4j),
(c)-[:PURCHASE {date: "2013-11-25"}]->(mysql);

ここで "neo4j-sh (?)$" はNeo4jのプロンプトを表しています。簡単に説明しておくと、(graphdb:Item {name:"Graph Databases [ペーパーバック]", genre:"Technology"})はノードを表しており、graphdbはそのノードを後で参照するための変数名、Itemはラベル、{}内はそのノードの持つプロパティとなります。(c)-[:PURCHASE {date: "2013-06-17"}]->(graphdb)はノードcからノードgraphdbに向かうリレーションシップで、PURCHASEがラベル(もしくはリレーションシップタイプ)、{}内がリレーションシップの持つプロパティです。従ってこれは「cさんがgraphdbというアイテムを2013年6月17日に購入した」という関係性を表現しています。
 次にnameプロパティの値によってノードを指定できるようにするため、ラベルに対してインデックスを作成します。※4

neo4j-sh (?)$ CREATE INDEX ON :Person(name);
neo4j-sh (?)$ CREATE INDEX ON :Item(name);

 それではいくつかデータを取得するCypherクエリを流してみましょう。まずはAさんの購入履歴を日付の降順で表示してみます。

neo4j-sh (?)$ MATCH (a:Person {name:"A"})-[p:PURCHASE]->(i:Item) 
RETURN i.name, p.date ORDER BY p.date DESC;
+---------------------------------------------------+
| i.name                             | p.date       |
+---------------------------------------------------+
| "犬神さんと猫山さん [Blu-ray]"     | "2014-07-18" |
| "Graph Databases [ペーパーバック]" | "2014-01-01" |
+---------------------------------------------------+

MATCH句においてマッチさせたいパターンをアスキーアート的に表現します。ここでは"A"という名前のPersonノードを始点とし、PURCHASEという関係性によって関連付けられたItemノードを探索しています。ORDER BY句でソート順序を、RETURN句で何を返すかを指定します。始点の特定は、よりSQLに近い次のような方法も可能です(もちろん同じ結果が得られます)。

neo4j-sh (?)$ MATCH (a:Person)-[p:PURCHASE]->(i:Item) WHERE a.name="A" 
RETURN i.name, p.date ORDER BY p.date DESC;

 次に、Aさんがログインしてきたときに、Aさんの友達が買っている商品をおすすめするには

neo4j-sh (?)$ MATCH (a:Person {name:"A"})-[:FRIEND]-()-[:PURCHASE]->(i:Item) 
RETURN DISTINCT i.name;
+-----------------------------------+
| i.name                            |
+-----------------------------------+
| "犬とハサミは使いよう Blu-ray(1)" |
| "犬神さんと猫山さん [Blu-ray]"    |
+-----------------------------------+

データ作成時にはリレーションシップはいずれかの向きを持つ必要がありますが、取得時には矢印をつけずにどちらにもマッチさせることが可能です(※パフォーマンスについては後述)。またAさんの友達(この例ではBさん)自身に関する情報には興味がないため、()にノードを束縛するための変数名をつけていません。DISTINCTはSQL同様、重複を排除します。この結果、AさんのFRIENDであるBさんの購入商品一覧を返すことができます。
 最後の例として、誰かが犬神さんと猫山さん [Blu-ray]を購入したときに、同じジャンルの中で「この商品を買った人はこんな商品も買っています」をやるためには

neo4j-sh (?)$ MATCH (y:Item)<-[:PURCHASE]-(x:Person)-[:PURCHASE]->(i:Item {name:"犬神さんと猫山さん [Blu-ray]"})
WHERE y.genre=i.genre RETURN DISTINCT y.name;
+-----------------------------------+
| y.name                            |
+-----------------------------------+
| "犬とハサミは使いよう Blu-ray(1)" |
+-----------------------------------+

Aさんは犬神さんと猫山さん [Blu-ray]の他にGraph Databases [ペーパーバック]も買っていますが、ジャンルが異なるため抽出対象とはなっていません。
 なお、MySQLにおけるEXPLAINに相当するものとしてPROFILEがあります。

neo4j-sh (?)$ PROFILE MATCH (a:Person {name:"A"})-[p:PURCHASE]->(i:Item) RETURN i.name, p.date ORDER BY p.date DESC;
+-----------------------------------------------------+
| i.name                               | p.date       |
+-----------------------------------------------------+
| "犬神さんと猫山さん [Blu-ray]"       | "2014-07-18" |
| "Graph Databases [ペーパーバック]"   | "2014-01-01" |
+-----------------------------------------------------+
2 rows

ColumnFilter
  |
  +Sort
    |
    +Extract
      |
      +Filter
        |
        +TraversalMatcher

+------------------+------+--------+-------------+-----------------------------+
|         Operator | Rows | DbHits | Identifiers |                       Other |
+------------------+------+--------+-------------+-----------------------------+
|     ColumnFilter |    2 |      0 |             | keep columns i.name, p.date |
|             Sort |    2 |      0 |             |  Cached(p.date of type Any) |
|          Extract |    2 |      8 |             |              i.name, p.date |
|           Filter |    2 |      2 |             |         hasLabel(i:Item(1)) |
| TraversalMatcher |    2 |      7 |             |                     i, p, i |
+------------------+------+--------+-------------+-----------------------------+

Total database accesses: 17

双方向/無向リレーションシップ

 上記の例に出てきたPURCHASEリレーションシップは、人が商品を購入することはあっても逆に商品が人を購入するということはないので、自然に向きがつきます。人同士においてもKNOWS(知っている)という関係は、片方が有名人でもう片方が一般人だったりするケースがあるので、やはり向きを持ちます。一方、友達関係なんかは(俺はあいつのことを友達だと思っていたのに、あいつはそうは思っていなかった…という悲しいケースを除いて)特定の向きは持ちません。リレーションシップを作成する際に必ずどちらかの向きをつけなければならないという前提の下では、このような無向のリレーションシップをモデル化する方法は2通りあって、

  1. 今回のAさんとBさんの例のように2ノード間に双方向のリレーションシップを張り、どちらの方向にも辿れるようにする
  2. どちらか一方のみリレーションシップを張り(向きは任意)、辿る際に向きを気にしない

どちらかというと1.の方が対称性があって美しいような気もしますが、実際に計測してみると、こちらに書かれている通り2.の方が高速なようです。

パフォーマンステスト

 クエリのパフォーマンスを調べるため、テストデータとして100万ノードを登録し、各ノードからランダムに2ノードへのリレーションシップを張ります。これをCREATE文で全部登録するのはつらいので、CSVファイルから読み込む方法を紹介します。MySQLのLOAD DATA INFILE構文みたいなものですね。まずはノードですが、今回はID以外に特に属性はいらないので

id
1
2
…
1000000

を/tmp/nodes.datとして保存します。リレーションシップの方は開始ノードと終端ノード(ランダム)を指定して

from,to
1,226064
1,500570
2,326457
2,354377
…
1000000,919215
1000000,992803

を/tmp/relationships.datとして保存します。そして次のコマンドを流せば登録完了です。

neo4j-sh (?)$ LOAD CSV WITH HEADERS FROM "file:///tmp/nodes.dat" AS csvLine CREATE (p:Person {id: toInt(csvLine.id)});
neo4j-sh (?)$ CREATE INDEX ON :Person(id);
neo4j-sh (?)$ LOAD CSV WITH HEADERS FROM "file:///tmp/relationships.dat" AS csvLine
MATCH (f:Person {id: toInt(csvLine.from)}), (t:Person {id: toInt(csvLine.to)})
CREATE (f)-[:KNOWS]->(t);

このデータを用いて例えば「id=1のノードの知人の知人の知人」の数を求めるには以下のようにします。

neo4j-sh (?)$ MATCH (a:Person)-[:KNOWS*3]->(b:Person) WHERE a.id=1 RETURN count(b.id);
+-------------+
| count(b.id) |
+-------------+
| 8           |
+-------------+

我々が実際に使いたいのは無向グラフであるという事情があるので、以下は向きを気にしないマッチ (a:Person)-[:KNOWS*n]-(b:Person) でパフォーマンスチェックを行います(両方を見なければならないので、一方向にのみ辿る場合よりはだいぶ遅くなります)。辿る回数(ステップ数)をnとして(先ほどの知人の知人の知人ならn=3)、13までのnに対して計算にかかった時間と取得件数を表にまとめると以下のようになりました。時間は3回計測を行い、その平均としています。

n 時間[ms] 件数
3 6 42
4 8 137
5 12 445
6 26 1,515
7 83 5,088
8 270 17,212
9 948 57,551
10 3,392 181,612
11 12,126 485,334
12 44,708 874,060
13 188,502 997,390

ステップ数を横軸に、かかった時間を対数目盛で縦軸にとってグラフ化すると次のようになります(ただし、n≦5だと叩くタイミングによって数ミリ秒の差が出てしまい、計測値に対する誤差の割合が大きすぎるので省いてあります)。 f:id:fancs:20160502140552p:plain Neo4j query performance

このグラフから、計測点がきれいに直線上に乗っていることがわかります。従ってNeo4jではこの手のクエリの所要時間はステップ数に指数関数的に依存するということがわかります [参考]。つまり、対象となるグラフの平均次数をdとすると(現在の例ではd=4)、ステップ数を1つ増やすたびに計算時間が約d倍になるので、現実的に辿ることができるステップ数には限界があります。(むしろ100万ノードもある中で1秒以内に9回も辿れる方がすごい!という見方もできます)

最短経路問題

 これまでは関係性を順に辿っていく、所謂"friend-of-a-friend"スタイルのクエリを見てきましたが、グラフ理論におけるもう一つの典型的問題として最短経路問題 (shortest path problem) があります。各リレーションシップに所要時間や金額といった重みを持たせ、与えられた始点と終点を結ぶ経路の中で重みの合計が最小になるような経路を見つけるという問題です。Neo4jでは、次のようなクエリによって最短経路を探します。

neo4j-sh (?)$ MATCH (a:Person {id:1}), (b:Person {id:94047}), p=shortestPath((a)-[*..15]-(b)) RETURN p;
+--------------------------------------------------------------------------------------------------------------------------------------+
| p                                                                                                                                    |
+--------------------------------------------------------------------------------------------------------------------------------------+
| [Node[0]{id:1},:KNOWS[0]{},Node[500569]{id:500570},:KNOWS[1001138]{},Node[455341]{id:455342},:KNOWS[810682]{},Node[94046]{id:94047}] |
+--------------------------------------------------------------------------------------------------------------------------------------+

これはid=1のノードとid=94047のノードを結ぶ経路のうち最短のものを、15ステップ以内までという制限つきで調べるというものです。結果は1→500570→455342→94047という最短経路が見つかったことを示しています。これは3ステップ必要なので、上限ステップ数を2にして検索すると見つからなくなります。

neo4j-sh (?)$ MATCH (a:Person {id:1}), (b:Person {id:94047}), p=shortestPath((a)-[*..2]-(b)) RETURN p;
+---+
| p |
+---+
+---+

 我々は今のところ業務で最短経路問題を扱う計画がないので、詳細な検証は省かせていただきます。

参考書

 Neo4jの書籍としては、2014年9月現在では翻訳書も含めて日本語のものは出版されていないと思われます。英語の書籍ではO'ReillyのGraph Databasesがあります。蛸です。Graph Databasesと銘打ってはいますが、著者がNeo Technologyの中の人であることもあり、グラフDBの一般論というよりはNeo4jの本だと思った方がよいでしょう。こちらから名前やメールアドレスといった個人情報と引き換えにPDF版を無料でダウンロードすることもできます。

アンインストール

 今の僕には理解できない という方は

# aptitude remove neo4j #設定ファイルは残す
# aptitude purge neo4j  #設定ファイルも削除

MariaDB OQGRAPH Storage Engine

 MariaDBは言わずと知れたMySQLの妹分であり、リレーショナルデータベース(RDB)の代表格ですが、ストレージエンジンレベルでグラフ操作を可能にしたものがOQGRAPHです。参考資料を探してみたのですが、Open Query社のサイトMariaDB公式ページの説明以外になかなか見つかりません。なので最初に白状しておくと、この章はちょっとした紹介レベルで終了しますw
 MariaDB自体のインストールについては割愛させていただきます。yumやapt-getなどで適当に入れておいてください。ただし、OQGRAPHを使うには、MariaDB 10.0.7以上が必要です。今回実際に用いたサーバーバージョンは10.0.12になります。OQGRAPHのインストールはMariaDB公式サイトを参考にして

$ sudo apt-get install mariadb-oqgraph-engine-10.0 #パッケージをインストール
$ mysql -u root -p #"MariaDB"に接続
MariaDB [(none)]> INSTALL PLUGIN oqgraph SONAME 'ha_oqgraph'; #プラグインをインストール

OQGRAPHが正しく動作するためにはクエリキャッシュを無効にしなければならないとのことですので

MariaDB [(none)]> SET GLOBAL query_cache_size = 0;
MariaDB [(none)]> SET GLOBAL query_cache_type = 0;
MariaDB [(none)]> flush query cache;
MariaDB [(none)]> reset query cache;

 適当なデータベースを作成した後、テーブルの作成を行います。OQGRAPHでは2種類のテーブルを作る必要があります: 一つは実際のデータを格納するための通常の(=InnoDB)テーブル、もう一つはOQGRAPHのインターフェイスとなるENGINE=OQGRAPHなテーブルです。前者の"backing table"は始点ID(origid)と終点ID(destid)を持つだけの

CREATE TABLE oq_backing (
  origid INT UNSIGNED NOT NULL, 
  destid INT UNSIGNED NOT NULL,  
  PRIMARY KEY (origid, destid), 
  KEY (destid)
);

とします。OQGRAPHではNeo4jのような「向きを気にせず辿る」といった芸当はできないので、無向リレーションシップは双方向にリンクを作ることで実現します。

INSERT INTO oq_backing VALUES
(2,0),(2,1),(2,3),(2,4),
(3,1),(3,2),(3,4),(3,5),
…
(999999,999997),(999999,999998),(999999,0),(999999,1),
(0,999998),(0,999999),(0,1),(0,2),
(1,999999),(1,0),(1,2),(1,3);

次にread onlyなOQGRAPHテーブルを作成します。

CREATE TABLE oq_graph (
  latch VARCHAR(32) NULL,
  origid BIGINT UNSIGNED NULL,
  destid BIGINT UNSIGNED NULL,
  weight DOUBLE NULL,
  seq BIGINT UNSIGNED NULL,
  linkid BIGINT UNSIGNED NULL,
  KEY (latch, origid, destid) USING HASH,
  KEY (latch, destid, origid) USING HASH
) 
ENGINE=OQGRAPH 
data_table='oq_backing' origid='origid' destid='destid';

最終行で先ほど作ったbacking tableに合わせたテーブル名、カラム名を指定しますが、これ以外については基本的にこの通り打ち込んでください。ほんのちょっとでも違ってたらエラーを出すよ!とのことです。

 それでは早速クエリを投げてみましょう。Neo4jのようなNoSQLとは異なり、あくまでも投げるクエリはSQLです。まずは最短経路問題から。

SELECT GROUP_CONCAT(linkid ORDER BY seq) AS path FROM oq_graph 
WHERE latch='dijkstras' AND origid=0 AND destid=10;
+--------------+
| path         |
+--------------+
| 0,2,4,6,8,10 |
+--------------+
1 row in set (0.03 sec)

oq_backingではなくoq_graphに対してクエリを投げていることに注意してください。linkidが途中のノードIDを表すので、ID=0から出発してID=10に到達するための最短経路は0→2→4→6→8→10であることがわかります。latch='dijkstras'は探索アルゴリズムとしてダイクストラ法を用いることを表しています。latch='breadth_first'とすると代わりに幅優先探索が使われるようです。
 今回は簡単のためoq_backingにweightをつけなかったので単純にステップ数が少ないものが最短経路になりますが、weightをつけてあげると重みの合計が最小の経路を探すようになります。

 では次にfriend-of-a-friendスタイルのクエリを。ID=0から1ステップで辿りつけるノードは…

SELECT * FROM oq_graph WHERE latch='dijkstras' AND origid=0 AND weight=1;
+-----------+--------+--------+--------+------+--------+
| latch     | origid | destid | weight | seq  | linkid |
+-----------+--------+--------+--------+------+--------+
| dijkstras |      0 |   NULL |      1 |    5 | 999998 |
| dijkstras |      0 |   NULL |      1 |    4 |      2 |
| dijkstras |      0 |   NULL |      1 |    3 | 999999 |
| dijkstras |      0 |   NULL |      1 |    2 |      1 |
+-----------+--------+--------+--------+------+--------+
4 rows in set (18.11 sec)

ん?18秒もかかる?じゃあ一気に伸ばして10ステップで辿りつけるノードは…

SELECT * FROM oq_graph WHERE latch='dijkstras' AND origid=0 AND weight=10;
+-----------+--------+--------+--------+------+--------+
| latch     | origid | destid | weight | seq  | linkid |
+-----------+--------+--------+--------+------+--------+
| dijkstras |      0 |   NULL |     10 |   41 |     19 |
| dijkstras |      0 |   NULL |     10 |   40 | 999981 |
| dijkstras |      0 |   NULL |     10 |   39 | 999980 |
| dijkstras |      0 |   NULL |     10 |   38 |     20 |
+-----------+--------+--------+--------+------+--------+
4 rows in set (18.01 sec)

うん、要するにorigid=0から必要最小限のリレーションを辿っていってるのではなくて、あらゆる可能な経路を調べあげた上で、たまたまweightが指定のものになってるのを返してるだけですね。だめじゃん!

InnoDB

 …気を取り直してMariaDBのInnoDBです。実装としてはXtraDBらしいのですが、以下のようにMariaDBにはInnoDBと言ってあげないと通じないようなのでInnoDBで通します。

MariaDB [oqgraph_test]> show engines;
+--------+---------+----------------------------------------------------------------------------+--------------+------+------------+
| Engine | Support | Comment                                                                    | Transactions | XA   | Savepoints |
+--------+---------+----------------------------------------------------------------------------+--------------+------+------------+
| InnoDB | DEFAULT | Percona-XtraDB, Supports transactions, row-level locking, and foreign keys | YES          | YES  | YES        |
+--------+---------+----------------------------------------------------------------------------+--------------+------+------------+
(↑一部のみ抜粋)

MariaDB [oqgraph_test]> create table hoge (id int) engine=XtraDB;
Query OK, 0 rows affected, 2 warnings (0.15 sec)

MariaDB [oqgraph_test]> show warnings;
+---------+------+----------------------------------------------+
| Level   | Code | Message                                      |
+---------+------+----------------------------------------------+
| Warning | 1286 | Unknown storage engine 'XtraDB'              |
| Warning | 1266 | Using storage engine InnoDB for table 'hoge' |
+---------+------+----------------------------------------------+
2 rows in set (0.00 sec)

 先ほどのbacking table同様、始点と終点を持つ次のようなテーブルを用いることにします。

CREATE TABLE `innodb_test` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `origid` int(10) unsigned NOT NULL,
  `destid` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`),
  KEY `combined` (`origid`,`destid`),
  KEY `destid` (`destid`)
) ENGINE=InnoDB;

Neo4jのときと同様、テストデータとして100万ID用意し、各ノードからランダムに選んだ2ノードへのリレーションシップを、今回は双方向に張ります。

INSERT INTO innodb_test(origid, destid) VALUES 
(1,876952),(876952,1),(1,243025),(243025,1),
(2,661894),(661894,2),(2,940629),(940629,2),
…
(1000000,675933),(675933,1000000),(1000000,682044),(682044,1000000);

愚直なJOINによってグラフ探索を実現します。4ステップの場合は

select distinct t4.destid from innodb_test t1
inner join innodb_test t2 on t1.destid=t2.origid
inner join innodb_test t3 on t2.destid=t3.origid
inner join innodb_test t4 on t3.destid=t4.origid
where t1.origid=100 order by 1;

ID=100から出発して、繋がっているdestidを次のテーブルのorigidに設定して、そのdestidを次のテーブルのorigidに…の繰り返しです。explainで見てみると、indexでガチガチに固められていることがわかります。

MariaDB [oqgraph_test]> explain select distinct t4.destid from innodb_test t1
    -> inner join innodb_test t2 on t1.destid=t2.origid
    -> inner join innodb_test t3 on t2.destid=t3.origid
    -> inner join innodb_test t4 on t3.destid=t4.origid
    -> where t1.origid=100 order by 1;
+------+-------------+-------+------+-----------------+----------+---------+------------------------+------+----------------------------------------------+
| id   | select_type | table | type | possible_keys   | key      | key_len | ref                    | rows | Extra                                        |
+------+-------------+-------+------+-----------------+----------+---------+------------------------+------+----------------------------------------------+
|    1 | SIMPLE      | t1    | ref  | combined,destid | combined | 4       | const                  |    5 | Using index; Using temporary; Using filesort |
|    1 | SIMPLE      | t2    | ref  | combined,destid | combined | 4       | oqgraph_test.t1.destid |    1 | Using index                                  |
|    1 | SIMPLE      | t3    | ref  | combined,destid | combined | 4       | oqgraph_test.t2.destid |    1 | Using index                                  |
|    1 | SIMPLE      | t4    | ref  | combined        | combined | 4       | oqgraph_test.t3.destid |    1 | Using index                                  |
+------+-------------+-------+------+-----------------+----------+---------+------------------------+------+----------------------------------------------+

 それではパフォーマンステストに移りましょう。ステップ数nに対し次の結果が得られました。

n 時間[ms] 件数 Neo4jでの時間[ms]
6 10 1,392 26
7 20 4,689 83
8 100 15,745 270
9 450 52,702 948
10 2,070 167,755 3,392
11 12,810 456,999 12,126
12 127,150 852,623 44,708
13 615,200 994,991 188,502

比較のためNeo4jでかかった時間も再掲してあります。これをグラフ化すると次のようになります。 f:id:fancs:20160502140631p:plain InnoDB query performance

これを見ると、InnoDBではステップ数が増えるにつれて指数関数よりなお悪く時間が延びていっていることがわかります。また、当然のことながらRDBはグラフ問題をサポートするよう設計されているわけではないので、最短経路問題や複雑なグラフ探索をDBレベルで取り扱うことはできません。とはいえ、10ステップまでならNeo4jより速いという結果も得られたことから、ステップ数の決まったガチガチのfriend-of-a-friendクエリを流すことに限定すれば、InnoDBも選択肢として充分アリなのではないかと思います。

Summary

 We first introduced Neo4j as an implementation of graph database. We have seen how to use Cypher query language to register and retrieve data. We then conducted performance measurement containing one million nodes and found that the execution time grew exponentially with the increase of depth to be traced. We also mentioned how to treat shortest path problems with Neo4j.
 Secondly we touched OQGRAPH computation engine implemented for MariaDB. It enables us to tackle graph problems using standard SQL syntax, although we don't know how to execute queries of the "friend-of-a-friend" style efficiently...
 Finally we showed that InnoDB could also be applied to a particular class of graph traversal problems, i.e. friend-of-a-friend style queries with the depth specified. We think that InnoDB, though not designed for graph traversal, may be useful in this very limited situation.

References

[1] グラフDBのNeo4jを1日触ってみた - Wantedly Engineer Blog
[2] Neo4jで学ぶGraph DB入門 - omotenashi-mind
[3] グラフデータベース「Neo4j」の 導入の導入
[4] グラフデータベース、NOSQL、Neo4j
[5] Neo4j Cypher Refcard 2.1
[6] GRAPH Computation Engine - Documentation
[7] OQGRAPH - MariaDB Knowledge Base


※1. ^ このグラフはNeoclipseを使って可視化したものです。
※2. ^ "neo4j クエリ"などでググるとCypherの説明とかはいっぱい出てくるのですが、果たしてそれをどこに打ち込んだらいいのか、筆者は結構悩みました…。
※3. ^ CypherはNeo4j専用言語のため、他のグラフデータベースでは使うことができません。Neo4jは他にもGremlinやSPARQLといったクエリ言語をサポートしているようですが、ここでは触れません。
※4. ^ CREATE INDEXで作成されるインデックスはschema indexと呼ばれ、Neo4jには別にlegacy indexと呼ばれるものもあります [参考]。ここでは詳細は割愛しますが、schema indexはSTART句では使えないなど、注意が必要です。