Skip to main content

uqa_sql/semantics/
join_predicates.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Join conjunct analysis and structural side binding.
8
9use std::borrow::Cow;
10
11use crate::RowSchema;
12use crate::ScalarExpr;
13
14/// Visit flattened conjunctions in their original order without allocating an intermediate reference tree.
15pub 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
31/// Move an equality's selected operands to their own input scopes. Right-input positions change coordinates without copying either scalar tree.
32pub 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
81/// Determine the input side of equality operands from structured identities and joined logical positions. Planning does not synthesize a sample row, and punctuation in a quoted identifier is never interpreted as a relation boundary.
82pub 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
101/// Rebase selected right-input positions for independent key evaluation, borrowing expressions whose coordinates already match their own input.
102pub 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}