Skip to main content

uqa_sql/semantics/
cte_strategy.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Shared CTE scheduling decisions for execution and traversal analysis.
8
9use crate::{
10    ast::CteMaterialization,
11    plan::{CtePlan, QueryPlan},
12    semantics::{
13        cte_order::analysis::CteAnalysis,
14        volatility::{query_contains_volatile_function, VolatilityCatalog},
15    },
16    SQLError,
17};
18use std::collections::BTreeSet;
19use uqa_core::memory::{Produced, ProductionControl, ProductionVec};
20
21#[derive(Clone, Copy, Debug)]
22pub struct ScheduledCte<'a> {
23    pub plan: &'a CtePlan,
24    pub deferred: bool,
25}
26
27pub fn schedule_plan_ctes<'a>(
28    catalog: &dyn VolatilityCatalog,
29    plan: &'a QueryPlan,
30) -> Result<Vec<ScheduledCte<'a>>, SQLError> {
31    Ok(
32        schedule_plan_ctes_with_control(catalog, plan, ProductionControl::uncontrolled())?
33            .into_uncontrolled()
34            .expect("ordinary CTE schedule"),
35    )
36}
37
38pub fn schedule_plan_ctes_with_control<'a>(
39    catalog: &dyn VolatilityCatalog,
40    plan: &'a QueryPlan,
41    control: ProductionControl<'_>,
42) -> Result<Produced<Vec<ScheduledCte<'a>>>, SQLError> {
43    let analysis = CteAnalysis::query(plan, control)?;
44    let ordered = analysis.order()?;
45    let reachable = analysis.reachable()?;
46    let mut scheduled = ProductionVec::new(control);
47    for index in ordered.iter().copied() {
48        control.check()?;
49        if !reachable[index] {
50            continue;
51        }
52        let cte = &plan.ctes[index];
53        let deferred = !cte.body.modifies_data()
54            && !analysis.recursive(index)
55            && match cte.materialization {
56                CteMaterialization::Default => analysis.single_reference(index),
57                CteMaterialization::Materialized => false,
58                CteMaterialization::NotMaterialized => true,
59            }
60            && matches!(
61                cte.body
62                    .query()
63                    .map_or(Ok(true), |query| query_contains_volatile_function(
64                        catalog, query
65                    )),
66                Ok(false)
67            );
68        scheduled.push_copy(ScheduledCte {
69            plan: cte,
70            deferred,
71        })?;
72    }
73    Ok(scheduled.finish()?)
74}
75
76/// Materialized WITH items split by native execution time: read dependencies precede the primary query; unread mutations finish afterward, last defined first.
77#[derive(Debug)]
78pub struct StatementCteOrder<'a> {
79    pub primary: Vec<&'a CtePlan>,
80    pub postponed: Vec<&'a CtePlan>,
81}
82
83pub fn order_statement_ctes<'a>(
84    ctes: &'a [CtePlan],
85    scheduled: Vec<&'a CtePlan>,
86    primary_references: &BTreeSet<String>,
87) -> StatementCteOrder<'a> {
88    order_statement_ctes_with_control(
89        ctes,
90        scheduled,
91        primary_references.iter().map(String::as_str),
92        ProductionControl::uncontrolled(),
93    )
94    .expect("ordinary statement CTE order")
95    .into_uncontrolled()
96    .expect("ordinary statement CTE owner")
97}
98
99/// Allocate dependency and ordering scratch under the invoking owner, retaining both returned arrays with that allowance.
100pub fn order_statement_ctes_with_control<'a, 'n>(
101    ctes: &'a [CtePlan],
102    scheduled: impl IntoIterator<Item = &'a CtePlan>,
103    primary_references: impl IntoIterator<Item = &'n str>,
104    control: ProductionControl<'_>,
105) -> Result<Produced<StatementCteOrder<'a>>, SQLError> {
106    let mut retained = ProductionVec::new(control);
107    for plan in scheduled {
108        retained.push_copy(plan)?;
109    }
110    let mut primary = ProductionVec::new(control);
111    let mut postponed = ProductionVec::new(control);
112    if retained.iter().any(|cte| cte.body.modifies_data()) {
113        let mut analysis = CteAnalysis::new(ctes, control)?;
114        analysis.set_primary_names(primary_references)?;
115        let read = analysis.closure(analysis.primary_indices())?;
116        let mut deferred = ProductionVec::new(control);
117        for _ in ctes {
118            deferred.push_copy(false)?;
119        }
120        for (index, cte) in ctes.iter().enumerate().rev() {
121            control.check()?;
122            if !cte.body.modifies_data() || read[index] {
123                continue;
124            }
125            let needed = analysis.closure(std::iter::once(index))?;
126            for plan in retained.iter().copied() {
127                control.check()?;
128                if let Some(index) = analysis.index(&plan.name) {
129                    if needed[index] && !read[index] && !deferred[index] {
130                        postponed.push_copy(plan)?;
131                        deferred.as_mut_slice()[index] = true;
132                    }
133                }
134            }
135        }
136        for plan in retained.iter().copied() {
137            control.check()?;
138            if !analysis
139                .index(&plan.name)
140                .is_some_and(|index| deferred[index])
141            {
142                primary.push_copy(plan)?;
143            }
144        }
145    } else {
146        primary = retained;
147    }
148    let (primary, primary_memory) = primary.finish()?.into_parts();
149    let (postponed, postponed_memory) = postponed.finish()?.into_parts();
150    Ok(control.finish(
151        StatementCteOrder { primary, postponed },
152        control.combine(primary_memory, postponed_memory),
153    )?)
154}
155
156#[cfg(test)]
157mod tests;