lbug 0.16.0

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

#pragma once

#include "bfs_graph.h"
#include "common/counter.h"
#include "common/enums/path_semantic.h"
#include "common/mask.h"
#include "common/types/types.h"
#include "processor/result/factorized_table.h"

namespace lbug {
namespace function {

class RJOutputWriter {
public:
    RJOutputWriter(main::ClientContext* context, common::NodeOffsetMaskMap* outputNodeMask,
        common::nodeID_t sourceNodeID);
    virtual ~RJOutputWriter() = default;

    void beginWriting(common::table_id_t tableID) {
        pinOutputNodeMask(tableID);
        beginWritingInternal(tableID);
    }
    virtual void beginWritingInternal(common::table_id_t tableID) = 0;
    // Write
    virtual void write(processor::FactorizedTable& fTable, common::table_id_t tableID,
        common::LimitCounter* counter) = 0;
    virtual void write(processor::FactorizedTable& fTable, common::nodeID_t dstNodeID,
        common::LimitCounter* counter) = 0;

    bool inOutputNodeMask(common::offset_t offset);

    virtual std::unique_ptr<RJOutputWriter> copy() = 0;

protected:
    std::unique_ptr<common::ValueVector> createVector(const common::LogicalType& type);

    void pinOutputNodeMask(common::table_id_t tableID);

protected:
    main::ClientContext* context;
    common::NodeOffsetMaskMap* outputNodeMask;
    common::nodeID_t sourceNodeID_;

    std::vector<common::ValueVector*> vectors;
    std::unique_ptr<common::ValueVector> srcNodeIDVector;
    std::unique_ptr<common::ValueVector> dstNodeIDVector;
};

struct PathsOutputWriterInfo {
    // Semantic
    common::PathSemantic semantic = common::PathSemantic::WALK;
    // Range
    uint16_t lowerBound = 0;
    // Direction
    bool flipPath = false;
    bool writeEdgeDirection = false;
    bool writePath = false;
    // Node predicate mask
    common::NodeOffsetMaskMap* pathNodeMask = nullptr;

    bool hasNodeMask() const { return pathNodeMask != nullptr; }
};

class PathsOutputWriter : public RJOutputWriter {
public:
    PathsOutputWriter(main::ClientContext* context, common::NodeOffsetMaskMap* outputNodeMask,
        common::nodeID_t sourceNodeID, PathsOutputWriterInfo info, BaseBFSGraph& bfsGraph);

    void beginWritingInternal(common::table_id_t tableID) override { bfsGraph.pinTableID(tableID); }

    void write(processor::FactorizedTable& fTable, common::table_id_t tableID,
        common::LimitCounter* counter) override;
    void write(processor::FactorizedTable& fTable, common::nodeID_t dstNodeID,
        common::LimitCounter* counter) override;

protected:
    virtual void writeInternal(processor::FactorizedTable& fTable, common::nodeID_t dstNodeID,
        common::LimitCounter* counter) = 0;
    // Fast path when there is no node predicate or semantic check
    void dfsFast(ParentList* firstParent, processor::FactorizedTable& fTable,
        common::LimitCounter* counter);
    // Slow path to check node predicate or semantic.
    void dfsSlow(ParentList* firstParent, processor::FactorizedTable& fTable,
        common::LimitCounter* counter);

    bool updateCounterAndTerminate(common::LimitCounter* counter);

    ParentList* findFirstParent(common::offset_t dstOffset) const;

    bool checkPathNodeMask(ParentList* element) const;
    // Check semantics
    bool checkAppendSemantic(const std::vector<ParentList*>& path, ParentList* candidate) const;
    bool checkReplaceTopSemantic(const std::vector<ParentList*>& path, ParentList* candidate) const;
    bool isAppendTrail(const std::vector<ParentList*>& path, ParentList* candidate) const;
    bool isAppendAcyclic(const std::vector<ParentList*>& path, ParentList* candidate) const;
    bool isReplaceTopTrail(const std::vector<ParentList*>& path, ParentList* candidate) const;
    bool isReplaceTopAcyclic(const std::vector<ParentList*>& path, ParentList* candidate) const;

    bool isNextViable(ParentList* next, const std::vector<ParentList*>& path) const;

    void beginWritePath(common::idx_t length) const;
    void writePath(const std::vector<ParentList*>& path) const;
    void writePathFwd(const std::vector<ParentList*>& path) const;
    void writePathBwd(const std::vector<ParentList*>& path) const;

    void addEdge(common::relID_t edgeID, bool fwdEdge, common::sel_t pos) const;
    void addNode(common::nodeID_t nodeID, common::sel_t pos) const;

protected:
    PathsOutputWriterInfo info;
    BaseBFSGraph& bfsGraph;

    std::unique_ptr<common::ValueVector> directionVector = nullptr;
    std::unique_ptr<common::ValueVector> lengthVector = nullptr;
    std::unique_ptr<common::ValueVector> pathNodeIDsVector = nullptr;
    std::unique_ptr<common::ValueVector> pathEdgeIDsVector = nullptr;
};

class SPPathsOutputWriter : public PathsOutputWriter {
public:
    SPPathsOutputWriter(main::ClientContext* context, common::NodeOffsetMaskMap* outputNodeMask,
        common::nodeID_t sourceNodeID, PathsOutputWriterInfo info, BaseBFSGraph& bfsGraph)
        : PathsOutputWriter{context, outputNodeMask, sourceNodeID, info, bfsGraph} {}

    void writeInternal(processor::FactorizedTable& fTable, common::nodeID_t dstNodeID,
        common::LimitCounter* counter) override;

    std::unique_ptr<RJOutputWriter> copy() override {
        return std::make_unique<SPPathsOutputWriter>(context, outputNodeMask, sourceNodeID_, info,
            bfsGraph);
    }
};

} // namespace function
} // namespace lbug