ITPub博客

首页 > 数据库 > 国内数据库 > 初识分布式图数据库 Nebula Graph 2.0 Query Engine

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

原创 国内数据库 作者:nebulagraph 时间:2021-01-07 17:18:32 0 删除 编辑

初识 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-common 中主要是表达式的定义、函数定义和一些公共接口、nebula-graph 主要负责 Query 模块、nebula-storage 主要负责 Storage 和 Meta 模块。

本文主要介绍 Query 层的整体结构,并通过一条 nGQL 语句来介绍其通过 Query 层的四个主要模块的流程,由于 Nebula Graph 2.0 仍处于开发中,版本变化比较频繁,本文主要针对 2.0 的 nebula-graph 仓中 master 分支的 aea5befd179585c510fb83452cb82276a7756529 版本。

二、框架

Query 层主要框架如下所示:

初识 Nebula Graph 2.0 Query Engine

主要分为 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 层的数据流如下所示:

初识 Nebula Graph 2.0 Query Engine

主要流程如下:

第一阶段:生成 AST

第一阶段:首先经过 Flex 和 Bison 组成的词法语法解析器模块 Parser 生成对应的 AST, 结构如下: 

初识 Nebula Graph 2.0 Query Engine

在此阶段 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 子句要求结果是  boolnull 或者  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 目录下,其逻辑结构如下:

初识 Nebula Graph 2.0 Query Engine

Query 执行流

执行流:该执行计划是一个有向无环图,其中节点间的依赖关系在 Validator 中每个模块的   函数中确定,在这个例子中 Project 依赖 Filter, Filter 依赖 GetNeighbor,依次类推直到 Start 节点为止。

在执行阶段执行器会对每个节点生成一个对应的算子,并且从根节点(这个例子中是 Project 节点)开始调度,此时发现此节点依赖其他节点,就先 递归调用依赖的节点,一直找到没有任何依赖的节点(此时为 Start 节点),然后开始执行,执行此节点后,继续执行此节点被依赖的其他节点(此时为 GetNeighbor 节点),一直到根节点为止。

Query 数据流

数据流:每个节点的输入输出也是在   中确定的, 虽然 执行的时候会按照执行计划的先后关系执行,但是每个节点的输入并不完全依赖上个节点,可以自行定义,因为所有节点的输入、输出其实是存储在一个哈希表中的,其中 key 是在建立每个节点的时候自己定义的名称,假如哈希表的名字为 ResultMap,在建立 Filter 这个节点时,定义该节点从  ResultMap["GN1"] 中取数据,然后将结果放入  ResultMap["Filter2"] 中,依次类推,将每个节点的输入输出都确定好,该哈希表定义在 nebula-graph 仓下  src/context/ExecutionContext.cpp 中,因为执行计划并不是真正地执行,所以对应哈希表中每个 key 的 value 值都为空(除了开始节点,此时会将起始数据放入该节点的输入变量中),其值会在 Excutor 阶段被计算并填充。

这个例子比较简单,最后会放一个复杂点的例子以便更好地理解执行计划。

第四阶段:执行计划优化

第四阶段:执行计划优化。如果  etc/nebula-graphd.conf 配置文件中  enable_optimizer 设置为  true ,则会对执行计划的优化,例如上边的例子,当开启优化时:

初识 Nebula Graph 2.0 Query Engine

此时会将 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 都不能再应用该规则为止,再执行下一个规则的探索。

本例中的优化如下图所示:

初识 Nebula Graph 2.0 Query Engine

例如,当搜索到 Filter 节点时,发现 Filter 节点的子节点是 GetNeighbors,和规则中事先定义的模式匹配成功,启动转换,将 Filter 节点融入到 GetNeighbors 节点中,然后移除掉 Filter 节点,继续匹配下一个规则。

优化的代码在 nebula-graph 仓下  src/optimizer/ 目录下。

第五阶段:执行

第五阶段:最后 Scheduler 会根据执行计划生成对应的执行算子,从叶子节点开始执行,一直到根节点结束。其结构如下:

初识 Nebula Graph 2.0 Query Engine

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

五、实例

下面执行一个最短路径的实例看看执行计划的具体结构,打开  , 输入下面语句  FIND SHORTEST PATH FROM "YAO MING" TO "Tim Duncan" OVER like, serve UPTO 5 STEPS ,在这条语句前加  EXPLAIN 关键字就可以得到该语句生成的执行计划详细信息:

初识 Nebula Graph 2.0 Query Engine

上图从左到右依次显示执行计划中每个节点的唯一 ID、节点的名称、该节点所依赖的节点 ID、profiling data(执行 profile 命令时的信息)、该节点的详细信息(包括输入输出变量名称,输出结果的列名,节点的参数信息)。

如果想要可视化一点可以在这条语句前加  EXPLAIN format="dot",这时候 nebula-console 会生成 dot 格式的数据,然后打开   这个网站将生成的 dot 数据粘贴上去,就可以看到如下结构,该结构对应着执行阶段各个算子的执行流程。

初识 Nebula Graph 2.0 Query Engine

因为最短路径使用了双向广度搜索算法分别从 "YAO MING" 和  "Tim Duncan" 两边同时扩展,所以中间的  GetNeighborsBFSShortest、  Project、  Dedup 分别有两个算子,通过  PassThrough 算子连接输入,由  ConjunctPath 算子拼接路径。然后由  LOOP 算子控制向外扩展的步数,可以看到  DataCollect 算子的输入其实是从  ConjuctPath 算子的输出变量中取值的。

各个算子的信息在 nebula-graph 仓下的  src/executor 目录下。

作者有话说:Hi,我是明泉,是图数据 Nebula Graph 研发工程师,主要工作和数据库查询引擎相关,希望本次的经验分享能给大家带来帮助,如有不当之处也希望能帮忙纠正,谢谢~

喜欢这篇文章?来来来,给我们的   点个 star 表鼓励啦~~ 🙇‍♂️🙇‍♀️ [手动跪谢]

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

推荐阅读


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69952037/viewspace-2748269/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2019-10-28

  • 博文量
    68
  • 访问量
    34888