带过滤条件的图K步邻居查询

(Updated: )
图
filter, kneighbor, 图存储

原本在图中常见的 K 步邻居 API 一般是查询某个点触发的 K 层邻居, 是一个单点 BFS/DFS 查询, 参数条件一般比较少, 今天来看看如果想多点出发, 并携带过滤条件的 K 步邻居如何实现 (实现后我们就可以在 rest-api 里直接使用覆盖大多数查询要求的条件了)

0x00. 需求分析

1. 概述

要实现一个 kneighbors() 接口. 允许传入一个 Set<Id> 作为起始点集, 以及一个 Set<EdgeLabel> 作为扩展的边类型集合, 并允许传入两个过滤条件, 对原始 K 层的结果进行过滤, 最后返回所有输入点的 K 层邻居的并集.

2. 核心参数

分两类, 一类是当前算法特有的, 比较重要, 这里因为语义, 可以默认去重都使用 Set 来存储:

  1. Set<VertexId>: 起始的点集合, 也就是从 N 个点开始出发遍历 (必填)
  2. Set<EdgeLabel>: 遍历时扩展的边条件 (选填, 默认值根据 direction 来确定, 比如 BOTH 对应 ALL_Labels)
  3. Set<VertexPropertyFilter> : 对点的属性进行过滤 (选填)
  4. Set<EdgePropertyFilter>: 对点的属性进行过滤 (选填)

另一类是大部分算法通用的, limit 和 depth 等:

  1. depth: 遍历的层数, 对应 K 层邻居 (选填)
  2. direction: 遍历选择的方向 (选填, 默认 BOTH)
  3. max_degree: 每个点遍历时的最大出边数 (选填)
  4. limit: 总返回的最大点数 (选填)

注意点:

  • 传入的 Set<EdgeLables> 要检查一下合法性, 限定只允许传入起始点的 EdegeLabel, 比如 A-a->B-b->C 里, 只允许传入 a 边, 还是允许传入多种边
  • 目前的情况, 传入多类边会复杂许多, 先考虑每个 Filter 单一类型边

0x01. 过滤器

因为我们已经有了单机的 kneighbor 查询, 所以大部分的属性参数是无需重写的, 最主要的重点就在于这个点边的属性过滤器, 包括如何传入, 支持的类型等.

1. 类型

  • equal: 只选择属性相等的元素 (比如限定 name = “tom” 的点/边)
  • not_equal: 过滤掉属性相等的元素 (如限定 name != “tom” 的点/边)
  • >, <, ≥, ≤
  • contains: 字符串匹配, 给定 str 是否是原 str 的子串 (比如 filter = “ab” 是name = “cfabe” 的子串)
  • not_contains: 同上相反
  • in: 给一个 set 集合, 判断当前属性值是否满足集合中的任一个, 类似 contains (比如 filter = “[a, b, e]”, name = “b”)
  • not_in: 同上相反, not_contains

可以看到因为条件有一半是相反的关系, 所以核心就是两类:

  1. 判断数值类大小
  2. 判断字符串匹配 (包括是否相等)

2. 传入方式

用户期望的是传入一个 json, 包括多个过滤条件, 其中点和边的 key 是分开的, 那么我们就分开来说, 先看看点再说边

A. 点属性过滤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 用户期望的写法
"vertexPropFilter":[
   {
      "propName": "name",
      "operator": "IN",
      "propValue": [
         "中国建设行股份有限公司",
         "农行"
      ]
   },
   {
      "propName": "nick_name",
      "operator": "CONTAINS",
      "propValue": "工行"
   }
]

// 当前已经支持的边过滤写法
    "properties": {  // 可改名为 edgeFilter ?
      "weight": "P.gt(0.1)"
    },

可以看到上述的例子里的含义是很清晰的, 就是传入了一个个过滤条件对象, 多个过滤条件之间是 & 的关系, 从而大幅过滤数据

那么我们已有的逻辑里实现的过滤写法是什么样的呢? 从文档中可以看到, 已经提供了对边的属性过滤, 而且实现的更为通用和简洁, 默认 properties 就可代表通用的过滤器 map, 然后每个数组元素的 key 代表属性名, value 代表过滤条件, 那么不同点在于:

  1. 如果想传入一个 Set 的过滤器, 那么不知现有实现是否支持.

3. 注意事项

因为涉及到过滤器的实现和引入, 就需要注意一下有些地方:

  1. 不同条件的限定类型, 比如字符串类只允许做子串比较, 禁止比较大小.
  2. 多种条件叠加的时候, 如何处理
  3. 如果允许多个label 传入, 提前过滤是否会减少输出

0x02. 设计与实现

给一下目前的设计里, 是如何通用的支持点/边属性过滤的, 顺带还支持了底层遍历的时候不读取边的属性, 因为不少 path 类的遍历并不需要返回边的属性值, 可以进一步优化读取速度, 这是 gremlin 默认不支持的

A. Step(s) 对象

说 Step 和 Steps 对象之前, 先来看看整体的演化过程, 以任一个 TP 的遍历算法为例, 大体遵循:

  1. 参数不多, 直接使用 JSON 传递几个参数即可, 最简单. (常见 GET/DELETE 请求)
  2. 参数多, 则先封装成一个 Request 对象, 实际就是对 1 的封装, 然后如果还有嵌套.
    • 不需要过滤条件的 API, 把和遍历相关的放入 Step 对象
    • 需要点边复杂组合过滤的 API, 除了把遍历相关放入 VESteps 对象, 还构造两个 List<VEStepEntiy>
      1. 一个专门用来存放点 label 的过滤条件, 例如只查 Person 里 age > 10 和 Phone 里 count < 100 的点
      2. 一个专门用来存放边 label 的过滤条件, 例如只查 likes 中 name 包含 tom, 且 year > 2010 的边

嵌套对应的层级关系用简图表示如下:

graph LR

a(Request)--include-->b(VESteps)--include-->c(VEStepEntity--点集)--include-->d(properties-点过滤条件)
b--include-->c2(VEStepEntity--边集)--include-->d2(properties-边过滤条件)

那么简单来说, 这里把点和边属性的过滤拆开为了嵌套集合, 如果用户既对某些 VertexLabel 的属性做限制, 又需要对某些 EdgeLbale 的属性做限制, 那应构造类似如下的 json 请求:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
{
    "source": "1:tom",
    "steps": {
        "direction": "BOTH",
        "edge_steps": [
            {
                "label": "knows",
                "properties": {
                    "year": "P.lt(2010)"
                }
            },
            {
                "label": "created",
                "properties": {"name": "P.textContains('sub')"}
            }
        ],
        "vertex_steps": [
            {
                "label": "person",
                "properties": {
                    "age": "P.gt(25)"
                }
            },
            {
                "label": "software",
                "properties": {}
            }
        ]
    }
}

B. Kneighbor 例子

那么在 kneighbor 里, 具体是如何使用 Step 对象的呢, 一起来看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public String post(@Context GraphManager manager, @PathParam("graph") String graph,
                   Request request) {
    HugeGraph g = graph(manager, graph);
    Id sourceId = HugeVertex.getIdValue(request.source);
    Steps steps = steps(g, request.steps); // 初始化点边の过滤条件

    KneighborRecords results;
    try (KneighborTraverser traverser = new KneighborTraverser(g)) {
        results = traverser.customizedKneighbor(sourceId, steps, // 传入
                                                request.maxDepth,
                                                request.limit,
                                                request.withEdge);
    }

    // 省略其他无关的代码...
    return manager.serializer(g).writeNodesWithPath("kneighbor", neighbors, size,
                                                    paths, iterVertice, iterEdge, null);
}

// 然后看看上面的核心方法内容
public KneighborRecords customizedKneighbor(Id source, Steps steps,
                                            int maxDepth, long limit,
                                            boolean withEdge) {
    KneighborRecords records = new KneighborRecords(RecordType.INT,
                                                    concurrent,
                                                    source, true);

    Consumer<Id> consumer = v -> {
        if (this.reachLimit(limit, records.size())) {
            return;
        }
        Iterator<Edge> edges = edgesOfVertexAF(v, steps, false);

        while (!this.reachLimit(limit, records.size()) && edges.hasNext()) {
            HugeEdge edge = (HugeEdge) edges.next();
            Id target = edge.id().otherVertexId();
            records.addPath(v, target);
            if(withEdge) {
                // for breadth, we have to collect all edge during traversal,
                // to avoid over occupy memory, we collect edgeId only.
                records.addEdgeId(edge.id());
            }
        }
    };

    // 2. 开始 K 层迭代循环
    while (maxDepth-- > 0) {
        records.startOneLayer(true);
        traverseIds(records.keys(), consumer, concurrent);
        records.finishOneLayer();
    }

    // 3. 如果需要遍历边的属性?(可选) 
    if (withEdge) {
        // we should filter out unused-edges for breadth first algorithm.
        records.filterUnusedEdges(limit);
    }

    return records;
}

然后核心就转移到了 edgesOfVertexAF() ,

C. Kout + 边属性忽略

Kout 完全类似 kneighbor, 边属性过滤则详见源码, 不属于本篇重点, 暂略

0x04. 结果

最后, 基于上述设计实现的 kneighbors 接口, 我们能提供一个与 gremlin prediction 类似的过滤条件的设计, 下列已全部可支持:

  1. P.eq() 代表过滤出数值相等的元素
  2. P.neq() 代表过滤出数值不相等的元素
  3. P.lt() 代表过滤出数值小于 (<) 某数的元素
  4. P.lte() 代表过滤出数值小于相等 (≤) 某数的元素
  5. P.gt() 代表过滤出数值大于 (>) 某数的元素
  6. P.gte() 代表过滤出数值大于相等 (≥) 的元素
  7. P.between(a, b) 代表过滤出数值在 (a, b) 范围内的元素
  8. P.inside(a, b) 代表过滤出数值在 > a 且 < b 范围内的元素
  9. P.outside(a, b) 代表过滤出数值在 < a 且 > b 范围内的元素
  10. P.textcontains(str) 代表过滤出包含 str 子串的元素
  11. P.contains(str) 代表从集合中过滤出包含 str 字符串的元素
  12. P.within(a, b, c) 代表过滤出包含给定集合中任一子元素的元素

从这种加强的接口中也可以看出, 自定义接口的好处和缺点都很明显, 它远没有 gremlin/cypher 这类语法灵活, 由于不可能充当 DSL 的功能, 所以有新的需求则需要不断修改源码, 只适合在最常用的通用 api 上进行实现.

TODO: 后续考虑在 rest-api 中省略 P 的前缀, 更为友好, 最新支持类别请参考社区文档/代码

参考资料:

  1. HugeGraph Traverser Kneighbor - POST
  2. Gremlin Prediction - Gremlin Doc
  3. HugeGraph Kneighbors Source Code - Github