1use std::borrow::Cow;
10
11use crate::RowSchema;
12use crate::ScalarExpr;
13
14pub fn visit_join_conjuncts_with_control<'a>(
16 expression: &'a ScalarExpr,
17 control: &uqa_core::memory::ProductionControl<'_>,
18 visit: &mut impl FnMut(&'a ScalarExpr) -> Result<(), crate::SQLError>,
19) -> Result<(), crate::SQLError> {
20 control.check()?;
21 if let ScalarExpr::And(items) = expression {
22 for item in items {
23 visit_join_conjuncts_with_control(item, control, visit)?;
24 }
25 Ok(())
26 } else {
27 visit(expression)
28 }
29}
30
31pub fn bind_join_comparison_owned(
33 left: &RowSchema,
34 right: &RowSchema,
35 comparison: crate::plan::OwnedScalarExpr,
36 control: &uqa_core::memory::ProductionControl<'_>,
37) -> Result<Option<(crate::plan::OwnedScalarExpr, crate::plan::OwnedScalarExpr)>, crate::SQLError> {
38 control.check()?;
39 comparison.try_visit(&mut |_| {
40 control.check()?;
41 Ok::<_, crate::SQLError>(true)
42 })?;
43 let ScalarExpr::Binary { lhs, rhs, .. } = &*comparison else {
44 panic!("join side binding requires a comparison");
45 };
46 let Some((selected, _)) = decide_join_sides(left, right, lhs, rhs) else {
47 return Ok(None);
48 };
49 let reversed = !std::ptr::eq(selected, lhs.as_ref());
50 let mut children = comparison.into_children();
51 let lhs = children.next().expect("comparison left operand");
52 let rhs = children.next().expect("comparison right operand");
53 let (lhs, rhs) = if reversed { (rhs, lhs) } else { (lhs, rhs) };
54 let rhs = if left.is_empty() {
55 rhs
56 } else {
57 rhs.transform_nodes(control, &mut |_, expression| {
58 if let ScalarExpr::Position(position) = &*expression {
59 Ok(ScalarExpr::Position(position - left.len()).copy_for_rewrite(control)?)
60 } else {
61 Ok(expression)
62 }
63 })?
64 };
65 Ok(Some((lhs, rhs)))
66}
67
68pub fn join_conjuncts(expr: &ScalarExpr) -> Vec<&ScalarExpr> {
69 match expr {
70 ScalarExpr::And(items) => {
71 let mut conjuncts = Vec::with_capacity(items.len());
72 for item in items {
73 conjuncts.extend(join_conjuncts(item));
74 }
75 conjuncts
76 }
77 _ => vec![expr],
78 }
79}
80
81pub fn decide_join_sides<'a>(
83 left: &RowSchema,
84 right: &RowSchema,
85 lhs: &'a ScalarExpr,
86 rhs: &'a ScalarExpr,
87) -> Option<(&'a ScalarExpr, &'a ScalarExpr)> {
88 let binds = |expression, schema, offset| {
89 let (valid, has_column) = expression_binding(expression, schema, offset);
90 valid && has_column
91 };
92 if binds(lhs, left, 0) && binds(rhs, right, left.len()) {
93 return Some((lhs, rhs));
94 }
95 if binds(rhs, left, 0) && binds(lhs, right, left.len()) {
96 return Some((rhs, lhs));
97 }
98 None
99}
100
101pub fn bind_join_sides<'a>(
103 left: &RowSchema,
104 right: &RowSchema,
105 lhs: &'a ScalarExpr,
106 rhs: &'a ScalarExpr,
107) -> Option<(Cow<'a, ScalarExpr>, Cow<'a, ScalarExpr>)> {
108 let (lhs, rhs) = decide_join_sides(left, right, lhs, rhs)?;
109 Some((Cow::Borrowed(lhs), local_join_key(rhs, left.len())))
110}
111
112fn local_join_key(expression: &ScalarExpr, offset: usize) -> Cow<'_, ScalarExpr> {
113 let mut has_position = false;
114 if offset != 0 {
115 expression.visit(&mut |part| has_position |= matches!(part, ScalarExpr::Position(_)));
116 }
117 if !has_position {
118 return Cow::Borrowed(expression);
119 }
120 let mut bound = expression.clone();
121 crate::plan::rewrite_scalar_expression(&mut bound, &mut |part| {
122 if let ScalarExpr::Position(position) = part {
123 *position -= offset;
124 }
125 });
126 Cow::Owned(bound)
127}
128
129fn expression_binding(expression: &ScalarExpr, schema: &RowSchema, offset: usize) -> (bool, bool) {
130 match expression {
131 ScalarExpr::Column(column) => (schema.unqualified_position(column).is_some(), true),
132 ScalarExpr::QualifiedColumn { qualifier, column } => {
133 (schema.qualified_position(qualifier, column).is_some(), true)
134 }
135 ScalarExpr::Position(position) => (
136 position
137 .checked_sub(offset)
138 .is_some_and(|position| position < schema.len()),
139 true,
140 ),
141 ScalarExpr::InternalColumn(column) => (schema.internal_slot(*column).is_some(), true),
142 ScalarExpr::Literal(_)
143 | ScalarExpr::TypedLiteral { .. }
144 | ScalarExpr::RetainedLiteral(_)
145 | ScalarExpr::Param(_) => (true, false),
146 ScalarExpr::Func {
147 args,
148 order_by,
149 filter,
150 ..
151 } => combine_bindings(
152 args.iter()
153 .chain(order_by.iter().map(|order| &order.expr))
154 .chain(filter.as_deref()),
155 schema,
156 offset,
157 ),
158 ScalarExpr::Array(items)
159 | ScalarExpr::Row(items)
160 | ScalarExpr::CompositeRow { items, .. }
161 | ScalarExpr::And(items)
162 | ScalarExpr::Or(items) => combine_bindings(items, schema, offset),
163 ScalarExpr::Binary { lhs, rhs, .. } => {
164 combine_bindings([lhs.as_ref(), rhs.as_ref()], schema, offset)
165 }
166 ScalarExpr::UnaryMinus(expr)
167 | ScalarExpr::Not(expr)
168 | ScalarExpr::IsNull { expr, .. }
169 | ScalarExpr::Cast { expr, .. }
170 | ScalarExpr::Collated { expr, .. }
171 | ScalarExpr::InSubquery { expr, .. } => expression_binding(expr, schema, offset),
172 ScalarExpr::Between { expr, low, high } => {
173 combine_bindings([expr.as_ref(), low.as_ref(), high.as_ref()], schema, offset)
174 }
175 ScalarExpr::InList { expr, list, .. } => {
176 combine_bindings(std::iter::once(expr.as_ref()).chain(list), schema, offset)
177 }
178 ScalarExpr::Case {
179 base,
180 when,
181 else_branch,
182 } => combine_bindings(
183 base.as_deref()
184 .into_iter()
185 .chain(
186 when.iter()
187 .flat_map(|(condition, value)| [condition, value]),
188 )
189 .chain(else_branch.as_deref()),
190 schema,
191 offset,
192 ),
193 ScalarExpr::WindowCall { .. }
194 | ScalarExpr::Default
195 | ScalarExpr::Star
196 | ScalarExpr::QualifiedStar(_)
197 | ScalarExpr::ScalarSubquery(_)
198 | ScalarExpr::Exists { .. } => (false, false),
199 }
200}
201
202fn combine_bindings<'a>(
203 expressions: impl IntoIterator<Item = &'a ScalarExpr>,
204 schema: &RowSchema,
205 offset: usize,
206) -> (bool, bool) {
207 expressions
208 .into_iter()
209 .map(|expression| expression_binding(expression, schema, offset))
210 .fold((true, false), |(valid, has_column), binding| {
211 (valid && binding.0, has_column || binding.1)
212 })
213}
214
215#[cfg(test)]
216mod tests {
217 use super::*;
218 use crate::ColumnIdentity;
219
220 #[test]
221 fn join_side_binding_uses_structured_identities() {
222 let left = RowSchema::with_identities(
223 vec!["order.key".into()],
224 vec![ColumnIdentity::qualified("left.alias", "order.key")],
225 vec![None],
226 );
227 let right = RowSchema::with_qualified_types("right.alias", vec!["id".into()], vec![None]);
228 let lhs = ScalarExpr::qualified_column("left.alias", "order.key");
229 let rhs = ScalarExpr::qualified_column("right.alias", "id");
230 assert_eq!(
231 decide_join_sides(&left, &right, &lhs, &rhs),
232 Some((&lhs, &rhs))
233 );
234 }
235
236 #[test]
237 fn joined_positions_are_rebased_only_to_their_own_input() {
238 let left = RowSchema::new(vec!["l0".into(), "l1".into()]);
239 let right = RowSchema::new(vec!["r0".into()]);
240 let lhs = ScalarExpr::Position(1);
241 let rhs = ScalarExpr::Cast {
242 implicit: true,
243 expr: Box::new(ScalarExpr::Position(2)),
244 ty: "bigint".into(),
245 };
246 let expected = ScalarExpr::Cast {
247 implicit: true,
248 expr: Box::new(ScalarExpr::Position(0)),
249 ty: "bigint".into(),
250 };
251 for (a, b) in [(&lhs, &rhs), (&rhs, &lhs)] {
252 let (a, b) = bind_join_sides(&left, &right, a, b).unwrap();
253 assert_eq!(a.as_ref(), &lhs);
254 assert_eq!(b.as_ref(), &expected);
255 }
256 for other in [
257 ScalarExpr::Position(0),
258 ScalarExpr::Position(3),
259 ScalarExpr::Literal(uqa_core::Value::Int(1)),
260 ] {
261 assert!(decide_join_sides(&left, &right, &lhs, &other).is_none());
262 }
263 let mixed = ScalarExpr::Binary {
264 op: crate::ast::BinaryOp::Add,
265 lhs: Box::new(lhs.clone()),
266 rhs: Box::new(rhs.clone()),
267 };
268 assert!(decide_join_sides(&left, &right, &mixed, &rhs).is_none());
269 }
270
271 #[test]
272 fn ambiguous_unqualified_join_key_is_not_assigned_arbitrarily() {
273 let left = RowSchema::with_identities(
274 vec!["id".into(), "id".into()],
275 vec![
276 ColumnIdentity::qualified("left", "id"),
277 ColumnIdentity::qualified("other", "id"),
278 ],
279 vec![None, None],
280 );
281 let right = RowSchema::with_qualified_types("right", vec!["id".into()], vec![None]);
282 let lhs = ScalarExpr::Column("id".into());
283 let rhs = ScalarExpr::qualified_column("right", "id");
284 assert_eq!(decide_join_sides(&left, &right, &lhs, &rhs), None);
285 }
286}