Статьи

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)

Были использованы следующие параметры виртуальной машины Java:

-Xmx1000M -Xms500M

Ниже приведены общие времена выполнения для MySQL (красный) и Neo4j (синий) для обходов длины 1, 2, 3 и 4.

Необработанные данные представлены ниже вместе с общим числом вершин, возвращаемых каждым обходом, что, конечно, одинаково для MySQL и Neo4j, учитывая, что обрабатывается один и тот же набор графовых данных. Также следует понимать, что обходы могут выполняться в цикле, и, следовательно, многие из тех же вершин возвращаются несколько раз. Наконец, обратите внимание, что только Neo4j имеет время выполнения для обхода длины 5. MySQL не завершил работу после ожидания 2 часов для завершения. Для сравнения, Neo4j потребовалось 14,37 минут для завершения 5-шагового обхода.

[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 и Neo4j представлены на графике ниже. Каждая точка обозначает, сколько времени потребовалось, чтобы вернуть n вершин для переменной длины обхода.

Наконец, данные ниже предоставляют количество вершин, возвращаемых за миллисекунду (в среднем) для каждого из обходов. Снова, MySQL не закончил в своем 2-часовом пределе для обхода длины 5.

[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

Вывод

В заключение, учитывая обход искусственного графа с естественной статистикой, база данных графов Neo4j является более оптимальной, чем реляционная база данных MySQL. Однако не было предпринято никаких попыток оптимизировать виртуальную машину Java, запросы SQL и т. Д. Эти эксперименты проводились с Neo4j и MySQL «из коробки» и с «естественным синтаксисом» для обоих типов запросов.

Источник: http://markorodriguez.com/2011/02/18/mysql-vs-neo4j-on-a-large-scale-graph-traversal/