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
14pub fn join_conjuncts(expr: &ScalarExpr) -> Vec<&ScalarExpr> {
15    match expr {
16        ScalarExpr::And(items) => {
17            let mut conjuncts = Vec::with_capacity(items.len());
18            for item in items {
19                conjuncts.extend(join_conjuncts(item));
20            }
21            conjuncts
22        }
23        _ => vec![expr],
24    }
25}
26
27/// 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.
28pub fn decide_join_sides<'a>(
29    left: &RowSchema,
30    right: &RowSchema,
31    lhs: &'a ScalarExpr,
32    rhs: &'a ScalarExpr,
33) -> Option<(&'a ScalarExpr, &'a ScalarExpr)> {
34    let binds = |expression, schema, offset| {
35        let (valid, has_column) = expression_binding(expression, schema, offset);
36        valid && has_column
37    };
38    if binds(lhs, left, 0) && binds(rhs, right, left.len()) {
39        return Some((lhs, rhs));
40    }
41    if binds(rhs, left, 0) && binds(lhs, right, left.len()) {
42        return Some((rhs, lhs));
43    }
44    None
45}
46
47/// Rebase selected right-input positions for independent key evaluation, borrowing expressions whose coordinates already match their own input.
48pub fn bind_join_sides<'a>(
49    left: &RowSchema,
50    right: &RowSchema,
51    lhs: &'a ScalarExpr,
52    rhs: &'a ScalarExpr,
53) -> Option<(Cow<'a, ScalarExpr>, Cow<'a, ScalarExpr>)> {
54    let (lhs, rhs) = decide_join_sides(left, right, lhs, rhs)?;
55    Some((Cow::Borrowed(lhs), local_join_key(rhs, left.len())))
56}
57
58fn local_join_key(expression: &ScalarExpr, offset: usize) -> Cow<'_, ScalarExpr> {
59    let mut has_position = false;
60    if offset != 0 {
61        expression.visit(&mut |part| has_position |= matches!(part, ScalarExpr::Position(_)));
62    }
63    if !has_position {
64        return Cow::Borrowed(expression);
65    }
66    let mut bound = expression.clone();
67    crate::plan::rewrite_scalar_expression(&mut bound, &mut |part| {
68        if let ScalarExpr::Position(position) = part {
69            *position -= offset;
70        }
71    });
72    Cow::Owned(bound)
73}
74
75fn expression_binding(expression: &ScalarExpr, schema: &RowSchema, offset: usize) -> (bool, bool) {
76    match expression {
77        ScalarExpr::Column(column) => (schema.unqualified_position(column).is_some(), true),
78        ScalarExpr::QualifiedColumn { qualifier, column } => {
79            (schema.qualified_position(qualifier, column).is_some(), true)
80        }
81        ScalarExpr::Position(position) => (
82            position
83                .checked_sub(offset)
84                .is_some_and(|position| position < schema.len()),
85            true,
86        ),
87        ScalarExpr::InternalColumn(column) => (schema.internal_slot(*column).is_some(), true),
88        ScalarExpr::Literal(_) | ScalarExpr::TypedLiteral { .. } | ScalarExpr::Param(_) => {
89            (true, false)
90        }
91        ScalarExpr::Func {
92            args,
93            order_by,
94            filter,
95            ..
96        } => combine_bindings(
97            args.iter()
98                .chain(order_by.iter().map(|order| &order.expr))
99                .chain(filter.as_deref()),
100            schema,
101            offset,
102        ),
103        ScalarExpr::Array(items)
104        | ScalarExpr::Row(items)
105        | ScalarExpr::CompositeRow { items, .. }
106        | ScalarExpr::And(items)
107        | ScalarExpr::Or(items) => combine_bindings(items, schema, offset),
108        ScalarExpr::Binary { lhs, rhs, .. } => {
109            combine_bindings([lhs.as_ref(), rhs.as_ref()], schema, offset)
110        }
111        ScalarExpr::UnaryMinus(expr)
112        | ScalarExpr::Not(expr)
113        | ScalarExpr::IsNull { expr, .. }
114        | ScalarExpr::Cast { expr, .. }
115        | ScalarExpr::Collated { expr, .. }
116        | ScalarExpr::InSubquery { expr, .. } => expression_binding(expr, schema, offset),
117        ScalarExpr::Between { expr, low, high } => {
118            combine_bindings([expr.as_ref(), low.as_ref(), high.as_ref()], schema, offset)
119        }
120        ScalarExpr::InList { expr, list, .. } => {
121            combine_bindings(std::iter::once(expr.as_ref()).chain(list), schema, offset)
122        }
123        ScalarExpr::Case {
124            base,
125            when,
126            else_branch,
127        } => combine_bindings(
128            base.as_deref()
129                .into_iter()
130                .chain(
131                    when.iter()
132                        .flat_map(|(condition, value)| [condition, value]),
133                )
134                .chain(else_branch.as_deref()),
135            schema,
136            offset,
137        ),
138        ScalarExpr::WindowCall { .. }
139        | ScalarExpr::Default
140        | ScalarExpr::Star
141        | ScalarExpr::QualifiedStar(_)
142        | ScalarExpr::ScalarSubquery(_)
143        | ScalarExpr::Exists { .. } => (false, false),
144    }
145}
146
147fn combine_bindings<'a>(
148    expressions: impl IntoIterator<Item = &'a ScalarExpr>,
149    schema: &RowSchema,
150    offset: usize,
151) -> (bool, bool) {
152    expressions
153        .into_iter()
154        .map(|expression| expression_binding(expression, schema, offset))
155        .fold((true, false), |(valid, has_column), binding| {
156            (valid && binding.0, has_column || binding.1)
157        })
158}
159
160#[cfg(test)]
161mod tests {
162    use super::*;
163    use crate::ColumnIdentity;
164
165    #[test]
166    fn join_side_binding_uses_structured_identities() {
167        let left = RowSchema::with_identities(
168            vec!["order.key".into()],
169            vec![ColumnIdentity::qualified("left.alias", "order.key")],
170            vec![None],
171        );
172        let right = RowSchema::with_qualified_types("right.alias", vec!["id".into()], vec![None]);
173        let lhs = ScalarExpr::qualified_column("left.alias", "order.key");
174        let rhs = ScalarExpr::qualified_column("right.alias", "id");
175        assert_eq!(
176            decide_join_sides(&left, &right, &lhs, &rhs),
177            Some((&lhs, &rhs))
178        );
179    }
180
181    #[test]
182    fn joined_positions_are_rebased_only_to_their_own_input() {
183        let left = RowSchema::new(vec!["l0".into(), "l1".into()]);
184        let right = RowSchema::new(vec!["r0".into()]);
185        let lhs = ScalarExpr::Position(1);
186        let rhs = ScalarExpr::Cast {
187            implicit: true,
188            expr: Box::new(ScalarExpr::Position(2)),
189            ty: "bigint".into(),
190        };
191        let expected = ScalarExpr::Cast {
192            implicit: true,
193            expr: Box::new(ScalarExpr::Position(0)),
194            ty: "bigint".into(),
195        };
196        for (a, b) in [(&lhs, &rhs), (&rhs, &lhs)] {
197            let (a, b) = bind_join_sides(&left, &right, a, b).unwrap();
198            assert_eq!(a.as_ref(), &lhs);
199            assert_eq!(b.as_ref(), &expected);
200        }
201        for other in [
202            ScalarExpr::Position(0),
203            ScalarExpr::Position(3),
204            ScalarExpr::Literal(uqa_core::Value::Int(1)),
205        ] {
206            assert!(decide_join_sides(&left, &right, &lhs, &other).is_none());
207        }
208        let mixed = ScalarExpr::Binary {
209            op: crate::ast::BinaryOp::Add,
210            lhs: Box::new(lhs.clone()),
211            rhs: Box::new(rhs.clone()),
212        };
213        assert!(decide_join_sides(&left, &right, &mixed, &rhs).is_none());
214    }
215
216    #[test]
217    fn ambiguous_unqualified_join_key_is_not_assigned_arbitrarily() {
218        let left = RowSchema::with_identities(
219            vec!["id".into(), "id".into()],
220            vec![
221                ColumnIdentity::qualified("left", "id"),
222                ColumnIdentity::qualified("other", "id"),
223            ],
224            vec![None, None],
225        );
226        let right = RowSchema::with_qualified_types("right", vec!["id".into()], vec![None]);
227        let lhs = ScalarExpr::Column("id".into());
228        let rhs = ScalarExpr::qualified_column("right", "id");
229        assert_eq!(decide_join_sides(&left, &right, &lhs, &rhs), None);
230    }
231}
uqa_sql/semantics/join_predicates.rs

uqa_sql/semantics/
join_predicates.rs
