Neo4j Cypher Lowest Common Ancestor 性能问题

Question

我正在尝试使用 graphrepository 在 spring-neo4j 中创建一个应用程序。要求之一是找到两个子节点之间的最低公共祖先 (lca)。

目前我使用以下查询来实现：

 @Query("MATCH path = (c1:Concept)-[r:Relation*{type: 'Is a'}]->(ca:Concept)<-[r:Relation*{type: 'Is a'}]-(c2:Concept) 
      WHERE c1.conceptID = {conceptId1} AND c2.conceptID = {conceptId2}
      RETURN ca ORDER BY length(path) LIMIT 1")

Concept findLowestCommonAncestor(@Param("conceptId1") Long conceptId1, @Param("conceptId2") Long conceptId2);

这里的问题是性能。最初我的图表由 330 000 个节点和 2 000 000 个关系组成。我感兴趣的关系是类型为："Is a" 的关系。它们只在树中向上移动（连接子节点和父节点）。最大向上距离为 3.

这是树结构：

因为我有几个像这样的树结构，所以我决定添加一个根节点将所有不同的树结构连接在一起。这样 lca 总会被发现。但是添加这个根节点极大地改变了我的表现：从 558 毫秒到 562286 毫秒

我知道添加根节点会影响性能，但应该不会这么大吧？如果是这样，有没有更好的方法来计算lca？

我认为我的密码查询只会在树中向上查找节点。所以在那种情况下，增加一个额外的根节点应该不会对性能有这么大的影响。

Answer 1

你的问题是关系标签问题，我来解释一下：

首先，您的请求与 :Relation 关系的无限深度匹配。

你说你数据库中的每棵树现在都与根节点相关，我猜它与使用 :Relation 关系的根节点相关。

因此，当您将每个标记为 :Relation 的关系与无限深度匹配时，它会在过滤 type 属性之前匹配数据库中的每个关系。这就是为什么这个根节点添加了这样一个性能问题，因为它以相同的关系将每个节点连接在一起。

如何解决？

更改您的关系标签，使用它们而不是与属性:

匹配

(ca:Concept{properties...})-[:IS_A]->(ca2:Concept)

和 link 您的顶级树节点使用另一个关系标签到根节点。

然后，当您使用无限深度请求匹配您的节点时，您将能够使用标签进行匹配，从而避免您实际遇到的问题。

另一种解决方案是在您的查询中添加一个最大深度，因为您的树最多有 3 个级别，您可以将关系深度限制为 3。但我认为第一个解决方案更好，因为只创建一个使用它们的属性的关系类型和过滤在 neo4j 中是一种不好的做法。

编辑

所以，这是您的第一份个人资料：http://i.imgur.com/xskg39J.png

这里可以看到匹配[:Relation*]过滤前有31328条命中，已经很不错了

在第二个配置文件（带根节点）上：http://i.imgur.com/14yleCo.png

你可以看到同样的匹配得到了将近200万的点击量，过滤后是50万...这太多了。

我认为解决方案是路径，你可以看看这个：

http://grokbase.com/t/gg/neo4j/1454y795dw/how-to-find-lowest-common-ancestor-of-two-nodes

仅用"better"密码查询无法解决问题。我认为您的问题可以通过更好的数据模型来解决，但是如果不处理项目本身就很难找到哪个模型。我唯一能提供的是指南：http://neo4j.com/developer/guide-data-modeling/

Answer 2

首先感谢@Supamiu 对我的问题的帮助

尽管他的回答对于某些情况可能已经足够了。在我的例子中，改变模型是不可能的。

令人惊讶的是，我仅通过更改密码查询就设法提高了性能。

我的原始查询：

MATCH path = (c1:Concept)-[r1:Relation*{type: "Is a"}]->(ca:Concept)<-[r2:Relation*{type: "Is a"}]-(c2:Concept)
WHERE c1.conceptID=35104066 AND c2.conceptID=35808913
RETURN ca
ORDER BY length(path)
LIMIT 1

个人资料：http://i.imgur.com/14yleCo.png

我改成了：

MATCH (c1:Concept {conceptID: 35104066})-[:Relation*{type: "Is a"}]->(p1:Concept)
MATCH (:Concept {conceptID: 35808913})-[:Relation*{type: "Is a"}]->(p2:Concept)
WHERE p1.conceptID = p2.conceptID
MATCH path = (c1)-[:Relation*{type: "Is a"}]->(p1)
RETURN p1
ORDER BY length(path)
LIMIT 1

个人资料：http://imgur.com/YCDDF5H

这在大约 100 毫秒内给出了我的最低公共祖先，这是一个显着的改进！

我仍然不完全理解为什么这会造成如此大的不同。但是我认为原因之一是我使用了树结构。我认为在第二个查询中，Cypher 只在树中向上搜索，导致搜索的关系较少。所以我认为这在 blob 结构中并没有什么帮助。

有人可以证实这一点吗？

Neo4j Cypher Lowest Common Ancestor 性能问题

Neo4j Cypher Lowest Common Ancestor performance issue

neo4j

cypher

lowest-common-ancestor

编辑