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};
10
11use crate::plan::{ComputePlan, ProjectionPlan, QueryPlan, RelationalPlan, SourcePlan};
12use crate::SQLError;
13use crate::{ScalarExpr, ScalarFrameBound};
14
15use crate::catalog::{analysis::AnalysisCatalog, resolution::RelationNameResolution};
16use crate::semantics::projection_columns;
17
18/// A single immutable namespace and catalog view used throughout correlation analysis.
19#[derive(Clone, Copy)]
20pub struct CorrelationContext<'a> {
21    pub catalog: &'a dyn AnalysisCatalog,
22    pub resolution: &'a RelationNameResolution,
23}
24
25#[derive(Clone, Default)]
26struct RelationColumns {
27    names: BTreeSet<String>,
28    ordered: Vec<String>,
29    complete: bool,
30}
31
32impl RelationColumns {
33    fn known(ordered: Vec<String>) -> Self {
34        Self {
35            names: ordered.iter().cloned().collect(),
36            ordered,
37            complete: true,
38        }
39    }
40
41    fn empty_known() -> Self {
42        Self::known(Vec::new())
43    }
44
45    fn apply_positional_aliases(&mut self, aliases: &[String]) {
46        for (column, alias) in self.ordered.iter_mut().zip(aliases) {
47            column.clone_from(alias);
48        }
49        self.names = self.ordered.iter().cloned().collect();
50    }
51}
52
53#[derive(Clone, Default)]
54struct QueryScope {
55    qualifiers: BTreeSet<String>,
56    internal_relations: BTreeSet<crate::ast::InternalRelationId>,
57    columns: RelationColumns,
58}
59
60pub struct DecorrelatedExistsPlan {
61    pub inner: QueryPlan,
62    pub outer_keys: Vec<ScalarExpr>,
63}
64
65/// Turn a simple correlated equality EXISTS into an uncorrelated key query.
66///
67/// The caller materializes the returned inner key rows once and probes them
68/// with `outer_keys`, which is the physical equivalent of a hash semi-join.
69pub fn decorrelate_exists(
70    context: CorrelationContext<'_>,
71    plan: &QueryPlan,
72) -> Result<Option<DecorrelatedExistsPlan>, SQLError> {
73    if !plan.ctes.is_empty() {
74        return Ok(None);
75    }
76    let RelationalPlan::QueryBlock(block) = &plan.root else {
77        return Ok(None);
78    };
79    let Some(source) = block.from.as_ref() else {
80        return Ok(None);
81    };
82    if !matches!(block.compute, ComputePlan::Project)
83        || !block.group_by.is_empty()
84        || !block.grouping_sets.is_empty()
85        || block.having.is_some()
86        || block.limit.is_some()
87        || block.offset.is_some()
88        || block.distinct
89        || !block.distinct_on.is_empty()
90        || !block.subqueries.is_empty()
91    {
92        return Ok(None);
93    }
94
95    let scope = source_scope(context, source, &BTreeMap::new())?;
96    let mut source_scopes = vec![scope.clone()];
97    if source_has_external_reference(context, source, &mut source_scopes)? {
98        return Ok(None);
99    }
100    let Some(predicate) = block.r#where.as_ref() else {
101        return Ok(None);
102    };
103    let conjuncts = match predicate {
104        ScalarExpr::And(items) => items.as_slice(),
105        expression => std::slice::from_ref(expression),
106    };
107    let mut inner_keys = Vec::new();
108    let mut outer_keys = Vec::new();
109    let mut residual = Vec::new();
110    for conjunct in conjuncts {
111        if let ScalarExpr::Binary {
112            op: crate::ast::BinaryOp::Equal,
113            lhs,
114            rhs,
115        } = conjunct
116        {
117            let lhs_scope = correlation_column_scope(lhs, &scope);
118            let rhs_scope = correlation_column_scope(rhs, &scope);
119            match (lhs_scope, rhs_scope) {
120                (Some(ColumnScope::Inner), Some(ColumnScope::Outer)) => {
121                    inner_keys.push((**lhs).clone());
122                    outer_keys.push((**rhs).clone());
123                    continue;
124                }
125                (Some(ColumnScope::Outer), Some(ColumnScope::Inner)) => {
126                    inner_keys.push((**rhs).clone());
127                    outer_keys.push((**lhs).clone());
128                    continue;
129                }
130                _ => {}
131            }
132        }
133        if expression_has_external_reference(conjunct, std::slice::from_ref(&scope)) {
134            return Ok(None);
135        }
136        residual.push(conjunct.clone());
137    }
138    if inner_keys.is_empty() {
139        return Ok(None);
140    }
141
142    let mut inner = plan.clone();
143    let RelationalPlan::QueryBlock(inner_block) = &mut inner.root else {
144        unreachable!("query-block shape checked above");
145    };
146    inner_block.projections = inner_keys
147        .into_iter()
148        .map(|expr| ProjectionPlan { expr, alias: None })
149        .collect();
150    inner_block.r#where = match residual.len() {
151        0 => None,
152        1 => residual.pop(),
153        _ => Some(ScalarExpr::And(residual)),
154    };
155    inner_block.order_by.clear();
156    Ok(Some(DecorrelatedExistsPlan { inner, outer_keys }))
157}
158
159#[derive(Clone, Copy, PartialEq, Eq)]
160enum ColumnScope {
161    Inner,
162    Outer,
163}
164
165fn correlation_column_scope(expression: &ScalarExpr, scope: &QueryScope) -> Option<ColumnScope> {
166    match expression {
167        ScalarExpr::Column(column) => {
168            if scope
169                .columns
170                .names
171                .iter()
172                .any(|local| local.eq_ignore_ascii_case(column))
173                || scope
174                    .qualifiers
175                    .iter()
176                    .any(|local| local.eq_ignore_ascii_case(column))
177            {
178                Some(ColumnScope::Inner)
179            } else if scope.columns.complete {
180                Some(ColumnScope::Outer)
181            } else {
182                None
183            }
184        }
185        ScalarExpr::QualifiedColumn { qualifier, .. } => {
186            if scope
187                .qualifiers
188                .iter()
189                .any(|local| local.eq_ignore_ascii_case(qualifier))
190            {
191                Some(ColumnScope::Inner)
192            } else {
193                Some(ColumnScope::Outer)
194            }
195        }
196        ScalarExpr::InternalColumn(column) => {
197            if scope.internal_relations.contains(&column.relation()) {
198                Some(ColumnScope::Inner)
199            } else {
200                Some(ColumnScope::Outer)
201            }
202        }
203        ScalarExpr::Cast { expr, .. } | ScalarExpr::Collated { expr, .. } => {
204            correlation_column_scope(expr, scope)
205        }
206        _ => None,
207    }
208}
209
210pub fn query_depends_on_outer_row(
211    context: CorrelationContext<'_>,
212    plan: &QueryPlan,
213) -> Result<bool, SQLError> {
214    query_has_external_reference(context, plan, &mut Vec::new())
215}
216
217/// 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.
218pub(crate) fn query_depends_on_current_row(
219    context: CorrelationContext<'_>,
220    plan: &QueryPlan,
221    input: &crate::RowSchema,
222) -> Result<bool, SQLError> {
223    let mut enclosing = QueryScope {
224        columns: RelationColumns::empty_known(),
225        ..QueryScope::default()
226    };
227    for (identity, _) in input.typed_physical_alias_identities() {
228        if !input.resolves_local_column(identity.qualifier(), identity.column()) {
229            if let Some(qualifier) = identity.qualifier() {
230                enclosing.qualifiers.insert(qualifier.to_owned());
231            } else {
232                enclosing.columns.names.insert(identity.column().to_owned());
233            }
234        }
235    }
236    for (column, slot) in input.internal_identities() {
237        if !input.slot_is_local(slot) {
238            enclosing.internal_relations.insert(column.relation());
239        }
240    }
241    query_has_external_reference(context, plan, &mut vec![enclosing])
242}
243
244#[expect(
245    clippy::too_many_lines,
246    reason = "preserves scope and subquery identity"
247)]
248fn query_has_external_reference(
249    context: CorrelationContext<'_>,
250    plan: &QueryPlan,
251    scopes: &mut Vec<QueryScope>,
252) -> Result<bool, SQLError> {
253    let mut ctes = BTreeMap::new();
254    if plan.ctes.iter().any(|cte| cte.recursive) {
255        for cte in &plan.ctes {
256            let columns = if cte.columns.is_empty() {
257                cte.body
258                    .query()
259                    .map_or_else(RelationColumns::default, query_output_columns)
260            } else {
261                RelationColumns::known(cte.columns.clone())
262            };
263            ctes.insert(cte.name.clone(), columns);
264        }
265    }
266    for cte in &plan.ctes {
267        let columns = if cte.columns.is_empty() {
268            cte.body
269                .query()
270                .map_or_else(RelationColumns::default, query_output_columns)
271        } else {
272            RelationColumns::known(cte.columns.clone())
273        };
274        if cte.recursive {
275            ctes.insert(cte.name.clone(), columns.clone());
276        }
277        if cte.body.query().map_or(Ok(true), |query| {
278            query_has_external_reference(context, query, scopes)
279        })? {
280            return Ok(true);
281        }
282        ctes.insert(cte.name.clone(), columns);
283    }
284
285    match &plan.root {
286        RelationalPlan::QueryBlock(block) => {
287            let scope = match block.from.as_ref() {
288                Some(source) => source_scope(context, source, &ctes)?,
289                None => QueryScope {
290                    qualifiers: BTreeSet::new(),
291                    internal_relations: BTreeSet::new(),
292                    columns: RelationColumns::empty_known(),
293                },
294            };
295            scopes.push(scope);
296            let result = (|| {
297                for expression in block.expressions() {
298                    if expression_has_external_reference(expression, scopes) {
299                        return Ok(true);
300                    }
301                }
302                if let Some(source) = block.from.as_ref() {
303                    if source_has_external_reference(context, source, scopes)? {
304                        return Ok(true);
305                    }
306                }
307                for subquery in &block.subqueries {
308                    if query_has_external_reference(context, subquery, scopes)? {
309                        return Ok(true);
310                    }
311                }
312                Ok(false)
313            })();
314            scopes.pop();
315            result
316        }
317        RelationalPlan::SetOp {
318            left,
319            right,
320            order_by,
321            limit,
322            offset,
323            subqueries,
324            ..
325        } => {
326            if query_has_external_reference(context, left, scopes)?
327                || query_has_external_reference(context, right, scopes)?
328            {
329                return Ok(true);
330            }
331            scopes.push(QueryScope {
332                qualifiers: BTreeSet::new(),
333                internal_relations: BTreeSet::new(),
334                columns: query_output_columns(left),
335            });
336            let result = (|| {
337                for expression in order_by.iter().map(|order| &order.expr) {
338                    if expression_has_external_reference(expression, scopes) {
339                        return Ok(true);
340                    }
341                }
342                if limit
343                    .as_deref()
344                    .is_some_and(|expr| expression_has_external_reference(expr, scopes))
345                    || offset
346                        .as_deref()
347                        .is_some_and(|expr| expression_has_external_reference(expr, scopes))
348                {
349                    return Ok(true);
350                }
351                for subquery in subqueries {
352                    if query_has_external_reference(context, subquery, scopes)? {
353                        return Ok(true);
354                    }
355                }
356                Ok(false)
357            })();
358            scopes.pop();
359            result
360        }
361        RelationalPlan::Values { rows, subqueries } => {
362            scopes.push(QueryScope {
363                qualifiers: BTreeSet::new(),
364                internal_relations: BTreeSet::new(),
365                columns: RelationColumns::empty_known(),
366            });
367            let result = (|| {
368                for expression in rows.iter().flatten() {
369                    if expression_has_external_reference(expression, scopes) {
370                        return Ok(true);
371                    }
372                }
373                for subquery in subqueries {
374                    if query_has_external_reference(context, subquery, scopes)? {
375                        return Ok(true);
376                    }
377                }
378                Ok(false)
379            })();
380            scopes.pop();
381            result
382        }
383    }
384}
385
386#[expect(
387    clippy::too_many_lines,
388    reason = "preserves scope and subquery identity"
389)]
390fn source_scope(
391    context: CorrelationContext<'_>,
392    source: &SourcePlan,
393    ctes: &BTreeMap<String, RelationColumns>,
394) -> Result<QueryScope, SQLError> {
395    match source {
396        SourcePlan::Table {
397            bound_columns,
398            name,
399            qualifier,
400            alias,
401            column_aliases,
402            ..
403        } => {
404            let mut qualifiers = BTreeSet::new();
405            qualifiers.insert(alias.as_ref().unwrap_or(qualifier).clone());
406            let mut columns = match bound_columns {
407                Some(columns) => RelationColumns::known(columns.clone()),
408                None => relation_columns(context, name, ctes)?,
409            };
410            columns.apply_positional_aliases(column_aliases);
411            Ok(QueryScope {
412                qualifiers,
413                internal_relations: BTreeSet::new(),
414                columns,
415            })
416        }
417        SourcePlan::Join {
418            left,
419            right,
420            alias,
421            column_aliases,
422            ..
423        } => {
424            let left = source_scope(context, left, ctes)?;
425            let right = source_scope(context, right, ctes)?;
426            let complete = left.columns.complete && right.columns.complete;
427            let mut names = left.columns.names;
428            names.extend(right.columns.names);
429            let mut ordered = left.columns.ordered;
430            ordered.extend(right.columns.ordered);
431            let mut internal_relations = left.internal_relations;
432            internal_relations.extend(right.internal_relations);
433            if let Some(alias) = alias {
434                if !column_aliases.is_empty() {
435                    names = column_aliases.iter().cloned().collect();
436                    ordered.clone_from(column_aliases);
437                }
438                return Ok(QueryScope {
439                    qualifiers: [alias.clone()].into_iter().collect(),
440                    internal_relations,
441                    columns: RelationColumns {
442                        names,
443                        ordered,
444                        complete: complete && column_aliases.is_empty(),
445                    },
446                });
447            }
448            let mut qualifiers = left.qualifiers;
449            qualifiers.extend(right.qualifiers);
450            Ok(QueryScope {
451                qualifiers,
452                internal_relations,
453                columns: RelationColumns {
454                    names,
455                    ordered,
456                    complete,
457                },
458            })
459        }
460        SourcePlan::Values {
461            rows,
462            alias,
463            column_aliases,
464            internal_relation,
465            ..
466        } => {
467            if let Some(internal_relation) = internal_relation {
468                return Ok(QueryScope {
469                    qualifiers: BTreeSet::new(),
470                    internal_relations: [*internal_relation].into_iter().collect(),
471                    columns: RelationColumns::empty_known(),
472                });
473            }
474            let qualifiers = alias.iter().cloned().collect();
475            let columns = if column_aliases.is_empty() {
476                (0..rows.first().map_or(0, Vec::len))
477                    .map(|index| format!("column{}", index + 1))
478                    .collect::<Vec<_>>()
479            } else {
480                column_aliases.clone()
481            };
482            Ok(QueryScope {
483                qualifiers,
484                internal_relations: BTreeSet::new(),
485                columns: RelationColumns::known(columns),
486            })
487        }
488        SourcePlan::Function {
489            name,
490            output_name,
491            alias,
492            column_aliases,
493            ..
494        } => {
495            let qualifiers = [alias.as_ref().unwrap_or(output_name).clone()]
496                .into_iter()
497                .collect();
498            let mut names: BTreeSet<String> = column_aliases.iter().cloned().collect();
499            let complete = !column_aliases.is_empty()
500                || matches!(
501                    name.to_ascii_lowercase().as_str(),
502                    "generate_series"
503                        | "unnest"
504                        | "regexp_matches"
505                        | "regexp_split_to_table"
506                        | "string_to_table"
507                );
508            if names.is_empty() && complete {
509                names.insert(output_name.clone());
510            }
511            Ok(QueryScope {
512                qualifiers,
513                internal_relations: BTreeSet::new(),
514                columns: RelationColumns {
515                    ordered: names.iter().cloned().collect(),
516                    names,
517                    complete,
518                },
519            })
520        }
521        SourcePlan::FunctionGroup {
522            functions,
523            alias,
524            column_aliases,
525            ordinality,
526        } => {
527            let qualifier = alias.clone().or_else(|| {
528                functions
529                    .first()
530                    .map(|function| function.output_name.clone())
531            });
532            let qualifiers = qualifier.into_iter().collect();
533            let mut names = Vec::new();
534            let mut complete = true;
535            for function in functions {
536                if function.column_aliases.is_empty() {
537                    let local = crate::semantics::builtin_function_dispatch_name(&function.name);
538                    if matches!(
539                        local.as_str(),
540                        "generate_series"
541                            | "unnest"
542                            | "regexp_matches"
543                            | "regexp_split_to_table"
544                            | "string_to_table"
545                    ) {
546                        names.push(function.output_name.clone());
547                    } else {
548                        complete = false;
549                    }
550                } else {
551                    names.extend(function.column_aliases.iter().cloned());
552                }
553            }
554            if *ordinality {
555                names.push("ordinality".into());
556            }
557            for (name, alias) in names.iter_mut().zip(column_aliases) {
558                name.clone_from(alias);
559            }
560            let column_names = names.iter().cloned().collect();
561            Ok(QueryScope {
562                qualifiers,
563                internal_relations: BTreeSet::new(),
564                columns: RelationColumns {
565                    names: column_names,
566                    ordered: names,
567                    complete,
568                },
569            })
570        }
571        SourcePlan::Subquery {
572            body,
573            alias,
574            column_aliases,
575        } => {
576            let qualifiers = alias.iter().cloned().collect();
577            let columns = if column_aliases.is_empty() {
578                query_output_columns(body)
579            } else {
580                RelationColumns {
581                    names: column_aliases.iter().cloned().collect(),
582                    ordered: column_aliases.clone(),
583                    complete: true,
584                }
585            };
586            Ok(QueryScope {
587                qualifiers,
588                internal_relations: BTreeSet::new(),
589                columns,
590            })
591        }
592    }
593}
594
595fn relation_columns(
596    context: CorrelationContext<'_>,
597    name: &str,
598    ctes: &BTreeMap<String, RelationColumns>,
599) -> Result<RelationColumns, SQLError> {
600    if let Some(columns) = ctes
601        .iter()
602        .find(|(cte, _)| cte.eq_ignore_ascii_case(name))
603        .map(|(_, columns)| columns)
604    {
605        return Ok(columns.clone());
606    }
607    let catalog = context.catalog;
608    let resolution = context.resolution;
609    if let Some(columns) = catalog.virtual_relation_schema(resolution, name)? {
610        return Ok(RelationColumns::known(
611            columns.into_iter().map(|(name, _)| name).collect(),
612        ));
613    }
614    if let Ok(Some(table)) = catalog.table_resolved(resolution, name) {
615        return Ok(RelationColumns::known(
616            table
617                .columns
618                .iter()
619                .map(|column| column.name.clone())
620                .collect(),
621        ));
622    }
623    if let Some(view) = catalog.view_resolved(resolution, name)? {
624        return Ok(if view.materialized {
625            RelationColumns::known(view.output_columns.unwrap_or_default())
626        } else {
627            query_output_columns(&view.query)
628        });
629    }
630    if let Ok(Some(table)) = catalog.foreign_table_resolved(resolution, name) {
631        return Ok(RelationColumns::known(
632            table
633                .columns
634                .iter()
635                .map(|column| column.name.clone())
636                .collect(),
637        ));
638    }
639    Ok(RelationColumns::default())
640}
641
642fn source_has_external_reference(
643    context: CorrelationContext<'_>,
644    source: &SourcePlan,
645    scopes: &mut Vec<QueryScope>,
646) -> Result<bool, SQLError> {
647    match source {
648        SourcePlan::Join {
649            left, right, on, ..
650        } => Ok(source_has_external_reference(context, left, scopes)?
651            || source_has_external_reference(context, right, scopes)?
652            || on
653                .as_ref()
654                .is_some_and(|expr| expression_has_external_reference(expr, scopes))),
655        SourcePlan::Values { rows, .. } => Ok(rows
656            .iter()
657            .flatten()
658            .any(|expr| expression_has_external_reference(expr, scopes))),
659        SourcePlan::Function { args, .. } => Ok(args
660            .iter()
661            .any(|expr| expression_has_external_reference(expr, scopes))),
662        SourcePlan::FunctionGroup { functions, .. } => Ok(functions.iter().any(|function| {
663            function
664                .args
665                .iter()
666                .any(|expr| expression_has_external_reference(expr, scopes))
667        })),
668        SourcePlan::Subquery { body, .. } => query_has_external_reference(context, body, scopes),
669        SourcePlan::Table { .. } => Ok(false),
670    }
671}
672
673fn query_output_columns(plan: &QueryPlan) -> RelationColumns {
674    match &plan.root {
675        RelationalPlan::QueryBlock(block) => {
676            let ordered = projection_columns(&block.projections);
677            RelationColumns {
678                names: ordered.iter().cloned().collect(),
679                ordered,
680                complete: !block
681                    .projections
682                    .iter()
683                    .any(|projection| matches!(projection.expr, ScalarExpr::Star)),
684            }
685        }
686        RelationalPlan::SetOp { left, .. } => query_output_columns(left),
687        RelationalPlan::Values { rows, .. } => RelationColumns::known(
688            (0..rows.first().map_or(0, Vec::len))
689                .map(|index| format!("column{}", index + 1))
690                .collect(),
691        ),
692    }
693}
694
695fn expression_has_external_reference(expr: &ScalarExpr, scopes: &[QueryScope]) -> bool {
696    match expr {
697        ScalarExpr::Column(column) => !resolves_unqualified(column, scopes),
698        ScalarExpr::QualifiedColumn { qualifier, .. } => !scopes.iter().rev().any(|scope| {
699            scope
700                .qualifiers
701                .iter()
702                .any(|local| local.eq_ignore_ascii_case(qualifier))
703        }),
704        ScalarExpr::QualifiedStar(qualifier) => !scopes.iter().rev().any(|scope| {
705            scope
706                .qualifiers
707                .iter()
708                .any(|local| local.eq_ignore_ascii_case(qualifier))
709        }),
710        ScalarExpr::InternalColumn(column) => !scopes
711            .iter()
712            .rev()
713            .any(|scope| scope.internal_relations.contains(&column.relation())),
714        ScalarExpr::Func {
715            binding,
716            args,
717            order_by,
718            filter,
719            ..
720        } => {
721            binding
722                .as_ref()
723                .and_then(crate::semantics::function_implicit_row_input)
724                .is_some_and(|column| {
725                    expression_has_external_reference(&ScalarExpr::InternalColumn(column), scopes)
726                })
727                || args
728                    .iter()
729                    .any(|expr| expression_has_external_reference(expr, scopes))
730                || order_by
731                    .iter()
732                    .any(|order| expression_has_external_reference(&order.expr, scopes))
733                || filter
734                    .as_deref()
735                    .is_some_and(|expr| expression_has_external_reference(expr, scopes))
736        }
737        ScalarExpr::Array(items)
738        | ScalarExpr::Row(items)
739        | ScalarExpr::CompositeRow { items, .. }
740        | ScalarExpr::And(items)
741        | ScalarExpr::Or(items) => items
742            .iter()
743            .any(|expr| expression_has_external_reference(expr, scopes)),
744        ScalarExpr::Binary { lhs, rhs, .. } => {
745            expression_has_external_reference(lhs, scopes)
746                || expression_has_external_reference(rhs, scopes)
747        }
748        ScalarExpr::Not(inner)
749        | ScalarExpr::UnaryMinus(inner)
750        | ScalarExpr::IsNull { expr: inner, .. }
751        | ScalarExpr::Cast { expr: inner, .. }
752        | ScalarExpr::Collated { expr: inner, .. } => {
753            expression_has_external_reference(inner, scopes)
754        }
755        ScalarExpr::Between { expr, low, high } => {
756            expression_has_external_reference(expr, scopes)
757                || expression_has_external_reference(low, scopes)
758                || expression_has_external_reference(high, scopes)
759        }
760        ScalarExpr::InList { expr, list, .. } => {
761            expression_has_external_reference(expr, scopes)
762                || list
763                    .iter()
764                    .any(|item| expression_has_external_reference(item, scopes))
765        }
766        ScalarExpr::WindowCall {
767            args, spec, filter, ..
768        } => window_has_external_reference(args, filter.as_deref(), spec, scopes),
769        ScalarExpr::Case {
770            base,
771            when,
772            else_branch,
773        } => {
774            base.as_deref()
775                .is_some_and(|expr| expression_has_external_reference(expr, scopes))
776                || when.iter().any(|(condition, result)| {
777                    expression_has_external_reference(condition, scopes)
778                        || expression_has_external_reference(result, scopes)
779                })
780                || else_branch
781                    .as_deref()
782                    .is_some_and(|expr| expression_has_external_reference(expr, scopes))
783        }
784        ScalarExpr::InSubquery { expr, .. } => expression_has_external_reference(expr, scopes),
785        ScalarExpr::Default
786        | ScalarExpr::Star
787        | ScalarExpr::Position(_)
788        | ScalarExpr::Literal(_)
789        | ScalarExpr::TypedLiteral { .. }
790        | ScalarExpr::Param(_)
791        | ScalarExpr::ScalarSubquery(_)
792        | ScalarExpr::Exists { .. } => false,
793    }
794}
795
796fn resolves_unqualified(column: &str, scopes: &[QueryScope]) -> bool {
797    for scope in scopes.iter().rev() {
798        if scope
799            .columns
800            .names
801            .iter()
802            .any(|local| local.eq_ignore_ascii_case(column))
803            || scope
804                .qualifiers
805                .iter()
806                .any(|local| local.eq_ignore_ascii_case(column))
807        {
808            return true;
809        }
810        if !scope.columns.complete {
811            return false;
812        }
813    }
814    false
815}
816
817/// Whether a window call's arguments, `FILTER`, keys or frame offsets refer outside the query scopes.
818fn window_has_external_reference(
819    args: &[ScalarExpr],
820    filter: Option<&ScalarExpr>,
821    spec: &crate::ScalarWindowSpec,
822    scopes: &[QueryScope],
823) -> bool {
824    args.iter()
825        .chain(filter)
826        .chain(&spec.partition_by)
827        .chain(spec.order_by.iter().map(|order| &order.expr))
828        .any(|expr| expression_has_external_reference(expr, scopes))
829        || spec.frame.as_ref().is_some_and(|frame| {
830            frame_bound_has_external_reference(&frame.start, scopes)
831                || frame_bound_has_external_reference(&frame.end, scopes)
832        })
833}
834
835fn frame_bound_has_external_reference(bound: &ScalarFrameBound, scopes: &[QueryScope]) -> bool {
836    match bound {
837        ScalarFrameBound::Preceding(expr) | ScalarFrameBound::Following(expr) => {
838            expression_has_external_reference(expr, scopes)
839        }
840        ScalarFrameBound::UnboundedPreceding
841        | ScalarFrameBound::UnboundedFollowing
842        | ScalarFrameBound::CurrentRow => false,
843    }
844}
845
846#[cfg(test)]
847mod tests {
848    use super::*;
849
850    #[test]
851    fn implicit_action_inputs_preserve_their_enclosing_row_identity() {
852        let binding = crate::binding::fixture::empty_binding_context();
853        let context = CorrelationContext {
854            catalog: binding.catalog.as_ref(),
855            resolution: &binding.resolution,
856        };
857        for (sql, expected) in [
858            ("SELECT merge_action()", true),
859            ("SELECT lower(merge_action())", true),
860            ("SELECT (SELECT merge_action())", true),
861            ("SELECT public.merge_action()", false),
862            ("SELECT \"merge_action\"()", false),
863            ("SELECT lower('constant')", false),
864        ] {
865            let crate::plan::UnifiedPlan::Query(query) =
866                crate::plan::UnifiedPlan::lower(crate::compile(sql).unwrap().remove(0))
867            else {
868                panic!("query")
869            };
870            assert_eq!(
871                query_depends_on_outer_row(context, &query).unwrap(),
872                expected,
873                "{sql}"
874            );
875            let mut enclosing = QueryScope::default();
876            enclosing
877                .internal_relations
878                .insert(crate::semantics::merge_action_attribute().relation());
879            assert!(
880                !query_has_external_reference(context, &query, &mut vec![enclosing]).unwrap(),
881                "{sql}"
882            );
883        }
884    }
885
886    #[test]
887    fn table_range_aliases_replace_physical_correlation_names() {
888        let crate::ast::Statement::CreateTable(definition) =
889            crate::compile("CREATE TABLE correlation_alias_source(id INTEGER, label TEXT)")
890                .unwrap()
891                .remove(0)
892        else {
893            panic!("expected table definition")
894        };
895        let catalog = crate::binding::fixture::catalog(BTreeMap::from([(
896            crate::RelationIdentity::from_legacy_name("public.correlation_alias_source").unwrap(),
897            crate::binding::fixture::table_definition(definition.columns),
898        )]));
899        let resolution =
900            crate::binding::fixture::resolution(vec!["public".into()], "pg_temp_1".into());
901        let context = CorrelationContext {
902            catalog: catalog.as_ref(),
903            resolution: &resolution,
904        };
905        let source = SourcePlan::Table {
906            bound_columns: None,
907            name: "correlation_alias_source".into(),
908            qualifier: "correlation_alias_source".into(),
909            alias: Some("source".into()),
910            column_aliases: vec!["key".into(), "value".into()],
911            include_descendants: true,
912        };
913        let scope = source_scope(context, &source, &BTreeMap::new()).unwrap();
914        assert_eq!(
915            scope.columns.names,
916            BTreeSet::from(["key".to_string(), "value".to_string()])
917        );
918    }
919}