1#include "duckdb/optimizer/optimizer.hpp"
2
3#include "duckdb/execution/expression_executor.hpp"
4#include "duckdb/main/client_context.hpp"
5#include "duckdb/optimizer/column_lifetime_optimizer.hpp"
6#include "duckdb/optimizer/cse_optimizer.hpp"
7#include "duckdb/optimizer/expression_heuristics.hpp"
8#include "duckdb/optimizer/filter_pushdown.hpp"
9#include "duckdb/optimizer/in_clause_rewriter.hpp"
10#include "duckdb/optimizer/index_scan.hpp"
11#include "duckdb/optimizer/join_order_optimizer.hpp"
12#include "duckdb/optimizer/regex_range_filter.hpp"
13#include "duckdb/optimizer/remove_unused_columns.hpp"
14#include "duckdb/optimizer/rule/list.hpp"
15#include "duckdb/optimizer/topn_optimizer.hpp"
16#include "duckdb/planner/binder.hpp"
17
18using namespace duckdb;
19using namespace std;
20
21Optimizer::Optimizer(Binder &binder, ClientContext &context) : context(context), binder(binder), rewriter(context) {
22 rewriter.rules.push_back(make_unique<ConstantFoldingRule>(rewriter));
23 rewriter.rules.push_back(make_unique<DistributivityRule>(rewriter));
24 rewriter.rules.push_back(make_unique<ArithmeticSimplificationRule>(rewriter));
25 rewriter.rules.push_back(make_unique<CaseSimplificationRule>(rewriter));
26 rewriter.rules.push_back(make_unique<ConjunctionSimplificationRule>(rewriter));
27 rewriter.rules.push_back(make_unique<DatePartSimplificationRule>(rewriter));
28 rewriter.rules.push_back(make_unique<ComparisonSimplificationRule>(rewriter));
29 rewriter.rules.push_back(make_unique<MoveConstantsRule>(rewriter));
30 rewriter.rules.push_back(make_unique<LikeOptimizationRule>(rewriter));
31 rewriter.rules.push_back(make_unique<EmptyNeedleRemovalRule>(rewriter));
32
33#ifdef DEBUG
34 for (auto &rule : rewriter.rules) {
35 // root not defined in rule
36 assert(rule->root);
37 }
38#endif
39}
40
41unique_ptr<LogicalOperator> Optimizer::Optimize(unique_ptr<LogicalOperator> plan) {
42 // first we perform expression rewrites using the ExpressionRewriter
43 // this does not change the logical plan structure, but only simplifies the expression trees
44 context.profiler.StartPhase("expression_rewriter");
45 rewriter.Apply(*plan);
46 context.profiler.EndPhase();
47
48 // perform filter pushdown
49 context.profiler.StartPhase("filter_pushdown");
50 FilterPushdown filter_pushdown(*this);
51 plan = filter_pushdown.Rewrite(move(plan));
52 context.profiler.EndPhase();
53
54 // check if filters match with existing indexes, if true transforms filters to index scans
55 context.profiler.StartPhase("index_scan");
56 IndexScan index_scan;
57 plan = index_scan.Optimize(move(plan));
58 context.profiler.EndPhase();
59
60 context.profiler.StartPhase("regex_range");
61 RegexRangeFilter regex_opt;
62 plan = regex_opt.Rewrite(move(plan));
63 context.profiler.EndPhase();
64
65 context.profiler.StartPhase("in_clause");
66 InClauseRewriter rewriter(*this);
67 plan = rewriter.Rewrite(move(plan));
68 context.profiler.EndPhase();
69
70 // then we perform the join ordering optimization
71 // this also rewrites cross products + filters into joins and performs filter pushdowns
72 context.profiler.StartPhase("join_order");
73 JoinOrderOptimizer optimizer;
74 plan = optimizer.Optimize(move(plan));
75 context.profiler.EndPhase();
76
77 // then we extract common subexpressions inside the different operators
78 // context.profiler.StartPhase("common_subexpressions");
79 // CommonSubExpressionOptimizer cse_optimizer;
80 // cse_optimizer.VisitOperator(*plan);
81 // context.profiler.EndPhase();
82
83 context.profiler.StartPhase("unused_columns");
84 RemoveUnusedColumns unused(true);
85 unused.VisitOperator(*plan);
86 context.profiler.EndPhase();
87
88 context.profiler.StartPhase("column_lifetime");
89 ColumnLifetimeAnalyzer column_lifetime(true);
90 column_lifetime.VisitOperator(*plan);
91 context.profiler.EndPhase();
92
93 // transform ORDER BY + LIMIT to TopN
94 context.profiler.StartPhase("top_n");
95 TopN topn;
96 plan = topn.Optimize(move(plan));
97 context.profiler.EndPhase();
98
99 // apply simple expression heuristics to get an initial reordering
100 context.profiler.StartPhase("reorder_filter_expressions");
101 ExpressionHeuristics expression_heuristics(*this);
102 plan = expression_heuristics.Rewrite(move(plan));
103 context.profiler.EndPhase();
104
105 return plan;
106}
107