关于nebula:Nebula-Graph-源码解读系列-｜-Vol02-详解-Validator

34次阅读

共计 7469 个字符，预计需要花费 19 分钟才能阅读完成。

整体架构  

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 statement
    NG_RETURN_IF_ERROR(checkDuplicateColName());

    // Execute after validateImpl because need field from it
    if (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
发表至： nebula
2021-09-24
 0
关于nebula:AI-协助办公-｜记一次用-GPT4-写一个消息同步-App
关于nebula:实操适配-NebulaGraph-新版本与压测实践
关于nebula:关于-LLM-和图数据库知识图谱的那些事
关于nebula:Nebula-在-Akulaku-智能风控的实践图模型的训练与部署