Planner est un générateur de plan d’exécution. Il génère un plan d’exécution basé sur l’AST sémantiquement valide qui a été validé par Validator, puis transmet le plan à Optimizer pour générer un plan d’exécution optimisé. Enfin, Executor exécutera le plan optimisé. Un plan d’exécution est composé d’une série de nœuds (PlanNode).
Structure des fichiers sources
Voici la structure des fichiers sources pour Planner.
src/planner
├── CMakeLists.txt
├── match/
├── ngql/
├── plan/
├── Planner.cpp
├── Planner.h
├── PlannersRegister.cpp
├── PlannersRegister.h
├── SequentialPlanner.cpp
├── SequentialPlanner.h
└── testLes Planner.h fichier définit la structure de données de SubPlan et les interfaces de Planner.
struct SubPlan {
// root and tail of a subplan.
PlanNode* root{nullptr};
PlanNode* tail{nullptr};
};PlannersRegister est responsable de l’enregistrement des agendas disponibles. Jusque là, SequentialPlanner, PathPlanner, LookupPlanner, GoPlanner, et MatchPlanner ont été enregistrés pour Nebula Graph.
La phrase correspondante de SequentialPlanner est SequentialSentences, qui est une phrase combinée composée de plusieurs phrases séparées par des points-virgules. Chaque phrase peut être un GO, LOOKUP, ou MATCH déclaration. Par conséquent, SequentialPlanner génère plusieurs plans d’exécution en appelant d’autres planificateurs de phrases, puis en appelant Validator::appendPlan pour connecter les plans de bout en bout.
Les match/ répertoire définit les planificateurs et les stratégies de connexion des sous-plans de certaines instructions et clauses compatibles avec openCypher, telles que MATCH, UNWIND, WITH, RETURN, WHERE, ORDER BY, SKIP, et LIMIT. SegmentsConnector utilise une stratégie appropriée, comme AddInput, addDependency, ou innerJoinSegments, pour connecter les sous-plans de bout en bout pour générer un plan d’exécution complet.
src/planner/match
├── AddDependencyStrategy.cpp
├── AddDependencyStrategy.h
├── AddInputStrategy.cpp
├── AddInputStrategy.h
├── CartesianProductStrategy.cpp
├── CartesianProductStrategy.h
├── CypherClausePlanner.h
├── EdgeIndexSeek.h
├── Expand.cpp
├── Expand.h
├── InnerJoinStrategy.cpp
├── InnerJoinStrategy.h
├── LabelIndexSeek.cpp
├── LabelIndexSeek.h
├── LeftOuterJoinStrategy.h
├── MatchClausePlanner.cpp
├── MatchClausePlanner.h
├── MatchPlanner.cpp
├── MatchPlanner.h
├── MatchSolver.cpp
├── MatchSolver.h
├── OrderByClausePlanner.cpp
├── OrderByClausePlanner.h
├── PaginationPlanner.cpp
├── PaginationPlanner.h
├── PropIndexSeek.cpp
├── PropIndexSeek.h
├── ReturnClausePlanner.cpp
├── ReturnClausePlanner.h
├── SegmentsConnector.cpp
├── SegmentsConnector.h
├── SegmentsConnectStrategy.h
├── StartVidFinder.cpp
├── StartVidFinder.h
├── UnionStrategy.h
├── UnwindClausePlanner.cpp
├── UnwindClausePlanner.h
├── VertexIdSeek.cpp
├── VertexIdSeek.h
├── WhereClausePlanner.cpp
├── WhereClausePlanner.h
├── WithClausePlanner.cpp
├── WithClausePlanner.h
├── YieldClausePlanner.cpp
└── YieldClausePlanner.hLes ngql/ répertoire définit les planificateurs des instructions nGQL telles que GO, LOOKUP, et FIND PATH.
src/planner/ngql
├── GoPlanner.cpp
├── GoPlanner.h
├── LookupPlanner.cpp
├── LookupPlanner.h
├── PathPlanner.cpp
└── PathPlanner.hLes plan/ répertoire définit sept catégories, avec un total de plus de 100 nœuds de plan.
src/planner/plan
├── Admin.cpp
├── Admin.h
├── Algo.cpp
├── Algo.h
├── ExecutionPlan.cpp
├── ExecutionPlan.h
├── Logic.cpp
├── Logic.h
├── Maintain.cpp
├── Maintain.h
├── Mutate.cpp
├── Mutate.h
├── PlanNode.cpp
├── PlanNode.h
├── Query.cpp
├── Query.h
└── Scan.hVoici une introduction à l’objectif des nœuds de plan :
Admin: Pour les nœuds liés à l’administration de la base de données.Algo: Pour les nœuds liés aux algorithmes de chemins, sous-graphes, etc.Logic: Pour les nœuds liés au contrôle logique, tels que la boucle et la sélection binaire.Maintain: Pour les nœuds liés au schéma.Mutate: Pour les nœuds liés à DML.Query: Pour les nœuds liés au calcul des requêtes.Scan: Pour les nœuds liés à l’indexation et à l’analyse.
Dans la phase Executor, chaque PlanNode génère un exécuteur et chaque exécuteur est responsable d’une fonctionnalité spécifique.
Par exemple, voici le code source du GetNeighbors nœud.
static GetNeighbors* make(QueryContext* qctx,
PlanNode* input,
GraphSpaceID space,
Expression* src,
std::vector<EdgeType> edgeTypes,
Direction edgeDirection,
std::unique_ptr<std::vector<VertexProp>>&& vertexProps,
std::unique_ptr<std::vector<EdgeProp>>&& edgeProps,
std::unique_ptr<std::vector<StatProp>>&& statProps,
std::unique_ptr<std::vector<Expr>>&& exprs,
bool dedup = false,
bool random = false,
std::vector<storage::cpp2::OrderBy> orderBy = {},
int64_t limit = -1,
std::string filter = "")GetNeighbors est l’encapsulation sémantique du KV d’une arête dans la couche de stockage. En fonction du sommet source du type d’arête donné, il trouvera le sommet de destination d’une arête. Pendant le cours de recherche de bord, GetNeighbors peut récupérer les propriétés de l’arête (edgeProps). De plus, l’arête sortante est stockée avec son sommet source dans une partition (shard), de sorte que les propriétés du sommet source (vertexProps) peuvent être récupérées facilement.
Voici le code source du Aggregate nœud.
static Aggregate* make(QueryContext* qctx,
PlanNode* input,
std::vector<Expression*>&& groupKeys = {},
std::vector<Expression*>&& groupItems = {})Les Aggregate nœud est pour le calcul agrégé. Il regroupe le tableau selon groupKeys, et effectue un calcul global sur groupItems.
Voici le code source du Loop nœud.
static Loop* make(QueryContext* qctx,
PlanNode* input,
PlanNode* body = nullptr,
Expression* condition = nullptr);Les Loop nœud est pour la boucle. Il continue à exécuter le segment PlanNode entre le corps et le nœud de démarrage suivant jusqu’à ce que la valeur de condition est changé en false.
Voici le code source du InnerJoin nœud.
static InnerJoin* make(QueryContext* qctx,
PlanNode* input,
std::pair<std::string, int64_t> leftVar,
std::pair<std::string, int64_t> rightVar,
std::vector<Expression*> hashKeys = {},
std::vector<Expression*> probeKeys = {})Les InnerJoin node vise à effectuer une jointure interne entre deux tables (Table ou DataSet). leftVar et rightVar se référer respectivement aux deux tableaux.
Fonctions de saisie
La fonction de saisie du planificateur est Validator∷toPlan().
Status Validator::toPlan() {
auto* astCtx = getAstContext();
if (astCtx != nullptr) {
astCtx->space = space_;
}
auto subPlanStatus = Planner::toPlan(astCtx);
NG_RETURN_IF_ERROR(subPlanStatus);
auto subPlan = std::move(subPlanStatus).value();
root_ = subPlan.root;
tail_ = subPlan.tail;
VLOG(1) << "root: " << root_->kind() << " tail: " << tail_->kind();
return Status::OK();
}
Pas
1. Appeler getAstContext()
Premièrement, getAstContext() est appelé pour obtenir les contextes AST validés (par le validateur) et réécrits. La structure de données de ces contextes est définie dans src/context/.
src/context/ast
├── AstContext.h
├── CypherAstContext.h
└── QueryAstContext.hstruct AstContext {
QueryContext* qctx; // The context of each query request
Sentence* sentence; // The AST of each query statement
SpaceInfo space; // The current graph space
};CypherAstContext définit les contextes AST des instructions compatibles openCypher. QueryAstContext définit les contextes AST des instructions nGQL.
2. Appeler Planner::toPlan(astCtx)
Deuxièmement, Planner∷toPlan(astCtx) est appelé. Sur la base des contextes AST, il trouvera les planificateurs enregistrés pour l’instruction de requête dans PlannerMap, puis le plan d’exécution correspondant est généré.
Chaque plan est composé d’une série de PlanNodes. Il existe deux relations principales entre PlanNodes, la dépendance d’exécution et la dépendance de données.
- Dépendance d’exécution: Du point de vue de l’ordre d’exécution, un plan d’exécution est un graphe acyclique orienté, et les dépendances entre les nœuds sont déterminées lorsque le plan est généré. Dans la phase d’exécution, l’exécuteur génère un opérateur pour chaque nœud et démarre la planification à partir du nœud racine. Si le nœud racine est trouvé dépendant d’un autre nœud, un appel récursif est exécuté pour le nœud dont dépend le nœud racine. Le processus se répète jusqu’à ce qu’il trouve un nœud qui ne dépend d’aucun autre nœud. Et puis, le nœud est exécuté. Une fois l’exécution terminée, l’exécuteur continuera à exécuter les nœuds qui en dépendent jusqu’à ce que le nœud racine soit atteint.
- Dépendance des données: La dépendance de données entre les nœuds est comme la dépendance d’exécution, c’est-à-dire que la sortie de l’exécution précédente est l’entrée de l’exécution suivante. Prenons le
InnerJoinnœud à titre d’exemple. Les entrées deInnerJoinpeut-être les sorties de certains nœuds qui ne lui sont pas adjacents.
(Dans la figure précédente, les lignes pleines représentent les dépendances d’exécution et les lignes pointillées représentent les dépendances de données.)
Un exemple
Dans cette section, je vais prendre MatchPlanner comme exemple pour montrer comment un plan d’exécution est généré.
Voici l’exemple de déclaration.
MATCH (v:player)-[:like*2..4]-(v2:player)
WITH v, v2.age AS age ORDER BY age WHERE age > 18Après avoir été validée par MatchValidator et réécrite, cette instruction sera sortie sous forme d’arbre composé de contextes.
=>
Chaque contexte correspond à une clause ou à une sous-clause.
enum class CypherClauseKind : uint8_t {
kMatch,
kUnwind,
kWith,
kWhere,
kReturn,
kOrderBy,
kPagination,
kYield,
};
struct CypherClauseContextBase : AstContext {
explicit CypherClauseContextBase(CypherClauseKind k) : kind(k) {}
virtual ~CypherClauseContextBase() = default;
const CypherClauseKind kind;
};
struct MatchClauseContext final : CypherClauseContextBase {
MatchClauseContext() : CypherClauseContextBase(CypherClauseKind::kMatch) {}
std::vector<NodeInfo> nodeInfos; // pattern 中涉及的顶点信息
std::vector<EdgeInfo> edgeInfos; // pattern...