ClickHouse

1
#include <Common/Exception.h>
2
#include <Processors/QueryPlan/ReadFromMergeTree.h>
3
#include <Processors/QueryPlan/MergingAggregatedStep.h>
4
#include <Processors/QueryPlan/Optimizations/Optimizations.h>
5
#include <Processors/QueryPlan/Optimizations/QueryPlanOptimizationSettings.h>
6
#include <Processors/QueryPlan/UnionStep.h>
7

8
#include <stack>
9

10
namespace DB
11
{
12

13
namespace ErrorCodes
14
{
15
    extern const int TOO_MANY_QUERY_PLAN_OPTIMIZATIONS;
16
    extern const int PROJECTION_NOT_USED;
17
}
18

19
namespace QueryPlanOptimizations
20
{
21

22
void optimizeTreeFirstPass(const QueryPlanOptimizationSettings & settings, QueryPlan::Node & root, QueryPlan::Nodes & nodes)
23
{
24
    if (!settings.optimize_plan)
25
        return;
26

27
    const auto & optimizations = getOptimizations();
28

29
    struct Frame
30
    {
31
        QueryPlan::Node * node = nullptr;
32

33
        /// If not zero, traverse only depth_limit layers of tree (if no other optimizations happen).
34
        /// Otherwise, traverse all children.
35
        size_t depth_limit = 0;
36

37
        /// Next child to process.
38
        size_t next_child = 0;
39
    };
40

41
    std::stack<Frame> stack;
42
    stack.push({.node = &root});
43

44
    const size_t max_optimizations_to_apply = settings.max_optimizations_to_apply;
45
    size_t total_applied_optimizations = 0;
46

47
    while (!stack.empty())
48
    {
49
        auto & frame = stack.top();
50

51
        /// If traverse_depth_limit == 0, then traverse without limit (first entrance)
52
        /// If traverse_depth_limit > 1, then traverse with (limit - 1)
53
        if (frame.depth_limit != 1)
54
        {
55
            /// Traverse all children first.
56
            if (frame.next_child < frame.node->children.size())
57
            {
58
                stack.push(
59
                {
60
                    .node = frame.node->children[frame.next_child],
61
                    .depth_limit = frame.depth_limit ? (frame.depth_limit - 1) : 0,
62
                });
63

64
                ++frame.next_child;
65
                continue;
66
            }
67
        }
68

69
        size_t max_update_depth = 0;
70

71
        /// Apply all optimizations.
72
        for (const auto & optimization : optimizations)
73
        {
74
            if (!(settings.*(optimization.is_enabled)))
75
                continue;
76

77
            /// Just in case, skip optimization if it is not initialized.
78
            if (!optimization.apply)
79
                continue;
80

81
            if (max_optimizations_to_apply && max_optimizations_to_apply < total_applied_optimizations)
82
                throw Exception(ErrorCodes::TOO_MANY_QUERY_PLAN_OPTIMIZATIONS,
83
                                "Too many optimizations applied to query plan. Current limit {}",
84
                                max_optimizations_to_apply);
85

86
            /// Try to apply optimization.
87
            auto update_depth = optimization.apply(frame.node, nodes);
88
            if (update_depth)
89
                ++total_applied_optimizations;
90
            max_update_depth = std::max<size_t>(max_update_depth, update_depth);
91
        }
92

93
        /// Traverse `max_update_depth` layers of tree again.
94
        if (max_update_depth)
95
        {
96
            frame.depth_limit = max_update_depth;
97
            frame.next_child = 0;
98
            continue;
99
        }
100

101
        /// Nothing was applied.
102
        stack.pop();
103
    }
104
}
105

106
void optimizeTreeSecondPass(const QueryPlanOptimizationSettings & optimization_settings, QueryPlan::Node & root, QueryPlan::Nodes & nodes)
107
{
108
    const size_t max_optimizations_to_apply = optimization_settings.max_optimizations_to_apply;
109
    size_t num_applied_projection = 0;
110
    bool has_reading_from_mt = false;
111

112
    Stack stack;
113
    stack.push_back({.node = &root});
114

115
    while (!stack.empty())
116
    {
117
        optimizePrimaryKeyCondition(stack);
118

119
        /// NOTE: optimizePrewhere can modify the stack.
120
        /// Prewhere optimization relies on PK optimization (getConditionEstimatorByPredicate)
121
        if (optimization_settings.optimize_prewhere)
122
            optimizePrewhere(stack, nodes);
123

124
        auto & frame = stack.back();
125

126
        if (frame.next_child == 0)
127
        {
128

129
            if (optimization_settings.read_in_order)
130
                optimizeReadInOrder(*frame.node, nodes);
131

132
            if (optimization_settings.distinct_in_order)
133
                tryDistinctReadInOrder(frame.node);
134
        }
135

136
        /// Traverse all children first.
137
        if (frame.next_child < frame.node->children.size())
138
        {
139
            auto next_frame = Frame{.node = frame.node->children[frame.next_child]};
140
            ++frame.next_child;
141
            stack.push_back(next_frame);
142
            continue;
143
        }
144

145
        stack.pop_back();
146
    }
147

148
    stack.push_back({.node = &root});
149

150
    while (!stack.empty())
151
    {
152
        {
153
            /// NOTE: frame cannot be safely used after stack was modified.
154
            auto & frame = stack.back();
155

156
            if (frame.next_child == 0)
157
            {
158
                has_reading_from_mt |= typeid_cast<const ReadFromMergeTree *>(frame.node->step.get()) != nullptr;
159

160
                /// Projection optimization relies on PK optimization
161
                if (optimization_settings.optimize_projection)
162
                    num_applied_projection
163
                        += optimizeUseAggregateProjections(*frame.node, nodes, optimization_settings.optimize_use_implicit_projections);
164

165

166
                if (optimization_settings.aggregation_in_order)
167
                    optimizeAggregationInOrder(*frame.node, nodes);
168
            }
169

170
            /// Traverse all children first.
171
            if (frame.next_child < frame.node->children.size())
172
            {
173
                auto next_frame = Frame{.node = frame.node->children[frame.next_child]};
174
                ++frame.next_child;
175
                stack.push_back(next_frame);
176
                continue;
177
            }
178
        }
179

180
        if (optimization_settings.optimize_projection)
181
        {
182
            /// Projection optimization relies on PK optimization
183
            if (optimizeUseNormalProjections(stack, nodes))
184
            {
185
                ++num_applied_projection;
186

187
                if (max_optimizations_to_apply && max_optimizations_to_apply < num_applied_projection)
188
                    throw Exception(ErrorCodes::TOO_MANY_QUERY_PLAN_OPTIMIZATIONS,
189
                                    "Too many projection optimizations applied to query plan. Current limit {}",
190
                                    max_optimizations_to_apply);
191

192
                /// Stack is updated after this optimization and frame is not valid anymore.
193
                /// Try to apply optimizations again to newly added plan steps.
194
                --stack.back().next_child;
195
                continue;
196
            }
197
        }
198

199
        enableMemoryBoundMerging(*stack.back().node, nodes);
200

201
        stack.pop_back();
202
    }
203

204
    if (optimization_settings.force_use_projection && has_reading_from_mt && num_applied_projection == 0)
205
        throw Exception(
206
            ErrorCodes::PROJECTION_NOT_USED,
207
            "No projection is used when optimize_use_projections = 1 and force_optimize_projection = 1");
208
}
209

210
void optimizeTreeThirdPass(QueryPlan & plan, QueryPlan::Node & root, QueryPlan::Nodes & nodes)
211
{
212
    Stack stack;
213
    stack.push_back({.node = &root});
214

215
    while (!stack.empty())
216
    {
217
        /// NOTE: frame cannot be safely used after stack was modified.
218
        auto & frame = stack.back();
219

220
        /// Traverse all children first.
221
        if (frame.next_child < frame.node->children.size())
222
        {
223
            auto next_frame = Frame{.node = frame.node->children[frame.next_child]};
224
            ++frame.next_child;
225
            stack.push_back(next_frame);
226
            continue;
227
        }
228

229
        addPlansForSets(plan, *frame.node, nodes);
230

231
        stack.pop_back();
232
    }
233
}
234

235
}
236
}
237