基于AWS Neptune的Gremlin回溯聚合端点查询优化咨询

场景与需求 #

使用AWS Neptune搭配Gremlin Python，现有层级树状的Website节点，每个节点关联若干Endpoint节点。需统计每个Website节点自身及其所有子树节点关联的唯一Endpoint数量。

现有暴力解法 #

目前已实现暴力遍历方案，但效率较低，代码如下：

g.V()
  .hasLabel("Website").as("k")
  .project("website", "count")
    .by(select("k").by(T.id))
    .by(
      repeat(out().as("k")).until(outE().count().is(0))
      .select(all, "k")
      .unfold()
      .out("Related")
      .dedup()
      .count())

该方法通过重复遍历子树再去重统计，存在大量冗余计算。

优化思路与困境 #

希望采用**记忆化（memoization）**方式优化：从叶子节点开始收集Endpoint集合，回溯至父节点时复用子节点的集合，避免重复计算。尝试过sack()算子，但在Gremlin-Java中无法结合集合或自定义合并算子实现，寻求可行方案。

示例图构建代码 #

g.addV("Website").property("name", "www.ex1.com").property("type", "root")
.addV("Website").property("name", "www.ex1.com/sub1")
.addV("Website").property("name", "www.ex1.com/sub2")
.addV("Website").property("name", "www.ex1.com/sub1/about")
.addV("Endpoint").property("name", "Node 1")
.addV("Endpoint").property("name", "Node 2")
.addV("Endpoint").property("name", "Node 3")
.addV("Endpoint").property("name", "Node 4")
.addE("SUBPATH").from(V().has("name", "www.ex1.com")).to(V().has("name", "www.ex1.com/sub1"))
.addE("SUBPATH").from(V().has("name", "www.ex1.com")).to(V().has("name", "www.ex1.com/sub2"))
.addE("SUBPATH").from(V().has("name", "www.ex1.com/sub1")).to(V().has("name", "www.ex1.com/sub1/about"))
.addE("RELATED").from(V().has("name", "www.ex1.com")).to(V().has("name", "Node 3"))
.addE("RELATED").from(V().has("name", "www.ex1.com/sub1")).to(V().has("name", "Node 1"))
.addE("RELATED").from(V().has("name", "www.ex1.com/sub1")).to(V().has("name", "Node 4"))
.addE("RELATED").from(V().has("name", "www.ex1.com/sub2")).to(V().has("name", "Node 2"))
.addE("RELATED").from(V().has("name", "www.ex1.com/sub1/about")).to(V().has("name", "Node 2"))
.addE("RELATED").from(V().has("name", "www.ex1.com/sub1/about")).to(V().has("name", "Node 4"))

内容的提问来源于stack exchange，提问作者Gabriel Tudor