База данных графиков или расширения общих таблиц реляционной базы данных: сравнение производительности запросов ациклических графов

Question

Являются ли графические базы данных более производительными, чем реляционные, для высокосвязных данных ациклических графов?

Мне нужно значительно ускорить результаты моего запроса и надеюсь, что графические базы данных будут ответом. Я заметил значительное улучшение запросов к реляционной базе данных, когда я использовал Common Table Extensions, благодаря чему рекурсивный поиск моих выборочных данных увеличился с 16 часов до 30 минут. Тем не менее, 30 минут - это слишком много для веб-приложения, и попытки обойти такой ответ довольно быстро становятся довольно нелепыми, полагаясь на кеширование.

Мой запрос Гремлина выглядит примерно так:

g.withSack(100D).
V(with vertex id).
repeat(out('edge_label').
sack(div).by(constant(2D))).
emit().
group().by('node_property').by(sack().sum()).
unfold().
order().by(values,decr).
fold()

эквивалент Cypher (спасибо cyberSam) что-то вроде:

MATCH p=(f:Foo)-[:edge_label*]->(g)
WHERE f.id = 123
RETURN g, SUM(100*0.5^(LENGTH(p)-1)) AS weight
ORDER BY weight DESC

и мой SQL примерно такой:

WITH PctCTE(id, pt, tipe, ct)
AS
    (SELECT id, CONVERT(DECIMAL(28,25),100.0) AS pt, kynd, 1 
        FROM db.reckrd parent
        WHERE parent.id = @id
    UNION ALL
        SELECT child.id, CONVERT(DECIMAL(28,25),parent.pt/2.0), child.kynd, parent.ct+1
        FROM db.reckrd AS child
        INNER JOIN PctCTE AS parent
        ON (parent.tipe = 'M' AND
        (child .emm = parent.id))
        OR
        (NOT parent.tipe = 'M' AND
        (child .not_emm = parent.id))
    ),
    mergeCTE(dups, h, p)
    AS
        (SELECT ROW_NUMBER () OVER (PARTITION BY id ORDER BY ct) 'dups', id, SUM(pt) OVER (PARTITION BY id)
        FROM PctCTE
        )

который должен вернуть набор результатов с более чем 500 000 ребер в моем тестовом экземпляре.

Если бы я отфильтровал, чтобы уменьшить размер вывода, мне все равно пришлось бы сначала пройти через все эти ребра, чтобы добраться до интересного материала, который я хочу проанализировать.

Я могу предвидеть, что некоторые запросы к реальным данным приблизятся к необходимости пересечь 3 000 000+ ребер...

Если графические базы данных - это не ответ, так ли хорош CTE?

Answer 1

Я пробовал JanusGraph-0.5.2 с BerkeleyDB Java Edition. Мой образец данных содержит 580832 вершины, 2325896 ребер, загруженных из файла graphML размером примерно 1 ГБ. Средняя степень сети составляет 4, диаметр 30, средняя длина пути 1124, модульность 0,7, средний коэффициент кластеризации 0,013 и центральность собственного вектора (100 итераций) 4,5.

Без сомнения, я делаю свой запрос довольно любопытно, но после ожидания 10 часов только для получения ошибки нехватки памяти стека Java стало ясно, что моя производительность CTE как минимум в 20 раз быстрее!!!

В моем файле conf/janusgraph-berkeleyje.properties были следующие настройки:

gremlin.graph = org.janusgraph.core.JanusGraphFactory
storage.backent = berkeleyje
storage.directory = ../db/berkeley
cache.db-cache = true
cache.db-cache-size = 0.5
cache.db-cache-time = 0
cache.tx-cache-size = 20000
cache.db-cache-clean-wait = 0
storage.transaction = false
storage.berkeleyje.cache-percentage = 65

На данном этапе моего исследования может показаться, что CTE по крайней мере на порядок более производительны для сильно рекурсивных запросов, чем графические базы данных. Я бы хотел ошибаться...

Answer 2

[ОБНОВЛЕНО]

При использовании neo4j вот примерно эквивалентный запрос Cypher, который использует шаблон отношения переменной длины:

MATCH p=(f:Foo)-[:edge_label*]->(g)
WHERE f.id = 123
RETURN g, SUM(100*0.5^(LENGTH(p)-1)) AS weight
ORDER BY weight DESC

Отношения переменной длины имеют экспоненциальную сложность. Если средняя степеньD а максимальная глубина N, то следует ожидать, что сложность составит около O(D^N). В вашем варианте использования это порядка 4^30 операций.

Однако, поскольку в вашем варианте использования вклад узла в его общий вес экспоненциально уменьшается на его глубину на заданном пути, вы можете получить близкое приближение к фактическому результату, просто игнорируя узлы, которые превышают пороговую глубину.

Например, узел на глубине 8 добавит всего 0,0078 к его общему весу. И сложность на этой глубине будет всего 4^8 (или 65К), что должно быть достаточно быстро. Запрос Cypher для максимальной глубины 8 будет немного отличаться:

MATCH p=(f:Foo)-[:edge_label*..8]->(g)
WHERE f.id = 123
RETURN g, SUM(100*0.5^(LENGTH(p)-1)) AS weight
ORDER BY weight DESC