neo4j - 为长但(几乎)唯一的路径寻求 Neo4J Cypher 查询

Question

我们有一个 Neo4J 数据库，代表一个进化过程，大约有 10 万个节点和 20 万个关系。节点是世代中的个体，边代表父子关系。主要目标是能够在最后一代中获取一个或多个感兴趣的节点，并探索它们的进化历史(粗略地说，“我们是如何到达这里的？”)。

查找所有祖先的“明显”第一个查询不起作用，因为有太多可能的祖先和路径通过该空间:

match (a)-[:PARENT_OF*]->(c {is_interesting: true}) 
return distinct a;

因此，我们对数据进行了预处理，以便将某些边标记为“特殊”，这样几乎每个节点最多都有一个“特殊”父边，尽管偶尔两个父边都标记为“特殊”。我的希望是，这个查询会(有效地)沿着“特殊”边缘生成(几乎)唯一的路径:

match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

然而，这仍然非常缓慢。

这令人沮丧，因为“作为人类”，逻辑很简单:从少量“有趣”节点(通常为 1 个，从不超过几十个)开始，然后沿着几乎总是独特的“特殊”边缘追回。假设具有两个“特殊”父节点的节点数量非常少，这应该类似于 O(N)，其中 N 是回溯的代数。

然而，在 Neo4J 中，从一个独特的“有趣”节点返回 25 步，其中每一步都是唯一的，然而，需要 30 秒，一旦出现一个 fork ( parent 双方都是“特殊的”)，它会变得更糟，因为步骤的功能。 28 步(让我们到达第一个 fork )需要 2 分钟，30 步(仍然只有一个 fork )需要 6 分钟，我什至没有想过在模拟开始时尝试完整的 100 步。

去年的一些类似工作似乎表现更好，但我们使用了各种边缘标签(例如， (a)-[:SPECIAL_PARENT_OF*]->(c) 以及 (a)-[:PARENT_OF*]->(c))而不是在边缘使用数据字段。查询关系字段值不是一个好主意吗？我们在这个模型中的关系上附加了很多不同的值(一些 bool 值，一些数字)，我们希望/假设我们可以使用它们来有效地限制搜索，但也许事实并非如此。

关于如何调整我们的模型或查询的建议将不胜感激。

更新 我应该提到，这是 Neo4J 2.1.7 的全部内容。我将按照 Brian Underwood 的建议尝试 2.2，并将报告。

Answer 1

我很幸运地指定了路径长度的限制。因此，如果您知道它永远不会超过 30 跳，您可以尝试:

MATCH (c {is_interesting: true})
WITH c
MATCH (a)-[:PARENT_OF*1..30]->c 
RETURN DISTINCT a

另外， is_interesting上有索引吗？属性(property)？当然，这也可能导致缓慢。

您使用的是什么版本的 Neo4j？如果您正在使用或升级到 2.2.0，则可以使用新的查询分析工具:

http://neo4j.com/docs/2.2.0/how-do-i-profile-a-query.html

此外，如果您在 Web 控制台中使用它们，您会得到一个很好的图形树(技术术语)显示每个步骤。