1#include "duckdb/planner/expression/bound_columnref_expression.hpp"
2#include "duckdb/planner/expression/bound_comparison_expression.hpp"
3#include "duckdb/planner/expression/bound_conjunction_expression.hpp"
4#include "duckdb/planner/expression/bound_constant_expression.hpp"
5#include "duckdb/planner/expression/bound_operator_expression.hpp"
6#include "duckdb/planner/expression/bound_subquery_expression.hpp"
7#include "duckdb/planner/expression_iterator.hpp"
8#include "duckdb/planner/binder.hpp"
9#include "duckdb/planner/operator/logical_any_join.hpp"
10#include "duckdb/planner/operator/logical_comparison_join.hpp"
11#include "duckdb/planner/operator/logical_cross_product.hpp"
12#include "duckdb/planner/operator/logical_filter.hpp"
13#include "duckdb/planner/tableref/bound_joinref.hpp"
14
15using namespace duckdb;
16using namespace std;
17
18//! Create a JoinCondition from a comparison
19static bool CreateJoinCondition(Expression &expr, unordered_set<idx_t> &left_bindings,
20 unordered_set<idx_t> &right_bindings, vector<JoinCondition> &conditions) {
21 // comparison
22 auto &comparison = (BoundComparisonExpression &)expr;
23 auto left_side = JoinSide::GetJoinSide(*comparison.left, left_bindings, right_bindings);
24 auto right_side = JoinSide::GetJoinSide(*comparison.right, left_bindings, right_bindings);
25 if (left_side != JoinSide::BOTH && right_side != JoinSide::BOTH) {
26 // join condition can be divided in a left/right side
27 JoinCondition condition;
28 condition.comparison = expr.type;
29 auto left = move(comparison.left);
30 auto right = move(comparison.right);
31 if (left_side == JoinSide::RIGHT) {
32 // left = right, right = left, flip the comparison symbol and reverse sides
33 swap(left, right);
34 condition.comparison = FlipComparisionExpression(expr.type);
35 }
36 condition.left = move(left);
37 condition.right = move(right);
38 conditions.push_back(move(condition));
39 return true;
40 }
41 return false;
42}
43
44unique_ptr<LogicalOperator> LogicalComparisonJoin::CreateJoin(JoinType type, unique_ptr<LogicalOperator> left_child,
45 unique_ptr<LogicalOperator> right_child,
46 unordered_set<idx_t> &left_bindings,
47 unordered_set<idx_t> &right_bindings,
48 vector<unique_ptr<Expression>> &expressions) {
49 vector<JoinCondition> conditions;
50 vector<unique_ptr<Expression>> arbitrary_expressions;
51 // first check if we can create
52 for (idx_t i = 0; i < expressions.size(); i++) {
53 auto &expr = expressions[i];
54 auto total_side = JoinSide::GetJoinSide(*expr, left_bindings, right_bindings);
55 if (total_side != JoinSide::BOTH) {
56 // join condition does not reference both sides, add it as filter under the join
57 if (type == JoinType::LEFT && total_side == JoinSide::RIGHT) {
58 // filter is on RHS and the join is a LEFT OUTER join, we can push it in the right child
59 if (right_child->type != LogicalOperatorType::FILTER) {
60 // not a filter yet, push a new empty filter
61 auto filter = make_unique<LogicalFilter>();
62 filter->AddChild(move(right_child));
63 right_child = move(filter);
64 }
65 // push the expression into the filter
66 auto &filter = (LogicalFilter &)*right_child;
67 filter.expressions.push_back(move(expr));
68 continue;
69 }
70 } else if (expr->type >= ExpressionType::COMPARE_EQUAL &&
71 expr->type <= ExpressionType::COMPARE_GREATERTHANOREQUALTO) {
72 // comparison, check if we can create a comparison JoinCondition
73 if (CreateJoinCondition(*expr, left_bindings, right_bindings, conditions)) {
74 // successfully created the join condition
75 continue;
76 }
77 }
78 arbitrary_expressions.push_back(move(expr));
79 }
80 if (conditions.size() > 0) {
81 // we successfully convertedexpressions into JoinConditions
82 // create a LogicalComparisonJoin
83 auto comp_join = make_unique<LogicalComparisonJoin>(type);
84 comp_join->conditions = move(conditions);
85 comp_join->children.push_back(move(left_child));
86 comp_join->children.push_back(move(right_child));
87 if (arbitrary_expressions.size() > 0) {
88 // we have some arbitrary expressions as well
89 // add them to a filter
90 auto filter = make_unique<LogicalFilter>();
91 for (auto &expr : arbitrary_expressions) {
92 filter->expressions.push_back(move(expr));
93 }
94 LogicalFilter::SplitPredicates(filter->expressions);
95 filter->children.push_back(move(comp_join));
96 return move(filter);
97 }
98 return move(comp_join);
99 } else {
100 if (arbitrary_expressions.size() == 0) {
101 // all conditions were pushed down, add TRUE predicate
102 arbitrary_expressions.push_back(make_unique<BoundConstantExpression>(Value::BOOLEAN(true)));
103 }
104 // if we get here we could not create any JoinConditions
105 // turn this into an arbitrary expression join
106 auto any_join = make_unique<LogicalAnyJoin>(type);
107 // create the condition
108 any_join->children.push_back(move(left_child));
109 any_join->children.push_back(move(right_child));
110 // AND all the arbitrary expressions together
111 // do the same with any remaining conditions
112 any_join->condition = move(arbitrary_expressions[0]);
113 for (idx_t i = 1; i < arbitrary_expressions.size(); i++) {
114 any_join->condition = make_unique<BoundConjunctionExpression>(
115 ExpressionType::CONJUNCTION_AND, move(any_join->condition), move(arbitrary_expressions[i]));
116 }
117 return move(any_join);
118 }
119}
120
121unique_ptr<LogicalOperator> Binder::CreatePlan(BoundJoinRef &ref) {
122 auto left = CreatePlan(*ref.left);
123 auto right = CreatePlan(*ref.right);
124 if (ref.type == JoinType::RIGHT) {
125 ref.type = JoinType::LEFT;
126 std::swap(left, right);
127 }
128
129 if (ref.type == JoinType::INNER) {
130 // inner join, generate a cross product + filter
131 // this will be later turned into a proper join by the join order optimizer
132 auto cross_product = make_unique<LogicalCrossProduct>();
133
134 cross_product->AddChild(move(left));
135 cross_product->AddChild(move(right));
136
137 unique_ptr<LogicalOperator> root = move(cross_product);
138
139 auto filter = make_unique<LogicalFilter>(move(ref.condition));
140 // visit the expressions in the filter
141 for (idx_t i = 0; i < filter->expressions.size(); i++) {
142 PlanSubqueries(&filter->expressions[i], &root);
143 }
144 filter->AddChild(move(root));
145 return move(filter);
146 }
147
148 // split the expressions by the AND clause
149 vector<unique_ptr<Expression>> expressions;
150 expressions.push_back(move(ref.condition));
151 LogicalFilter::SplitPredicates(expressions);
152
153 // find the table bindings on the LHS and RHS of the join
154 unordered_set<idx_t> left_bindings, right_bindings;
155 LogicalJoin::GetTableReferences(*left, left_bindings);
156 LogicalJoin::GetTableReferences(*right, right_bindings);
157 // now create the join operator from the set of join conditions
158 auto result = LogicalComparisonJoin::CreateJoin(ref.type, move(left), move(right), left_bindings, right_bindings,
159 expressions);
160
161 LogicalOperator *join;
162 if (result->type == LogicalOperatorType::FILTER) {
163 join = result->children[0].get();
164 } else {
165 join = result.get();
166 }
167
168 // we visit the expressions depending on the type of join
169 if (join->type == LogicalOperatorType::COMPARISON_JOIN) {
170 // comparison join
171 // in this join we visit the expressions on the LHS with the LHS as root node
172 // and the expressions on the RHS with the RHS as root node
173 auto &comp_join = (LogicalComparisonJoin &)*join;
174 for (idx_t i = 0; i < comp_join.conditions.size(); i++) {
175 PlanSubqueries(&comp_join.conditions[i].left, &comp_join.children[0]);
176 PlanSubqueries(&comp_join.conditions[i].right, &comp_join.children[1]);
177 }
178 } else if (join->type == LogicalOperatorType::ANY_JOIN) {
179 auto &any_join = (LogicalAnyJoin &)*join;
180 // for the any join we just visit the condition
181 if (any_join.condition->HasSubquery()) {
182 throw NotImplementedException("Cannot perform non-inner join on subquery!");
183 }
184 }
185 return result;
186}
187