Skip to main content

uqa_execution/query/
ordering.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Physical output positions and ordering expression identities.
8
9use crate::query::projection::{projection_target_expression, visible_projection_source_position};
10use crate::query::row_at_a_time::RowAtATime;
11use crate::query::{OutputColumnMapping, PhysicalProjection};
12use crate::{ProjectionTarget, ScalarExpr, SharedExpressionEvaluator};
13use std::collections::HashSet;
14use uqa_core::Value;
15use uqa_sql::{
16    plan::{ProjectionPlan, QueryBlockPlan},
17    semantics::projection_columns,
18    SQLError,
19};
20
21pub use uqa_sql::semantics::output_position_error;
22
23/// Build collision-free physical target columns for a plain SELECT whose ORDER BY must be able to see both input columns and SELECT-list aliases. Public aliases cannot safely be appended directly: `SELECT x + 1 AS x ... ORDER BY x` must order by the output alias, while `ORDER BY x + 1` still resolves `x` against the input namespace. Each non-star target is therefore computed once under an opaque internal attribute and assigned its public label only after Sort/Limit has consumed it.
24pub fn order_projection(
25    projections: &[ProjectionPlan],
26    input_schema: &crate::RowSchema,
27) -> Result<(Vec<PhysicalProjection>, Vec<OutputColumnMapping>), SQLError> {
28    let labels = projection_columns(projections);
29    let mut physical = Vec::new();
30    let mut output = Vec::new();
31    let internal_relation = uqa_sql::ast::InternalRelationId::allocate();
32    let mut next_internal_attribute = 0usize;
33
34    for (index, projection) in projections.iter().enumerate() {
35        if matches!(projection.expr, ScalarExpr::Star) {
36            for (position, column) in input_schema.columns().iter().enumerate() {
37                if visible_projection_source_position(input_schema, position) {
38                    output.push((
39                        input_schema
40                            .public_name(position)
41                            .unwrap_or(column)
42                            .to_string(),
43                        ScalarExpr::Position(position),
44                    ));
45                }
46            }
47            continue;
48        }
49        if let ScalarExpr::QualifiedStar(qualifier) = &projection.expr {
50            let columns = input_schema.qualified_star_position_layout(qualifier);
51            if columns.is_empty() {
52                return Err(SQLError::UnknownTable(qualifier.clone()));
53            }
54            for (column, logical, _, _) in columns {
55                if logical.is_some_and(|position| {
56                    !visible_projection_source_position(input_schema, position)
57                }) {
58                    continue;
59                }
60                if let Some(logical) = logical {
61                    output.push((column, ScalarExpr::Position(logical)));
62                    continue;
63                }
64                let internal = internal_relation.column(next_internal_attribute);
65                next_internal_attribute += 1;
66                physical.push((
67                    ProjectionTarget::Internal(internal),
68                    ScalarExpr::qualified_column(qualifier, &column),
69                ));
70                output.push((column, ScalarExpr::InternalColumn(internal)));
71            }
72            continue;
73        }
74
75        if let ScalarExpr::Column(source) = &projection.expr {
76            if &labels[index] == source {
77                if let Some(position) = input_schema.unqualified_position(source) {
78                    output.push((labels[index].clone(), ScalarExpr::Position(position)));
79                    continue;
80                }
81            }
82        }
83        if let ScalarExpr::QualifiedColumn { qualifier, column } = &projection.expr {
84            if &labels[index] == column {
85                if let Some(position) = input_schema.qualified_position(qualifier, column) {
86                    output.push((labels[index].clone(), ScalarExpr::Position(position)));
87                    continue;
88                }
89            }
90        }
91
92        let internal = internal_relation.column(next_internal_attribute);
93        next_internal_attribute += 1;
94        physical.push((
95            ProjectionTarget::Internal(internal),
96            projection.expr.clone(),
97        ));
98        output.push((labels[index].clone(), ScalarExpr::InternalColumn(internal)));
99    }
100    Ok((physical, output))
101}
102
103pub fn identity_order_columns(columns: &[String]) -> Vec<OutputColumnMapping> {
104    columns
105        .iter()
106        .enumerate()
107        .map(|(position, column)| (column.clone(), ScalarExpr::Position(position)))
108        .collect()
109}
110
111pub fn output_selection_positions(
112    schema: &crate::RowSchema,
113    output: Vec<OutputColumnMapping>,
114) -> Result<Vec<(String, usize)>, SQLError> {
115    output
116        .into_iter()
117        .map(|(label, source)| {
118            let position = match source {
119                ScalarExpr::Position(position) if position < schema.len() => {
120                    schema.physical_slot(position)
121                }
122                ScalarExpr::Column(column) => schema
123                    .position(&column)
124                    .and_then(|logical| schema.physical_slot(logical)),
125                ScalarExpr::InternalColumn(column) => schema.internal_slot(column),
126                _ => None,
127            }
128            .ok_or_else(|| {
129                SQLError::Internal(format!(
130                    "bound output column `{label}` is unavailable in the physical row"
131                ))
132            })?;
133            Ok((label, position))
134        })
135        .collect()
136}
137
138pub fn resolve_order_expression(
139    expression: &ScalarExpr,
140    output_columns: &[OutputColumnMapping],
141) -> Result<ScalarExpr, SQLError> {
142    match expression {
143        ScalarExpr::Literal(Value::Int(position)) => {
144            let index = uqa_sql::semantics::query_output_position(
145                *position,
146                output_columns.len(),
147                "ORDER BY",
148            )?;
149            Ok(output_columns[index].1.clone())
150        }
151        ScalarExpr::Column(name) => {
152            let mut matches = output_columns.iter().filter(|(output, _)| output == name);
153            let Some((_, physical)) = matches.next() else {
154                return Ok(expression.clone());
155            };
156            if matches.next().is_some() {
157                return Err(SQLError::AmbiguousColumn(name.clone()));
158            }
159            Ok(physical.clone())
160        }
161        _ => Ok(expression.clone()),
162    }
163}
164
165#[derive(Clone, Copy)]
166pub struct OutputTarget {
167    pub position: usize,
168    pub direct: bool,
169}
170
171pub fn output_target_position(
172    statement: &QueryBlockPlan,
173    expression: &ScalarExpr,
174    output: &[OutputColumnMapping],
175) -> Result<Option<OutputTarget>, SQLError> {
176    output_target_position_for(statement, expression, output, "ORDER BY")
177}
178
179pub fn distinct_output_target_position(
180    statement: &QueryBlockPlan,
181    expression: &ScalarExpr,
182    output: &[OutputColumnMapping],
183) -> Result<Option<OutputTarget>, SQLError> {
184    output_target_position_for(statement, expression, output, "DISTINCT ON")
185}
186
187fn output_target_position_for(
188    statement: &QueryBlockPlan,
189    expression: &ScalarExpr,
190    output: &[OutputColumnMapping],
191    clause: &str,
192) -> Result<Option<OutputTarget>, SQLError> {
193    match expression {
194        ScalarExpr::Literal(Value::Int(position)) => {
195            let position =
196                uqa_sql::semantics::query_output_position(*position, output.len(), clause)?;
197            return Ok(Some(OutputTarget {
198                position,
199                direct: true,
200            }));
201        }
202        ScalarExpr::Column(name) => {
203            let mut matches = output
204                .iter()
205                .enumerate()
206                .filter(|(_, (label, _))| label == name);
207            if let Some((position, _)) = matches.next() {
208                if matches.next().is_some() {
209                    return Err(SQLError::AmbiguousColumn(name.clone()));
210                }
211                return Ok(Some(OutputTarget {
212                    position,
213                    direct: true,
214                }));
215            }
216        }
217        _ => {}
218    }
219    if statement.projections.len() != output.len() {
220        return Ok(None);
221    }
222    Ok(statement
223        .projections
224        .iter()
225        .position(|projection| {
226            uqa_sql::semantics::aggregates::exprs_match(&projection.expr, expression)
227        })
228        .map(|position| OutputTarget {
229            position,
230            direct: false,
231        }))
232}
233
234pub fn one_based_output_position(position: usize) -> Result<ScalarExpr, SQLError> {
235    let position = position
236        .checked_add(1)
237        .and_then(|position| i64::try_from(position).ok())
238        .ok_or_else(|| SQLError::Internal("SELECT output position exceeds i64".into()))?;
239    Ok(ScalarExpr::Literal(Value::Int(position)))
240}
241
242fn distinct_key_expressions_match(
243    statement: &QueryBlockPlan,
244    left: &ScalarExpr,
245    right: &ScalarExpr,
246    output: &[OutputColumnMapping],
247    right_is_order_by: bool,
248) -> Result<bool, SQLError> {
249    let left_target = distinct_output_target_position(statement, left, output)?;
250    let right_target = if right_is_order_by {
251        output_target_position(statement, right, output)?
252    } else {
253        distinct_output_target_position(statement, right, output)?
254    };
255    match (left_target, right_target) {
256        (Some(left), Some(right)) => Ok(left.position == right.position),
257        (None, None) => Ok(uqa_sql::semantics::aggregates::exprs_match(
258            &resolve_order_expression(left, output)?,
259            &resolve_order_expression(right, output)?,
260        )),
261        _ => Ok(false),
262    }
263}
264
265pub fn prior_distinct_key_index(
266    statement: &QueryBlockPlan,
267    index: usize,
268    expression: &ScalarExpr,
269    output: &[OutputColumnMapping],
270) -> Result<Option<usize>, SQLError> {
271    for (prior, candidate) in statement.distinct_on[..index].iter().enumerate() {
272        if distinct_key_expressions_match(statement, candidate, expression, output, false)? {
273            return Ok(Some(prior));
274        }
275    }
276    Ok(None)
277}
278
279pub fn validate_distinct_ordering(statement: &QueryBlockPlan) -> Result<(), SQLError> {
280    if !statement.distinct || statement.order_by.is_empty() {
281        return Ok(());
282    }
283    let output = identity_order_columns(&projection_columns(&statement.projections));
284    if statement.distinct_on.is_empty() {
285        if statement
286            .order_by
287            .iter()
288            .try_fold(false, |invalid, order| {
289                Ok::<_, SQLError>(
290                    invalid || output_target_position(statement, &order.expr, &output)?.is_none(),
291                )
292            })?
293        {
294            return Err(SQLError::Routine {
295                sqlstate: "42P10".into(),
296                message: "for SELECT DISTINCT, ORDER BY expressions must appear in select list"
297                    .into(),
298            });
299        }
300        return Ok(());
301    }
302    let mut matched = vec![false; statement.distinct_on.len()];
303    let mut encountered_non_distinct = false;
304    for order in &statement.order_by {
305        let mut order_is_distinct = false;
306        for (index, expression) in statement.distinct_on.iter().enumerate() {
307            if distinct_key_expressions_match(statement, expression, &order.expr, &output, true)? {
308                order_is_distinct = true;
309                matched[index] = true;
310            }
311        }
312        if order_is_distinct {
313            if encountered_non_distinct {
314                return Err(distinct_on_ordering_error());
315            }
316        } else {
317            encountered_non_distinct = true;
318        }
319    }
320    if encountered_non_distinct && matched.iter().any(|matched| !matched) {
321        return Err(distinct_on_ordering_error());
322    }
323    Ok(())
324}
325
326fn distinct_on_ordering_error() -> SQLError {
327    SQLError::Routine {
328        sqlstate: "42P10".into(),
329        message: "SELECT DISTINCT ON expressions must match initial ORDER BY expressions".into(),
330    }
331}
332
333pub fn split_locking_order_projections(
334    statement: &QueryBlockPlan,
335    output: &[OutputColumnMapping],
336    physical: Vec<PhysicalProjection>,
337) -> Result<
338    (
339        QueryBlockPlan,
340        Vec<PhysicalProjection>,
341        Vec<PhysicalProjection>,
342    ),
343    SQLError,
344> {
345    let (sort_statement, required) = order_projection_targets(statement, output, &physical)?;
346    let (before_sort, after_sort) = physical
347        .into_iter()
348        .partition(|(target, _)| required.contains(target));
349    Ok((sort_statement, before_sort, after_sort))
350}
351
352pub fn order_projection_targets(
353    statement: &QueryBlockPlan,
354    output: &[OutputColumnMapping],
355    physical: &[PhysicalProjection],
356) -> Result<(QueryBlockPlan, HashSet<ProjectionTarget>), SQLError> {
357    let mut sort_statement = statement.clone();
358    let mut required = HashSet::new();
359    for (index, order) in statement.order_by.iter().enumerate() {
360        let expression = resolve_order_expression(&order.expr, output)?;
361        if let Some((target, _)) = physical.iter().find(|(target, _)| {
362            uqa_sql::semantics::aggregates::exprs_match(
363                &projection_target_expression(target),
364                &expression,
365            )
366        }) {
367            required.insert(target.clone());
368            sort_statement.order_by[index].expr = projection_target_expression(target);
369            continue;
370        }
371        if let ScalarExpr::Column(column) = &expression {
372            let target = ProjectionTarget::Column(column.clone());
373            if physical.iter().any(|(candidate, _)| candidate == &target) {
374                required.insert(target);
375                continue;
376            }
377        }
378        if let Some((target, _)) = physical.iter().find(|(_, projected)| {
379            uqa_sql::semantics::aggregates::exprs_match(projected, &expression)
380        }) {
381            required.insert(target.clone());
382            sort_statement.order_by[index].expr = projection_target_expression(target);
383        }
384    }
385    Ok((sort_statement, required))
386}
387
388pub fn append_row_at_time_projection<'a>(
389    operator: Box<dyn crate::PhysicalOperator + 'a>,
390    projections: Vec<PhysicalProjection>,
391    evaluator: SharedExpressionEvaluator<'a>,
392) -> Box<dyn crate::PhysicalOperator + 'a> {
393    if projections.is_empty() {
394        return operator;
395    }
396    Box::new(crate::Project::appending_target_evaluator(
397        Box::new(RowAtATime::new(operator)),
398        projections,
399        evaluator,
400    ))
401}
402
403#[cfg(test)]
404mod tests;