1

我有一个包含大量相对较小的不相交图的图形数据集。我需要从一组匹配特定搜索条件的顶点中找到所有可到达的顶点。我使用以下查询：

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    FOR node IN 0..100000 OUTBOUND startnode edges
        COLLECT k = node._key
        RETURN k

查询很慢，即使它返回正确的结果。这是因为 Arango 实际上最终会多次遍历相同的子图。例如，假设有以下子图：

a -> b -> c -> d -> e

当过滤条件选择顶点 a 和 c 时，Arango 最终会从 a 和 c 开始进行两次独立的遍历。它在这两个遍历过程中访问顶点 d 和 e，这会浪费时间。添加 uniqueVertices 选项没有帮助，因为在不同的遍历中不会检查顶点的唯一性。

为了确认对性能的影响，我创建了一个额外的根文档，并将其中的链接添加到我的过滤器找到的所有文档：

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    INSERT { _from: 'fakeVertices/0', _to: startnode._id } IN fakeEdges

现在，以下查询的运行速度比我的原始查询快 4 倍，同时产生相同的结果：

FOR node IN 1..1000000 OUTBOUND 'fakeVertices/0' edges, fakeEdges
    OPTIONS { uniqueVertices: 'global', bfs: true }
    COLLECT k = node._key
    RETURN k

不幸的是，我无法为所有查询创建假顶点/边，因为创建它需要更多时间。

我的问题是：Arango 是否提供了一种方法来确保在给定查询中的所有遍历中访问的顶点的唯一性？如果没有，有没有更好的方法来解决上述问题？

4

1 回答 1

2

据我了解，这是该uniqueVertices选项的用途，但对于FOR ...语句的每次迭代，它认为顶点对于从该起始节点的遍历是唯一的。它不知道FOR ...语句中其他节点上发生的其他遍历。看来您每次都会遍历很多顶点，这发生在每个新的起始节点上。

只是把它扔到墙上看看它是否粘住了，但是将这两个查询组合起来，添加OPTIONS到原来的呢？

FOR startnode IN nodes
    FILTER startnode._key IN [...set of values...]
    FOR node IN 0..100000 OUTBOUND startnode edges
        OPTIONS { uniqueVertices: 'global', bfs: true }
        COLLECT k = node._key
        RETURN k

另外，我强烈推荐使用命名图而不是指定边集合。它不仅更加灵活，还允许您使用最短路径计算，这可能会有所帮助。

于 2020-06-11T23:22:38.977 回答