图形数据库或关系数据库公共表扩展:比较非循环图形查询性能

Question

对于高度连接的非循环图数据，图数据库是否比关系数据库更具性能？

我需要显著加快我的查询结果，并希望图形数据库将是答案。当我使用Common Table Extensions将样本数据的递归搜索从16小时增加到30分钟时，我发现关系数据库查询有了显著的改进。尽管如此，对于一个web应用程序来说，30分钟的时间太长了，而且试图绕过这种响应很快就会变得相当荒谬，依赖于缓存。

我的Gremlin查询看起来像：

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
)

它应该在我的测试实例中返回一个具有500000多条边的结果集。

如果我过滤以减小输出的大小，那么我仍然必须首先遍历所有这些边，才能得到我想要分析的有趣的东西。

我可以预见，一些对真实数据的查询越来越接近于必须遍历3000000多条边。。。

如果图形数据库不能解决问题，那么CTE是否和它一样好？

Answer 1

我尝试了使用BerkeleyDB Java Edition的JanusGraph-0.5.2。我的示例数据集有580832个顶点，2325896条边，这些边是从大约1gb的graphML文件中加载的。网络平均度为4，直径为30，平均路径长度为1124，模块性为0.7，平均聚类系数为0.013，特征向量中心性(100次迭代(为4.5。

毫无疑问，我的查询相当业余，但在等待了10个小时才收到Java堆栈内存不足错误后，很明显，我的CTE性能至少快了20倍！！！

我的conf/janusgraph-berkeyje.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(或65K(，这应该是相当快的。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