1#include "duckdb/optimizer/cse_optimizer.hpp"
2
3#include "duckdb/planner/expression/common_subexpression.hpp"
4#include "duckdb/planner/expression_iterator.hpp"
5#include "duckdb/planner/operator/logical_filter.hpp"
6#include "duckdb/planner/operator/logical_projection.hpp"
7
8using namespace duckdb;
9using namespace std;
10
11void CommonSubExpressionOptimizer::VisitOperator(LogicalOperator &op) {
12 switch (op.type) {
13 case LogicalOperatorType::FILTER:
14 case LogicalOperatorType::PROJECTION:
15 ExtractCommonSubExpresions(op);
16 break;
17 default:
18 break;
19 }
20 LogicalOperatorVisitor::VisitOperator(op);
21}
22
23void CommonSubExpressionOptimizer::CountExpressions(Expression &expr, expression_map_t<CSENode> &expression_count) {
24 // we only consider expressions with children for CSE elimination
25 switch (expr.expression_class) {
26 case ExpressionClass::BOUND_COLUMN_REF:
27 case ExpressionClass::BOUND_CONSTANT:
28 case ExpressionClass::BOUND_PARAMETER:
29 case ExpressionClass::COMMON_SUBEXPRESSION:
30 return;
31 default:
32 break;
33 }
34 auto node = expression_count.find(&expr);
35 if (node == expression_count.end()) {
36 // first time we encounter this expression, insert this node with [count = 1]
37 expression_count[&expr] = CSENode(1);
38 } else {
39 // we encountered this expression before, increment the occurrence count
40 node->second.count++;
41 }
42 // recursively count the children
43 ExpressionIterator::EnumerateChildren(expr, [&](Expression &child) { CountExpressions(child, expression_count); });
44}
45
46void CommonSubExpressionOptimizer::PerformCSEReplacement(unique_ptr<Expression> *expr_ptr,
47 expression_map_t<CSENode> &expression_count) {
48 Expression &expr = **expr_ptr;
49 switch (expr.expression_class) {
50 case ExpressionClass::BOUND_COLUMN_REF:
51 case ExpressionClass::BOUND_CONSTANT:
52 case ExpressionClass::BOUND_PARAMETER:
53 case ExpressionClass::COMMON_SUBEXPRESSION:
54 return;
55 default:
56 break;
57 }
58 // check if this child is eligible for CSE elimination
59 if (expression_count.find(&expr) == expression_count.end()) {
60 // no occurrence: skip the node
61 return;
62 }
63 auto &node = expression_count[&expr];
64 if (node.count > 1) {
65 // this expression occurs more than once! replace it with a CSE
66 // check if it has already been replaced with a CSE before
67 auto alias = expr.alias.empty() ? expr.GetName() : expr.alias;
68 if (!node.expr) {
69 // the CSE does not exist yet: create the CSE with the ownership of this node
70 node.expr = &expr;
71 *expr_ptr = make_unique<CommonSubExpression>(move(*expr_ptr), alias);
72 } else {
73 // the CSE already exists: create a CSE referring to the existing node
74 *expr_ptr = make_unique<CommonSubExpression>(node.expr, alias);
75 }
76 return;
77 }
78 // this expression only occurs once, we can't perform CSE elimination
79 // look into the children to see if we can replace them
80 ExpressionIterator::EnumerateChildren(expr, [&](unique_ptr<Expression> child) -> unique_ptr<Expression> {
81 PerformCSEReplacement(&child, expression_count);
82 return move(child);
83 });
84}
85
86void CommonSubExpressionOptimizer::ExtractCommonSubExpresions(LogicalOperator &op) {
87 // first we count for each expression with children how many types it occurs
88 expression_map_t<CSENode> expression_count;
89 for (auto &expr : op.expressions) {
90 CountExpressions(*expr, expression_count);
91 }
92 // now we iterate over all the expressions and perform the actual CSE elimination
93 for (idx_t i = 0; i < op.expressions.size(); i++) {
94 PerformCSEReplacement(&op.expressions[i], expression_count);
95 }
96}
97