Рубрики
Uncategorized

1 способ рассказывает, как генерируется план выполнения

В последней статье мы упомянули, что Validator преобразует AST, сгенерированный Parser в … Tagged with OpenSource, база данных, DevOps, программирование.

В последней статье мы упомянули, что Validator преобразует AST, сгенерированный Parser в план выполнения. В этой статье мы объясним, как генерируется план исполнения.

Обзор

Планировщик — это генератор планов выполнения. Он генерирует план выполнения, основанный на семантически достоверном AST, который был подтвержден Validator, а затем передает план оптимизатору для создания оптимизированного плана выполнения. Наконец, исполнитель выполнит оптимизированный план. План выполнения состоит из ряда узлов (Plannode).

Структура исходных файлов

Вот структура исходных файлов для планировщика.

src/planner
├── CMakeLists.txt
├── match/
├── ngql/
├── plan/
├── Planner.cpp
├── Planner.h
├── PlannersRegister.cpp
├── PlannersRegister.h
├── SequentialPlanner.cpp
├── SequentialPlanner.h
└── test

Файл Planner.h определяет структуру данных SubPlan и интерфейсы планировщика.

struct SubPlan {
    // root and tail of a subplan.
    PlanNode*   root{nullptr};
    PlanNode*   tail{nullptr};
};

PlannersRegister отвечает за регистрацию доступных планировщиков. До сих пор последовательно -планнер, Pathplanner, Lookupplanner, Goplanner и MatchPlanner были зарегистрированы для графика туманности.

Соответствующим предложением SequentialPlanner является последовательным смыслом, которое представляет собой комбинированное предложение, состоящее из нескольких предложений, разделенных с полуколонами. Каждое предложение может быть заявлением о выходе, поиске или совпадении. Таким образом, SequentialPlanner генерирует несколько планов выполнения, вызывая другие планировщики предложений, а затем вызывая Validator:: AppendPlan для подключения планов в конце к концу.

Матч/каталог определяет планировщики и стратегии соединения подпланов некоторых утверждений и предложений, совместимых с Opencypher, такими как совпадение, раскручивать, с возвратом, где, порядок, пропустить и ограничить. SegmentsConnector использует соответствующую стратегию, такую как AddInput, AddDectendency или InnerjoinSegments, чтобы подключить подпланированные конец к концу, чтобы создать полный план выполнения.

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.h

NGQL/Directory определяет планировщики операторов NGQL, таких как GO, поиск и поиск пути.

src/planner/ngql
├── GoPlanner.cpp
├── GoPlanner.h
├── LookupPlanner.cpp
├── LookupPlanner.h
├── PathPlanner.cpp
└── PathPlanner.h

План/каталог определяет семь категорий, в общей сложности более 100 узлов плана.

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.h

Вот введение в цель узлов плана:

Администратор: Для узлов, связанных с администрированием базы данных. Алго: Для узлов, связанных с алгоритмами путей, подграфов и так далее. Логика: Для узлов, связанных с логическим контролем, таким как петля и бинарный выбор. Поддерживать: для узлов, связанных со схемой. Мутат: Для узлов, связанных с DML. Запрос: Для узлов, связанных с вычислением запросов. Сканирование: для узлов, связанных с индексацией и сканированием. На этапе исполнителя каждый планод генерирует исполнителя, и каждый исполнитель отвечает за определенную функциональность.

Например, вот исходный код узла Getneighbors.

static GetNeighbors* make(QueryContext* qctx,
                              PlanNode* input,
                              GraphSpaceID space,
                              Expression* src,
                              std::vector edgeTypes,
                              Direction edgeDirection,
                              std::unique_ptr>&& vertexProps,
                              std::unique_ptr>&& edgeProps,
                              std::unique_ptr>&& statProps,
                              std::unique_ptr>&& exprs,
                              bool dedup = false,
                              bool random = false,
                              std::vector orderBy = {},
                              int64_t limit = -1,
                              std::string filter = "")

Getneighbors — это семантическая инкапсуляция кВ края в слое хранения. На основании исходной вершины данного типа края он найдет вершину назначения края. Во время курса «Нахождение края» Getneighbors может получить свойства края (EdgeProps). Кроме того, исходящий край хранится с его исходной вершиной в одном разделе (Shard), поэтому свойства исходной вершины (VertexProps) можно легко извлечь.

Вот исходный код совокупного узла.

static Aggregate* make(QueryContext* qctx,
                               PlanNode* input, 
                               std::vector&& groupKeys = {},
                               std::vector&& groupItems = {})

Совокупный узел предназначен для агрегатных вычислений. Он группирует таблицу в соответствии с GroudKeys и выполняет агрегатные расчеты по групповым.

Вот исходный код узла петли.

static Loop* make(QueryContext* qctx,
                      PlanNode* input,
                      PlanNode* body = nullptr,
                      Expression* condition = nullptr);

Узел петли предназначен для цикла. Он продолжает выполнять сегмент планода между телом и следующим начальным узлом, пока значение условия не будет изменено на false.

Вот исходный код узла Innerjoin.

static InnerJoin* make(QueryContext* qctx,
                           PlanNode* input,
                           std::pair leftVar,
                           std::pair rightVar,
                           std::vector hashKeys = {},
                           std::vector probeKeys = {})

Узел Innerjoin стремится выполнить внутреннее соединение между двумя таблицами (таблица или набор данных). Левые и справа относятся к двум таблицам соответственно.

Функции входа

Функцией входа планировщика является varidator∷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();
}

Шаги

  1. Вызов GetastContext () Во -первых, GetastContext () вызывается для получения проверки (валидатором) и переписываемым контекстами AST. Структура данных этих контекстов определена в SRC/Context/.
src/context/ast
├── AstContext.h
├── CypherAstContext.h
└── QueryAstContext.h
struct AstContext {
    QueryContext*   qctx; // The context of each query request
    Sentence*       sentence; // The AST of each query statement
    SpaceInfo       space; // The current graph space
};

CypherastContext определяет контексты AST совместимых с Opencepher. QueryastContext определяет контексты AST операторов NGQL.

2. Нарушение планировщика:: toplan (astctx) Во -вторых, называется Planner∷toplan (ASTCTX). На основании контекстов AST он найдет зарегистрированных планировщиков для оператора запроса в Plannermap, а затем создается соответствующий план выполнения.

Каждый план состоит из ряда планодов. Существует две основные отношения между планодами, зависимостью выполнения и зависимостью данных.

Зависимость выполнения: с точки зрения порядка выполнения, план выполнения является направленным ациклическим графом, а зависимости между узлами определяются при создании плана. На этапе выполнения исполнитель генерирует оператора для каждого узла и начинает планирование из корневого узла. Если корневой узел найден в зависимости от другого узла, для узла выполняется рекурсивный вызов, от которого зависит корневой узел. Процесс повторяется, пока не найдет узел, который не зависит от каких -либо других узлов. И затем узел выполняется. После того, как выполнение будет выполнено, исполнитель будет продолжать выполнять узлы, которые зависят от него до тех пор, пока не будет достигнут корневой узел. Зависимость данных: зависимость данных между узлами похожа на зависимость выполнения, то есть вывод предыдущего выполнения является входом следующего выполнения. Давайте возьмем узел Innerjoin в качестве примера. Входные данные внутреннего суда могут быть выходами некоторых узлов, которые не смежны с ним.

(На предыдущем рисунке сплошные линии представляют зависимости выполнения, а пунктирные линии представляют зависимости данных.)

Пример

В этом разделе я возьму MatchPlanner в качестве примера, чтобы показать, как генерируется план выполнения.

Вот пример утверждения.

MATCH (v:player)-[:like*2..4]-(v2:player)\
WITH v, v2.age AS age ORDER BY age WHERE age > 18\
RETURN id(v), age

После проверки MatchValidator и перезаписываемого, это утверждение будет выводиться как дерево, состоящее из контекстов.

=>

Каждый контекст соответствует пункту или подпункту.

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                       nodeInfos; // The vertices involved in the pattern
    std::vector                       edgeInfos; // The edges involved in the pattern
    PathBuildExpression*                        pathBuild{nullptr}; // Constructing the expression of Path
    std::unique_ptr         where; // filter SubClause
    std::unordered_map* aliasesUsed{nullptr}; // The specified alias
    std::unordered_map  aliasesGenerated; // The generated alias
};
...

И затем эти шаги выполняются:

1. Планировщик для заявления это утверждение, поэтому MatchPlanner находится из Plannermap.

2. Огромная плана MatchPlanner:: Transform призван для создания плана выполнения.

StatusOr MatchPlanner::transform(AstContext* astCtx) {
    if (astCtx->sentence->kind() != Sentence::Kind::kMatch) {
        return Status::Error("Only MATCH is accepted for match planner.");
    }
    auto* matchCtx = static_cast(astCtx);

    std::vector subplans;
    for (auto& clauseCtx : matchCtx->clauses) {
        switch (clauseCtx->kind) {
            case CypherClauseKind::kMatch: {
                auto subplan = std::make_unique()->transform(clauseCtx.get());
                NG_RETURN_IF_ERROR(subplan);
                subplans.emplace_back(std::move(subplan).value());
                break;
            }
            case CypherClauseKind::kUnwind: {
                auto subplan = std::make_unique()->transform(clauseCtx.get());
                NG_RETURN_IF_ERROR(subplan);
                auto& unwind = subplan.value().root;
                std::vector inputCols;
                if (!subplans.empty()) {
                    auto input = subplans.back().root;
                    auto cols = input->colNames();
                    for (auto col : cols) {
                        inputCols.emplace_back(col);
                    }
                }
                inputCols.emplace_back(unwind->colNames().front());
                unwind->setColNames(inputCols);
                subplans.emplace_back(std::move(subplan).value());
                break;
            }
            case CypherClauseKind::kWith: {
                auto subplan = std::make_unique()->transform(clauseCtx.get());
                NG_RETURN_IF_ERROR(subplan);
                subplans.emplace_back(std::move(subplan).value());
                break;
            }
            case CypherClauseKind::kReturn: {
                auto subplan = std::make_unique()->transform(clauseCtx.get());
                NG_RETURN_IF_ERROR(subplan);
                subplans.emplace_back(std::move(subplan).value());
                break;
            }
            default: { return Status::Error("Unsupported clause."); }
        }
    }

    auto finalPlan = connectSegments(astCtx, subplans, matchCtx->clauses);
    NG_RETURN_IF_ERROR(finalPlan);
    return std::move(finalPlan).value();
}

Оператор соответствия может состоять из множества совпадений, расслабленных, с и returnclauses. Следовательно, с MatchPlanner:: Transform соответствующие клаузелины вызываются непосредственно для генерации соответствующих подплатов, а затем подплаты подключены к концу к концу SegmentsConnector в соответствии с соответствующими стратегиями соединения.

В заявлении примера первый пункт-это пункт о матче: Match (V: Player)-[: как*2 .. 4]-(v2: игрок) , так что MatchClauseplanner:: Transform называется.

StatusOr MatchClausePlanner::transform(CypherClauseContextBase* clauseCtx) {
    if (clauseCtx->kind != CypherClauseKind::kMatch) {
        return Status::Error("Not a valid context for MatchClausePlanner.");
    }

    auto* matchClauseCtx = static_cast(clauseCtx);
    auto& nodeInfos = matchClauseCtx->nodeInfos;
    auto& edgeInfos = matchClauseCtx->edgeInfos;
    SubPlan matchClausePlan;
    size_t startIndex = 0;
    bool startFromEdge = false;

    NG_RETURN_IF_ERROR(findStarts(matchClauseCtx, startFromEdge, startIndex, matchClausePlan));
    NG_RETURN_IF_ERROR(
        expand(nodeInfos, edgeInfos, matchClauseCtx, startFromEdge, startIndex, matchClausePlan));
    NG_RETURN_IF_ERROR(projectColumnsBySymbols(matchClauseCtx, startIndex, matchClausePlan));
    NG_RETURN_IF_ERROR(appendFilterPlan(matchClauseCtx, matchClausePlan));
    return matchClausePlan;
}

Метод MatchClauseplanner:: Transform выполняет эти шаги:

Поиск начальной вершины расширения. В настоящее время доступны три стратегии для поиска начальной вершины. Они зарегистрированы в Startvidfinders.

// MATCH(n) WHERE id(n) = value RETURN n
startVidFinders.emplace_back(&VertexIdSeek::make);

// MATCH(n:Tag{prop:value}) RETURN n
// MATCH(n:Tag) WHERE n.prop = value RETURN n
startVidFinders.emplace_back(&PropIndexSeek::make);

// seek by tag or edge(index)
// MATCH(n: tag) RETURN n
// MATCH(s)-[:edge]->(e) RETURN e
startVidFinders.emplace_back(&LabelIndexSeek::make);

Из этих трех стратегий VertexidSeek является лучшим, что может определить конкретное видеоразовое виды исходной вершины. PropindexSeek — это второе, которое преобразуется в индекс, который фильтрует вершины по свойству. LabelIndexSeek будет преобразован в IndexScan.

Для каждой стратегии поиска исходной вершины функция FindStarts будет проходить все узлы в шаблоне соответствия, пока не найдет узел, который можно использовать в качестве узла исходной вершины, и генерирует соответствующие планоды для поиска исходной вершины.

Для этого примера используется LabelIndexScan, и исходная вершина — v.

Согласно стартовой вершине и шаблону соответствия, выполняется расширение на несколько шагов. Для примера утверждение, шаблон соответствия (V: Player)-[: как*1..2]-(V2: Player). Это означает, что V — начальная вершина, и расширение на одном или двух шагах вдоль края выполнена, а конечная вершина — тег игрока.

Вот как выполняется расширение.

Status Expand::doExpand(const NodeInfo& node, const EdgeInfo& edge, SubPlan* plan) {
    NG_RETURN_IF_ERROR(expandSteps(node, edge, plan));
    NG_RETURN_IF_ERROR(filterDatasetByPathLength(edge, plan->root, plan));
    return Status::OK();
}

Расширение на нескольких этапах генерирует петлевой узел. Корпус узла петли является расширением, что означает, что из данной исходной вершины выполняется одноступенчатое расширение, и такое расширение генерирует узел Getneighbors. Конечная вершина каждого расширения — начальная вершина следующего расширения. Он сохраняет цикл до тех пор, пока не будет достигнуто максимальное количество шагов, указанных в шаблоне.

Чтобы сделать расширение шага M, конечная вершина шага M-1 длиной используется в качестве начальной вершины расширения. Расширяя на один шаг больше, результат расширения построен в виде 1-ступенчатого длинного пути, состоящего из исходной вершины края и самого края. И затем внутренний младший выполняется на 1-ступенчатую длинный путь, а предыдущий длинный путь М-1, чтобы получить набор путей M шагов длиной.

Этот набор путей отфильтрован для удаления путей с помощью дублирующих краев, которые не допускаются для расширения пути в Opencypher. Наконец, конечная вершина используется в качестве начальной вершины следующего расширения. Такие расширения продолжаются до тех пор, пока не будет достигнуто указанное максимальное количество шагов.

После петли генерируется узел UnionAllVersionVar. Он сочетает в себе пути, варьирующиеся от 1-ступенчатого до M-шагов длиной, которые генерируются в результате выполнения каждой петли тела. Функция FilterDatasetBypathlength () будет генерировать узел фильтра для фильтрации всех путей, которые короче, чем минимальное количество шагов, указанных в шаблоне соответствия.

После расширения путь выглядит как (v) -подобный-()-e- (v)-?, Где свойства конечной вершины все еще отсутствует. На этом этапе необходимо генерирование узла Getvertices. Когда конечная вершина получена, к нему выполняется внутренний младший вариант и длинный путь M-шагов, и тогда у нас будет набор путей, которые соответствуют требованиям шаблона соответствия.

Более подробная информация о расширении по нескольким этапам совпадения будет представлена в новой статье «Матч шаблона переменной длины».

// Build Start node from first step
SubPlan loopBodyPlan;
PlanNode* startNode = StartNode::make(matchCtx_->qctx);
startNode->setOutputVar(firstStep->outputVar());
startNode->setColNames(firstStep->colNames());
loopBodyPlan.tail = startNode;
loopBodyPlan.root = startNode;

// Construct loop body
NG_RETURN_IF_ERROR(expandStep(edge,
                              startNode,                // dep
                              startNode->outputVar(),   // inputVar
                              nullptr,
                              &loopBodyPlan));

NG_RETURN_IF_ERROR(collectData(startNode,           // left join node
                               loopBodyPlan.root,   // right join node
                               &firstStep,          // passThrough
                               &subplan));
// Union node
auto body = subplan.root;

// Loop condition
auto condition = buildExpandCondition(body->outputVar(), startIndex, maxHop);

// Create loop
auto* loop = Loop::make(matchCtx_->qctx, firstStep, body, condition);

// Unionize the results of each expansion which are stored in the firstStep node
auto uResNode = UnionAllVersionVar::make(matchCtx_->qctx, loop);
uResNode->setInputVar(firstStep->outputVar());
uResNode->setColNames({kPathStr});

subplan.root = uResNode;
plan->root = subplan.root;

Таблица выводится, и ее имена столбцов определены. Все именованные символы, указанные в шаблоне соответствия, используются в качестве имен столбцов для генерации таблицы для последующих предложений, которые будут генерировать узел проекта.

Второй пункт в заявлении примера — с. Он вызывает кв.

WITH v, v2.age AS age ORDER BY age WHERE age > 18

Это с пунктом дает таблицу с двумя столбцами с названием V и V2.age. Эти столбцы сортируются по возрасту, а затем таблица используется в качестве фильтра.

Доходная часть будет генерировать узел проекта. Порядок от части будет генерировать узел сортировки. И где часть будет генерировать узел фильтра.

Третий пункт — возврат. Он будет генерировать узел проекта.

RETURN id(v), age

Полный план выполнения оператора примера показан следующим образом.

Это конец этой статьи.

Если вы столкнетесь с какими -либо проблемами в процессе использования графика туманности, пожалуйста, обратитесь к Руководству по базе данных графика туманности, чтобы устранить задачу. Он подробно записывает точки знаний и конкретное использование базы данных графиков и график туманности базы данных графиков.

Оригинал: «https://dev.to/lisahui/1-way-tells-how-an-execution-plan-is-generated-4k9k»

Читайте ещё по теме: