1#include "duckdb/parser/tableref/joinref.hpp"
2#include "duckdb/planner/binder.hpp"
3#include "duckdb/planner/expression_binder/where_binder.hpp"
4#include "duckdb/planner/tableref/bound_joinref.hpp"
5#include "duckdb/parser/expression/comparison_expression.hpp"
6#include "duckdb/parser/expression/columnref_expression.hpp"
7#include "duckdb/parser/expression/constant_expression.hpp"
8#include "duckdb/parser/expression/conjunction_expression.hpp"
9#include "duckdb/parser/expression/bound_expression.hpp"
10#include "duckdb/parser/expression/star_expression.hpp"
11#include "duckdb/common/string_util.hpp"
12#include "duckdb/common/case_insensitive_map.hpp"
13#include "duckdb/planner/expression_binder/lateral_binder.hpp"
14#include "duckdb/planner/query_node/bound_select_node.hpp"
15
16namespace duckdb {
17
18static unique_ptr<ParsedExpression> BindColumn(Binder &binder, ClientContext &context, const string &alias,
19 const string &column_name) {
20 auto expr = make_uniq_base<ParsedExpression, ColumnRefExpression>(args: column_name, args: alias);
21 ExpressionBinder expr_binder(binder, context);
22 auto result = expr_binder.Bind(expr);
23 return make_uniq<BoundExpression>(args: std::move(result));
24}
25
26static unique_ptr<ParsedExpression> AddCondition(ClientContext &context, Binder &left_binder, Binder &right_binder,
27 const string &left_alias, const string &right_alias,
28 const string &column_name, ExpressionType type) {
29 ExpressionBinder expr_binder(left_binder, context);
30 auto left = BindColumn(binder&: left_binder, context, alias: left_alias, column_name);
31 auto right = BindColumn(binder&: right_binder, context, alias: right_alias, column_name);
32 return make_uniq<ComparisonExpression>(args&: type, args: std::move(left), args: std::move(right));
33}
34
35bool Binder::TryFindBinding(const string &using_column, const string &join_side, string &result) {
36 // for each using column, get the matching binding
37 auto bindings = bind_context.GetMatchingBindings(column_name: using_column);
38 if (bindings.empty()) {
39 return false;
40 }
41 // find the join binding
42 for (auto &binding : bindings) {
43 if (!result.empty()) {
44 string error = "Column name \"";
45 error += using_column;
46 error += "\" is ambiguous: it exists more than once on ";
47 error += join_side;
48 error += " side of join.\nCandidates:";
49 for (auto &binding : bindings) {
50 error += "\n\t";
51 error += binding;
52 error += ".";
53 error += bind_context.GetActualColumnName(binding, column_name: using_column);
54 }
55 throw BinderException(error);
56 } else {
57 result = binding;
58 }
59 }
60 return true;
61}
62
63string Binder::FindBinding(const string &using_column, const string &join_side) {
64 string result;
65 if (!TryFindBinding(using_column, join_side, result)) {
66 throw BinderException("Column \"%s\" does not exist on %s side of join!", using_column, join_side);
67 }
68 return result;
69}
70
71static void AddUsingBindings(UsingColumnSet &set, optional_ptr<UsingColumnSet> input_set, const string &input_binding) {
72 if (input_set) {
73 for (auto &entry : input_set->bindings) {
74 set.bindings.insert(x: entry);
75 }
76 } else {
77 set.bindings.insert(x: input_binding);
78 }
79}
80
81static void SetPrimaryBinding(UsingColumnSet &set, JoinType join_type, const string &left_binding,
82 const string &right_binding) {
83 switch (join_type) {
84 case JoinType::LEFT:
85 case JoinType::INNER:
86 case JoinType::SEMI:
87 case JoinType::ANTI:
88 set.primary_binding = left_binding;
89 break;
90 case JoinType::RIGHT:
91 set.primary_binding = right_binding;
92 break;
93 default:
94 break;
95 }
96}
97
98string Binder::RetrieveUsingBinding(Binder &current_binder, optional_ptr<UsingColumnSet> current_set,
99 const string &using_column, const string &join_side) {
100 string binding;
101 if (!current_set) {
102 binding = current_binder.FindBinding(using_column, join_side);
103 } else {
104 binding = current_set->primary_binding;
105 }
106 return binding;
107}
108
109static vector<string> RemoveDuplicateUsingColumns(const vector<string> &using_columns) {
110 vector<string> result;
111 case_insensitive_set_t handled_columns;
112 for (auto &using_column : using_columns) {
113 if (handled_columns.find(x: using_column) == handled_columns.end()) {
114 handled_columns.insert(x: using_column);
115 result.push_back(x: using_column);
116 }
117 }
118 return result;
119}
120
121unique_ptr<BoundTableRef> Binder::Bind(JoinRef &ref) {
122 auto result = make_uniq<BoundJoinRef>(args&: ref.ref_type);
123 result->left_binder = Binder::CreateBinder(context, parent: this);
124 result->right_binder = Binder::CreateBinder(context, parent: this);
125 auto &left_binder = *result->left_binder;
126 auto &right_binder = *result->right_binder;
127
128 result->type = ref.type;
129 result->left = left_binder.Bind(ref&: *ref.left);
130 {
131 LateralBinder binder(left_binder, context);
132 result->right = right_binder.Bind(ref&: *ref.right);
133 result->correlated_columns = binder.ExtractCorrelatedColumns(binder&: right_binder);
134
135 result->lateral = binder.HasCorrelatedColumns();
136 if (result->lateral) {
137 // lateral join: can only be an INNER or LEFT join
138 if (ref.type != JoinType::INNER && ref.type != JoinType::LEFT) {
139 throw BinderException("The combining JOIN type must be INNER or LEFT for a LATERAL reference");
140 }
141 }
142 }
143
144 vector<unique_ptr<ParsedExpression>> extra_conditions;
145 vector<string> extra_using_columns;
146 switch (ref.ref_type) {
147 case JoinRefType::NATURAL: {
148 // natural join, figure out which column names are present in both sides of the join
149 // first bind the left hand side and get a list of all the tables and column names
150 case_insensitive_set_t lhs_columns;
151 auto &lhs_binding_list = left_binder.bind_context.GetBindingsList();
152 for (auto &binding : lhs_binding_list) {
153 for (auto &column_name : binding.get().names) {
154 lhs_columns.insert(x: column_name);
155 }
156 }
157 // now bind the rhs
158 for (auto &column_name : lhs_columns) {
159 auto right_using_binding = right_binder.bind_context.GetUsingBinding(column_name);
160
161 string right_binding;
162 // loop over the set of lhs columns, and figure out if there is a table in the rhs with the same name
163 if (!right_using_binding) {
164 if (!right_binder.TryFindBinding(using_column: column_name, join_side: "right", result&: right_binding)) {
165 // no match found for this column on the rhs: skip
166 continue;
167 }
168 }
169 extra_using_columns.push_back(x: column_name);
170 }
171 if (extra_using_columns.empty()) {
172 // no matching bindings found in natural join: throw an exception
173 string error_msg = "No columns found to join on in NATURAL JOIN.\n";
174 error_msg += "Use CROSS JOIN if you intended for this to be a cross-product.";
175 // gather all left/right candidates
176 string left_candidates, right_candidates;
177 auto &rhs_binding_list = right_binder.bind_context.GetBindingsList();
178 for (auto &binding_ref : lhs_binding_list) {
179 auto &binding = binding_ref.get();
180 for (auto &column_name : binding.names) {
181 if (!left_candidates.empty()) {
182 left_candidates += ", ";
183 }
184 left_candidates += binding.alias + "." + column_name;
185 }
186 }
187 for (auto &binding_ref : rhs_binding_list) {
188 auto &binding = binding_ref.get();
189 for (auto &column_name : binding.names) {
190 if (!right_candidates.empty()) {
191 right_candidates += ", ";
192 }
193 right_candidates += binding.alias + "." + column_name;
194 }
195 }
196 error_msg += "\n Left candidates: " + left_candidates;
197 error_msg += "\n Right candidates: " + right_candidates;
198 throw BinderException(FormatError(ref_context&: ref, message: error_msg));
199 }
200 break;
201 }
202 case JoinRefType::REGULAR:
203 case JoinRefType::ASOF:
204 if (!ref.using_columns.empty()) {
205 // USING columns
206 D_ASSERT(!result->condition);
207 extra_using_columns = ref.using_columns;
208 }
209 break;
210
211 case JoinRefType::CROSS:
212 case JoinRefType::POSITIONAL:
213 break;
214 }
215 extra_using_columns = RemoveDuplicateUsingColumns(using_columns: extra_using_columns);
216
217 if (!extra_using_columns.empty()) {
218 vector<optional_ptr<UsingColumnSet>> left_using_bindings;
219 vector<optional_ptr<UsingColumnSet>> right_using_bindings;
220 for (idx_t i = 0; i < extra_using_columns.size(); i++) {
221 auto &using_column = extra_using_columns[i];
222 // we check if there is ALREADY a using column of the same name in the left and right set
223 // this can happen if we chain USING clauses
224 // e.g. x JOIN y USING (c) JOIN z USING (c)
225 auto left_using_binding = left_binder.bind_context.GetUsingBinding(column_name: using_column);
226 auto right_using_binding = right_binder.bind_context.GetUsingBinding(column_name: using_column);
227 if (!left_using_binding) {
228 left_binder.bind_context.GetMatchingBinding(column_name: using_column);
229 }
230 if (!right_using_binding) {
231 right_binder.bind_context.GetMatchingBinding(column_name: using_column);
232 }
233 left_using_bindings.push_back(x: left_using_binding);
234 right_using_bindings.push_back(x: right_using_binding);
235 }
236
237 for (idx_t i = 0; i < extra_using_columns.size(); i++) {
238 auto &using_column = extra_using_columns[i];
239 string left_binding;
240 string right_binding;
241
242 auto set = make_uniq<UsingColumnSet>();
243 auto &left_using_binding = left_using_bindings[i];
244 auto &right_using_binding = right_using_bindings[i];
245 left_binding = RetrieveUsingBinding(current_binder&: left_binder, current_set: left_using_binding, using_column, join_side: "left");
246 right_binding = RetrieveUsingBinding(current_binder&: right_binder, current_set: right_using_binding, using_column, join_side: "right");
247
248 // Last column of ASOF JOIN ... USING is >=
249 const auto type = (ref.ref_type == JoinRefType::ASOF && i == extra_using_columns.size() - 1)
250 ? ExpressionType::COMPARE_GREATERTHANOREQUALTO
251 : ExpressionType::COMPARE_EQUAL;
252
253 extra_conditions.push_back(
254 x: AddCondition(context, left_binder, right_binder, left_alias: left_binding, right_alias: right_binding, column_name: using_column, type));
255
256 AddUsingBindings(set&: *set, input_set: left_using_binding, input_binding: left_binding);
257 AddUsingBindings(set&: *set, input_set: right_using_binding, input_binding: right_binding);
258 SetPrimaryBinding(set&: *set, join_type: ref.type, left_binding, right_binding);
259 bind_context.TransferUsingBinding(current_context&: left_binder.bind_context, current_set: left_using_binding, new_set&: *set, binding: left_binding,
260 using_column);
261 bind_context.TransferUsingBinding(current_context&: right_binder.bind_context, current_set: right_using_binding, new_set&: *set, binding: right_binding,
262 using_column);
263 AddUsingBindingSet(set: std::move(set));
264 }
265 }
266
267 auto right_bindings_list_copy = right_binder.bind_context.GetBindingsList();
268
269 bind_context.AddContext(other: std::move(left_binder.bind_context));
270 bind_context.AddContext(other: std::move(right_binder.bind_context));
271 MoveCorrelatedExpressions(other&: left_binder);
272 MoveCorrelatedExpressions(other&: right_binder);
273 for (auto &condition : extra_conditions) {
274 if (ref.condition) {
275 ref.condition = make_uniq<ConjunctionExpression>(args: ExpressionType::CONJUNCTION_AND, args: std::move(ref.condition),
276 args: std::move(condition));
277 } else {
278 ref.condition = std::move(condition);
279 }
280 }
281 if (ref.condition) {
282 WhereBinder binder(*this, context);
283 result->condition = binder.Bind(expr&: ref.condition);
284 }
285
286 if (result->type == JoinType::SEMI || result->type == JoinType::ANTI) {
287 bind_context.RemoveContext(other_bindings_list&: right_bindings_list_copy);
288 }
289
290 return std::move(result);
291}
292
293} // namespace duckdb
294