带过滤条件的图K步邻居查询
原本在图中常见的 K 步邻居 API 一般是查询某个点触发的 K 层邻居, 是一个单点 BFS/DFS 查询, 参数条件一般比较少, 今天来看看如果想多点出发, 并携带过滤条件的 K 步邻居如何实现 (实现后我们就可以在 rest-api
里直接使用覆盖大多数查询要求的条件了)
0x00. 需求分析
1. 概述
要实现一个 kneighbors()
接口. 允许传入一个 Set<Id>
作为起始点集, 以及一个 Set<EdgeLabel>
作为扩展的边类型集合, 并允许传入两个过滤条件, 对原始 K 层的结果进行过滤, 最后返回所有输入点的 K 层邻居的并集.
2. 核心参数
分两类, 一类是当前算法特有的, 比较重要, 这里因为语义, 可以默认去重都使用 Set 来存储:
Set<VertexId>
: 起始的点集合, 也就是从 N 个点开始出发遍历 (必填)Set<EdgeLabel>
: 遍历时扩展的边条件 (选填, 默认值根据 direction 来确定, 比如 BOTH 对应 ALL_Labels)Set<VertexPropertyFilter>
: 对点的属性进行过滤 (选填)Set<EdgePropertyFilter>: 对点的属性进行过滤 (选填)
另一类是大部分算法通用的, limit 和 depth 等:
- depth: 遍历的层数, 对应 K 层邻居 (选填)
- direction: 遍历选择的方向 (选填, 默认 BOTH)
- max_degree: 每个点遍历时的最大出边数 (选填)
- 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
可以看到因为条件有一半是相反的关系, 所以核心就是两类:
- 判断数值类大小
- 判断字符串匹配 (包括是否相等)
2. 传入方式
用户期望的是传入一个 json, 包括多个过滤条件, 其中点和边的 key 是分开的, 那么我们就分开来说, 先看看点再说边
A. 点属性过滤
1 | // 用户期望的写法 |
可以看到上述的例子里的含义是很清晰的, 就是传入了一个个过滤条件对象, 多个过滤条件之间是 &
的关系, 从而大幅过滤数据
那么我们已有的逻辑里实现的过滤写法是什么样的呢? 从文档中可以看到, 已经提供了对边的属性过滤, 而且实现的更为通用和简洁, 默认 properties
就可代表通用的过滤器 map, 然后每个数组元素的 key 代表属性名, value 代表过滤条件, 那么不同点在于:
- 如果想传入一个 Set 的过滤器, 那么不知现有实现是否支持.
3. 注意事项
因为涉及到过滤器的实现和引入, 就需要注意一下有些地方:
- 不同条件的限定类型, 比如字符串类只允许做子串比较, 禁止比较大小.
- 多种条件叠加的时候, 如何处理
- 如果允许多个label 传入, 提前过滤是否会减少输出
0x02. 设计与实现
给一下目前的设计里, 是如何通用的支持点/边属性过滤的, 顺带还支持了底层遍历的时候不读取边的属性, 因为不少 path 类的遍历并不需要返回边的属性值, 可以进一步优化读取速度, 这是 gremlin
默认不支持的
A. Step(s) 对象
说 Step 和 Steps 对象之前, 先来看看整体的演化过程, 以任一个 TP 的遍历算法为例, 大体遵循:
- 参数不多, 直接使用 JSON 传递几个参数即可, 最简单. (常见 GET/DELETE 请求)
- 参数多, 则先封装成一个
Request
对象, 实际就是对 1 的封装, 然后如果还有嵌套.- 不需要过滤条件的 API, 把和遍历相关的放入 Step 对象
- 需要点边复杂组合过滤的 API, 除了把遍历相关放入 VESteps 对象, 还构造两个
List<VEStepEntiy>
- 一个专门用来存放点 label 的过滤条件, 例如只查 Person 里 age > 10 和 Phone 里 count < 100 的点
- 一个专门用来存放边 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 | { |
B. Kneighbor 例子
那么在 kneighbor 里, 具体是如何使用 Step 对象的呢, 一起来看看
1 | public String post(@Context GraphManager manager, @PathParam("graph") String graph, |
然后核心就转移到了 edgesOfVertexAF()
,
C. Kout + 边属性忽略
Kout 完全类似 kneighbor, 边属性过滤则详见源码, 不属于本篇重点, 暂略
0x04. 结果
最后, 基于上述设计实现的 kneighbors
接口, 我们能提供一个与 gremlin prediction 类似的过滤条件的设计, 下列已全部可支持:
P.eq()
代表过滤出数值相等的元素P.neq()
代表过滤出数值不相等的元素P.lt()
代表过滤出数值小于 (<) 某数的元素P.lte()
代表过滤出数值小于相等 (≤) 某数的元素P.gt()
代表过滤出数值大于 (>) 某数的元素P.gte()
代表过滤出数值大于相等 (≥) 的元素P.between(a, b)
代表过滤出数值在(a, b)
范围内的元素P.inside(a, b)
代表过滤出数值在> a
且< b
范围内的元素P.outside(a, b)
代表过滤出数值在< a
且> b
范围内的元素P.textcontains(str)
代表过滤出包含 str 子串的元素P.contains(str)
代表从集合中过滤出包含 str 字符串的元素P.within(a, b, c)
代表过滤出包含给定集合中任一子元素的元素
从这种加强的接口中也可以看出, 自定义接口的好处和缺点都很明显, 它远没有 gremlin/cypher
这类语法灵活, 由于不可能充当 DSL 的功能, 所以有新的需求则需要不断修改源码, 只适合在最常用的通用 api 上进行实现.
TODO: 后续考虑在 rest-api 中省略 P
的前缀, 更为友好, 最新支持类别请参考社区文档/代码
参考资料:
- HugeGraph Traverser Kneighbor - POST
- Gremlin Prediction - Gremlin Doc
- HugeGraph Kneighbors Source Code - Github