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
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(_)
89        | ScalarExpr::TypedLiteral { .. }
90        | ScalarExpr::RetainedLiteral(_)
91        | ScalarExpr::Param(_) => (true, false),
92        ScalarExpr::Func {
93            args,
94            order_by,
95            filter,
96            ..
97        } => combine_bindings(
98            args.iter()
99                .chain(order_by.iter().map(|order| &order.expr))
100                .chain(filter.as_deref()),
101            schema,
102            offset,
103        ),
104        ScalarExpr::Array(items)
105        | ScalarExpr::Row(items)
106        | ScalarExpr::CompositeRow { items, .. }
107        | ScalarExpr::And(items)
108        | ScalarExpr::Or(items) => combine_bindings(items, schema, offset),
109        ScalarExpr::Binary { lhs, rhs, .. } => {
110            combine_bindings([lhs.as_ref(), rhs.as_ref()], schema, offset)
111        }
112        ScalarExpr::UnaryMinus(expr)
113        | ScalarExpr::Not(expr)
114        | ScalarExpr::IsNull { expr, .. }
115        | ScalarExpr::Cast { expr, .. }
116        | ScalarExpr::Collated { expr, .. }
117        | ScalarExpr::InSubquery { expr, .. } => expression_binding(expr, schema, offset),
118        ScalarExpr::Between { expr, low, high } => {
119            combine_bindings([expr.as_ref(), low.as_ref(), high.as_ref()], schema, offset)
120        }
121        ScalarExpr::InList { expr, list, .. } => {
122            combine_bindings(std::iter::once(expr.as_ref()).chain(list), schema, offset)
123        }
124        ScalarExpr::Case {
125            base,
126            when,
127            else_branch,
128        } => combine_bindings(
129            base.as_deref()
130                .into_iter()
131                .chain(
132                    when.iter()
133                        .flat_map(|(condition, value)| [condition, value]),
134                )
135                .chain(else_branch.as_deref()),
136            schema,
137            offset,
138        ),
139        ScalarExpr::WindowCall { .. }
140        | ScalarExpr::Default
141        | ScalarExpr::Star
142        | ScalarExpr::QualifiedStar(_)
143        | ScalarExpr::ScalarSubquery(_)
144        | ScalarExpr::Exists { .. } => (false, false),
145    }
146}
147
148fn combine_bindings<'a>(
149    expressions: impl IntoIterator<Item = &'a ScalarExpr>,
150    schema: &RowSchema,
151    offset: usize,
152) -> (bool, bool) {
153    expressions
154        .into_iter()
155        .map(|expression| expression_binding(expression, schema, offset))
156        .fold((true, false), |(valid, has_column), binding| {
157            (valid && binding.0, has_column || binding.1)
158        })
159}
160
161#[cfg(test)]
162mod tests {
163    use super::*;
164    use crate::ColumnIdentity;
165
166    #[test]
167    fn join_side_binding_uses_structured_identities() {
168        let left = RowSchema::with_identities(
169            vec!["order.key".into()],
170            vec![ColumnIdentity::qualified("left.alias", "order.key")],
171            vec![None],
172        );
173        let right = RowSchema::with_qualified_types("right.alias", vec!["id".into()], vec![None]);
174        let lhs = ScalarExpr::qualified_column("left.alias", "order.key");
175        let rhs = ScalarExpr::qualified_column("right.alias", "id");
176        assert_eq!(
177            decide_join_sides(&left, &right, &lhs, &rhs),
178            Some((&lhs, &rhs))
179        );
180    }
181
182    #[test]
183    fn joined_positions_are_rebased_only_to_their_own_input() {
184        let left = RowSchema::new(vec!["l0".into(), "l1".into()]);
185        let right = RowSchema::new(vec!["r0".into()]);
186        let lhs = ScalarExpr::Position(1);
187        let rhs = ScalarExpr::Cast {
188            implicit: true,
189            expr: Box::new(ScalarExpr::Position(2)),
190            ty: "bigint".into(),
191        };
192        let expected = ScalarExpr::Cast {
193            implicit: true,
194            expr: Box::new(ScalarExpr::Position(0)),
195            ty: "bigint".into(),
196        };
197        for (a, b) in [(&lhs, &rhs), (&rhs, &lhs)] {
198            let (a, b) = bind_join_sides(&left, &right, a, b).unwrap();
199            assert_eq!(a.as_ref(), &lhs);
200            assert_eq!(b.as_ref(), &expected);
201        }
202        for other in [
203            ScalarExpr::Position(0),
204            ScalarExpr::Position(3),
205            ScalarExpr::Literal(uqa_core::Value::Int(1)),
206        ] {
207            assert!(decide_join_sides(&left, &right, &lhs, &other).is_none());
208        }
209        let mixed = ScalarExpr::Binary {
210            op: crate::ast::BinaryOp::Add,
211            lhs: Box::new(lhs.clone()),
212            rhs: Box::new(rhs.clone()),
213        };
214        assert!(decide_join_sides(&left, &right, &mixed, &rhs).is_none());
215    }
216
217    #[test]
218    fn ambiguous_unqualified_join_key_is_not_assigned_arbitrarily() {
219        let left = RowSchema::with_identities(
220            vec!["id".into(), "id".into()],
221            vec![
222                ColumnIdentity::qualified("left", "id"),
223                ColumnIdentity::qualified("other", "id"),
224            ],
225            vec![None, None],
226        );
227        let right = RowSchema::with_qualified_types("right", vec!["id".into()], vec![None]);
228        let lhs = ScalarExpr::Column("id".into());
229        let rhs = ScalarExpr::qualified_column("right", "id");
230        assert_eq!(decide_join_sides(&left, &right, &lhs, &rhs), None);
231    }
232}