0

我正在尝试使用以下 Cypher Query 计算 Neo4j 中无向图的传递闭包（“E”是图的每条边都具有的标签）：

MATCH (a) -[:E*]- (b) WHERE ID(a) < ID(b) RETURN DISTINCT a, b

我试图在一个有 10k 节点和大约 150k 边的图上执行这个查询，但即使在 8 小时后它也没有完成。我觉得这很令人惊讶，因为即使是最简单的 SQL 解决方案也快得多，而且我预计 Neo4j 对这类标准图形查询的效率会更高。那么我是否缺少一些东西，也许是对 Neo4j 服务器的一些调整或编写查询的更好方法？

编辑

以下是EXPLAIN上述查询的结果：

+--------------------------------------------+
| No data returned, and nothing was changed. |
+--------------------------------------------+
908 ms

Compiler CYPHER 3.3

Planner COST

Runtime INTERPRETED

+-----------------------+----------------+------------------+--------------------------------+
| Operator              | Estimated Rows | Variables        | Other                          |
+-----------------------+----------------+------------------+--------------------------------+
| +ProduceResults       |          14069 | a, b             |                                |
| |                     +----------------+------------------+--------------------------------+
| +Distinct             |          14069 | a, b             | a, b                           |
| |                     +----------------+------------------+--------------------------------+
| +Filter               |          14809 | anon[11], a, b   | ID(a) < ID(b)                  |
| |                     +----------------+------------------+--------------------------------+
| +VarLengthExpand(All) |          49364 | anon[11], b -- a | (a)-[:E*]-(b)                  |
| |                     +----------------+------------------+--------------------------------+
| +AllNodesScan         |          40012 | a                |                                |
+-----------------------+----------------+------------------+--------------------------------+

Total database accesses: ?
4

1 回答 1

0

您可以限制方向，但它需要对图形进行定向。

在我自己做了一些测试和分析之后，我发现即使是非常小的数据集（随机生成的 10 个节点集，每个节点有 2 个随机边），使查询仅针对减少数据库命中的单个方向10000 倍（从 2266909 到 149 个数据库命中）。

为您的查询添加一个方向（从而强制图形被定向）大大减少了搜索空间，但它需要图形被定向。

我还尝试简单地为每个定向关系添加一个反向关系，看看是否会有类似的性能。它没; 它在 5 分钟过去之前没有完成，此时我将其杀死。

不幸的是，您没有做错任何事情，但是您的查询量很大。

Neo4J 是一个图形数据库，并不意味着所有涉及图形的数学运算都会非常快；它们仍然受到性能限制，直至并包括传递闭包操作。

您编写的查询是对每一对节点的无界路径搜索。节点对是有界的，但不是以一种非常有意义的方式（ID（a）< ID（b）的界限只是意味着搜索只需要以一种方式完成；仍然有10k！（如阶乘）可能结果集中的节点集。

然后，只有在检查了每条路径之后。搜索您指定大小的图的整个传递闭包在性能方面将非常昂贵。

您发布的 SQL 没有执行相同的操作。

您在评论中提到您在关系表中以递归形式尝试此查询：

WITH RECURSIVE temp_tc AS (
  SELECT v AS a, v AS b FROM nodes
  UNION SELECT a,b FROM edges g
  UNION SELECT t.a,g.b FROM temp_tc t, edges g WHERE t.b = g.a
)
SELECT a, b FROM temp_tc;

我应该注意，这个查询与 Neo4J 在尝试查找所有路径时执行的操作不同。在 Neo4J 可以开始缩减您的结果之前，它必须生成一个包含整个图表中每条路径的结果集。

SQL 和关系查询不这样做；它从链接列表开始，但递归查询具有删除任何潜在重复链接的效果；它发现其他链接作为它搜索他人的链接；例如，如果图看起来像 (A)-(B)-(C)，则该查询将在发现 A 连接到 C 的过程中发现 B 连接到 C。

使用 Neo4J，必须单独发现每条路径。

如果这是您的一般用例，如果速度是一个问题，Neo4J 可能不是一个好的选择。

于 2018-04-17T14:25:07.083 回答