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