1#[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#[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
40pub 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
50pub 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
220pub 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
237pub 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
281pub(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 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;