k_oomoriごきげんよう。k_oomoriです。業務でデータノード間の関連性を追いかけるようなクエリが投げたくなったので、グラフデータベースについて調べてみました。ここではネイティブなグラフDBであるNeo4j、本来はRDBであるMariaDBのグラフ計算用エンジンとして開発されたOQGRAPH、それとお馴染みのInnoDBを直接グラフ問題に適用した例を試してみようと思います。14.04になります。Technology社が開発しているJavaで実装されたグラフデータベースソフトウェアであり、NoSQLデータベースに分類されます。オープンソースのコミュニティ版と商用パッケージ版のデュアルライセンスで提供されていますが、ここではコミュニティ版を用いて検証します。-y今回試したサーバーバージョンは2.1.2です。インストールすると自動でサービスが起動していると思いますが、手動で起動・停止するには以下のようにします。stopグラフ型データモデル準備が整ったところで実際のデータを扱ってみます。例として、次のようなグラフを考えましょう。model)と呼ばれるモデル化手法に基づいており、次のような特徴を持っています。プロパティグラフはノード(node)、リレーションシップ(relationship)、プロパティ(property)によって構成される。ノード及びリレーションシップは、属性名-属性値のキーバリューペアの形のプロパティを持つことができる。リレーションシップは開始ノードと終端ノードの間の関係性を表し、向きとラベルを持つ。これをNeo4jに登録するため、Neo4jシェルを立ち上げます※2。neo4j-shellデータを操作するクエリ言語として、ここではCypherを用います※3。Neo4jはスキーマレスなのでデータ構造を事前に定義する必要はありません。データを登録するには次のようなCREATE文をNeo4jシェルに流します。Neo4jのプロンプトを表しています。genre:"Technology"})はノードを表しており、graphdbはそのノードを後で参照するための変数名、Itemはラベル、{}内はそのノードの持つプロパティとなります。"2013-06-17"}]->(graphdb)はノードcからノードgraphdbに向かうリレーションシップで、PURCHASEがラベル(もしくはリレーションシップタイプ)、{}内がリレーションシップの持つプロパティです。従ってこれは「cさんがgraphdbというアイテムを2013年6月17日に購入した」という関係性を表現しています。次にnameプロパティの値によってノードを指定できるようにするため、ラベルに対してインデックスを作成します。:Item(name);それではいくつかデータを取得するCypherクエリを流してみましょう。Aさんの購入履歴を日付の降順で表示してみます。|+---------------------------------------------------+MATCH句においてマッチさせたいパターンをアスキーアート的に表現します。ここでは"A"という名前のPersonノードを始点とし、PURCHASEという関係性によって関連付けられたItemノードを探索しています。BY句でソート順序を、RETURN句で何を返すかを指定します。始点の特定は、よりSQLに近い次のような方法も可能です(もちろん同じ結果が得られます)。|+-----------------------------------+データ作成時にはリレーションシップはいずれかの向きを持つ必要がありますが、取得時には矢印をつけずにどちらにもマッチさせることが可能です(※パフォーマンスについては後述)。Aさんの友達(この例ではBさん)自身に関する情報には興味がないため、()にノードを束縛するための変数名をつけていません。DISTINCTはSQL同様、重複を排除します。この結果、AさんのFRIENDであるBさんの購入商品一覧を返すことができます。[ペーパーバック]も買っていますが、ジャンルが異なるため抽出対象とはなっていません。MySQLにおけるEXPLAINに相当するものとしてPROFILEがあります。17双方向/無向リレーションシップ上記の例に出てきたPURCHASEリレーションシップは、人が商品を購入することはあっても逆に商品が人を購入するということはないので、自然に向きがつきます。人同士においてもKNOWS(知っている)という関係は、片方が有名人でもう片方が一般人だったりするケースがあるので、やはり向きを持ちます。友達関係なんかは(俺はあいつのことを友達だと思っていたのに、あいつはそうは思っていなかった...という悲しいケースを除いて)特定の向きは持ちません。今回のAさんとBさんの例のように2ノード間に双方向のリレーションシップを張り、どちらの方向にも辿れるようにするどちらか一方のみリレーションシップを張り(向きは任意)、辿る際に向きを気にしないどちらかというと1.の方が対称性があって美しいような気もしますが、実際に計測してみると、こちらに書かれている通り2.の方が高速なようです。パフォーマンステストクエリのパフォーマンスを調べるため、テストデータとして100万ノードを登録し、各ノードからランダムに2ノードへのリレーションシップを張ります。これをCREATE文で全部登録するのはつらいので、CSVファイルから読み込む方法を紹介します。INFILE構文みたいなものですね。ノードですが、今回はID以外に特に属性はいらないのでid12...1000000を/tmp/nodes.datとして保存します。リレーションシップの方は開始ノードと終端ノード(ランダム)を指定してfrom,to1,2260641,5005702,3264572,354377...1000000,9192151000000,992803を/tmp/relationships.datとして保存します。次のコマンドを流せば登録完了です。(f)-[:KNOWS]->(t);このデータを用いて例えば「id=1のノードの知人の知人の知人」の数を求めるには以下のようにします。パフォーマンスチェックを行います(両方を見なければならないので、一方向にのみ辿る場合よりはだいぶ遅くなります)。辿る回数(ステップ数)をnとして(先ほどの知人の知人の知人ならn=3)、13までのnに対して計算にかかった時間と取得件数を表にまとめると以下のようになりました。時間は3回計測を行い、その平均としています。997,390ステップ数を横軸に、かかった時間を対数目盛で縦軸にとってグラフ化すると次のようになります(ただし、n≦5だと叩くタイミングによって数ミリ秒の差が出てしまい、計測値に対する誤差の割合が大きすぎるので省いてあります)。performanceこのグラフから、計測点がきれいに直線上に乗っていることがわかります。対象となるグラフの平均次数をdとすると(現在の例ではd=4)、ステップ数を1つ増やすたびに計算時間が約d倍になるので、現実的に辿ることができるステップ数には限界があります。各リレーションシップに所要時間や金額といった重みを持たせ、与えられた始点と終点を結ぶ経路の中で重みの合計が最小になるような経路を見つけるという問題です。Neo4jでは、次のようなクエリによって最短経路を探します。|+--------------------------------------------------------------------------------------------------------------------------------------+これはid=1のノードとid=94047のノードを結ぶ経路のうち最短のものを、15ステップ以内までという制限つきで調べるというものです。結果は1→500570→455342→94047という最短経路が見つかったことを示しています。これは3ステップ必要なので、上限ステップ数を2にして検索すると見つからなくなります。|+---++---+我々は今のところ業務で最短経路問題を扱う計画がないので、詳細な検証は省かせていただきます。参考書Neo4jの書籍としては、2014年9月現在では翻訳書も含めて日本語のものは出版されていないと思われます。Databasesがあります。Technologyの中の人であることもあり、グラフDBの一般論というよりはNeo4jの本だと思った方がよいでしょう。こちらから名前やメールアドレスといった個人情報と引き換えにPDF版を無料でダウンロードすることもできます。EngineMariaDBは言わずと知れたMySQLの妹分であり、リレーショナルデータベース(RDB)の代表格ですが、ストレージエンジンレベルでグラフ操作を可能にしたものがOQGRAPHです。Query社のサイトとMariaDB公式ページの説明以外になかなか見つかりません。最初に白状しておくと、この章はちょっとした紹介レベルで終了しますwMariaDB自体のインストールについては割愛させていただきます。yumやapt-getなどで適当に入れておいてください。10.0.7以上が必要です。今回実際に用いたサーバーバージョンは10.0.12になります。cache;適当なデータベースを作成した後、テーブルの作成を行います。一つは実際のデータを格納するための通常の(=InnoDB)テーブル、もう一つはOQGRAPHのインターフェイスとなるENGINE=OQGRAPHなテーブルです。(destid));とします。OQGRAPHではNeo4jのような「向きを気にせず辿る」といった芸当はできないので、無向リレーションシップは双方向にリンクを作ることで実現します。onlyなOQGRAPHテーブルを作成します。tableに合わせたテーブル名、カラム名を指定しますが、これ以外については基本的にこの通り打ち込んでください。ほんのちょっとでも違ってたらエラーを出すよ!とのことです。それでは早速クエリを投げてみましょう。Neo4jのようなNoSQLとは異なり、あくまでも投げるクエリはSQLです。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スタイルのクエリを。sec)うん、要するにorigid=0から必要最小限のリレーションを辿っていってるのではなくて、あらゆる可能な経路を調べあげた上で、たまたまweightが指定のものになってるのを返してるだけですね。だめじゃん!InnoDB...気を取り直してMariaDBのInnoDBです。実装としてはXtraDBらしいのですが、以下のようにMariaDBにはInnoDBと言ってあげないと通じないようなのでInnoDBで通します。table同様、始点と終点を持つ次のようなテーブルを用いることにします。ENGINE=InnoDB;Neo4jのときと同様、テストデータとして100万ID用意し、各ノードからランダムに選んだ2ノードへのリレーションシップを、今回は双方向に張ります。(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によってグラフ探索を実現します。1;ID=100から出発して、繋がっているdestidを次のテーブルのorigidに設定して、そのdestidを次のテーブルのorigidに...の繰り返しです。explainで見てみると、indexでガチガチに固められていることがわかります。|+------+-------------+-------+------+-----------------+----------+---------+------------------------+------+----------------------------------------------+それではパフォーマンステストに移りましょう。ステップ数nに対し次の結果が得られました。188,502比較のためNeo4jでかかった時間も再掲してあります。これをグラフ化すると次のようになります。performanceこれを見ると、InnoDBではステップ数が増えるにつれて指数関数よりなお悪く時間が延びていっていることがわかります。当然のことながらRDBはグラフ問題をサポートするよう設計されているわけではないので、最短経路問題や複雑なグラフ探索をDBレベルで取り扱うことはできません。いえ、10ステップまでならNeo4jより速いという結果も得られたことから、ステップ数の決まったガチガチのfriend-of-a-friendクエリを流すことに限定すれば、InnoDBも選択肢として充分アリなのではないかと思います。このグラフはNeoclipseを使って可視化したものです。クエリ"などでググるとCypherの説明とかはいっぱい出てくるのですが、果たしてそれをどこに打ち込んだらいいのか、筆者は結構悩みました...。CypherはNeo4j専用言語のため、他のグラフデータベースでは使うことができません。Neo4jは他にもGremlinやSPARQLといったクエリ言語をサポートしているようですが、ここでは触れません。indexはSTART句では使えないなど、注意が必要です。Aerospike×DynamoDBこんにちは、k_oomoriです。nex8でダイナミックリタゲの配信システムを開発し...2014-07-29MongoDBとHiveでごにょごにょ事始めこんにちは、s_mamedaifukuです。...2014-03-28MuninでELBのメトリクスをモニタリングするこんにちは、t_oookaです。こんにちは、k_oomoriです。Are青山のアドテク会社。アドネットワークやDSPを開発・運用。サーバを止めてみたよ。インターン:実業務体験編インターンでCTR予測をしましたSearchArchiveスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。