lbug 0.21.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

#pragma once

#include "logical_operator_visitor.h"
#include "planner/operator/logical_plan.h"

namespace lbug {
namespace binder {
class Expression;
class NodeExpression;
class RelExpression;
} // namespace binder
namespace main {
class ClientContext;
}

namespace optimizer {

/**
 * This optimizer detects patterns where we're counting all rows from a single rel table
 * without any filters, and replaces the scan + aggregate with a direct count from table metadata.
 * It also rewrites SUM(constant) using the same metadata count.
 *
 * Pattern detected:
 *   AGGREGATE (COUNT_STAR, COUNT(rel), or SUM(literal), no keys) →
 *   PROJECTION (empty or pass-through) →
 *   EXTEND (single rel table) →
 *   SCAN_NODE_TABLE
 *
 * This pattern is replaced with:
 *   COUNT_REL_TABLE (new operator that directly reads the count from table metadata)
 */
class CountRelTableOptimizer : public LogicalOperatorVisitor {
public:
    explicit CountRelTableOptimizer(main::ClientContext* context) : _context{context} {}

    void rewrite(planner::LogicalPlan* plan);

private:
    std::shared_ptr<planner::LogicalOperator> visitOperator(
        const std::shared_ptr<planner::LogicalOperator>& op);

    std::shared_ptr<planner::LogicalOperator> visitAggregateReplace(
        std::shared_ptr<planner::LogicalOperator> op) override;
    std::shared_ptr<planner::LogicalOperator> visitOrderByReplace(
        std::shared_ptr<planner::LogicalOperator> op) override;

    // Rewrite COUNT(*) over a chain of >= 2 extends (a pure path, possibly connected by
    // node-ID hash joins) into a count-only chain operator.
    std::shared_ptr<planner::LogicalOperator> tryRewriteExtendChainCount(
        std::shared_ptr<planner::LogicalOperator> op);

    // Rewrite COUNT(*) over the LSQB-q9 shape: a path n0-R-n1-R-n2-... whose first two hops
    // are BOTH-direction R extends with an anti-edge filter NOT(EXISTS{n0-R-n2}) (+ optional
    // id(n0)<>id(n2)), plus a filter-free suffix chain from n2. Replaced with count arithmetic
    // T - A - S (see CountAntiEdgeChain).
    std::shared_ptr<planner::LogicalOperator> tryRewriteAntiEdgeChainCount(
        std::shared_ptr<planner::LogicalOperator> op);

    // Check if the aggregate is a simple (non-distinct) COUNT with no keys.
    bool isSimpleCount(planner::LogicalOperator* op) const;

    // Check if the aggregate is SUM(non-NULL literal) without DISTINCT or grouping keys.
    // Only safe for rewrites whose output can carry SUM's type and NULL-on-empty semantics
    // (i.e. COUNT_REL_TABLE); must not be treated as a plain row count.
    bool isConstantSum(planner::LogicalOperator* op) const;
    static bool isLiteralOne(const binder::Expression& expression);
    static std::shared_ptr<binder::Expression> getConstantSumChild(planner::LogicalOperator* op);

    bool isCountStar(planner::LogicalOperator* op) const;
    bool isCountRelID(planner::LogicalOperator* op, const binder::RelExpression& rel) const;
    bool isDistinctCountNodeKey(planner::LogicalOperator* op,
        const std::shared_ptr<binder::Expression>& nodeKey) const;
    bool isCountNbr(planner::LogicalOperator* op, const binder::NodeExpression& nbr) const;
    bool isRelIDExpression(const std::shared_ptr<binder::Expression>& expression,
        const binder::RelExpression& rel) const;

    // Check if the plan below aggregate matches the pattern for optimization
    bool canOptimize(planner::LogicalOperator* aggregate) const;
    std::shared_ptr<planner::LogicalOperator> tryRewriteActiveBoundCount(
        std::shared_ptr<planner::LogicalOperator> op);
    std::shared_ptr<planner::LogicalOperator> tryRewriteSortedOffsetCount(
        std::shared_ptr<planner::LogicalOperator> op);
    std::shared_ptr<planner::LogicalOperator> tryRewriteReachableCount(
        std::shared_ptr<planner::LogicalOperator> op);
    std::shared_ptr<planner::LogicalOperator> tryRewriteDegreeTopK(
        std::shared_ptr<planner::LogicalOperator> op);

    [[maybe_unused]] main::ClientContext* _context;
};

} // namespace optimizer
} // namespace lbug