引用:https://info.tigergraph.com/gsql
はじめに
TigerGraphとNeo4jでどちらが速いのか簡単に検証してみました。
TigerGraphのレポートによると、かなり速そうです。
TigerGraphの導入や基礎的な話は、以下に記載しています。
【入門】TigerGraphを触ってみた ~導入編~
検証項目
以下の項目で速度を比較しようと思います。
- データインポート
- 1次の関係抽出
- 2次の関係抽出
- 2点間の最短経路探索
検証環境
- バージョン
- TigerGraph v2.1.3
- neo4j 3.4.6
- 検証サーバ
- EC2インスタンス:t3.2xlarge
- vCPU:8
- Memory:32GB
- OS:Ubuntu, 16.04 LTS, amd64 xenial image build on 2018-06-27
検証データ
- Vertex:1億
- Edge:10億
- VertexとEdgeのプロパティは、必要なもの以外、特に持たせていません。
- 無向グラフを、ランダムに生成しました。
- Vertexが約2GB、Edgeが約20GBです。
それぞれ投入したデータの中身は、こんな感じです。
TigerGraph
pid,person_id
1,1
2,2
3,3
4,4
5,5
...
person_1,person_2
94127280,3966913
85497021,63762317
51137447,36392931
85336587,88331345
78305284,52482292
...
Neo4j
person_id:ID,:LABEL
1,PERSON
2,PERSON
3,PERSON
4,PERSON
5,PERSON
...
person_1:START_ID,person_2:END_ID,:TYPE
94127280,3966913,RELATION
85497021,63762317,RELATION
51137447,36392931,RELATION
85336587,88331345,RELATION
78305284,52482292,RELATION
...
グラフの作成とデータロード
person_idをキーにperson_1がFROM、person_2がTOの関係でグラフを構築しました。
TigerGraph
CREATE VERTEX person (PRIMARY_ID pid INT, person_id STRING)
CREATE UNDIRECTED EDGE relation (FROM person, TO person)
CREATE GRAPH relation_graph (person, relation)
---
USE GRAPH relation_graph
---
BEGIN
CREATE LOADING JOB load_relation_graph FOR GRAPH relation_graph {
DEFINE FILENAME file_id = "/home/tigergraph/vertex_tiger.csv";
DEFINE FILENAME file_relation = "/home/tigergraph/edge_tiger.csv";
LOAD file_id TO VERTEX person VALUES ($"pid", $"person_id") USING header="true", separator=",";
LOAD file_relation TO EDGE relation VALUES ($0,$1) USING header="true", separator=",";
}
END
---
RUN LOADING JOB load_relation_graph
Neo4j
neo4j-admin import --database relation_graph.db --nodes vertex_neo4j.csv --relationships edge_neo4j.csv
検証
検証クエリ
1次の関係抽出(One-Neighborhood)
select * from person-(relation)->person where from_id == "1"
match (n {person_id:"1"})-[r*1]->(m) return n,r,m;
2次の関係抽出(Twe-Neighborhood)
CREATE QUERY secondNeighbors (VERTEX<person> p) FOR GRAPH relation_graph {
Start = {p};
FirstNeighbors = select tgt from Start -(relation)-> person:tgt;
SecondNeighbors = select tgt from FirstNeighbors -(relation)-> person:tgt;
PRINT SecondNeighbors;
}
INSTALL QUERY secondNeighbors
RUN QUERY secondNeighbors("1")
match (n {person_id:"1"})-[r*2]->(m) return n,r,m;
2点間の最短経路探索(Shortest Paths)
CREATE QUERY shortest_path (VERTEX<person> S, VERTEX<person> T, INT maxDepth) FOR GRAPH relation_graph {
OrAccum @@found = false;
OrAccum @notSeen = true;
ListAccum<STRING> @pathResult;
Start (ANY) = {S};
Start = SELECT v
FROM Start:v
//assume each vertex has an id attribute
ACCUM v.@notSeen = false, v.@pathResult = v.person_id;
WHILE NOT @@found LIMIT maxDepth DO
Start = SELECT v
FROM Start - (:e) -> :v
WHERE v.@notSeen
ACCUM v.@notSeen = false,
//add partial result paths to target v. v2.0 ListAccum requires FOREACH.
FOREACH path IN Start.@pathResult DO
v.@pathResult += (path + "-" + v.person_id)
END,
CASE WHEN v == T
THEN @@found += true
END;
END;
IF @@found THEN
Result = {T};
PRINT Result [Result.@pathResult]; #JSON output API version v2
ELSE
PRINT "Can't find shortest path within max steps";
END;
}
INSTALL QUERY shortest_path
RUN QUERY secondNeighbors("1","100","10")
match p=allShortestPaths((n {person_id:"1"})-[*]-(m {person_id:"100"})) return p;
検証結果
TigerGraph | Neo4j | |
---|---|---|
Data Import | 75min | 32min |
One-Neighborhood | 35ms | 45s |
Two-Neighborhood | 2ms (*1) | 45s |
Shortest Paths | NaN (*2) | 97s |
(*1):TigerGraphの2次関係抽出が1次関係抽出より高速な理由は、手元で作成したGSQLをインストールして実行したためと考えられます。1次関係抽出は、コマンドベースでGSQLを実行しています。
(*2):System Memory in Critical stateとなり、結果が返って来ませんでした。TigerGraphの最短経路ロジックは公式のサンプルコードを流用したため、メモリ使用が非効率な可能性が高いです。また、Neo4jはallShortestPathsメソッドを利用したため、正確な比較になっていません。
検証結果を受けて
- (*1)(*2)のように色々注釈がついてしまう検証結果となりましたが、1hop、2hopの検索はTigerGraphの方がかなり速そうです。
- (*1)については、おそらくクエリのインストール時に裏でTigerGraphが色々最適化しているのでしょう。なので、One-Neighborhoodで発行したクエリもインストールして実行すれば、より高速になることが期待されます。
- Neo4jに詳しくないので、なんとも言えないのですが、TigerGraphと同様のクエリ実行ができるものなのか疑問に思いました。要調査です。
- 最短経路はNeo4jの関数の方が優秀と言えそうです。中のロジックがどうなっているかは、不明ですが。
- TigerGraphのクエリを作り変えれば、結果が得られるかもしれませんが、結局ロジックを合わせないと比較対象として微妙なので辞めました。
- 逆に同じロジックでTigerGraphにインストールさせるとどうなるかは気になるポイントです。
- Neo4jはメモリをいい感じに使っているのか、時間がかかっても健気に結果を返してくれます。Shortest Pathsのように、TigerGraphはメモリが足りないと動いてくれませんでした。
- データ投入はNeo4j-importの方が速かったです。こちらもNeo4jの方がリソースを効率よく使っているからかもしれません。TigerGraphのインポートは並列化されているのか、そもそも並列化できるのかは調査が必要です。
終わりに
TigerGraphのレポートの記載と同様に1hop、2hopの速度はTigerGraphの方が速そうです。
データインポートは、Neo4jの方が速かったのでレポート通りとはなりませんでした。前提条件の違いや、インポートをもっと速くする方法があったりするのでしょうか?
ちなみに、TigerGraphの更新速度も気になったので試したのですが、Vertex 1億の1プロパティをキーに1つのVertexを更新しようとすると、更新に5秒ほどかかってしまいました。また、PKをキーに更新ができないみたいです。これらはGraphDBあるあるなのでしょうか?
色々疑問が残りますが、別の機会に調査しようと思います。
もし、こういう観点も検証すべき、ここもっと精度高く結果出すべき、こういう所もっと詳しく情報ほしい等あれば、フィードバックいただければ幸いです。