AQL验证节点的路径

Question

我们需要一些AQL来验证实体的特定路径。由于需要扫描整个集合，当前的解决方案执行得非常糟糕。

例如这里我们有3个实体'类型'：a，b，c（虽然它们都在一个集合中）和它们之间的特定边集合，我们想要确定_key“123”和_key之间是否存在连接234“完全通过 - > b - > c。

FOR a IN entities FILTER e._key == "123"
FOR b IN 1..1 OUTBOUND e edges_a_to_b
FOR c IN 1..1 INBOUND e_1 edges_c_to_b
FILTER e_2._key == "234"
...

这可以非常迅速地散开！

我们有另一个解决方案，我们使用SHORTEST PATH并指定适当的DIRECTION和边集合，速度更快（> 100次）。但是担心这种方法不能满足我们的一般情况......边缘的顺序没有强制执行，我们可能不得不多次经历相同的边集合，这是我们无法用该语法做的。

还有另一种方法，可能涉及遍历中的路径吗？

谢谢！和。

Answer 1

如果我理解正确，你总是知道两个顶点之间所需的确切路径。

因此，以你的例子a -> b -> c为例，一个有效的结果将有：path.vertices == [a, b, c]所以我们可以使用这个路径对它进行过滤，这只适用于你使用单个遍历步骤而不是多个遍历步骤。所以我们尝试du是以下模式：

FOR c,e, path IN <pathlength> <direction> <start> <edge-collections>
  FILTER path.vertices[0] == a // This needs to be formulated correctly
  FILTER path.vertices[1] == b // This needs to be formulated correctly
  FILTER path.vertices[2] == c // This needs to be formulated correctly
  LIMIT 1 // We only net exactly one path, so limit 1 is enough
  [...]

因此，使用此提示可以按以下方式编写查询：

FOR a IN entities
  FILTER a._key == "123"
  FOR c, e, path IN 2 OUTBOUND a edges_a_to_b, INBOUND edges_b_to_c
    FILTER path.vertices[1] == /* whatever identifies b e.g. vertices[1].type == "b" */
    FILTER path.vertices[2]._key == "234"
    LIMIT 1 /* This will stop as soon as the first match is found, so very important! */
    /* [...] */

这将允许优化器尽早应用过滤条件，并且（几乎）将使用与最短路径实现相同的算法。诀窍是使用一个遍历而不是倍数来节省内部开销并允许更好的优化。

还要考虑到在相反方向搜索可能更好：

例如而不是a -> b -> c检查可能更快的c <- b <- a。这取决于每个节点的边缘量。我认为医生有很多手术，但是一个病人很可能只进行少量手术，所以最好从患者开始并向后检查，而不是从医生那里开始检查。

请让我知道这有帮助，否则我们可以讨论更多细节，看看我们是否可以找到一些进一步的优化。

免责声明：我是ArangoDB的Core-Dev团队的一员