lbug 0.16.1

An in-process property graph database management system built for query speed and scalability
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355

#pragma once

#include "binder/bound_statement.h"
#include "binder/query/query_graph.h"
#include "common/enums/accumulate_type.h"
#include "common/enums/extend_direction.h"
#include "common/enums/join_type.h"
#include "planner/join_order/cardinality_estimator.h"
#include "planner/join_order_enumerator_context.h"
#include "planner/operator/logical_plan.h"
#include "planner/operator/sip/semi_mask_target_type.h"

namespace lbug {
namespace extension {
class PlannerExtension;
}
namespace binder {
struct BoundTableScanInfo;
struct BoundCopyFromInfo;
struct BoundInsertInfo;
struct BoundSetPropertyInfo;
struct BoundDeleteInfo;
struct BoundJoinHintNode;
class NormalizedSingleQuery;
class NormalizedQueryPart;
class BoundReadingClause;
class BoundUpdatingClause;
class BoundProjectionBody;
} // namespace binder
namespace planner {

struct LogicalInsertInfo;

enum class SubqueryPlanningType : uint8_t {
    NONE = 0,
    UNNEST_CORRELATED = 1,
    CORRELATED = 2,
};

struct QueryGraphPlanningInfo {
    // Predicate info.
    binder::expression_vector predicates;
    // Subquery info.
    SubqueryPlanningType subqueryType = SubqueryPlanningType::NONE;
    binder::expression_vector corrExprs;
    cardinality_t corrExprsCard = 0;
    // Join hint info.
    std::shared_ptr<binder::BoundJoinHintNode> hint = nullptr;

    bool containsCorrExpr(const binder::Expression& expr) const;
};

// Group property expressions based on node/relationship.
class PropertyExprCollection {
public:
    void addProperties(const std::string& patternName,
        std::shared_ptr<binder::Expression> property);
    binder::expression_vector getProperties(const binder::Expression& pattern) const;
    binder::expression_vector getProperties() const;

    void clear();

private:
    std::unordered_map<std::string, binder::expression_vector> patternNameToProperties;
};

class LBUG_API Planner {
public:
    explicit Planner(main::ClientContext* clientContext);
    DELETE_COPY_AND_MOVE(Planner);

    LogicalPlan planStatement(const binder::BoundStatement& statement);

    // Plan simple statement.
    LogicalPlan planCreateTable(const binder::BoundStatement& statement);
    LogicalPlan planCreateType(const binder::BoundStatement& statement);
    LogicalPlan planCreateSequence(const binder::BoundStatement& statement);
    LogicalPlan planCreateMacro(const binder::BoundStatement& statement);
    LogicalPlan planDrop(const binder::BoundStatement& statement);
    LogicalPlan planAlter(const binder::BoundStatement& statement);
    LogicalPlan planStandaloneCall(const binder::BoundStatement& statement);
    LogicalPlan planStandaloneCallFunction(const binder::BoundStatement& statement);
    LogicalPlan planExplain(const binder::BoundStatement& statement);
    LogicalPlan planTransaction(const binder::BoundStatement& statement);
    LogicalPlan planExtension(const binder::BoundStatement& statement);
    LogicalPlan planAttachDatabase(const binder::BoundStatement& statement);
    LogicalPlan planDetachDatabase(const binder::BoundStatement& statement);
    LogicalPlan planUseDatabase(const binder::BoundStatement& statement);
    LogicalPlan planCreateGraph(const binder::BoundStatement& statement);
    LogicalPlan planUseGraph(const binder::BoundStatement& statement);
    LogicalPlan planExtensionClause(const binder::BoundStatement& statement);

    // Plan copy.
    LogicalPlan planCopyTo(const binder::BoundStatement& statement);
    LogicalPlan planCopyFrom(const binder::BoundStatement& statement);
    LogicalPlan planCopyNodeFrom(const binder::BoundCopyFromInfo* info);
    LogicalPlan planCopyRelFrom(const binder::BoundCopyFromInfo* info);

    // Plan export/import database
    std::vector<std::shared_ptr<LogicalOperator>> planExportTableData(
        const binder::BoundStatement& boundExportDatabase);
    LogicalPlan planExportDatabase(const binder::BoundStatement& statement);
    LogicalPlan planImportDatabase(const binder::BoundStatement& statement);

    // Plan query.
    LogicalPlan planQuery(const binder::BoundStatement& boundStatement);
    LogicalPlan planSingleQuery(const binder::NormalizedSingleQuery& singleQuery);
    void planQueryPart(const binder::NormalizedQueryPart& queryPart, LogicalPlan& prevPlan);

    // Plan read.
    void planReadingClause(const binder::BoundReadingClause& readingClause, LogicalPlan& plan);
    void planMatchClause(const binder::BoundReadingClause& readingClause, LogicalPlan& plan);
    void planUnwindClause(const binder::BoundReadingClause& readingClause, LogicalPlan& plan);
    void planTableFunctionCall(const binder::BoundReadingClause& readingClause, LogicalPlan& plan);

    void planReadOp(std::shared_ptr<LogicalOperator> op,
        const binder::expression_vector& predicates, LogicalPlan& plan);
    void planLoadFrom(const binder::BoundReadingClause& readingClause, LogicalPlan& plan);

    // Plan updating
    void planUpdatingClause(const binder::BoundUpdatingClause& updatingClause, LogicalPlan& plan);
    void planInsertClause(const binder::BoundUpdatingClause& updatingClause, LogicalPlan& plan);
    void planMergeClause(const binder::BoundUpdatingClause& updatingClause, LogicalPlan& plan);
    void planSetClause(const binder::BoundUpdatingClause& updatingClause, LogicalPlan& plan);
    void planDeleteClause(const binder::BoundUpdatingClause& updatingClause, LogicalPlan& plan);

    // Plan projection
    void planProjectionBody(const binder::BoundProjectionBody* projectionBody, LogicalPlan& plan);
    void planAggregate(const binder::expression_vector& expressionsToAggregate,
        const binder::expression_vector& expressionsToGroupBy, LogicalPlan& plan);
    void planOrderBy(const binder::expression_vector& expressionsToProject,
        const binder::expression_vector& expressionsToOrderBy, const std::vector<bool>& isAscOrders,
        LogicalPlan& plan);

    // Plan subquery
    void planOptionalMatch(const binder::QueryGraphCollection& queryGraphCollection,
        const binder::expression_vector& predicates, LogicalPlan& leftPlan,
        std::shared_ptr<binder::BoundJoinHintNode> hint);
    // Write whether optional match succeed or not to mark.
    void planOptionalMatch(const binder::QueryGraphCollection& queryGraphCollection,
        const binder::expression_vector& predicates, std::shared_ptr<binder::Expression> mark,
        LogicalPlan& leftPlan, std::shared_ptr<binder::BoundJoinHintNode> hint);
    void planRegularMatch(const binder::QueryGraphCollection& queryGraphCollection,
        const binder::expression_vector& predicates, LogicalPlan& leftPlan,
        std::shared_ptr<binder::BoundJoinHintNode> hint);
    void planSubquery(const std::shared_ptr<binder::Expression>& subquery, LogicalPlan& outerPlan);
    void planSubqueryIfNecessary(std::shared_ptr<binder::Expression> expression, LogicalPlan& plan);

    static binder::expression_vector getCorrelatedExprs(
        const binder::QueryGraphCollection& collection, const binder::expression_vector& predicates,
        Schema* outerSchema);

    // Plan query graphs
    LogicalPlan planQueryGraphCollectionInNewContext(
        const binder::QueryGraphCollection& queryGraphCollection,
        const QueryGraphPlanningInfo& info);
    LogicalPlan planQueryGraphCollection(const binder::QueryGraphCollection& queryGraphCollection,
        const QueryGraphPlanningInfo& info);
    LogicalPlan planQueryGraph(const binder::QueryGraph& queryGraph,
        const QueryGraphPlanningInfo& info);

    // Plan node/rel table scan
    void planBaseTableScans(const QueryGraphPlanningInfo& info);
    void planCorrelatedExpressionsScan(const QueryGraphPlanningInfo& info);
    void planNodeScan(uint32_t nodePos);
    void planNodeIDScan(uint32_t nodePos);
    void planRelScan(uint32_t relPos, const QueryGraphPlanningInfo& info);
    void appendExtend(std::shared_ptr<binder::NodeExpression> boundNode,
        std::shared_ptr<binder::NodeExpression> nbrNode, std::shared_ptr<binder::RelExpression> rel,
        common::ExtendDirection direction, const binder::expression_vector& properties,
        LogicalPlan& plan);

    // Plan dp level
    void planLevel(uint32_t level);
    void planLevelExactly(uint32_t level);
    void planLevelApproximately(uint32_t level);

    // Plan worst case optimal join
    void planWCOJoin(uint32_t leftLevel, uint32_t rightLevel);
    void planWCOJoin(const binder::SubqueryGraph& subgraph,
        const std::vector<std::shared_ptr<binder::RelExpression>>& rels,
        const std::shared_ptr<binder::NodeExpression>& intersectNode);

    // Plan index-nested-loop join / hash join
    void planInnerJoin(uint32_t leftLevel, uint32_t rightLevel);
    bool tryPlanINLJoin(const binder::SubqueryGraph& subgraph,
        const binder::SubqueryGraph& otherSubgraph,
        const std::vector<std::shared_ptr<binder::NodeExpression>>& joinNodes);
    void planInnerHashJoin(const binder::SubqueryGraph& subgraph,
        const binder::SubqueryGraph& otherSubgraph,
        const std::vector<std::shared_ptr<binder::NodeExpression>>& joinNodes, bool flipPlan);

    // Plan semi mask
    void appendNodeSemiMask(SemiMaskTargetType targetType, const binder::NodeExpression& node,
        LogicalPlan& plan);
    LogicalPlan getNodeSemiMaskPlan(SemiMaskTargetType targetType,
        const binder::NodeExpression& node, std::shared_ptr<binder::Expression> nodePredicate);

    // This is mostly used when we try to reinterpret function output as node and read its
    // properties, e.g. query_vector_index, gds algorithms ...
    LogicalPlan getNodePropertyScanPlan(const binder::NodeExpression& node);

    // Append dummy sink
    void appendDummySink(LogicalPlan& plan);

    // Append empty result
    void appendEmptyResult(LogicalPlan& plan);

    // Append updating operators
    void appendInsertNode(const std::vector<const binder::BoundInsertInfo*>& boundInsertInfos,
        LogicalPlan& plan);
    void appendInsertRel(const std::vector<const binder::BoundInsertInfo*>& boundInsertInfos,
        LogicalPlan& plan);

    void appendSetProperty(const std::vector<binder::BoundSetPropertyInfo>& infos,
        LogicalPlan& plan);
    void appendDelete(const std::vector<binder::BoundDeleteInfo>& infos, LogicalPlan& plan);
    std::unique_ptr<LogicalInsertInfo> createLogicalInsertInfo(
        const binder::BoundInsertInfo* info) const;

    // Append projection operators
    void appendProjection(const binder::expression_vector& expressionsToProject, LogicalPlan& plan);
    void appendAggregate(const binder::expression_vector& expressionsToGroupBy,
        const binder::expression_vector& expressionsToAggregate, LogicalPlan& plan);
    void appendOrderBy(const binder::expression_vector& expressions,
        const std::vector<bool>& isAscOrders, LogicalPlan& plan);
    void appendMultiplicityReducer(LogicalPlan& plan);
    void appendLimit(std::shared_ptr<binder::Expression> skipNum,
        std::shared_ptr<binder::Expression> limitNum, LogicalPlan& plan);

    // Append scan operators
    void appendExpressionsScan(const binder::expression_vector& expressions, LogicalPlan& plan);
    void appendScanNodeTable(std::shared_ptr<binder::Expression> nodeID,
        std::vector<common::table_id_t> tableIDs, const binder::expression_vector& properties,
        LogicalPlan& plan);

    // Append extend operators
    void appendNonRecursiveExtend(const std::shared_ptr<binder::NodeExpression>& boundNode,
        const std::shared_ptr<binder::NodeExpression>& nbrNode,
        const std::shared_ptr<binder::RelExpression>& rel, common::ExtendDirection direction,
        bool extendFromSource, const binder::expression_vector& properties, LogicalPlan& plan);
    void appendRecursiveExtend(const std::shared_ptr<binder::NodeExpression>& boundNode,
        const std::shared_ptr<binder::NodeExpression>& nbrNode,
        const std::shared_ptr<binder::RelExpression>& rel, common::ExtendDirection direction,
        LogicalPlan& plan);
    void createPathNodePropertyScanPlan(const std::shared_ptr<binder::NodeExpression>& node,
        const binder::expression_vector& properties, LogicalPlan& plan);
    void createPathRelPropertyScanPlan(const std::shared_ptr<binder::NodeExpression>& boundNode,
        const std::shared_ptr<binder::NodeExpression>& nbrNode,
        const std::shared_ptr<binder::RelExpression>& recursiveRel,
        common::ExtendDirection direction, bool extendFromSource,
        const binder::expression_vector& properties, LogicalPlan& plan);
    void appendNodeLabelFilter(std::shared_ptr<binder::Expression> nodeID,
        std::unordered_set<common::table_id_t> tableIDSet, LogicalPlan& plan);

    // Append Join operators
    void appendHashJoin(const binder::expression_vector& joinNodeIDs, common::JoinType joinType,
        LogicalPlan& probePlan, LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendHashJoin(const binder::expression_vector& joinNodeIDs, common::JoinType joinType,
        std::shared_ptr<binder::Expression> mark, LogicalPlan& probePlan, LogicalPlan& buildPlan,
        LogicalPlan& resultPlan);
    void appendHashJoin(const std::vector<binder::expression_pair>& joinConditions,
        common::JoinType joinType, std::shared_ptr<binder::Expression> mark, LogicalPlan& probePlan,
        LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendAccHashJoin(const std::vector<binder::expression_pair>& joinConditions,
        common::JoinType joinType, std::shared_ptr<binder::Expression> mark, LogicalPlan& probePlan,
        LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendMarkJoin(const binder::expression_vector& joinNodeIDs,
        const std::shared_ptr<binder::Expression>& mark, LogicalPlan& probePlan,
        LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendMarkJoin(const std::vector<binder::expression_pair>& joinConditions,
        const std::shared_ptr<binder::Expression>& mark, LogicalPlan& probePlan,
        LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendIntersect(const std::shared_ptr<binder::Expression>& intersectNodeID,
        binder::expression_vector& boundNodeIDs, LogicalPlan& probePlan,
        std::vector<LogicalPlan>& buildPlans);

    void appendCrossProduct(const LogicalPlan& probePlan, const LogicalPlan& buildPlan,
        LogicalPlan& resultPlan);
    // Optional cross product produce at least one tuple for each probe tuple
    void appendOptionalCrossProduct(std::shared_ptr<binder::Expression> mark,
        const LogicalPlan& probePlan, const LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendAccOptionalCrossProduct(std::shared_ptr<binder::Expression> mark,
        LogicalPlan& probePlan, const LogicalPlan& buildPlan, LogicalPlan& resultPlan);
    void appendCrossProduct(common::AccumulateType accumulateType,
        std::shared_ptr<binder::Expression> mark, const LogicalPlan& probePlan,
        const LogicalPlan& buildPlan, LogicalPlan& resultPlan);

    // Append accumulate operators
    // Skip if plan has been accumulated.
    void tryAppendAccumulate(LogicalPlan& plan);
    // Accumulate everything.
    void appendAccumulate(LogicalPlan& plan);
    // Accumulate everything. Append mark.
    void appendOptionalAccumulate(std::shared_ptr<binder::Expression> mark, LogicalPlan& plan);
    // Append accumulate with a set of expressions being flattened first.
    void appendAccumulate(const binder::expression_vector& flatExprs, LogicalPlan& plan);
    // Append accumulate with a set of expressions being flattened first. Append mark.
    void appendAccumulate(common::AccumulateType accumulateType,
        const binder::expression_vector& flatExprs, std::shared_ptr<binder::Expression> mark,
        LogicalPlan& plan);

    void appendDummyScan(LogicalPlan& plan);

    void appendUnwind(const binder::BoundReadingClause& boundReadingClause, LogicalPlan& plan);

    void appendFlattens(const f_group_pos_set& groupsPos, LogicalPlan& plan);
    void appendFlattenIfNecessary(f_group_pos groupPos, LogicalPlan& plan);

    void appendFilters(const binder::expression_vector& predicates, LogicalPlan& plan);
    void appendFilter(const std::shared_ptr<binder::Expression>& predicate, LogicalPlan& plan);

    void appendTableFunctionCall(const binder::BoundTableScanInfo& info, LogicalPlan& plan);

    void appendDistinct(const binder::expression_vector& keys, LogicalPlan& plan);

    const CardinalityEstimator& getCardinalityEstimator() const { return cardinalityEstimator; }
    CardinalityEstimator& getCardinliatyEstimatorUnsafe() { return cardinalityEstimator; }

    // Get operators
    static std::shared_ptr<LogicalOperator> getTableFunctionCall(
        const binder::BoundTableScanInfo& info);
    static std::shared_ptr<LogicalOperator> getTableFunctionCall(
        const binder::BoundReadingClause& readingClause);

    LogicalPlan createUnionPlan(std::vector<LogicalPlan>& childrenPlans,
        const binder::expression_vector& expressions, bool isUnionAll);

    binder::expression_vector getProperties(const binder::Expression& pattern) const;

    JoinOrderEnumeratorContext enterNewContext();
    void exitContext(JoinOrderEnumeratorContext prevContext);
    PropertyExprCollection enterNewPropertyExprCollection();
    void exitPropertyExprCollection(PropertyExprCollection collection);

    static binder::expression_vector getNewlyMatchedExprs(
        const std::vector<binder::SubqueryGraph>& prevs, const binder::SubqueryGraph& new_,
        const binder::expression_vector& exprs);
    static binder::expression_vector getNewlyMatchedExprs(const binder::SubqueryGraph& prev,
        const binder::SubqueryGraph& new_, const binder::expression_vector& exprs);
    static binder::expression_vector getNewlyMatchedExprs(const binder::SubqueryGraph& leftPrev,
        const binder::SubqueryGraph& rightPrev, const binder::SubqueryGraph& new_,
        const binder::expression_vector& exprs);

private:
    main::ClientContext* clientContext;
    PropertyExprCollection propertyExprCollection;
    CardinalityEstimator cardinalityEstimator;
    JoinOrderEnumeratorContext context;
    const QueryGraphPlanningInfo* currentQueryGraphPlanningInfo = nullptr;
    std::vector<extension::PlannerExtension*> plannerExtensions;
};

} // namespace planner
} // namespace lbug