lbug 0.22.0

An in-process property graph database management system built for query speed and scalability
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

#pragma once

#include <algorithm>

#include "common/assert.h"
#include "common/types/types.h"

namespace lbug {
namespace processor {

namespace intersect_kernels_detail {

constexpr common::sel_t MIN_GALLOPING_RIGHT_COUNT = 64;
constexpr common::sel_t MIN_GALLOPING_SIZE_RATIO = 8;

inline bool isHomogeneous(const common::nodeID_t* values, common::sel_t count) {
    return count != 0 && values[0].tableID == values[count - 1].tableID;
}

inline common::sel_t lowerBoundOffset(const common::nodeID_t* values, common::sel_t begin,
    common::sel_t end, common::offset_t target) {
    while (begin < end) {
        const auto middle = begin + (end - begin) / 2;
        if (values[middle].offset < target) {
            begin = middle + 1;
        } else {
            end = middle;
        }
    }
    return begin;
}

// Branchless lower bound over offsets, in the style of CRoaring's binarySearch: the caller
// advances the base monotonically, so every probe searches a shrinking suffix. Unlike galloping
// there is no exponential probing phase; each left element pays a full binary search.
inline common::sel_t lowerBoundOffsetBranchless(const common::nodeID_t* values, common::sel_t count,
    common::offset_t target) {
    const auto* base = values;
    auto n = count;
    while (n > 1) {
        const auto half = n >> 1;
        base = (base[half].offset < target) ? &base[half] : base;
        n -= half;
    }
    if (n == 0) {
        return 0;
    }
    return static_cast<common::sel_t>((base[0].offset < target) + (base - values));
}

// CRoaring-style skewed intersection (cf. intersect_skewed_uint16): one branchless binary search
// per left element over the remaining right suffix. Same output contract as the galloping path:
// matches are compacted into left[] and both sides' positions are recorded.
inline common::sel_t intersectSameTableBatchedSearch(common::nodeID_t* left,
    common::sel_t leftCount, const common::nodeID_t* right, common::sel_t rightCount,
    common::sel_t* leftPositions, common::sel_t* rightPositions) {
    common::sel_t rightPosition = 0;
    common::sel_t outputPosition = 0;
    for (common::sel_t leftPosition = 0; leftPosition < leftCount; ++leftPosition) {
        const auto leftNodeID = left[leftPosition];
        rightPosition += lowerBoundOffsetBranchless(right + rightPosition,
            rightCount - rightPosition, leftNodeID.offset);
        if (rightPosition == rightCount) {
            break;
        }
        if (right[rightPosition].offset == leftNodeID.offset) {
            leftPositions[outputPosition] = leftPosition;
            rightPositions[outputPosition] = rightPosition;
            left[outputPosition++] = leftNodeID;
            ++rightPosition;
        }
    }
    return outputPosition;
}

inline common::sel_t intersectSameTableGalloping(common::nodeID_t* left, common::sel_t leftCount,
    const common::nodeID_t* right, common::sel_t rightCount, common::sel_t* leftPositions,
    common::sel_t* rightPositions) {
    common::sel_t leftPosition = 0;
    common::sel_t rightPosition = 0;
    common::sel_t outputPosition = 0;
    while (leftPosition < leftCount && rightPosition < rightCount) {
        const auto leftNodeID = left[leftPosition];
        const auto target = leftNodeID.offset;
        if (right[rightPosition].offset < target) {
            common::sel_t step = 1;
            const auto remaining = rightCount - rightPosition;
            while (step < remaining && right[rightPosition + step].offset < target) {
                step = step > remaining - step ? remaining : step + step;
            }
            const auto begin = std::min(rightPosition + (step >> 1) + 1, rightCount);
            const auto end = std::min(rightPosition + step + 1, rightCount);
            rightPosition = lowerBoundOffset(right, begin, end, target);
            if (rightPosition == rightCount) {
                break;
            }
        }
        if (right[rightPosition].offset == target) {
            leftPositions[outputPosition] = leftPosition;
            rightPositions[outputPosition] = rightPosition;
            left[outputPosition++] = leftNodeID;
            ++rightPosition;
        }
        ++leftPosition;
    }
    return outputPosition;
}

} // namespace intersect_kernels_detail

// Reference merge used for mixed-table lists, balanced lists, and differential tests.
inline common::sel_t intersectNodeIDsScalar(common::nodeID_t* left, common::sel_t leftCount,
    const common::nodeID_t* right, common::sel_t rightCount, common::sel_t* leftPositions,
    common::sel_t* rightPositions) {
    common::sel_t leftPosition = 0;
    common::sel_t rightPosition = 0;
    common::sel_t outputPosition = 0;
    while (leftPosition < leftCount && rightPosition < rightCount) {
        const auto leftNodeID = left[leftPosition];
        const auto rightNodeID = right[rightPosition];
        if (leftNodeID < rightNodeID) {
            ++leftPosition;
        } else if (leftNodeID > rightNodeID) {
            ++rightPosition;
        } else {
            leftPositions[outputPosition] = leftPosition;
            rightPositions[outputPosition] = rightPosition;
            left[outputPosition++] = leftNodeID;
            ++leftPosition;
            ++rightPosition;
        }
    }
    return outputPosition;
}

// Same gating as intersectNodeIDs but uses the CRoaring-style batched binary search for the
// same-table fast path. Exists for differential testing and benchmarking against galloping.
inline common::sel_t intersectNodeIDsBatched(common::nodeID_t* left, common::sel_t leftCount,
    const common::nodeID_t* right, common::sel_t rightCount, common::sel_t* leftPositions,
    common::sel_t* rightPositions) {
    DASSERT(leftCount <= rightCount);
    using namespace intersect_kernels_detail;
    if (leftCount == 0 || rightCount < MIN_GALLOPING_RIGHT_COUNT ||
        rightCount / leftCount < MIN_GALLOPING_SIZE_RATIO || !isHomogeneous(left, leftCount) ||
        !isHomogeneous(right, rightCount) || left[0].tableID != right[0].tableID) {
        return intersectNodeIDsScalar(left, leftCount, right, rightCount, leftPositions,
            rightPositions);
    }
    return intersectSameTableBatchedSearch(left, leftCount, right, rightCount, leftPositions,
        rightPositions);
}

// Selects the skew-aware same-table fast path when it is profitable and otherwise uses the
// reference merge. Both inputs must be sorted by nodeID_t's lexicographic ordering, and leftCount
// must be less than or equal to rightCount.
inline common::sel_t intersectNodeIDs(common::nodeID_t* left, common::sel_t leftCount,
    const common::nodeID_t* right, common::sel_t rightCount, common::sel_t* leftPositions,
    common::sel_t* rightPositions) {
    DASSERT(leftCount <= rightCount);
    using namespace intersect_kernels_detail;
    if (leftCount == 0 || rightCount < MIN_GALLOPING_RIGHT_COUNT ||
        rightCount / leftCount < MIN_GALLOPING_SIZE_RATIO || !isHomogeneous(left, leftCount) ||
        !isHomogeneous(right, rightCount) || left[0].tableID != right[0].tableID) {
        return intersectNodeIDsScalar(left, leftCount, right, rightCount, leftPositions,
            rightPositions);
    }
    return intersectSameTableGalloping(left, leftCount, right, rightCount, leftPositions,
        rightPositions);
}

} // namespace processor
} // namespace lbug