Skip to main content

uqa_sql/binding/
correlation.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Physical-plan correlation analysis for scalar subquery initialization.
8
9use std::collections::{BTreeMap, BTreeSet};
10use std::sync::Arc;
11
12use crate::plan::{ComputePlan, ProjectionPlan, QueryPlan, RelationalPlan, SourcePlan};
13use crate::SQLError;
14use crate::{ScalarExpr, ScalarFrameBound};
15
16use crate::catalog::{analysis::AnalysisCatalog, resolution::RelationNameResolution};
17mod outputs;
18use outputs::{cte_output_columns, query_output_columns, source_scope};
19
20mod sources;
21pub use sources::source_depends_on_current_row;
22use sources::{expression_references_outer, source_references_outer};
23
24/// A single immutable namespace and catalog view used throughout correlation analysis.
25#[derive(Clone, Copy)]
26pub struct CorrelationContext<'a> {
27    pub routines: &'a dyn crate::routines::RoutineResolution,
28    pub catalog: &'a dyn AnalysisCatalog,
29    pub resolution: &'a RelationNameResolution,
30    pub scoped_relations: Option<&'a dyn CorrelationRelations>,
31}
32
33/// Relation descriptors already retained by the invoking query, including transition relations.
34pub trait CorrelationRelations {
35    fn columns(&self, relation: &str) -> Option<&[String]>;
36}
37
38#[derive(Clone, Default)]
39struct RelationColumns {
40    names: BTreeSet<String>,
41    ordered: Vec<String>,
42    complete: bool,
43}
44
45impl RelationColumns {
46    fn known(ordered: Vec<String>) -> Self {
47        Self {
48            names: ordered.iter().cloned().collect(),
49            ordered,
50            complete: true,
51        }
52    }
53
54    fn empty_known() -> Self {
55        Self::known(Vec::new())
56    }
57
58    fn apply_positional_aliases(&mut self, aliases: &[String]) {
59        for (column, alias) in self.ordered.iter_mut().zip(aliases) {
60            column.clone_from(alias);
61        }
62        self.names = self.ordered.iter().cloned().collect();
63    }
64}
65
66#[derive(Clone, Default)]
67struct QueryScope {
68    qualifiers: BTreeMap<String, Arc<RelationColumns>>,
69    internal_relations: BTreeSet<crate::ast::InternalRelationId>,
70    columns: Arc<RelationColumns>,
71    enclosing: Option<crate::RowSchema>,
72}
73
74pub struct DecorrelatedExistsPlan {
75    pub inner: QueryPlan,
76    pub outer_keys: Vec<ScalarExpr>,
77}
78
79/// Turn a simple correlated equality EXISTS into an uncorrelated key query.
80///
81/// The caller materializes the returned inner key rows once and probes them
82/// with `outer_keys`, which is the physical equivalent of a hash semi-join.
83pub fn decorrelate_exists(
84    context: CorrelationContext<'_>,
85    plan: &QueryPlan,
86) -> Result<Option<DecorrelatedExistsPlan>, SQLError> {
87    if !plan.ctes.is_empty() {
88        return Ok(None);
89    }
90    let RelationalPlan::QueryBlock(block) = &plan.root else {
91        return Ok(None);
92    };
93    let Some(source) = block.from.as_ref() else {
94        return Ok(None);
95    };
96    if !block.deferred_outer_rewrites.is_empty()
97        || !matches!(block.compute, ComputePlan::Project)
98        || !block.group_by.is_empty()
99        || !block.grouping_sets.is_empty()
100        || block.having.is_some()
101        || block.limit.is_some()
102        || block.offset.is_some()
103        || block.distinct
104        || !block.distinct_on.is_empty()
105        || !block.subqueries.is_empty()
106    {
107        return Ok(None);
108    }
109
110    let scope = source_scope(context, source, &BTreeMap::new(), &[])?;
111    if source_references_outer(
112        context,
113        source,
114        &block.subqueries,
115        &mut Vec::new(),
116        &BTreeMap::new(),
117    )? {
118        return Ok(None);
119    }
120    let Some(predicate) = block.r#where.as_ref() else {
121        return Ok(None);
122    };
123    let conjuncts = match predicate {
124        ScalarExpr::And(items) => items.as_slice(),
125        expression => std::slice::from_ref(expression),
126    };
127    let mut inner_keys = Vec::new();
128    let mut outer_keys = Vec::new();
129    let mut residual = Vec::new();
130    for conjunct in conjuncts {
131        if let ScalarExpr::Binary {
132            op: crate::ast::BinaryOp::Equal,
133            lhs,
134            rhs,
135        } = conjunct
136        {
137            let lhs_scope = correlation_column_scope(lhs, &scope);
138            let rhs_scope = correlation_column_scope(rhs, &scope);
139            match (lhs_scope, rhs_scope) {
140                (Some(ColumnScope::Inner), Some(ColumnScope::Outer)) => {
141                    inner_keys.push((**lhs).clone());
142                    outer_keys.push((**rhs).clone());
143                    continue;
144                }
145                (Some(ColumnScope::Outer), Some(ColumnScope::Inner)) => {
146                    inner_keys.push((**rhs).clone());
147                    outer_keys.push((**lhs).clone());
148                    continue;
149                }
150                _ => {}
151            }
152        }
153        if expression_has_external_reference(conjunct, std::slice::from_ref(&scope)) {
154            return Ok(None);
155        }
156        residual.push(conjunct.clone());
157    }
158    if inner_keys.is_empty() {
159        return Ok(None);
160    }
161
162    let mut inner = plan.clone();
163    let RelationalPlan::QueryBlock(inner_block) = &mut inner.root else {
164        unreachable!("query-block shape checked above");
165    };
166    inner_block.projections = inner_keys
167        .into_iter()
168        .map(|expr| ProjectionPlan { expr, alias: None })
169        .collect();
170    inner_block.r#where = match residual.len() {
171        0 => None,
172        1 => residual.pop(),
173        _ => Some(ScalarExpr::And(residual)),
174    };
175    inner_block.order_by.clear();
176    Ok(Some(DecorrelatedExistsPlan { inner, outer_keys }))
177}
178
179#[derive(Clone, Copy, PartialEq, Eq)]
180enum ColumnScope {
181    Inner,
182    Outer,
183}
184
185fn correlation_column_scope(expression: &ScalarExpr, scope: &QueryScope) -> Option<ColumnScope> {
186    match expression {
187        ScalarExpr::Column(column) => {
188            if scope.columns.names.contains(column.as_str())
189                || scope.qualifiers.contains_key(column.as_str())
190            {
191                Some(ColumnScope::Inner)
192            } else if scope.columns.complete {
193                Some(ColumnScope::Outer)
194            } else {
195                None
196            }
197        }
198        ScalarExpr::QualifiedColumn { qualifier, .. } => {
199            if scope.qualifiers.contains_key(qualifier) {
200                Some(ColumnScope::Inner)
201            } else {
202                Some(ColumnScope::Outer)
203            }
204        }
205        ScalarExpr::InternalColumn(column) => {
206            if scope.internal_relations.contains(&column.relation()) {
207                Some(ColumnScope::Inner)
208            } else {
209                Some(ColumnScope::Outer)
210            }
211        }
212        ScalarExpr::Cast { expr, .. } | ScalarExpr::Collated { expr, .. } => {
213            correlation_column_scope(expr, scope)
214        }
215        _ => None,
216    }
217}
218
219pub fn query_depends_on_outer_row(
220    context: CorrelationContext<'_>,
221    plan: &QueryPlan,
222) -> Result<bool, SQLError> {
223    query_has_external_reference(context, plan, &mut Vec::new())
224}
225
226/// Whether a scalar expression needs a row outside its declared FROM namespace. Scalar subqueries keep their own local aliases and CTEs; an uncorrelated subquery does not introduce an outer-row dependency.
227pub fn expression_depends_on_outer_row(
228    context: CorrelationContext<'_>,
229    expression: &crate::plan::ExpressionPlan,
230    source: Option<&SourcePlan>,
231    definitions: &[crate::plan::CtePlan],
232) -> Result<bool, SQLError> {
233    let mut ctes = BTreeMap::new();
234    for cte in definitions.iter().filter(|cte| cte.recursive) {
235        ctes.insert(
236            cte.name.clone(),
237            RelationColumns {
238                names: cte.columns.iter().cloned().collect(),
239                ordered: cte.columns.clone(),
240                complete: false,
241            },
242        );
243    }
244    for cte in definitions {
245        let columns = cte_output_columns(context, cte, &ctes, &[])?;
246        ctes.insert(cte.name.clone(), columns);
247    }
248    let mut scopes = match source {
249        Some(source) => vec![source_scope(context, source, &ctes, &[])?],
250        None => Vec::new(),
251    };
252    expression_references_outer(
253        context,
254        &expression.scalar,
255        &expression.subqueries,
256        &mut scopes,
257        &ctes,
258    )
259}
260
261/// Whether a subquery refers to the caller's own row. Seed enclosing identities so references beyond that row are not mistaken for level-zero variables.
262pub(crate) fn query_depends_on_current_row(
263    context: CorrelationContext<'_>,
264    plan: &QueryPlan,
265    input: &crate::RowSchema,
266) -> Result<bool, SQLError> {
267    query_has_external_reference(context, plan, &mut vec![enclosing_scope(input)])
268}
269
270fn enclosing_scope(input: &crate::RowSchema) -> QueryScope {
271    let deferred_columns = Arc::new(RelationColumns::default());
272    let mut enclosing = QueryScope {
273        columns: Arc::new(RelationColumns::empty_known()),
274        enclosing: Some(input.clone()),
275        ..QueryScope::default()
276    };
277    for (identity, _) in input.typed_physical_alias_identities() {
278        if !input.resolves_local_column(identity.qualifier(), identity.column()) {
279            if let Some(qualifier) = identity.qualifier() {
280                enclosing
281                    .qualifiers
282                    .entry(qualifier.to_owned())
283                    .or_insert_with(|| Arc::clone(&deferred_columns));
284            } else {
285                Arc::make_mut(&mut enclosing.columns)
286                    .names
287                    .insert(identity.column().to_owned());
288            }
289        }
290    }
291    for (column, slot) in input.internal_identities() {
292        if !input.slot_is_local(slot) {
293            enclosing.internal_relations.insert(column.relation());
294        }
295    }
296    enclosing
297}
298
299fn query_has_external_reference(
300    context: CorrelationContext<'_>,
301    plan: &QueryPlan,
302    scopes: &mut Vec<QueryScope>,
303) -> Result<bool, SQLError> {
304    query_references_outer(context, plan, scopes, &BTreeMap::new())
305}
306
307#[expect(
308    clippy::too_many_lines,
309    reason = "preserves scope and subquery identity"
310)]
311fn query_references_outer(
312    context: CorrelationContext<'_>,
313    plan: &QueryPlan,
314    scopes: &mut Vec<QueryScope>,
315    parent_ctes: &BTreeMap<String, RelationColumns>,
316) -> Result<bool, SQLError> {
317    let mut ctes = parent_ctes.clone();
318    if plan.ctes.iter().any(|cte| cte.recursive) {
319        for cte in &plan.ctes {
320            let columns = RelationColumns {
321                names: cte.columns.iter().cloned().collect(),
322                ordered: cte.columns.clone(),
323                complete: false,
324            };
325            ctes.insert(cte.name.clone(), columns);
326        }
327    }
328    for cte in &plan.ctes {
329        let columns = cte_output_columns(context, cte, &ctes, scopes)?;
330        if cte.recursive {
331            ctes.insert(cte.name.clone(), columns.clone());
332        }
333        if cte.body.query().map_or(Ok(true), |query| {
334            query_references_outer(context, query, scopes, &ctes)
335        })? {
336            return Ok(true);
337        }
338        ctes.insert(cte.name.clone(), columns);
339    }
340
341    match &plan.root {
342        RelationalPlan::QueryBlock(block) => {
343            // A FROM item's own output is not visible to its arguments. Bind its dependencies before adding the complete query namespace used by projections and predicates.
344            if let Some(source) = block.from.as_ref() {
345                if source_references_outer(context, source, &block.subqueries, scopes, &ctes)? {
346                    return Ok(true);
347                }
348            }
349            let scope = match block.from.as_ref() {
350                Some(source) => source_scope(context, source, &ctes, scopes)?,
351                None => QueryScope {
352                    qualifiers: BTreeMap::new(),
353                    internal_relations: BTreeSet::new(),
354                    columns: Arc::new(RelationColumns::empty_known()),
355                    enclosing: None,
356                },
357            };
358            scopes.push(scope);
359            let result = block
360                .try_visit_expressions(&mut |expression| {
361                    expression_references_outer(
362                        context,
363                        expression,
364                        &block.subqueries,
365                        scopes,
366                        &ctes,
367                    )
368                    .map(|references_outer| !references_outer)
369                })
370                .map(|completed| !completed);
371            scopes.pop();
372            result
373        }
374        RelationalPlan::SetOp {
375            left,
376            right,
377            order_by,
378            limit,
379            offset,
380            subqueries,
381            ..
382        } => {
383            if query_references_outer(context, left, scopes, &ctes)?
384                || query_references_outer(context, right, scopes, &ctes)?
385            {
386                return Ok(true);
387            }
388            scopes.push(QueryScope {
389                qualifiers: BTreeMap::new(),
390                internal_relations: BTreeSet::new(),
391                columns: Arc::new(query_output_columns(context, left, &ctes, scopes)?),
392                enclosing: None,
393            });
394            let result = (|| {
395                for expression in order_by.iter().map(|order| &order.expr) {
396                    if expression_references_outer(context, expression, subqueries, scopes, &ctes)?
397                    {
398                        return Ok(true);
399                    }
400                }
401                for expression in limit.iter().chain(offset).map(AsRef::as_ref) {
402                    if expression_references_outer(context, expression, subqueries, scopes, &ctes)?
403                    {
404                        return Ok(true);
405                    }
406                }
407                Ok(false)
408            })();
409            scopes.pop();
410            result
411        }
412        RelationalPlan::Values { rows, subqueries } => {
413            scopes.push(QueryScope {
414                qualifiers: BTreeMap::new(),
415                internal_relations: BTreeSet::new(),
416                columns: Arc::new(RelationColumns::empty_known()),
417                enclosing: None,
418            });
419            let result = (|| {
420                for expression in rows.iter().flatten() {
421                    if expression_references_outer(context, expression, subqueries, scopes, &ctes)?
422                    {
423                        return Ok(true);
424                    }
425                }
426                Ok(false)
427            })();
428            scopes.pop();
429            result
430        }
431    }
432}
433
434fn expression_has_external_reference(expr: &ScalarExpr, scopes: &[QueryScope]) -> bool {
435    match expr {
436        ScalarExpr::Column(column) => !resolves_unqualified(column, scopes),
437        ScalarExpr::QualifiedColumn { qualifier, .. } => !scopes
438            .iter()
439            .rev()
440            .any(|scope| scope.qualifiers.contains_key(qualifier)),
441        ScalarExpr::QualifiedStar(qualifier) => !scopes
442            .iter()
443            .rev()
444            .any(|scope| scope.qualifiers.contains_key(qualifier.as_str())),
445        ScalarExpr::InternalColumn(column) => !scopes
446            .iter()
447            .rev()
448            .any(|scope| scope.internal_relations.contains(&column.relation())),
449        ScalarExpr::Func {
450            binding,
451            args,
452            order_by,
453            filter,
454            ..
455        } => {
456            binding
457                .as_ref()
458                .and_then(crate::semantics::function_implicit_row_input)
459                .is_some_and(|column| {
460                    expression_has_external_reference(&ScalarExpr::InternalColumn(column), scopes)
461                })
462                || args
463                    .iter()
464                    .any(|expr| expression_has_external_reference(expr, scopes))
465                || order_by
466                    .iter()
467                    .any(|order| expression_has_external_reference(&order.expr, scopes))
468                || filter
469                    .as_deref()
470                    .is_some_and(|expr| expression_has_external_reference(expr, scopes))
471        }
472        ScalarExpr::Array(items)
473        | ScalarExpr::Row(items)
474        | ScalarExpr::CompositeRow { items, .. }
475        | ScalarExpr::And(items)
476        | ScalarExpr::Or(items) => items
477            .iter()
478            .any(|expr| expression_has_external_reference(expr, scopes)),
479        ScalarExpr::Binary { lhs, rhs, .. } => {
480            expression_has_external_reference(lhs, scopes)
481                || expression_has_external_reference(rhs, scopes)
482        }
483        ScalarExpr::Not(inner)
484        | ScalarExpr::UnaryMinus(inner)
485        | ScalarExpr::IsNull { expr: inner, .. }
486        | ScalarExpr::Cast { expr: inner, .. }
487        | ScalarExpr::Collated { expr: inner, .. } => {
488            expression_has_external_reference(inner, scopes)
489        }
490        ScalarExpr::Between { expr, low, high } => {
491            expression_has_external_reference(expr, scopes)
492                || expression_has_external_reference(low, scopes)
493                || expression_has_external_reference(high, scopes)
494        }
495        ScalarExpr::InList { expr, list, .. } => {
496            expression_has_external_reference(expr, scopes)
497                || list
498                    .iter()
499                    .any(|item| expression_has_external_reference(item, scopes))
500        }
501        ScalarExpr::WindowCall {
502            args, spec, filter, ..
503        } => window_has_external_reference(args, filter.as_deref(), spec, scopes),
504        ScalarExpr::Case {
505            base,
506            when,
507            else_branch,
508        } => {
509            base.as_deref()
510                .is_some_and(|expr| expression_has_external_reference(expr, scopes))
511                || when.iter().any(|(condition, result)| {
512                    expression_has_external_reference(condition, scopes)
513                        || expression_has_external_reference(result, scopes)
514                })
515                || else_branch
516                    .as_deref()
517                    .is_some_and(|expr| expression_has_external_reference(expr, scopes))
518        }
519        ScalarExpr::InSubquery { expr, .. } => expression_has_external_reference(expr, scopes),
520        ScalarExpr::Default
521        | ScalarExpr::Star
522        | ScalarExpr::Position(_)
523        | ScalarExpr::Literal(_)
524        | ScalarExpr::TypedLiteral { .. }
525        | ScalarExpr::RetainedLiteral(_)
526        | ScalarExpr::Param(_)
527        | ScalarExpr::ScalarSubquery(_)
528        | ScalarExpr::Exists { .. } => false,
529    }
530}
531
532fn resolves_unqualified(column: &str, scopes: &[QueryScope]) -> bool {
533    for scope in scopes.iter().rev() {
534        if scope.columns.names.contains(column) || scope.qualifiers.contains_key(column) {
535            return true;
536        }
537        if !scope.columns.complete {
538            return false;
539        }
540    }
541    false
542}
543
544/// Whether a window call's arguments, `FILTER`, keys or frame offsets refer outside the query scopes.
545fn window_has_external_reference(
546    args: &[ScalarExpr],
547    filter: Option<&ScalarExpr>,
548    spec: &crate::ScalarWindowSpec,
549    scopes: &[QueryScope],
550) -> bool {
551    args.iter()
552        .chain(filter)
553        .chain(&spec.partition_by)
554        .chain(spec.order_by.iter().map(|order| &order.expr))
555        .any(|expr| expression_has_external_reference(expr, scopes))
556        || spec.frame.as_ref().is_some_and(|frame| {
557            frame_bound_has_external_reference(&frame.start, scopes)
558                || frame_bound_has_external_reference(&frame.end, scopes)
559        })
560}
561
562fn frame_bound_has_external_reference(bound: &ScalarFrameBound, scopes: &[QueryScope]) -> bool {
563    match bound {
564        ScalarFrameBound::Preceding(expr) | ScalarFrameBound::Following(expr) => {
565            expression_has_external_reference(expr, scopes)
566        }
567        ScalarFrameBound::UnboundedPreceding
568        | ScalarFrameBound::UnboundedFollowing
569        | ScalarFrameBound::CurrentRow => false,
570    }
571}
572
573#[cfg(test)]
574mod tests;