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