摘要:本文主要介绍 Query 层的整体结构,并通过一条 nGQL 语句来介绍其通过 Query 层的四个主要模块的流程。
一、概述
分布式图数据库 Nebula Graph 2.0 版本相比 1.0 有较大改动,最明显的变化便是,在 1.0 版本中 Query、Storage 和 Meta 模块代码不作区分放在同一个代码仓中,而 Nebula Graph 2.0 开始在架构上先解耦成三个代码仓:nebula-graph、nebula-common 和 nebula-storage,其中 nebula-common 中主要是表达式的定义、函数定义和一些公共接口、nebula-graph 主要负责 Query 模块、nebula-storage 主要负责 Storage 和 Meta 模块。
本文主要介绍 Query 层的整体结构,并通过一条 nGQL 语句来介绍其通过 Query 层的四个主要模块的流程,由于 Nebula Graph 2.0 仍处于开发中,版本变化比较频繁,本文主要针对 2.0 的 nebula-graph 仓中 master 分支的 aea5befd179585c510fb83452cb82276a7756529 版本。
二、框架
Query 层主要框架如下所示:
主要分为 4 个子模块
- Parser:词法语法解析模块
- Validator:语句校验模块
- Planner:执行计划和优化器模块
- Executor:执行算子模块
三、代码结构
下面讲下 nebula-graph 的代码层次结构,如下所示
|--src
|--context // 校验期和执行期上下文
|--daemons
|--executor // 执行算子
|--mock
|--optimizer // 优化规则
|--parser // 词法语法分析
|--planner // 执行计划结构
|--scheduler // 调度器
|--service
|--util // 基础组件
|--validator // 语句校验
|--vistor
四、一个案例聊 Query
自 Nebula Graph v2.0 起,nGQL 的语法规则已经支持起始点的类型为 string
,正在兼容 1.0 的 int
类型。举个例子:
GO FROM "Tim" OVER like WHERE like.likeness > 8.0 YIELD like._dst
上面的一条 nGQL 语句在 Nebula Graph 的 Query 层的数据流如下所示:
主要流程如下:
第一阶段:生成 AST
第一阶段:首先经过 Flex 和 Bison 组成的词法语法解析器模块 Parser 生成对应的 AST, 结构如下:
在此阶段 Parser 会拦截掉不符合语法规则的语句。举个例子,GO "Tim" FROM OVER like YIELD like._dst
这种语法使用错误的语句会在语法解析阶段直接被拦截。
第二阶段:校验
第二阶段:Validator 在 AST 上进行一系列的校验工作,主要工作如下:
- 元数据信息的校验
在解析 OVER
、 WHERE
和 YIELD
语句时,会查找 Schema,校验 edge、tag 的信息是否存在。或者在 INSERT
数据时校验插入数据类型和 Schema 中的是否一致
- 上下文引用校验
遇到多语句时,例如:$var = GO FROM "Tim" OVER like YIELD like._dst AS ID; GO FROM $var.ID OVER serve YIELD serve._dst
,Validator 会校验 $var.ID` 首先检查变量 `var` 是否定义,其次再检查属性 `ID` 是否属于变量 `var`, 如果是将 `$var.ID
替换为 $var1.ID` 或者 `$var.IID
, 则会校验失败。
- 类型推断校验
推断表达式的结果属于什么类型,并根据具体的子句,校验类型是否正确。比如 WHERE
子句要求结果是 bool
,null
或者 empty
。
- *'' 展开**
例如,若输入语句为 GO FROM "Tim" OVER * YIELD like._dst, like.likeness, serve._dst
,则在校验 OVER
子句时需要查询 Schema 将 *
展开为所有的边,假如 Schema 中只有 like 和 serve 两条边时,该语句会展开为:GO FROM "Tim" OVER serve, like YIELD like._dst, like.likeness, serve._dst
- 输入输出校验
遇到 PIPE
语句时,例如:GO FROM "Tim" OVER like YIELD like._dst AS ID | GO FROM $-.ID OVER serve YIELD serve._dst`,Validator 会校验 `$-.ID
由于 ID 在上一条语句中已经定义,则该子句合法,如果是将$-.ID 换为 `$-.a` 而此时 a 未定义,因此该子句非法。
第三阶段:生成可执行计划
第三阶段:经过 Validator 之后会生成一个可执行计划,其中执行计划的数据结构在 src/planner
目录下,其逻辑结构如下:
Query 执行流
执行流:该执行计划是一个有向无环图,其中节点间的依赖关系在 Validator 中每个模块的 toPlan() 函数中确定,在这个例子中 Project 依赖 Filter, Filter 依赖 GetNeighbor,依次类推直到 Start 节点为止。
在执行阶段执行器会对每个节点生成一个对应的算子,并且从根节点(这个例子中是 Project 节点)开始调度,此时发现此节点依赖其他节点,就先递归调用依赖的节点,一直找到没有任何依赖的节点(此时为 Start 节点),然后开始执行,执行此节点后,继续执行此节点被依赖的其他节点(此时为 GetNeighbor 节点),一直到根节点为止。
Query 数据流
数据流:每个节点的输入输出也是在 toPlan() 中确定的, 虽然执行的时候会按照执行计划的先后关系执行,但是每个节点的输入并不完全依赖上个节点,可以自行定义,因为所有节点的输入、输出其实是存储在一个哈希表中的,其中 key 是在建立每个节点的时候自己定义的名称,假如哈希表的名字为 ResultMap,在建立 Filter 这个节点时,定义该节点从 ResultMap["GN1"]
中取数据,然后将结果放入 ResultMap["Filter2"]
中,依次类推,将每个节点的输入输出都确定好,该哈希表定义在 nebula-graph 仓下 src/context/ExecutionContext.cpp
中,因为执行计划并不是真正地执行,所以对应哈希表中每个 key 的 value 值都为空(除了开始节点,此时会将起始数据放入该节点的输入变量中),其值会在 Excutor 阶段被计算并填充。
这个例子比较简单,最后会放一个复杂点的例子以便更好地理解执行计划。
第四阶段:执行计划优化
第四阶段:执行计划优化。如果 etc/nebula-graphd.conf
配置文件中 enable_optimizer
设置为 true
,则会对执行计划的优化,例如上边的例子,当开启优化时:
此时会将 Filter 节点融入到 GetNeighbor 节点中,在执行阶段当 GetNeighbor 算子调用 Storage 层的接口获取一个点的邻边的时候,Storage 层内部会直接将不符合条件的边过滤掉,这样就可以极大的减少数据量的传输,俗称过滤下推。
在执行计划中,每个节点直接依赖另外一个节点。为了探索等价的变换和重用计划中相同的部分,会将节点的这种直接依赖关系转换为 OptGroupNode 与 OptGroup 的依赖。每个 OptGroup 中可以包含等价的 OptGroupNode 的集合,每个 OptGroupNode 都包含执行计划中的一个节点,同时 OptGroupNode 依赖的不再是 OptGroupNode 而是 OptGroup,这样从该 OptGroupNode 出发可以根据其依赖 OptGroup 中的不同的 OptGroupNode 拓展出很多等价的执行计划。同时 OptGroup 还可以被不同的 OptGroupNode 共用,节省存储的空间。
目前我们实现的所有优化规则认为是 RBO(rule-based optimization),即认为应用规则后的计划一定比应用前的计划要优。CBO(cost-based optimization) 目前正在同步开发。整个优化的过程是一个"自底向上"的探索过程,即对于每个规则而言,都会由执行计划的根节点(此例中是 Project 节点)开始,一步步向下找到最底层的节点,然后由该节点开始一步步向上探索每个 OptGroup 中的 OptGroupNode 是否匹配该规则,直到整个 Plan 都不能再应用该规则为止,再执行下一个规则的探索。
本例中的优化如下图所示:
例如,当搜索到 Filter 节点时,发现 Filter 节点的子节点是 GetNeighbors,和规则中事先定义的模式匹配成功,启动转换,将 Filter 节点融入到 GetNeighbors 节点中,然后移除掉 Filter 节点,继续匹配下一个规则。
优化的代码在 nebula-graph 仓下 src/optimizer/
目录下。
第五阶段:执行
第五阶段:最后 Scheduler 会根据执行计划生成对应的执行算子,从叶子节点开始执行,一直到根节点结束。其结构如下:
其中每一个执行计划节点都一一对应一个执行算子节点,其输入输出在执行计划期间已经确定,每个算子只需要拿到输入变量中的值然后进行计算,最后将计算结果放入对应的输出变量中即可,所以只需要从开始节点一步步执行,最后一个算子的结果会作为最终结果返回给用户。
五、实例
下面执行一个最短路径的实例看看执行计划的具体结构,打开 nebula-console, 输入下面语句FIND SHORTEST PATH FROM "YAO MING" TO "Tim Duncan" OVER like, serve UPTO 5 STEPS
,在这条语句前加 EXPLAIN
关键字就可以得到该语句生成的执行计划详细信息:
上图从左到右依次显示执行计划中每个节点的唯一 ID、节点的名称、该节点所依赖的节点 ID、profiling data(执行 profile 命令时的信息)、该节点的详细信息(包括输入输出变量名称,输出结果的列名,节点的参数信息)。
如果想要可视化一点可以在这条语句前加 EXPLAIN format="dot"
,这时候 nebula-console 会生成 dot 格式的数据,然后打开 Graphviz Online 这个网站将生成的 dot 数据粘贴上去,就可以看到如下结构,该结构对应着执行阶段各个算子的执行流程。
因为最短路径使用了双向广度搜索算法分别从"YAO MING"
和 "Tim Duncan"
两边同时扩展,所以中间的 GetNeighbors
、BFSShortest
、 Project
、 Dedup
分别有两个算子,通过 PassThrough
算子连接输入,由 ConjunctPath
算子拼接路径。然后由 LOOP
算子控制向外扩展的步数,可以看到 DataCollect
算子的输入其实是从 ConjuctPath
算子的输出变量中取值的。
各个算子的信息在 nebula-graph 仓下的 src/executor
目录下。
作者有话说:Hi,我是明泉,是图数据 Nebula Graph 研发工程师,主要工作和数据库查询引擎相关,希望本次的经验分享能给大家带来帮助,如有不当之处也希望能帮忙纠正,谢谢~
喜欢这篇文章?来来来,给我们的 GitHub 点个 star 表鼓励啦~~ 🙇♂️🙇♀️ [手动跪谢]
交流图数据库技术?交个朋友,Nebula Graph 官方小助手微信:NebulaGraphbot 拉你进交流群~~