1

我已经评估 Neo4j 1.9.M03 有一段时间了，并且达到了我没想到的程度。

我有一个约 140,000 个顶点的图。我也有三类边，我们称它们为父亲、母亲和丈夫。每个类大约有 80,000 条边。没有属性，也没有索引。顶点存储大小约为 1.3 MB，边缘存储约为 8 MB。

数据源自 SQL Server，并且已知从 SQL 迁移到 Neo4j 的质量是正确的。对几十个顶点对运行SQL最短路径存储过程，已知最短路径距离和路径。

最短路径查询是 Cypher：START one=node(0), two=node(1234) MATCH p = shortestPath(one-[*..1000]-two) RETURN p;

部分测试用例一：我只使用丈夫和父亲的关系，循环的出现（例如v[0] -> v[1] -> v[2] -> v[0])很低。如果我在特定的已知长路径（例如已知为~450 跳）上执行最短路径计算，它会在 50ms 内返回（非缓存），路径约为 550 跳。预计长度会增加，因为我们排除了部分边。

部分测试用例二：同样，如果我只使用夫妻关系，循环的发生率（例如v[0] -> v[1] -> v[2] -> v[0])很低。如果我执行相同的最短路径，我会得到与以前相同的顺序的结果：大约 50 毫秒（非缓存)，路径长度也有类似的增加。

完整测试案例：我使用所有（父亲、母亲和丈夫）关系。由于常见情况，现在可以预见循环的发生率很高v[0] mother-> v[1] husband-> v[2] <-father v[0]。当我执行最短路径查询时，JVM 分配了 4 GB 的内存并且计算没有完成。这就是问题。

我的论点是循环的定期发生导致了这种行为，否则当我只添加另一类父边时，我不会期望性能有如此巨大的差异——除非最短路径算法没有考虑循环。

我直接使用 Java API 应用了 Dijkstra 算法，所有边的成本为 1，并获得了与使用的标准 ShortestPath 算法相似的结果。结果，我在 IntelliJ 调试 6 分钟后收到了这个异常。

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
    at org.neo4j.kernel.impl.util.RelIdArray$RelIdIteratorImpl.<init>(RelIdArray.java:661)
    at org.neo4j.kernel.impl.util.RelIdArray$DirectionWrapper$3.iterator(RelIdArray.java:327)
    at org.neo4j.kernel.impl.util.RelIdArray.iterator(RelIdArray.java:270)
    at org.neo4j.kernel.impl.core.NodeImpl.getAllRelationships(NodeImpl.java:172)
    at org.neo4j.kernel.impl.core.NodeImpl.getRelationships(NodeImpl.java:270)
    at org.neo4j.kernel.impl.core.NodeProxy.getRelationships(NodeProxy.java:82)
    at org.neo4j.kernel.StandardExpander$AllExpander.doExpand(StandardExpander.java:303)
    at org.neo4j.kernel.StandardExpander$RelationshipExpansion.iterator(StandardExpander.java:194)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.expandRelationshipsWithoutChecks(TraversalBranchImpl.java:114)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.expandRelationships(TraversalBranchImpl.java:104)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.initialize(TraversalBranchImpl.java:130)
    at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.next(TraversalBranchImpl.java:150)
    at org.neo4j.graphalgo.impl.util.BestFirstSelectorFactory$BestFirstSelector.next(BestFirstSelectorFactory.java:73)
    at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:65)
    at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:34)
    at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)
    at org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:45)
    at org.neo4j.graphalgo.impl.util.StopAfterWeightIterator.fetchNextOrNull(StopAfterWeightIterator.java:29)
    at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)
    at org.neo4j.helpers.collection.IteratorUtil.firstOrNull(IteratorUtil.java:51)
    at org.neo4j.helpers.collection.IteratorUtil.firstOrNull(IteratorUtil.java:201)
    at org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:98)
    at org.neo4j.graphalgo.impl.path.Dijkstra.findSinglePath(Dijkstra.java:50)
    at ShortestPathCalc.Dijkstra(Main.java:198)
    at Main.main(Main.java:53)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
    at java.lang.reflect.Method.invoke(Method.java:601)
    at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

你觉得我说的对吗？这是图形数据库或其最短路径算法的已知限制吗？对我来说，以前访问过的顶点不会存储在哈希表中似乎很愚蠢，这样最短路径算法就不会多次尝试离开以前访问过的顶点。

2013 年 1 月 25 日更新

一个 Github 回购，所以你可以跟随！

https://github.com/squirrelsama/neo4j-shortestpath-issue

2013 年 2 月 7 日更新

请参阅已接受的答案。简而言之，周期与它无关。

4

2 回答 2

1

使用 neo4j 遍历框架，您可以选择在遍历中使用的唯一性，例如 RELATIONSHIP_GLOBAL，这样它在遍历期间只遍历关系一次。这可能会解决您的问题：

// 单向
Traversal.traversal（唯一性.RELATIONSHIP_GLOBAL）
         .evaluator(Evaluators.returnWhereEndNodeIs(myEndNode)
         .traverse(myStartNode);

// 双向
Traversal.bidirectionalTraversal()
         .mirroredSides( Traversal.traversal( Uniqueness.RELATIONSHIP_GLOBAL ) )
         .traverse(myStartNode, myEndNode);

以上示例是原则性的，但可能需要修改才能与您的查询一起使用。

于 2013-01-27T21:02:27.893 回答
1

如果尝试获取节点 44715 和 17173 之间的最短路径，已知其最短路径为 112 跳，则可以观察到该问题。

如果我们将最短路径评估限制为 111 跳，则查询会很快完成，但没有路径。START one=node(44715), two=node(17173) MATCH p = shortestPath(one-[*..111]-two) RETURN p;

但是，如果我们将最短路径评估限制为 112 跳，我们会观察到查询无法完成，并且 JVM 会迅速分配高达 4 GB 的内存。START one=node(44715), two=node(17173) MATCH p = shortestPath(one-[*..112]-two) RETURN p;

Neo 已确认这是与要返回的 Path 对象的组装有关的边缘案例错误。它在他们的错误积压中。

换句话说，周期与问题无关。

于 2013-02-08T03:08:01.553 回答