1#include "duckdb/optimizer/optimizer.hpp"
2
3#include "duckdb/execution/column_binding_resolver.hpp"
4#include "duckdb/execution/expression_executor.hpp"
5#include "duckdb/main/client_context.hpp"
6#include "duckdb/main/config.hpp"
7#include "duckdb/main/query_profiler.hpp"
8#include "duckdb/optimizer/column_lifetime_optimizer.hpp"
9#include "duckdb/optimizer/common_aggregate_optimizer.hpp"
10#include "duckdb/optimizer/cse_optimizer.hpp"
11#include "duckdb/optimizer/deliminator.hpp"
12#include "duckdb/optimizer/unnest_rewriter.hpp"
13#include "duckdb/optimizer/expression_heuristics.hpp"
14#include "duckdb/optimizer/filter_pullup.hpp"
15#include "duckdb/optimizer/filter_pushdown.hpp"
16#include "duckdb/optimizer/in_clause_rewriter.hpp"
17#include "duckdb/optimizer/join_order/join_order_optimizer.hpp"
18#include "duckdb/optimizer/regex_range_filter.hpp"
19#include "duckdb/optimizer/remove_unused_columns.hpp"
20#include "duckdb/optimizer/rule/equal_or_null_simplification.hpp"
21#include "duckdb/optimizer/rule/in_clause_simplification.hpp"
22#include "duckdb/optimizer/rule/list.hpp"
23#include "duckdb/optimizer/statistics_propagator.hpp"
24#include "duckdb/optimizer/topn_optimizer.hpp"
25#include "duckdb/planner/binder.hpp"
26#include "duckdb/planner/planner.hpp"
27
28namespace duckdb {
29
30Optimizer::Optimizer(Binder &binder, ClientContext &context) : context(context), binder(binder), rewriter(context) {
31 rewriter.rules.push_back(x: make_uniq<ConstantFoldingRule>(args&: rewriter));
32 rewriter.rules.push_back(x: make_uniq<DistributivityRule>(args&: rewriter));
33 rewriter.rules.push_back(x: make_uniq<ArithmeticSimplificationRule>(args&: rewriter));
34 rewriter.rules.push_back(x: make_uniq<CaseSimplificationRule>(args&: rewriter));
35 rewriter.rules.push_back(x: make_uniq<ConjunctionSimplificationRule>(args&: rewriter));
36 rewriter.rules.push_back(x: make_uniq<DatePartSimplificationRule>(args&: rewriter));
37 rewriter.rules.push_back(x: make_uniq<ComparisonSimplificationRule>(args&: rewriter));
38 rewriter.rules.push_back(x: make_uniq<InClauseSimplificationRule>(args&: rewriter));
39 rewriter.rules.push_back(x: make_uniq<EqualOrNullSimplification>(args&: rewriter));
40 rewriter.rules.push_back(x: make_uniq<MoveConstantsRule>(args&: rewriter));
41 rewriter.rules.push_back(x: make_uniq<LikeOptimizationRule>(args&: rewriter));
42 rewriter.rules.push_back(x: make_uniq<OrderedAggregateOptimizer>(args&: rewriter));
43 rewriter.rules.push_back(x: make_uniq<RegexOptimizationRule>(args&: rewriter));
44 rewriter.rules.push_back(x: make_uniq<EmptyNeedleRemovalRule>(args&: rewriter));
45 rewriter.rules.push_back(x: make_uniq<EnumComparisonRule>(args&: rewriter));
46
47#ifdef DEBUG
48 for (auto &rule : rewriter.rules) {
49 // root not defined in rule
50 D_ASSERT(rule->root);
51 }
52#endif
53}
54
55void Optimizer::RunOptimizer(OptimizerType type, const std::function<void()> &callback) {
56 auto &config = DBConfig::GetConfig(context);
57 if (config.options.disabled_optimizers.find(x: type) != config.options.disabled_optimizers.end()) {
58 // optimizer is marked as disabled: skip
59 return;
60 }
61 auto &profiler = QueryProfiler::Get(context);
62 profiler.StartPhase(phase: OptimizerTypeToString(type));
63 callback();
64 profiler.EndPhase();
65 if (plan) {
66 Verify(op&: *plan);
67 }
68}
69
70void Optimizer::Verify(LogicalOperator &op) {
71 ColumnBindingResolver::Verify(op);
72}
73
74unique_ptr<LogicalOperator> Optimizer::Optimize(unique_ptr<LogicalOperator> plan_p) {
75 Verify(op&: *plan_p);
76 this->plan = std::move(plan_p);
77 // first we perform expression rewrites using the ExpressionRewriter
78 // this does not change the logical plan structure, but only simplifies the expression trees
79 RunOptimizer(type: OptimizerType::EXPRESSION_REWRITER, callback: [&]() { rewriter.VisitOperator(op&: *plan); });
80
81 // perform filter pullup
82 RunOptimizer(type: OptimizerType::FILTER_PULLUP, callback: [&]() {
83 FilterPullup filter_pullup;
84 plan = filter_pullup.Rewrite(op: std::move(plan));
85 });
86
87 // perform filter pushdown
88 RunOptimizer(type: OptimizerType::FILTER_PUSHDOWN, callback: [&]() {
89 FilterPushdown filter_pushdown(*this);
90 plan = filter_pushdown.Rewrite(op: std::move(plan));
91 });
92
93 RunOptimizer(type: OptimizerType::REGEX_RANGE, callback: [&]() {
94 RegexRangeFilter regex_opt;
95 plan = regex_opt.Rewrite(op: std::move(plan));
96 });
97
98 RunOptimizer(type: OptimizerType::IN_CLAUSE, callback: [&]() {
99 InClauseRewriter rewriter(context, *this);
100 plan = rewriter.Rewrite(op: std::move(plan));
101 });
102
103 // then we perform the join ordering optimization
104 // this also rewrites cross products + filters into joins and performs filter pushdowns
105 RunOptimizer(type: OptimizerType::JOIN_ORDER, callback: [&]() {
106 JoinOrderOptimizer optimizer(context);
107 plan = optimizer.Optimize(plan: std::move(plan));
108 });
109
110 // removes any redundant DelimGets/DelimJoins
111 RunOptimizer(type: OptimizerType::DELIMINATOR, callback: [&]() {
112 Deliminator deliminator(context);
113 plan = deliminator.Optimize(op: std::move(plan));
114 });
115
116 // rewrites UNNESTs in DelimJoins by moving them to the projection
117 RunOptimizer(type: OptimizerType::UNNEST_REWRITER, callback: [&]() {
118 UnnestRewriter unnest_rewriter;
119 plan = unnest_rewriter.Optimize(op: std::move(plan));
120 });
121
122 // removes unused columns
123 RunOptimizer(type: OptimizerType::UNUSED_COLUMNS, callback: [&]() {
124 RemoveUnusedColumns unused(binder, context, true);
125 unused.VisitOperator(op&: *plan);
126 });
127
128 // perform statistics propagation
129 RunOptimizer(type: OptimizerType::STATISTICS_PROPAGATION, callback: [&]() {
130 StatisticsPropagator propagator(context);
131 propagator.PropagateStatistics(node_ptr&: plan);
132 });
133
134 // then we extract common subexpressions inside the different operators
135 RunOptimizer(type: OptimizerType::COMMON_SUBEXPRESSIONS, callback: [&]() {
136 CommonSubExpressionOptimizer cse_optimizer(binder);
137 cse_optimizer.VisitOperator(op&: *plan);
138 });
139
140 RunOptimizer(type: OptimizerType::COMMON_AGGREGATE, callback: [&]() {
141 CommonAggregateOptimizer common_aggregate;
142 common_aggregate.VisitOperator(op&: *plan);
143 });
144
145 RunOptimizer(type: OptimizerType::COLUMN_LIFETIME, callback: [&]() {
146 ColumnLifetimeAnalyzer column_lifetime(true);
147 column_lifetime.VisitOperator(op&: *plan);
148 });
149
150 // transform ORDER BY + LIMIT to TopN
151 RunOptimizer(type: OptimizerType::TOP_N, callback: [&]() {
152 TopN topn;
153 plan = topn.Optimize(op: std::move(plan));
154 });
155
156 // apply simple expression heuristics to get an initial reordering
157 RunOptimizer(type: OptimizerType::REORDER_FILTER, callback: [&]() {
158 ExpressionHeuristics expression_heuristics(*this);
159 plan = expression_heuristics.Rewrite(op: std::move(plan));
160 });
161
162 for (auto &optimizer_extension : DBConfig::GetConfig(context).optimizer_extensions) {
163 RunOptimizer(type: OptimizerType::EXTENSION, callback: [&]() {
164 optimizer_extension.optimize_function(context, optimizer_extension.optimizer_info.get(), plan);
165 });
166 }
167
168 Planner::VerifyPlan(context, op&: plan);
169
170 return std::move(plan);
171}
172
173} // namespace duckdb
174