初识分布式图数据库 Nebula Graph 2.0 Query Engine

摘要：本文主要介绍 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 会根据执行计划生成对应的执行算子，从叶子节点开始执行，一直到根节点结束。其结构如下：

其中每一个执行计划节点都一一对应一个执行算子节点，其输入输出在执行计划期间已经确定，每个算子只需要拿到输入变量中的值然后进行计算，最后将计算结果放入对应的输出变量中即可，所以只需要从开始节点一步步执行，最后一个算子的结果会作为最终结果返回给用户。

五、实例

上图从左到右依次显示执行计划中每个节点的唯一 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 表鼓励啦~~ :bow:‍♂️:bow:‍♀️ [手动跪谢]

交流图数据库技术？交个朋友，Nebula Graph 官方小助手微信： NebulaGraphbot 拉你进交流群~~