如果我在图形节点中有 2way 关系并且节点相互关联，则 Neo4j 查询最短路径卡住（不工作）
Neo4j query for shortest path stuck (Do not work) if I have 2way relationship in graph nodes and nodes are interrelated
我制作了两个关系图，比如如果 A 知道 B 那么 B 就知道 A，每个节点都有唯一的 ID 和名称以及其他属性。所以我的图看起来像
如果我触发一个简单的查询
MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO* ]-(p2) RETURN 路径
它没有给出任何响应并消耗了 100% CPU 和机器的 RAM。
已更新
当我阅读 posts 和对此 post 的评论时，我简化了模型和关系。现在它结束了
每个关系都有不同的权重，为简化起见，考虑水平连接权重 1、垂直权重 1 和对角线关系权重 1.5
在我的数据库中有超过 85000 个节点和 30 万个关系
使用最短路径的查询不会以某些结果结束。它卡在处理中，CPU 变为 100%
MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO*]->(p2) RETURN path
或者：
MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}), (p1)-[path:NAVIGATE_TO*]->(p2) RETURN path
让我们考虑一下您的查询在做什么：
MATCH (p1:SearchableNode {name: "Ishaan"}),
(p2:SearchableNode {name: "Garima"}),
path = (p1)-[:NAVIGATE_TO*]-(p2)
RETURN path
如果您在控制台中 运行 此查询前面有 EXPLAIN，数据库将为您提供其如何回答的计划。当我这样做时，查询编译器警告我：
If a part of a query contains multiple disconnected patterns, this
will build a cartesian product between all those parts. This may
produce a large amount of data and slow down query processing. While
occasionally intended, it may often be possible to reformulate the
query that avoids the use of this cross product, perhaps by adding a
relationship between the different parts or by using OPTIONAL MATCH
您的查询有两个问题 - 首先，您分配的 p1 和 p2 彼此独立，可能会创建此笛卡尔积。第二个问题是因为你图表中的所有链接都双向并且你要求无向连接你正在制作DB 的工作量加倍，因为它实际上可以遍历您所要求的任何一种方式。更糟糕的是，因为所有链接都是双向的，你的图中有很多循环，所以当 cypher 探索它可以采用的路径时，它尝试的许多路径都会循环回到它开始的地方。这意味着查询引擎将花费大量时间追逐自己的尾巴。
您可以通过这样做立即改进查询：
MATCH p=shortestPath((p1:SearchableNode {name:"Ishaan"})-[:NAVIGATE_TO*]->(p2:SearchableNode {name:"Garima"}))
RETURN p;
这里有两个修改- p1 和p2 立即相互绑定，您不必单独匹配它们。其次，注意 [:NAVIGATE_TO*]-> 部分，最后一个箭头 ->；我们仅以一种方式匹配关系。由于您的图表中有如此多的反身链接，任何一种方式都可以正常工作，但无论您选择哪种方式，您都可以将数据库必须完成的工作减半。 :)
这可能仍然执行得不太好，因为遍历该图仍然会有很多循环，这将使 DB 追逐它的尾巴试图找到最佳路径。在此处的建模选择中，您通常不应双向 关系，除非您需要每个关系 的单独属性。关系可以在两个方向上遍历，因此拥有两个（每个方向一个）没有意义，除非关系捕获的信息在语义上不同。
通常您会发现查询性能可以通过重新制定查询并进行思考来做得更好，但是图形建模和整体性能之间存在主要的相互作用。由于图表设置了如此多的 bi-directional 链接，您可以做的优化就只有这么多了 path-finding.
恐怕你在这里做不了什么。您的图表非常具体，仅与最近的节点有关系。那太糟糕了，因为 neo4j 可以围绕起点玩 +- 很少的关系，而不是每个查询的整个图
这意味着，一旦您离开 2 个节点，计算复杂度将提高到：
8 relationships per node
distance 2
8 + 8^2
一般来说，距离 n 的最高复杂度是
O(8 + 8^n) //in case all affected nodes have 8 connections
你说，你得到了像nodes.this的~80 000的意思（如果我错了请纠正我），~280的最长距离（来自√80000）。让我们假设你的节点
(p1:SearchableNode {name: "Ishaan"}),
(p2:SearchableNode {name: "Garima"}),
只有 140 个希望。这将造成 8^140 = 10e126 的复杂性，我不确定世界上是否有任何计算机可以处理这个问题。
当然，并非所有节点都有 8 个连接，只有那些 "in the middle"，在我们的示例图中，它将有大约 500 000 个关系。你得到了大约 300 000，这可能少了 2 倍所以让我们假设平均距离为 70 的整体复杂性（在 140 中 - 一个非常宽松的底部估计）对于平均具有 4 个关系的节点（从 8, 80 000 *4 = 320 000) 为
O(4 + 4^70) = ~10e42
一个 1GHz CPU 应该可以通过以下方式计算：
-1000 000 per second
10e42 == 10e36 * 1 000 000 -> 10e36 seconds
假设我们有一个 100 个 10Ghz cpu 服务的集群，总共 1000 GHz。
那还是 10e33 * 1 000 000 000 -> 10e33seconds
我建议远离 AllshortestPaths，只寻找第一条可用路径。使用 gremlin 而不是 cypher 可以通过一些启发式方法实现自己的算法，因此实际上您可以将时间缩短到几秒或更短。
示例：仅使用一个方向 = 减少到 10e16 秒。
一个启发式示例：检查节点的id，node2.id-node1.id之间的差异（减法值）越大，实际距离就越大（考虑节点创建顺序-节点具有相似的 ID 靠在一起）。在这种情况下，您可以跳过查询，也可以使用 MATCH n1-[:RELATED..5]->q-[:RELATED..*]->n2 (i forgot the syntax of defining exact relation count) 之类的东西跳过一些关系，这将（应该）实际跳到（立即跳到）5 个距离更接近 n2 节点的节点= 复杂度从 4^70 降低到 4^65。因此，如果您可以准确计算与节点 id 的距离，您甚至可以匹配 ... [:RELATED..65] ...，这会将复杂性降低到 4^5，这对于 cpu.[=29= 来说只是几毫秒的问题]
我这里可能完全错了。我已经离开学校一段时间了，很高兴请一位数学家（图论）来证实这一点。
我制作了两个关系图，比如如果 A 知道 B 那么 B 就知道 A，每个节点都有唯一的 ID 和名称以及其他属性。所以我的图看起来像
如果我触发一个简单的查询 MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO* ]-(p2) RETURN 路径 它没有给出任何响应并消耗了 100% CPU 和机器的 RAM。
已更新
当我阅读 posts 和对此 post 的评论时，我简化了模型和关系。现在它结束了
每个关系都有不同的权重，为简化起见，考虑水平连接权重 1、垂直权重 1 和对角线关系权重 1.5 在我的数据库中有超过 85000 个节点和 30 万个关系
使用最短路径的查询不会以某些结果结束。它卡在处理中，CPU 变为 100%
MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO*]->(p2) RETURN path
或者：
MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}), (p1)-[path:NAVIGATE_TO*]->(p2) RETURN path
让我们考虑一下您的查询在做什么：
MATCH (p1:SearchableNode {name: "Ishaan"}),
(p2:SearchableNode {name: "Garima"}),
path = (p1)-[:NAVIGATE_TO*]-(p2)
RETURN path
如果您在控制台中 运行 此查询前面有 EXPLAIN，数据库将为您提供其如何回答的计划。当我这样做时，查询编译器警告我：
If a part of a query contains multiple disconnected patterns, this will build a cartesian product between all those parts. This may produce a large amount of data and slow down query processing. While occasionally intended, it may often be possible to reformulate the query that avoids the use of this cross product, perhaps by adding a relationship between the different parts or by using OPTIONAL MATCH
您的查询有两个问题 - 首先，您分配的 p1 和 p2 彼此独立，可能会创建此笛卡尔积。第二个问题是因为你图表中的所有链接都双向并且你要求无向连接你正在制作DB 的工作量加倍，因为它实际上可以遍历您所要求的任何一种方式。更糟糕的是，因为所有链接都是双向的，你的图中有很多循环，所以当 cypher 探索它可以采用的路径时，它尝试的许多路径都会循环回到它开始的地方。这意味着查询引擎将花费大量时间追逐自己的尾巴。
您可以通过这样做立即改进查询：
MATCH p=shortestPath((p1:SearchableNode {name:"Ishaan"})-[:NAVIGATE_TO*]->(p2:SearchableNode {name:"Garima"}))
RETURN p;
这里有两个修改- p1 和p2 立即相互绑定，您不必单独匹配它们。其次，注意 [:NAVIGATE_TO*]-> 部分，最后一个箭头 ->；我们仅以一种方式匹配关系。由于您的图表中有如此多的反身链接，任何一种方式都可以正常工作，但无论您选择哪种方式，您都可以将数据库必须完成的工作减半。 :)
这可能仍然执行得不太好，因为遍历该图仍然会有很多循环，这将使 DB 追逐它的尾巴试图找到最佳路径。在此处的建模选择中，您通常不应双向 关系，除非您需要每个关系 的单独属性。关系可以在两个方向上遍历，因此拥有两个（每个方向一个）没有意义，除非关系捕获的信息在语义上不同。
通常您会发现查询性能可以通过重新制定查询并进行思考来做得更好，但是图形建模和整体性能之间存在主要的相互作用。由于图表设置了如此多的 bi-directional 链接，您可以做的优化就只有这么多了 path-finding.
恐怕你在这里做不了什么。您的图表非常具体，仅与最近的节点有关系。那太糟糕了，因为 neo4j 可以围绕起点玩 +- 很少的关系，而不是每个查询的整个图
这意味着，一旦您离开 2 个节点，计算复杂度将提高到：
8 relationships per node
distance 2
8 + 8^2
一般来说，距离 n 的最高复杂度是
O(8 + 8^n) //in case all affected nodes have 8 connections
你说，你得到了像nodes.this的~80 000的意思（如果我错了请纠正我），~280的最长距离（来自√80000）。让我们假设你的节点
(p1:SearchableNode {name: "Ishaan"}),
(p2:SearchableNode {name: "Garima"}),
只有 140 个希望。这将造成 8^140 = 10e126 的复杂性，我不确定世界上是否有任何计算机可以处理这个问题。
当然，并非所有节点都有 8 个连接，只有那些 "in the middle"，在我们的示例图中，它将有大约 500 000 个关系。你得到了大约 300 000，这可能少了 2 倍所以让我们假设平均距离为 70 的整体复杂性（在 140 中 - 一个非常宽松的底部估计）对于平均具有 4 个关系的节点（从 8, 80 000 *4 = 320 000) 为
O(4 + 4^70) = ~10e42
一个 1GHz CPU 应该可以通过以下方式计算：
-1000 000 per second
10e42 == 10e36 * 1 000 000 -> 10e36 seconds
假设我们有一个 100 个 10Ghz cpu 服务的集群，总共 1000 GHz。
那还是 10e33 * 1 000 000 000 -> 10e33seconds
我建议远离 AllshortestPaths，只寻找第一条可用路径。使用 gremlin 而不是 cypher 可以通过一些启发式方法实现自己的算法，因此实际上您可以将时间缩短到几秒或更短。
示例：仅使用一个方向 = 减少到 10e16 秒。
一个启发式示例：检查节点的id，node2.id-node1.id之间的差异（减法值）越大，实际距离就越大（考虑节点创建顺序-节点具有相似的 ID 靠在一起）。在这种情况下，您可以跳过查询，也可以使用 MATCH n1-[:RELATED..5]->q-[:RELATED..*]->n2 (i forgot the syntax of defining exact relation count) 之类的东西跳过一些关系，这将（应该）实际跳到（立即跳到）5 个距离更接近 n2 节点的节点= 复杂度从 4^70 降低到 4^65。因此，如果您可以准确计算与节点 id 的距离，您甚至可以匹配 ... [:RELATED..65] ...，这会将复杂性降低到 4^5，这对于 cpu.[=29= 来说只是几毫秒的问题]
我这里可能完全错了。我已经离开学校一段时间了，很高兴请一位数学家（图论）来证实这一点。