Nebula Graph 源码解读系列 ｜ Vol.02 详解 Validator

2023-10-15 02:50
文章标签 源码 详解 系列 graph 解读 nebula validator vol.02

本文主要是介绍Nebula Graph 源码解读系列 ｜ Vol.02 详解 Validator，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Nebula Graph 源码解读系列 ｜ Vol.02 详解 Validator

整体架构

Nebula Graph Query Engine 主要分为四个模块，分别是 Parser、Validator、Optimizer 和 Executor。

Parser 完成对语句的词法语法解析并生成抽象语法树（AST），Validator 会将 AST 转化为执行计划，Optimizer 对执行计划进行优化，而 Executor 负责实际数据的计算。

这篇文章我们主要介绍 Validator 的实现原理。

目录结构

Validator 代码实现在 src/validator 和 src/planner 目录。

src/validator 目录主要包括各种子句的 Validator 实现，比如 OrderByValidator、LimitValidator、GoValidator 等等。

validator/
├── ACLValidator.h
├── AdminJobValidator.h
├── AdminValidator.h
├── AssignmentValidator.h
├── BalanceValidator.h
├── DownloadValidator.h
├── ExplainValidator.h
├── FetchEdgesValidator.h
├── FetchVerticesValidator.h
├── FindPathValidator.h
├── GetSubgraphValidator.h
├── GoValidator.h
├── GroupByValidator.h
├── IngestValidator.h
├── LimitValidator.h
├── LookupValidator.h
├── MaintainValidator.h
├── MatchValidator.h
├── MutateValidator.h
├── OrderByValidator.h
├── PipeValidator.h
├── ReportError.h
├── SequentialValidator.h
├── SetValidator.h
├── TraversalValidator.h
├── UseValidator.h
├── Validator.h
└── YieldValidator.h

src/planner/plan 目录定义了所有 PlanNode 的数据结构，用于生成最终的执行计划。比如，当查询语句中含有聚合函数时，执行计划中会生成 Aggregate 节点，Aggregate 类会指定聚合函数计算时所需的全部信息，包括分组列和聚合函数表达式，Aggregate 类定义在 Query.h 中。Nebula 定义了一百多种 PlanNode，PlanNode::kind 定义在 PlanNode.h 中，在此不做详细阐述。

planner/plan/
├── Admin.cpp          
├── Admin.h             // administration related  nodes
├── Algo.cpp
├── Algo.h              // graph algorithm related nodes
├── ExecutionPlan.cpp
├── ExecutionPlan.h     // explain and profile nodes
├── Logic.cpp
├── Logic.h             // nodes introduced by the implementation layer
├── Maintain.cpp
├── Maintain.h          // schema related nodes
├── Mutate.cpp
├── Mutate.h            // DML related nodes
├── PlanNode.cpp
├── PlanNode.h          // plan node base classes
├── Query.cpp
├── Query.h             // DQL related nodes
└── Scan.h              // index related nodes

src/planner 目录还定义了 nGQL 和 match 语句的 planner 实现，用于生成 nGQL 和 match 语句执行计划。

源码解析

validator 入口函数是 Validator::validate(Sentence*, QueryContext*)，负责将 parser 生成的抽象语法树转化为执行计划，QueryContext 中会保存最终生成的执行计划 root 节点，函数代码如下：

Status Validator::validate(Sentence* sentence, QueryContext* qctx) {DCHECK(sentence != nullptr);DCHECK(qctx != nullptr);// Check if space chosen from session. if chosen, add it to context.auto session = qctx->rctx()->session();if (session->space().id > kInvalidSpaceID) {auto spaceInfo = session->space();qctx->vctx()->switchToSpace(std::move(spaceInfo));}auto validator = makeValidator(sentence, qctx);NG_RETURN_IF_ERROR(validator->validate());auto root = validator->root();if (!root) {return Status::SemanticError("Get null plan from sequential validator");}qctx->plan()->setRoot(root);return Status::OK();
}

该函数首先获取当前 session 的 space 信息并保存在 ValidateContext中，之后调用 Validator::makeValidator() 和 Validator::validate() 函数。

Validator::makeValidator() 的功能是生成子句的 validator，该函数会首先生成 SequentialValidator，SequentialValidator 是 validator 的入口，所有语句都会首先生成 SequentialValidator。

SequentialValidator::validateImpl() 函数会调用 Validator::makeValidator() 生成相应子句的 validator。函数代码如下：

Status SequentialValidator::validateImpl() {Status status;if (sentence_->kind() != Sentence::Kind::kSequential) {return Status::SemanticError("Sequential validator validates a SequentialSentences, but %ld is given.",static_cast<int64_t>(sentence_->kind()));}auto seqSentence = static_cast<SequentialSentences*>(sentence_);auto sentences = seqSentence->sentences();seqAstCtx_->startNode = StartNode::make(seqAstCtx_->qctx);for (auto* sentence : sentences) {auto validator = makeValidator(sentence, qctx_);NG_RETURN_IF_ERROR(validator->validate());seqAstCtx_->validators.emplace_back(std::move(validator));}return Status::OK();
}

同样地，PipeValidator、AssignmentValidator 和 SetValidator 也会生成相应子句的 validator。

Validator::validate() 负责生成执行计划，函数代码如下：

Status Validator::validate() {auto vidType = space_.spaceDesc.vid_type_ref().value().type_ref().value();vidType_ = SchemaUtil::propTypeToValueType(vidType);NG_RETURN_IF_ERROR(validateImpl());// Check for duplicate reference column names in pipe or var statementNG_RETURN_IF_ERROR(checkDuplicateColName());// Execute after validateImpl because need field from itif (FLAGS_enable_authorize) {NG_RETURN_IF_ERROR(checkPermission());}NG_RETURN_IF_ERROR(toPlan());return Status::OK();
}

该函数首先检查 space 和用户权限等信息，之后调用函数 Validator:validateImpl() 完成子句校验，validateImpl() 函数是 Validator 类的纯虚函数，利用多态调用不同子句的 validatorImpl() 实现函数。最后调用 Validator::toPlan() 函数生成执行计划，toPlan() 函数会生成子句的执行计划，子执行计划会被连接形成完整的执行计划，比如 match 语句中通过函数 MatchPlanner::connectSegments() 连接子执行计划，而 nGQL 语句则通过 Validator::appendPlan() 实现。

举例

下面我们以 nGQL 语句为例具体介绍一下以上流程。

语句：

GO 3 STEPS FROM "vid" OVER edge 
WHERE $$.tag.prop > 30 
YIELD edge._dst AS dst 
| ORDER BY $-.dst

这条 nGQL 语句在 validator 阶段主要经历三个过程：

制作子句 validator

首先会调用 Validator::makeValidator() 生成 SequentialValidator。在 SequentialValidator::validateImpl() 函数中会生成 PipeValidator，PipeValidator 会制作左右子句的 validator，分别是 GoValidator 和 OrderByValidator。

子句校验

子句校验阶段会分别校验 Go 和 OrderBy 子句。

以 Go 语句为例，会先校验语义错误，比如 aggregate 函数使用不当、表达式类型不匹配等等，然后依次校验内部子句，校验过程中会把校验的中间结果保存在 GoContext 中，作为 GoPlanner 生成执行计划的依据。比如 validateWhere() 会保存过滤条件表达式用于之后生成 Filter 执行计划节点。

    NG_RETURN_IF_ERROR(validateStep(goSentence->stepClause(), goCtx_->steps));  // 校验 step 子句NG_RETURN_IF_ERROR(validateStarts(goSentence->fromClause(), goCtx_->from)); // 校验 from 子句NG_RETURN_IF_ERROR(validateOver(goSentence->overClause(), goCtx_->over));   // 校验 over 子句NG_RETURN_IF_ERROR(validateWhere(goSentence->whereClause()));               // 校验 where 子句NG_RETURN_IF_ERROR(validateYield(goSentence->yieldClause()));               // 校验 yield 子句

plan 生成

Go 语句的子执行计划由 GoPlanner::transform(Astcontext*) 函数生成，代码如下：

StatusOr<SubPlan> GoPlanner::transform(AstContext* astCtx) {goCtx_ = static_cast<GoContext *>(astCtx);auto qctx = goCtx_->qctx;goCtx_->joinInput = goCtx_->from.fromType != FromType::kInstantExpr;goCtx_->joinDst = !goCtx_->exprProps.dstTagProps().empty();SubPlan startPlan = QueryUtil::buildStart(qctx, goCtx_->from, goCtx_->vidsVar);auto& steps = goCtx_->steps;if (steps.isMToN()) {return mToNStepsPlan(startPlan);}if (steps.steps() == 0) {auto* pt = PassThroughNode::make(qctx, nullptr);pt->setColNames(std::move(goCtx_->colNames));SubPlan subPlan;subPlan.root = subPlan.tail = pt;return subPlan;}if (steps.steps() == 1) {return oneStepPlan(startPlan);}return nStepsPlan(startPlan);
}

该函数首先调用 QueryUtil::buildStart() 构造start 节点，然后根据四种不同 step 的情况采用不同的方式生成计划。本例中语句会采用 nStepPlan 策略。

GoPlanner::nStepsPlan() 函数代码如下：

SubPlan GoPlanner::nStepsPlan(SubPlan& startVidPlan) {auto qctx = goCtx_->qctx;auto* start = StartNode::make(qctx);auto* gn = GetNeighbors::make(qctx, start, goCtx_->space.id);gn->setSrc(goCtx_->from.src);gn->setEdgeProps(buildEdgeProps(true));gn->setInputVar(goCtx_->vidsVar);auto* getDst = QueryUtil::extractDstFromGN(qctx, gn, goCtx_->vidsVar);PlanNode* loopBody = getDst;PlanNode* loopDep = nullptr;if (goCtx_->joinInput) {auto* joinLeft = extractVidFromRuntimeInput(startVidPlan.root);auto* joinRight = extractSrcDstFromGN(getDst, gn->outputVar());loopBody = trackStartVid(joinLeft, joinRight);loopDep = joinLeft;}auto* condition = loopCondition(goCtx_->steps.steps() - 1, gn->outputVar());auto* loop = Loop::make(qctx, loopDep, loopBody, condition);auto* root = lastStep(loop, loopBody == getDst ? nullptr : loopBody);SubPlan subPlan;subPlan.root = root;subPlan.tail = startVidPlan.tail == nullptr ? loop : startVidPlan.tail;return subPlan;
}

Go 语句生成的子执行计划如下：

Start -> GetNeighbors -> Project -> Dedup -> Loop -> GetNeighbors -> Project -> GetVertices -> Project -> LeftJoin -> Filter -> Project

Go 语句的功能是完成图的拓展，GetNeighbors 是执行计划中最重要的节点，GetNeighbors 算子会在运行期访问存储服务，拿到通过起点和指定边类型一步拓展后终点的 id，多步拓展通过 Loop 节点实现，Start 到 Loop 之间是 Loop 子计划，当满足条件时 Loop 子计划会被循环执行，最后一步拓展节点在 Loop 外实现。Project 节点用来获取当前拓展的终点 id，Dedup 节点对终点 id 进行去重后作为下一步拓展的起点。GetVertices 节点负责取终点 tag 的属性，Filter 做条件过滤，LeftJoin 的作用是合并 GetNeightbors 和 GetVertices 的结果。

OrderBy 语句的功能是对数据进行排序，子执行计划会生成 Sort 节点。

左右子句计划生成之后，PipeValidator::toPlan() 函数会调用 Validator::appendPlan() 连接左右子计划并得到最终的执行计划。完整执行计划如下：

Start -> GetNeighbors -> Project -> Dedup -> Loop -> GetNeighbors -> Project -> GetVertices -> Project -> LeftJoin -> Filter -> Project -> Sort -> DataCollect

以上 Validator 部分就介绍完毕。

论坛相关问题

问：如何找寻 parser/GraphParser.hpp 文件

答：.h 文件是由编译时产生的文件，编译一次就有文件了。

以上为本篇文章的介绍内容。

交流图数据库技术？加入 Nebula 交流群请先填写下你的 Nebula 名片，Nebula 小助手会拉你进群~~

这篇关于Nebula Graph 源码解读系列 ｜ Vol.02 详解 Validator的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/214871。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入（Embedding）方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节：嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”，它将文本中的单词或短语转换成计算机能够理解的数学形式，即向量。 正如翻译机将一种语言
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
MCU7.keil中build产生的hex文件解读

MCU7.keil中build产生的hex文件解读

1.hex文件大致解读 闲来无事,查看了MCU6.用keil新建项目的hex文件 用FlexHex打开 给我的第一印象是:经过软件的解释之后,发现这些数据排列地十分整齐 :02000F0080FE71:03000000020003F8:0C000300787FE4F6D8FD75810702000F3D:00000001FF 把解释后的数据当作十六进制来观察 1.每一行数据
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2