Skip to main content

uqa_execution/
window.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! SQL window function evaluation. Window calls that partition and order their rows the same way share one sort, as the functions of one `WindowAgg` do, and each sorted partition is evaluated row by row with the frame semantics of `nodeWindowAgg.c`.
8
9use crate::scalar::plan::{PlanSubqueryArena, QueryExpressionContext};
10use crate::spill::BufferedIndexedSpill;
11use crate::RowSchemaExecution;
12use crate::{
13    eval_scalar, Batch, ExternalSort, PhysicalOperator, PhysicalRow, RowSchema, ScalarEvalContext,
14    ScalarExpr, ScalarFrameBound, ScalarOrder, ScalarSubqueryRunner, ScalarWindowSpec, SortKey,
15    SpillBuffer, SpillScan, WindowExecutor,
16};
17use uqa_core::Value;
18use uqa_sql::ast::{ColumnType, FrameExclusion, FrameMode, NullsOrder};
19use uqa_sql::plan::ProjectionPlan;
20use uqa_sql::semantics::projection_columns;
21use uqa_sql::{SQLError, SQLParam};
22
23mod aggregates;
24mod frame;
25mod functions;
26mod partition;
27mod planning;
28
29pub use planning::expr_has_window;
30use planning::rewrite_window_expr;
31
32use frame::{BoundKind, CurrentRow, FrameSpec};
33use functions::{WindowFunction, WindowFunctionState};
34use partition::PartitionRows;
35
36#[derive(Clone)]
37struct WindowSlot {
38    column: uqa_sql::ast::InternalColumnRef,
39    name: String,
40    args: Vec<ScalarExpr>,
41    spec: ScalarWindowSpec,
42    /// An aggregate's `FILTER (WHERE ...)` condition.
43    filter: Option<ScalarExpr>,
44}
45
46impl WindowSlot {
47    fn call(&self) -> ScalarExpr {
48        ScalarExpr::WindowCall {
49            name: self.name.clone(),
50            args: self.args.clone(),
51            spec: self.spec.clone(),
52            filter: self.filter.clone().map(Box::new),
53            modifiers: uqa_sql::ast::WindowCallModifiers::default(),
54        }
55    }
56}
57
58/// Window calls that partition and order their rows alike, evaluated over one sort.
59struct WindowPass {
60    partition_by: Vec<ScalarExpr>,
61    order_by: Vec<ScalarOrder>,
62    slots: Vec<WindowSlot>,
63}
64
65pub struct PreparedWindowPlan {
66    passes: Vec<WindowPass>,
67    projections: Vec<ProjectionPlan>,
68}
69
70impl PreparedWindowPlan {
71    pub fn projections(&self) -> &[ProjectionPlan] {
72        &self.projections
73    }
74
75    /// The input schema with one internal column per window call, in pass order.
76    pub fn output_schema(
77        &self,
78        context: &dyn uqa_sql::FunctionTypeResolver,
79        input: &RowSchema,
80        params: &[SQLParam],
81    ) -> Result<RowSchema, SQLError> {
82        let mut schema = input.clone();
83        for pass in &self.passes {
84            let types = slot_types(pass, context, &schema, params)?;
85            schema = pass_output_schema(&schema, &types);
86        }
87        Ok(schema)
88    }
89}
90
91pub struct PhysicalWindowExecutor<'a> {
92    context: std::sync::Arc<dyn QueryExpressionContext + 'a>,
93    plan: PreparedWindowPlan,
94    params: &'a [SQLParam],
95
96    schema: RowSchema,
97    work_mem_bytes: usize,
98    input: Option<SpillBuffer>,
99}
100
101impl<'a> PhysicalWindowExecutor<'a> {
102    pub fn new(
103        context: std::sync::Arc<dyn QueryExpressionContext + 'a>,
104        plan: PreparedWindowPlan,
105        params: &'a [SQLParam],
106
107        schema: RowSchema,
108        work_mem_bytes: usize,
109    ) -> Self {
110        Self {
111            context,
112            plan,
113            params,
114
115            schema,
116            work_mem_bytes,
117            input: Some(SpillBuffer::new((work_mem_bytes / 3).max(1))),
118        }
119    }
120}
121
122impl WindowExecutor for PhysicalWindowExecutor<'_> {
123    fn consume(&mut self, batch: Batch) -> crate::ExecResult<()> {
124        self.input
125            .as_mut()
126            .ok_or_else(|| crate::ExecError::Other("window executor already finalized".into()))?
127            .push(batch)?;
128        Ok(())
129    }
130
131    fn finish(&mut self) -> crate::ExecResult<SpillBuffer> {
132        let mut input = self
133            .input
134            .take()
135            .ok_or_else(|| crate::ExecError::Other("window executor already finalized".into()))?;
136        let mut schema = self.schema.clone();
137        for pass in &self.plan.passes {
138            let types = slot_types(pass, self.context.as_ref(), &schema, self.params)?;
139            input = execute_window_pass(
140                self.context.as_ref(),
141                pass,
142                input,
143                &schema,
144                &types,
145                self.work_mem_bytes,
146                self.params,
147            )?;
148            schema = pass_output_schema(&schema, &types);
149        }
150        Ok(input)
151    }
152}
153
154/// Each pass sorts into a compact layout before appending its window values.
155/// Keep the declared layout and the next pass's input aligned with those rows.
156fn pass_output_schema(
157    input: &RowSchema,
158    types: &[(uqa_sql::ast::InternalColumnRef, Option<ColumnType>)],
159) -> RowSchema {
160    let (partition, _) = input.canonical_projection();
161    RowSchema::append_internal_typed(&partition, types)
162}
163
164pub fn has_window(projections: &[ProjectionPlan]) -> bool {
165    projections.iter().any(|p| expr_has_window(&p.expr))
166}
167
168pub fn prepare_window_plan(projections: &[ProjectionPlan]) -> PreparedWindowPlan {
169    let labels = projection_columns(projections);
170    let mut slots = Vec::new();
171    let mut rewritten = Vec::with_capacity(projections.len());
172    for (idx, projection) in projections.iter().enumerate() {
173        let (expr, changed) = rewrite_window_expr(&projection.expr, &mut slots);
174        let mut projection = projection.clone();
175        projection.expr = expr;
176        if changed && projection.alias.is_none() {
177            projection.alias = Some(labels[idx].clone());
178        }
179        rewritten.push(projection);
180    }
181    let mut passes: Vec<WindowPass> = Vec::new();
182    for slot in slots {
183        match passes.iter_mut().find(|pass| {
184            pass.partition_by == slot.spec.partition_by && pass.order_by == slot.spec.order_by
185        }) {
186            Some(pass) => pass.slots.push(slot),
187            None => passes.push(WindowPass {
188                partition_by: slot.spec.partition_by.clone(),
189                order_by: slot.spec.order_by.clone(),
190                slots: vec![slot],
191            }),
192        }
193    }
194    PreparedWindowPlan {
195        passes,
196        projections: rewritten,
197    }
198}
199
200fn slot_types(
201    pass: &WindowPass,
202    context: &dyn uqa_sql::FunctionTypeResolver,
203    schema: &RowSchema,
204    params: &[SQLParam],
205) -> Result<Vec<(uqa_sql::ast::InternalColumnRef, Option<ColumnType>)>, SQLError> {
206    pass.slots
207        .iter()
208        .map(|slot| {
209            crate::scalar_type_with_resolver(&slot.call(), schema, params, context)
210                .map(|ty| (slot.column, ty))
211        })
212        .collect()
213}
214
215/// One pass's window calls prepared for evaluation, with the frame offsets each still has to evaluate.
216struct PreparedSlot {
217    state: WindowFunctionState,
218    start_offset: Option<FrameOffset>,
219    end_offset: Option<FrameOffset>,
220}
221
222/// A frame offset expression and the type `transformFrameOffset` coerces it to.
223struct FrameOffset {
224    expression: ScalarExpr,
225    target: ColumnType,
226}
227
228fn execute_window_pass(
229    context: &dyn QueryExpressionContext,
230    pass: &WindowPass,
231    input: SpillBuffer,
232    schema: &RowSchema,
233    types: &[(uqa_sql::ast::InternalColumnRef, Option<ColumnType>)],
234    work_mem_bytes: usize,
235    params: &[SQLParam],
236) -> Result<SpillBuffer, SQLError> {
237    let phase_budget = (work_mem_bytes / 3).max(1);
238    let mut slots = pass
239        .slots
240        .iter()
241        .map(|slot| prepare_slot(context, slot, schema, params, phase_budget))
242        .collect::<Result<Vec<_>, _>>()?;
243    let scan: Box<dyn PhysicalOperator + '_> = Box::new(SpillScan::new(schema.clone(), input));
244    let mut keys = pass
245        .partition_by
246        .iter()
247        .cloned()
248        .map(|expr| SortKey {
249            expr,
250            descending: false,
251            nulls_first: None,
252        })
253        .collect::<Vec<_>>();
254    keys.extend(pass.order_by.iter().map(|order| SortKey {
255        expr: order.expr.clone(),
256        descending: order.descending,
257        nulls_first: order.nulls.map(|nulls| matches!(nulls, NullsOrder::First)),
258    }));
259    let evaluator = context.expression_evaluator(params);
260    let mut sorted = ExternalSort::new(scan, keys, evaluator, None, phase_budget);
261    sorted.open().map_err(exec_to_sql_error)?;
262
263    let hook = context;
264    let subquery_arena = PlanSubqueryArena::new(context.subquery_plans(), Some(hook));
265    let partition_schema = sorted.row_schema().clone();
266    let output_schema = RowSchema::append_internal_typed(&partition_schema, types);
267    let mut output = SpillBuffer::new(phase_budget);
268    let mut offsets_evaluated = false;
269
270    let execution = (|| -> Result<(), SQLError> {
271        let mut partition = BufferedIndexedSpill::new(partition_schema.clone(), phase_budget);
272        let mut partition_key: Option<Vec<Value>> = None;
273        while let Some(batch) = sorted.next().map_err(exec_to_sql_error)? {
274            for row in batch.rows {
275                let key = evaluate_all(
276                    &pass.partition_by,
277                    &batch.schema,
278                    &row,
279                    params,
280                    hook,
281                    &subquery_arena,
282                )?;
283                let same_partition = match &partition_key {
284                    Some(current) => crate::relational::equal_sort_key_values(
285                        current,
286                        &key,
287                        uqa_sql::expr::EngineHook::enum_labels(hook),
288                    )
289                    .map_err(exec_to_sql_error)?,
290                    None => true,
291                };
292                if !same_partition {
293                    emit_partition(
294                        pass,
295                        &mut slots,
296                        &mut partition,
297                        (&output_schema, &mut output),
298                        (params, hook, &subquery_arena),
299                        &mut offsets_evaluated,
300                    )?;
301                    partition = BufferedIndexedSpill::new(partition_schema.clone(), phase_budget);
302                }
303                partition_key = Some(key);
304                partition.push(&row).map_err(exec_to_sql_error)?;
305            }
306        }
307        if partition.is_empty() {
308            // `calculate_frame_offsets` runs before the first input row is read, so an invalid constant offset is reported even when there are no rows.
309            if !offsets_evaluated {
310                let empty = RowSchema::default();
311                let row = PhysicalRow::default();
312                let view = empty.view(&row);
313                let evaluation = ScalarEvalContext::from_row_lookup(&view, params)
314                    .with_function_hook(hook)
315                    .with_subquery_runner(&subquery_arena);
316                for slot in &mut slots {
317                    if slot.offsets_reference_rows() {
318                        continue;
319                    }
320                    slot.evaluate_offsets(&evaluation)?;
321                }
322            }
323        } else {
324            emit_partition(
325                pass,
326                &mut slots,
327                &mut partition,
328                (&output_schema, &mut output),
329                (params, hook, &subquery_arena),
330                &mut offsets_evaluated,
331            )?;
332        }
333        Ok(())
334    })();
335    let close = sorted.close().map_err(exec_to_sql_error);
336    combine_execution_and_close(execution, close, "window sort")?;
337    Ok(output)
338}
339
340fn prepare_slot(
341    context: &dyn QueryExpressionContext,
342    slot: &WindowSlot,
343    schema: &RowSchema,
344    params: &[SQLParam],
345    budget_bytes: usize,
346) -> Result<PreparedSlot, SQLError> {
347    let spec = &slot.spec;
348    let (mode, start, end, exclusion) = spec.frame.as_ref().map_or(
349        // Without a frame clause the frame is RANGE UNBOUNDED PRECEDING, which ends with the current row's last peer.
350        (
351            FrameMode::Range,
352            BoundKind::UnboundedPreceding,
353            BoundKind::CurrentRow,
354            FrameExclusion::NoOthers,
355        ),
356        |frame| {
357            (
358                frame.mode,
359                bound_kind(&frame.start),
360                bound_kind(&frame.end),
361                frame.exclusion,
362            )
363        },
364    );
365    let (ascending, nulls_first) = spec.order_by.first().map_or((true, false), |order| {
366        (
367            !order.descending,
368            order
369                .nulls
370                .map_or(order.descending, |nulls| nulls == NullsOrder::First),
371        )
372    });
373    let offset = |bound: Option<&ScalarFrameBound>| -> Result<Option<FrameOffset>, SQLError> {
374        let Some(ScalarFrameBound::Preceding(expression) | ScalarFrameBound::Following(expression)) =
375            bound
376        else {
377            return Ok(None);
378        };
379        let target = if mode == FrameMode::Range {
380            let order = spec.order_by.first().ok_or_else(|| {
381                SQLError::Internal("RANGE frame offset has no ordering column".into())
382            })?;
383            let order_type =
384                crate::scalar_type_with_resolver(&order.expr, schema, params, context)?;
385            let offset_type =
386                crate::scalar_type_with_resolver(expression, schema, params, context)?;
387            let offset_type = uqa_sql::effective_overload_argument_type_with_params(
388                expression,
389                offset_type,
390                params,
391            );
392            uqa_sql::range_frame_offset_type(order_type.as_ref(), offset_type.as_ref())?
393        } else {
394            ColumnType::BigInteger
395        };
396        Ok(Some(FrameOffset {
397            expression: (**expression).clone(),
398            target,
399        }))
400    };
401    let start_offset = offset(spec.frame.as_ref().map(|frame| &frame.start))?;
402    let end_offset = offset(spec.frame.as_ref().map(|frame| &frame.end))?;
403    let frame = FrameSpec {
404        mode,
405        start,
406        end,
407        exclusion,
408        start_offset: None,
409        end_offset: None,
410        ascending,
411        nulls_first,
412    };
413    let function = window_function(context, slot, schema, params, budget_bytes)?;
414    Ok(PreparedSlot {
415        state: WindowFunctionState::new(function, frame),
416        start_offset,
417        end_offset,
418    })
419}
420
421const fn bound_kind(bound: &ScalarFrameBound) -> BoundKind {
422    match bound {
423        ScalarFrameBound::UnboundedPreceding => BoundKind::UnboundedPreceding,
424        ScalarFrameBound::UnboundedFollowing => BoundKind::UnboundedFollowing,
425        ScalarFrameBound::CurrentRow => BoundKind::CurrentRow,
426        ScalarFrameBound::Preceding(_) => BoundKind::Preceding,
427        ScalarFrameBound::Following(_) => BoundKind::Following,
428    }
429}
430
431fn window_function(
432    context: &dyn QueryExpressionContext,
433    slot: &WindowSlot,
434    schema: &RowSchema,
435    params: &[SQLParam],
436    budget_bytes: usize,
437) -> Result<WindowFunction, SQLError> {
438    let name = uqa_sql::semantics::builtin_function_dispatch_name(&slot.name);
439    let bind = |expression: &ScalarExpr| {
440        crate::bind_type_introspection_with_resolver(expression.clone(), schema, params, context)
441    };
442    let argument = |position: usize| {
443        slot.args
444            .get(position)
445            .map(|expression| crate::scalar::PreparedExpressions::scalar(bind(expression)))
446    };
447    let required = |position: usize| {
448        argument(position).ok_or_else(|| SQLError::BadArity {
449            name: name.clone(),
450            expected: format!(">={}", position + 1),
451            actual: slot.args.len(),
452        })
453    };
454    Ok(match name.as_str() {
455        "row_number" => WindowFunction::RowNumber,
456        "rank" => WindowFunction::Rank,
457        "dense_rank" => WindowFunction::DenseRank,
458        "percent_rank" => WindowFunction::PercentRank,
459        "cume_dist" => WindowFunction::CumeDist,
460        "ntile" => WindowFunction::Ntile(required(0)?),
461        "lag" | "lead" => WindowFunction::Shift(Box::new(functions::Shift {
462            forward: name == "lead",
463            target: required(0)?,
464            offset: argument(1),
465            default: argument(2),
466        })),
467        "first_value" => WindowFunction::FirstValue(required(0)?),
468        "last_value" => WindowFunction::LastValue(required(0)?),
469        "nth_value" => WindowFunction::NthValue {
470            target: required(0)?,
471            position: required(1)?,
472        },
473        _ => {
474            let call = ScalarExpr::Func {
475                order_syntax: uqa_sql::ast::FunctionOrderSyntax::Ordinary,
476                name: slot.name.clone(),
477                binding: None,
478                args: slot.args.iter().map(bind).collect(),
479                distinct: false,
480                order_by: Vec::new(),
481                filter: None,
482            };
483            let template = crate::aggregation::aggregate_accumulator_templates(
484                context,
485                std::slice::from_ref(&call),
486                schema,
487                params,
488            )?
489            .pop()
490            .ok_or_else(|| SQLError::Internal("window aggregate lost its accumulator".into()))?;
491            let ScalarExpr::Func { args, .. } = call else {
492                unreachable!()
493            };
494            let filter = slot.filter.as_ref().map(bind);
495            WindowFunction::Aggregate(Box::new(aggregates::WindowAggregate::new(
496                (&slot.name, &args, filter.as_ref()),
497                template,
498                budget_bytes,
499            )))
500        }
501    })
502}
503
504impl PreparedSlot {
505    fn offsets_reference_rows(&self) -> bool {
506        [&self.start_offset, &self.end_offset]
507            .into_iter()
508            .flatten()
509            .any(|offset| {
510                let mut found = false;
511                offset.expression.visit(&mut |part| {
512                    found |= matches!(
513                        part,
514                        ScalarExpr::Column(_)
515                            | ScalarExpr::QualifiedColumn { .. }
516                            | ScalarExpr::Position(_)
517                            | ScalarExpr::InternalColumn(_)
518                    );
519                });
520                found
521            })
522    }
523
524    /// `calculate_frame_offsets`: each offset is evaluated once, must not be NULL, and a `ROWS` or `GROUPS` count must not be negative.
525    fn evaluate_offsets(&mut self, context: &ScalarEvalContext<'_>) -> Result<(), SQLError> {
526        let mode = self.state.frame_mut().mode;
527        let start = self
528            .start_offset
529            .as_ref()
530            .map(|offset| frame_offset_value(offset, mode, "starting", context))
531            .transpose()?;
532        let end = self
533            .end_offset
534            .as_ref()
535            .map(|offset| frame_offset_value(offset, mode, "ending", context))
536            .transpose()?;
537        let frame = self.state.frame_mut();
538        frame.start_offset = start;
539        frame.end_offset = end;
540        Ok(())
541    }
542}
543
544fn frame_offset_value(
545    offset: &FrameOffset,
546    mode: FrameMode,
547    which: &str,
548    context: &ScalarEvalContext<'_>,
549) -> Result<Value, SQLError> {
550    let value = eval_scalar(&offset.expression, context)?;
551    if matches!(value, Value::Null) {
552        return Err(SQLError::Routine {
553            sqlstate: "22004".into(),
554            message: format!("frame {which} offset must not be null"),
555        });
556    }
557    let value = uqa_sql::expr::cast_value(&value, &offset.target.sql_name())?;
558    if mode != FrameMode::Range && matches!(value, Value::Int(count) if count < 0) {
559        return Err(SQLError::Routine {
560            sqlstate: "22013".into(),
561            message: format!("frame {which} offset must not be negative"),
562        });
563    }
564    Ok(value)
565}
566
567/// Evaluate every window call of a pass for each row of one sorted partition and append the results to the row.
568fn emit_partition(
569    pass: &WindowPass,
570    slots: &mut [PreparedSlot],
571    partition: &mut BufferedIndexedSpill,
572    (schema, output): (&RowSchema, &mut SpillBuffer),
573    (params, hook, subqueries): (
574        &[SQLParam],
575        &dyn uqa_sql::expr::EngineHook,
576        &dyn ScalarSubqueryRunner,
577    ),
578    offsets_evaluated: &mut bool,
579) -> Result<(), SQLError> {
580    let mut rows = PartitionRows::new(partition, &pass.order_by, params, hook, subqueries)?;
581    if rows.len() == 0 {
582        return Ok(());
583    }
584    if !*offsets_evaluated {
585        // Offsets may use an enclosing query's columns, which every row of the input carries.
586        for slot in slots.iter_mut() {
587            rows.with_context(0, |context| slot.evaluate_offsets(context))?;
588        }
589        *offsets_evaluated = true;
590    }
591    for slot in slots.iter_mut() {
592        slot.state.begin_partition();
593    }
594    let mut current = CurrentRow::new();
595    let mut pending = Vec::with_capacity(crate::batch::DEFAULT_BATCH_SIZE);
596    for position in 0..rows.len() {
597        if position > 0 {
598            for slot in slots.iter_mut() {
599                slot.state.advance();
600            }
601            current.advance(&mut rows)?;
602        }
603        let values = slots
604            .iter_mut()
605            .map(|slot| slot.state.value(&mut current, &mut rows))
606            .collect::<Result<Vec<_>, _>>()?;
607        pending.push(rows.row(position)?.append_values(values));
608        if pending.len() == crate::batch::DEFAULT_BATCH_SIZE {
609            output
610                .push(Batch::from_physical_rows(
611                    schema.clone(),
612                    std::mem::take(&mut pending),
613                ))
614                .map_err(exec_to_sql_error)?;
615            pending = Vec::with_capacity(crate::batch::DEFAULT_BATCH_SIZE);
616        }
617    }
618    if !pending.is_empty() {
619        output
620            .push(Batch::from_physical_rows(schema.clone(), pending))
621            .map_err(exec_to_sql_error)?;
622    }
623    Ok(())
624}
625
626fn evaluate_all(
627    expressions: &[ScalarExpr],
628    schema: &RowSchema,
629    row: &PhysicalRow,
630    params: &[SQLParam],
631    hook: &dyn uqa_sql::expr::EngineHook,
632    subqueries: &dyn ScalarSubqueryRunner,
633) -> Result<Vec<Value>, SQLError> {
634    expressions
635        .iter()
636        .map(|expression| evaluate_on_row(expression, schema, row, params, hook, subqueries))
637        .collect()
638}
639
640fn evaluate_on_row(
641    expression: &ScalarExpr,
642    schema: &RowSchema,
643    row: &PhysicalRow,
644    params: &[SQLParam],
645    eval_hook: &dyn uqa_sql::expr::EngineHook,
646    subquery_runner: &dyn ScalarSubqueryRunner,
647) -> Result<Value, SQLError> {
648    let view = schema.view(row);
649    let context = ScalarEvalContext::from_row_lookup(&view, params)
650        .with_function_hook(eval_hook)
651        .with_subquery_runner(subquery_runner)
652        .with_physical_outer_row(schema, row);
653    eval_scalar(expression, &context)
654}
655
656fn combine_execution_and_close(
657    execution: Result<(), SQLError>,
658    close: Result<(), SQLError>,
659    operator: &str,
660) -> Result<(), SQLError> {
661    match (execution, close) {
662        (Ok(()), Ok(())) => Ok(()),
663        (Ok(()), Err(error)) | (Err(error), Ok(())) => Err(error),
664        (Err(execution_error), Err(close_error)) => Err(SQLError::Internal(format!(
665            "{execution_error}; closing {operator} after failure also failed: {close_error}"
666        ))),
667    }
668}
669
670fn exec_to_sql_error(error: crate::ExecError) -> SQLError {
671    match error {
672        crate::ExecError::SQL(error) => error,
673        crate::ExecError::Other(message) => SQLError::Internal(message),
674    }
675}
676
677#[cfg(test)]
678mod tests;