nodedb_sql/planner/join/
constraint.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! ON-clause / USING-clause extraction: equi-join keys + non-equi residual.
4
5use sqlparser::ast;
6
7use crate::error::{Result, SqlError};
8use crate::parser::normalize::normalize_ident;
9use crate::planner::predicate_coerce::coerce_predicate_literals;
10use crate::resolver::ColumnScope;
11use crate::resolver::columns::{BareColumn, ColumnNaming, TableScope};
12use crate::resolver::expr::convert_expr;
13use crate::types::*;
14
15/// (join_type, equi_keys, non-equi condition)
16pub(super) type JoinSpec = (JoinType, Vec<(String, String)>, Option<SqlExpr>);
17
18/// Extract join type, equi-join keys, and non-equi condition.
19///
20/// `right_ref` is the scope key of the relation this join adds: a `USING`
21/// column must exist on it and on a relation before it.
22pub(super) fn extract_join_spec(
23    op: &ast::JoinOperator,
24    scope: &TableScope,
25    right_ref: Option<&str>,
26) -> Result<JoinSpec> {
27    let (join_type, constraint) = match op {
28        ast::JoinOperator::Inner(constraint) | ast::JoinOperator::Join(constraint) => {
29            (JoinType::Inner, constraint)
30        }
31        ast::JoinOperator::Left(constraint) | ast::JoinOperator::LeftOuter(constraint) => {
32            (JoinType::Left, constraint)
33        }
34        ast::JoinOperator::Right(constraint) | ast::JoinOperator::RightOuter(constraint) => {
35            (JoinType::Right, constraint)
36        }
37        ast::JoinOperator::FullOuter(constraint) => (JoinType::Full, constraint),
38        // `CROSS JOIN` takes no ON or USING clause: every left row pairs
39        // with every right row.
40        ast::JoinOperator::CrossJoin(ast::JoinConstraint::None) => {
41            return Ok((JoinType::Cross, Vec::new(), None));
42        }
43        ast::JoinOperator::CrossJoin(constraint) => (JoinType::Cross, constraint),
44        ast::JoinOperator::Semi(constraint) | ast::JoinOperator::LeftSemi(constraint) => {
45            (JoinType::Semi, constraint)
46        }
47        ast::JoinOperator::Anti(constraint) | ast::JoinOperator::LeftAnti(constraint) => {
48            (JoinType::Anti, constraint)
49        }
50        _ => {
51            return Err(SqlError::Unsupported {
52                detail: format!("join type: {op:?}"),
53            });
54        }
55    };
56    let (keys, cond) = extract_join_constraint(constraint, scope, right_ref)?;
57    Ok((join_type, keys, cond))
58}
59
60/// (equi_keys, non-equi condition)
61type JoinConstraintResult = (Vec<(String, String)>, Option<SqlExpr>);
62
63fn extract_join_constraint(
64    constraint: &ast::JoinConstraint,
65    scope: &TableScope,
66    right_ref: Option<&str>,
67) -> Result<JoinConstraintResult> {
68    match constraint {
69        ast::JoinConstraint::On(expr) => {
70            let mut keys = Vec::new();
71            let mut non_equi = Vec::new();
72            extract_equi_keys(expr, &mut keys, &mut non_equi, scope)?;
73            let cond = if non_equi.is_empty() {
74                None
75            } else {
76                let mut combined = convert_expr(&non_equi[0], &ColumnScope::Relations(scope))?;
77                for pred in &non_equi[1..] {
78                    combined = SqlExpr::BinaryOp {
79                        left: Box::new(combined),
80                        op: crate::types::BinaryOp::And,
81                        right: Box::new(convert_expr(pred, &ColumnScope::Relations(scope))?),
82                    };
83                }
84                // A non-equi ON predicate is evaluated per candidate pair by
85                // the same comparison the WHERE path uses, so its literals
86                // follow the same declared-instant rule.
87                coerce_predicate_literals(&mut combined, scope)?;
88                Some(combined)
89            };
90            Ok((keys, cond))
91        }
92        // `USING (k)` names `k` on both sides, so it is not an ambiguous
93        // bare reference. Each side reads its own `k` before the rows merge.
94        ast::JoinConstraint::Using(columns) => {
95            let keys = columns
96                .iter()
97                .map(|c| {
98                    let name = crate::parser::normalize::normalize_object_name_checked(c)?;
99                    scope.check_using_column(right_ref, &name)?;
100                    Ok((name.clone(), name))
101                })
102                .collect::<Result<Vec<_>>>()?;
103            Ok((keys, None))
104        }
105        ast::JoinConstraint::Natural => Err(SqlError::Unsupported {
106            detail: "NATURAL JOIN is not supported; use explicit ON or USING clause".into(),
107        }),
108        ast::JoinConstraint::None => Err(SqlError::Unsupported {
109            detail: "implicit cross join (no ON/USING clause) is not supported".into(),
110        }),
111    }
112}
113
114fn extract_equi_keys(
115    expr: &ast::Expr,
116    keys: &mut Vec<(String, String)>,
117    non_equi: &mut Vec<ast::Expr>,
118    scope: &TableScope,
119) -> Result<()> {
120    match expr {
121        ast::Expr::BinaryOp {
122            left,
123            op: ast::BinaryOperator::And,
124            right,
125        } => {
126            extract_equi_keys(left, keys, non_equi, scope)?;
127            extract_equi_keys(right, keys, non_equi, scope)?;
128        }
129        ast::Expr::BinaryOp {
130            left,
131            op: ast::BinaryOperator::Eq,
132            right,
133        } => {
134            if let (Some(l), Some(r)) = (extract_col_ref(left), extract_col_ref(right)) {
135                keys.push((resolve_join_key(scope, l)?, resolve_join_key(scope, r)?));
136            } else {
137                non_equi.push(expr.clone());
138            }
139        }
140        _ => {
141            non_equi.push(expr.clone());
142        }
143    }
144    Ok(())
145}
146
147/// Orient equi-join keys to the FROM order: `(left_side_key, right_side_key)`.
148///
149/// `extract_equi_keys` records each `a = b` pair in the textual order it
150/// appears in the ON clause (`(a, b)`), which is independent of which side of
151/// the FROM clause each operand belongs to. Downstream physical-plan
152/// conversion assumes `on.0` references the left input and `on.1` the right
153/// input (it builds the hash index on the right key and probes with the left).
154/// A query that writes `ON right.k = left.k` would otherwise build the index
155/// on the wrong side and match zero rows.
156///
157/// For each key pair, if the first operand is qualified by an alias/name
158/// belonging to the right side (and the second is not), swap so the right-side
159/// operand is always `on.1`. `right_ids` is the set of normalized
160/// alias/table-name identifiers for the right relation.
161pub(super) fn orient_keys_to_sides(keys: &mut [(String, String)], right_ids: &[String]) {
162    let qualifier = |k: &str| k.rsplit_once('.').map(|(q, _)| q.to_string());
163    let on_right = |k: &str| {
164        qualifier(k)
165            .map(|q| right_ids.iter().any(|id| id == &q))
166            .unwrap_or(false)
167    };
168    for (l, r) in keys.iter_mut() {
169        // Swap only when the left operand clearly belongs to the right side and
170        // the right operand does not — i.e. the pair is written reversed.
171        if on_right(l) && !on_right(r) {
172            std::mem::swap(l, r);
173        }
174    }
175}
176
177/// Check a join key, qualified or bare, against `scope` and return it in the
178/// form the join reads.
179///
180/// A qualified key is kept as written. Over a join's merged rows, a bare key
181/// is qualified with the relation that owns it, as written-qualified keys
182/// are, so it orients to its side and an ambiguous one is refused.
183fn resolve_join_key(scope: &TableScope, key: String) -> Result<String> {
184    if let Some((table, column)) = key.rsplit_once('.') {
185        scope.check_name(Some(table), column)?;
186        return Ok(key);
187    }
188    let owner = scope.resolve_bare(&key)?;
189    Ok(match (scope.column_naming(), owner) {
190        (ColumnNaming::JoinRow, BareColumn::Relation(table)) => {
191            format!("{}.{key}", table.ref_name())
192        }
193        (ColumnNaming::JoinRow, BareColumn::Output | BareColumn::Outer)
194        | (ColumnNaming::AsWritten | ColumnNaming::OutputRow, _) => key,
195    })
196}
197
198fn extract_col_ref(expr: &ast::Expr) -> Option<String> {
199    match expr {
200        ast::Expr::Identifier(ident) => Some(normalize_ident(ident)),
201        // Two-part: table.column — preserve the qualified form as the join key.
202        ast::Expr::CompoundIdentifier(parts) if parts.len() == 2 => Some(format!(
203            "{}.{}",
204            normalize_ident(&parts[0]),
205            normalize_ident(&parts[1])
206        )),
207        // Three or more parts: schema.table.column — reject by returning None;
208        // the caller will push the expression into non_equi which convert_expr
209        // then rejects with SqlError::Unsupported.
210        ast::Expr::CompoundIdentifier(_) => None,
211        _ => None,
212    }
213}
nodedb_sql/planner/join/constraint.rs

nodedb_sql/planner/join/
constraint.rs
