1use 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#[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
33pub 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
79pub 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
226pub 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
261pub(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 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
544fn 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;