MySQL против Neo4j на крупномасштабном обходе графа

В этом посте представлен анализ MySQL (реляционная база данных) и Neo4j ( графовая база данных) в параллельном сравнении простого обхода графа.

Использованный набор данных представлял собой искусственно созданный граф с естественной статистикой. Граф имеет 1 миллион вершин и 4 миллиона ребер. Распределение степени этого графика на графике log-log приведено ниже. Визуализация подмножества 1000 вершин графа приведена выше.

Загрузка графика

Набор данных графика был загружен как в MySQL, так и в Neo4j. В MySQL использовалась одна таблица со следующей схемой.

CREATE TABLE graph (
  outV INT NOT NULL,
  inV INT NOT NULL
);
CREATE INDEX outV_index USING BTREE ON graph (outV);
CREATE INDEX inV_index USING BTREE ON graph (inV);

После загрузки данных таблица выглядит следующим образом. Первая строка гласит: «вершина 0 связана с вершиной 1».

mysql> SELECT * FROM graph LIMIT 10;
+------+-----+
| outV | inV |
+------+-----+
|    0 |   1 |
|    0 |   2 |
|    0 |   6 |
|    0 |   7 |
|    0 |   8 |
|    0 |   9 |
|    0 |  10 |
|    0 |  12 |
|    0 |  19 |
|    0 |  25 |
+------+-----+
10 rows in set (0.04 sec)

Набор данных из 1 миллиона вершинных графов также был загружен в Neo4j. В Gremlin ребра графа выглядят так, как показано ниже. Первая строка гласит: «вершина 0 связана с вершиной 992915».

gremlin> g.E[1..10]
==>e[183][0-related->992915]
==>e[182][0-related->952836]
==>e[181][0-related->910150]
==>e[180][0-related->897901]
==>e[179][0-related->871349]
==>e[178][0-related->857804]
==>e[177][0-related->798969]
==>e[176][0-related->773168]
==>e[175][0-related->725516]
==>e[174][0-related->700292]

Разогрев тайников

Перед обходом структуры данных графа в MySQL и Neo4j каждая база данных выполняла процедуру « прогрева ». В MySQL был оценен «SELECT * FROM graph», и все результаты были повторены. В Neo4j каждая вершина графа проходила итерации и были получены исходящие ребра каждой вершины. Наконец, как для MySQL, так и для Neo4j, обсуждаемый далее эксперимент проводился дважды подряд, и результаты второго запуска оценивались.

Обход графа

Обход, который был оценен в каждой базе данных, начинался с некоторой корневой вершины и исходил из n шагов. Не было никакой сортировки, никакого различения и т. Д. Единственными двумя переменными для экспериментов являются длина обхода и корневая вершина, с которой начинается обход. В MySQL следующие 5 запросов обозначают обходы длины от 1 до 5. Обратите внимание, что «?» переменный параметр запроса, обозначающий корневую вершину.

SELECT a.inV FROM graph as a WHERE a.outV=?

SELECT b.inV FROM graph as a, graph as b WHERE a.inV=b.outV AND a.outV=?

SELECT c.inV FROM graph as a, graph as b, graph as c WHERE a.inV=b.outV AND b.inV=c.outV AND a.outV=?

SELECT d.inV FROM graph as a, graph as b, graph as c, graph as d WHERE a.inV=b.outV AND b.inV=c.outV AND c.inV=d.outV AND a.outV=?

SELECT e.inV FROM graph as a, graph as b, graph as c, graph as d, graph as e WHERE a.inV=b.outV AND b.inV=c.outV AND c.inV=d.outV AND d.inV=e.outV AND a.outV=?

Для Neo4j использовался каркас Blueprints Pipes . Труба длиной n была построена с использованием следующего статического метода.

public static Pipeline createPipeline(final Integer steps) {
  final ArrayList pipes = new ArrayList();
  for (int i = 0; i < steps; i++) {
    Pipe pipe1 = new VertexEdgePipe(VertexEdgePipe.Step.OUT_EDGES);
    Pipe pipe2 = new EdgeVertexPipe(EdgeVertexPipe.Step.IN_VERTEX);
    pipes.add(pipe1);
    pipes.add(pipe2);
  }
  return new Pipeline(pipes);
}

Для MySQL и Neo4j результаты запроса (SQL и Pipes) были повторены. Таким образом, все результаты были получены для каждого запроса. В MySQL это было сделано следующим образом.

while (resultSet.next()) {
  resultSet.getInt(finalColumn);
}

В Neo4j это делается следующим образом.

while (pipeline.hasNext()) {
  pipeline.next();
}

Результаты экспериментов

Набор данных искусственного графа был построен с использованием модели преференциального присоединения « богатее становиться богаче » . Таким образом, созданные ранее вершины являются наиболее плотными (т.е. наибольшим числом смежных вершин). Это свойство использовалось для ограничения количества времени, которое потребуется для оценки тестов для каждого обхода. Только первые 250 вершин были использованы в качестве корней обходов. Прежде чем представлять результаты синхронизации, обратите внимание, что все эти эксперименты проводились на MacBook Pro с процессором Intel Core 2 Duo 2,66 ГГц и 4 ГБ оперативной памяти на DDR3 1067 МГц. Были использованы следующие пакеты: Java 1.6, MySQL JDBC 5.0.8 и Blueprints Pipes 0.1.2.

java version "1.6.0_17"
Java(TM) SE Runtime Environment (build 1.6.0_17-b04-248-10M3025)
Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01-101, mixed mode)

-Xmx1000M -Xms500M

[mysql steps-1] time(ms):124 -- vertices_returned:11360
[mysql steps-2] time(ms):922 -- vertices_returned:162640
[mysql steps-3] time(ms):8851 -- vertices_returned:2206437
[mysql steps-4] time(ms):112930 -- vertices_returned:28125623
[mysql steps-5] N/A

[neo4j steps-1] time(ms):27 -- vertices_returned:11360
[neo4j steps-2] time(ms):474 -- vertices_returned:162640
[neo4j steps-3] time(ms):3366 -- vertices_returned:2206437
[neo4j steps-4] time(ms):49312 -- vertices_returned:28125623
[neo4j steps-5] time(ms):862399 -- vertices_returned:358765631

[mysql steps-1] vertices/ms:91.6128847554668
[mysql steps-2] vertices/ms:176.399127537985
[mysql steps-3] vertices/ms:249.286746556076
[mysql steps-4] vertices/ms:249.053599519823
[mysql steps-5] N/A

[neo4j steps-1] vertices/ms:420.740351166341
[neo4j steps-2] vertices/ms:343.122344772028
[neo4j steps-3] vertices/ms:655.507125256186
[neo4j steps-4] vertices/ms:570.360621871775
[neo4j steps-5] vertices/ms:416.00886711325