Skip to main content

uqa_execution/relational/
window.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Byte-bounded window execution.
8
9use super::{
10    compare_values, eval_scalar, value_to_f64, Batch, DefaultExpressionEvaluator, ExecError,
11    ExecResult, PhysicalOperator, RowSchema, SQLParam, ScalarEvalContext, ScalarExpr, SortKey,
12    Value,
13};
14use crate::RowSchemaExecution;
15use uqa_sql::expr::RowLookup;
16
17#[derive(Debug, Clone)]
18pub enum WindowKind {
19    RowNumber,
20    Rank,
21    DenseRank,
22    Lag(ScalarExpr, i64),
23    Lead(ScalarExpr, i64),
24    Ntile(i64),
25    AggSum(ScalarExpr),
26    AggCount(Option<ScalarExpr>),
27    AggAvg(ScalarExpr),
28    AggMin(ScalarExpr),
29    AggMax(ScalarExpr),
30}
31
32#[derive(Debug, Clone)]
33pub struct WindowSpec {
34    pub partition_by: Vec<ScalarExpr>,
35    pub order_by: Vec<SortKey>,
36}
37
38/// Byte-bounded window operator. Input sorting, random-access partitions, and
39/// output rows use disk-backed buffers; only fixed-size batches are decoded at
40/// the Volcano boundary.
41pub trait WindowExecutor: Send {
42    /// Consume one child batch without materializing the complete input in the
43    /// physical operator.
44    fn consume(&mut self, batch: Batch) -> ExecResult<()>;
45
46    /// Finalize window columns into a byte-bounded, disk-backed output stream.
47    fn finish(&mut self) -> ExecResult<crate::spill::SpillBuffer>;
48}
49
50pub struct Window<'a> {
51    child: Box<dyn PhysicalOperator + 'a>,
52    spec: WindowSpec,
53    functions: Vec<(String, WindowKind)>,
54    params: Vec<SQLParam>,
55    schema: RowSchema,
56    executor: Option<Box<dyn WindowExecutor + 'a>>,
57    work_mem_bytes: usize,
58    output: Option<crate::spill::SpillDrain>,
59    output_spilled: bool,
60}
61
62impl Window<'static> {
63    const DEFAULT_WORK_MEM_BYTES: usize = 64 * 1024 * 1024;
64
65    pub fn new(
66        child: Box<dyn PhysicalOperator>,
67        spec: WindowSpec,
68        functions: Vec<(String, WindowKind)>,
69        params: Vec<SQLParam>,
70    ) -> Self {
71        Self::new_with_work_mem(child, spec, functions, params, Self::DEFAULT_WORK_MEM_BYTES)
72    }
73
74    pub fn new_with_work_mem(
75        child: Box<dyn PhysicalOperator>,
76        spec: WindowSpec,
77        functions: Vec<(String, WindowKind)>,
78        params: Vec<SQLParam>,
79        work_mem_bytes: usize,
80    ) -> Self {
81        let names = functions
82            .iter()
83            .map(|(name, _)| name.clone())
84            .collect::<Vec<_>>();
85        let (schema, _) = RowSchema::append(child.row_schema(), &names).canonical_projection();
86        Self {
87            child,
88            spec,
89            functions,
90            params,
91            schema,
92            executor: None,
93            work_mem_bytes,
94            output: None,
95            output_spilled: false,
96        }
97    }
98}
99
100impl<'a> Window<'a> {
101    /// Construct a physical window operator backed by the engine's complete
102    /// frame and function implementation.
103    pub fn with_executor(
104        child: Box<dyn PhysicalOperator + 'a>,
105        output_schema: Vec<String>,
106        executor: Box<dyn WindowExecutor + 'a>,
107    ) -> Self {
108        let types = vec![None; output_schema.len()];
109        Self::with_typed_executor(child, output_schema, types, executor)
110    }
111
112    pub fn with_typed_executor(
113        child: Box<dyn PhysicalOperator + 'a>,
114        output_schema: Vec<String>,
115        output_types: Vec<Option<uqa_sql::ast::ColumnType>>,
116        executor: Box<dyn WindowExecutor + 'a>,
117    ) -> Self {
118        Self::with_row_schema_executor(
119            child,
120            RowSchema::with_types(output_schema, output_types),
121            executor,
122        )
123    }
124
125    pub fn with_row_schema_executor(
126        child: Box<dyn PhysicalOperator + 'a>,
127        schema: RowSchema,
128        executor: Box<dyn WindowExecutor + 'a>,
129    ) -> Self {
130        Self {
131            child,
132            spec: WindowSpec {
133                partition_by: Vec::new(),
134                order_by: Vec::new(),
135            },
136            functions: Vec::new(),
137            params: Vec::new(),
138            schema,
139            executor: Some(executor),
140            work_mem_bytes: 0,
141            output: None,
142            output_spilled: false,
143        }
144    }
145
146    /// Whether final window rows exceeded their output budget and were written
147    /// to disk during the current/most recent invocation.
148    pub fn output_has_spilled(&self) -> bool {
149        self.output_spilled
150    }
151}
152
153fn builtin_window_order_key(
154    row: &dyn RowLookup,
155    spec: &WindowSpec,
156    params: &[SQLParam],
157) -> ExecResult<Vec<Value>> {
158    let context = ScalarEvalContext::from_row_lookup(row, params);
159    spec.order_by
160        .iter()
161        .map(|key| Ok(eval_scalar(&key.expr, &context)?))
162        .collect()
163}
164
165fn builtin_window_partition_value(
166    kind: &WindowKind,
167    partition: &mut crate::spill::BufferedIndexedSpill,
168    params: &[SQLParam],
169) -> ExecResult<Option<Value>> {
170    let mut count = 0_i64;
171    let mut sum = 0.0_f64;
172    let mut min = None;
173    let mut max = None;
174    let expression = match kind {
175        WindowKind::AggSum(expression)
176        | WindowKind::AggAvg(expression)
177        | WindowKind::AggMin(expression)
178        | WindowKind::AggMax(expression) => Some(expression),
179        WindowKind::AggCount(expression) => expression.as_ref(),
180        _ => return Ok(None),
181    };
182    let partition_schema = partition.row_schema().clone();
183    for index in 0..partition.len() {
184        let row = partition.get(index)?;
185        let view = partition_schema.view(&row);
186        let value = match expression {
187            Some(expression) => eval_scalar(
188                expression,
189                &ScalarEvalContext::from_row_lookup(&view, params),
190            )?,
191            None => Value::Int(1),
192        };
193        if matches!(value, Value::Null) {
194            continue;
195        }
196        count = count
197            .checked_add(1)
198            .ok_or_else(|| ExecError::Other("window aggregate row count overflow".into()))?;
199        match kind {
200            WindowKind::AggSum(_) | WindowKind::AggAvg(_) => {
201                let number = value_to_f64(&value).ok_or_else(|| {
202                    ExecError::Other(format!("non-numeric window aggregate input: {value:?}"))
203                })?;
204                sum += number;
205            }
206            WindowKind::AggMin(_) => {
207                min = Some(match min.take() {
208                    Some(previous) if compare_values(&previous, &value)?.is_le() => previous,
209                    _ => value,
210                });
211            }
212            WindowKind::AggMax(_) => {
213                max = Some(match max.take() {
214                    Some(previous) if compare_values(&previous, &value)?.is_ge() => previous,
215                    _ => value,
216                });
217            }
218            WindowKind::AggCount(_) => {}
219            _ => {
220                return Err(ExecError::Other(
221                    "non-aggregate window kind reached aggregate evaluation".into(),
222                ))
223            }
224        }
225    }
226    Ok(Some(match kind {
227        WindowKind::AggSum(_) => {
228            if count == 0 {
229                Value::Null
230            } else {
231                Value::Float(sum)
232            }
233        }
234        WindowKind::AggCount(_) => Value::Int(count),
235        WindowKind::AggAvg(_) => {
236            if count == 0 {
237                Value::Null
238            } else {
239                Value::Float(sum / count as f64)
240            }
241        }
242        WindowKind::AggMin(_) => min.unwrap_or(Value::Null),
243        WindowKind::AggMax(_) => max.unwrap_or(Value::Null),
244        _ => {
245            return Err(ExecError::Other(
246                "non-aggregate window kind reached aggregate result construction".into(),
247            ))
248        }
249    }))
250}
251
252fn builtin_ntile(index: u64, rows: u64, buckets: i64) -> ExecResult<Value> {
253    let buckets = u64::try_from(buckets.max(1))
254        .map_err(|_| ExecError::Other("NTILE bucket count is out of range".into()))?;
255    let base = rows / buckets;
256    let extra = rows % buckets;
257    let larger_rows = if extra == 0 {
258        0
259    } else {
260        base.checked_add(1)
261            .and_then(|value| value.checked_mul(extra))
262            .ok_or_else(|| ExecError::Other("NTILE partition size overflow".into()))?
263    };
264    let bucket = if index < larger_rows {
265        index
266            .checked_div(
267                base.checked_add(1)
268                    .ok_or_else(|| ExecError::Other("NTILE bucket width overflow".into()))?,
269            )
270            .and_then(|value| value.checked_add(1))
271            .ok_or_else(|| ExecError::Other("NTILE bucket number overflow".into()))?
272    } else if base == 0 {
273        extra.max(1)
274    } else {
275        extra
276            .checked_add(
277                (index - larger_rows)
278                    .checked_div(base)
279                    .ok_or_else(|| ExecError::Other("invalid NTILE bucket width".into()))?,
280            )
281            .and_then(|value| value.checked_add(1))
282            .ok_or_else(|| ExecError::Other("NTILE bucket number overflow".into()))?
283    };
284    Ok(Value::Int(i64::try_from(bucket).map_err(|_| {
285        ExecError::Other("NTILE bucket number exceeds SQL integer range".into())
286    })?))
287}
288
289#[expect(
290    clippy::too_many_lines,
291    reason = "window execution preserves frame and peer ordering in one pass"
292)]
293fn emit_builtin_window_partition(
294    partition: &mut crate::spill::BufferedIndexedSpill,
295    spec: &WindowSpec,
296    functions: &[(String, WindowKind)],
297    params: &[SQLParam],
298    schema: &RowSchema,
299    output: &mut crate::spill::SpillBuffer,
300) -> ExecResult<()> {
301    let aliases = functions
302        .iter()
303        .map(|(alias, _)| alias.clone())
304        .collect::<Vec<_>>();
305    let partition_schema = partition.row_schema().clone();
306    let appended_schema = RowSchema::append(&partition_schema, &aliases);
307    let (physical_output_schema, output_slots) = appended_schema.canonical_projection();
308    if &physical_output_schema != schema {
309        return Err(ExecError::Other(format!(
310            "window output schema mismatch: expected {:?}, got {:?}",
311            schema.columns(),
312            physical_output_schema.columns()
313        )));
314    }
315    let aggregate_values = functions
316        .iter()
317        .map(|(_, kind)| builtin_window_partition_value(kind, partition, params))
318        .collect::<ExecResult<Vec<_>>>()?;
319    let mut previous_order_key = None;
320    let mut rank = 0_i64;
321    let mut dense_rank = 0_i64;
322    let mut pending = Vec::with_capacity(crate::batch::DEFAULT_BATCH_SIZE);
323    for index in 0..partition.len() {
324        let row = partition.get(index)?;
325        let row_view = partition_schema.view(&row);
326        let order_key = builtin_window_order_key(&row_view, spec, params)?;
327        if previous_order_key.as_ref() != Some(&order_key) {
328            rank = i64::try_from(
329                index
330                    .checked_add(1)
331                    .ok_or_else(|| ExecError::Other("window rank overflow".into()))?,
332            )
333            .map_err(|_| ExecError::Other("window rank exceeds SQL integer range".into()))?;
334            dense_rank = dense_rank
335                .checked_add(1)
336                .ok_or_else(|| ExecError::Other("window dense rank overflow".into()))?;
337        }
338        let mut window_values = Vec::with_capacity(functions.len());
339        for ((_, kind), aggregate_value) in functions.iter().zip(&aggregate_values) {
340            let value = match kind {
341                WindowKind::RowNumber => {
342                    Value::Int(
343                        i64::try_from(index.checked_add(1).ok_or_else(|| {
344                            ExecError::Other("window row number overflow".into())
345                        })?)
346                        .map_err(|_| {
347                            ExecError::Other("window row number exceeds SQL integer range".into())
348                        })?,
349                    )
350                }
351                WindowKind::Rank => Value::Int(rank),
352                WindowKind::DenseRank => Value::Int(dense_rank),
353                WindowKind::Lag(expression, offset) | WindowKind::Lead(expression, offset) => {
354                    let direction = if matches!(kind, WindowKind::Lag(..)) {
355                        -1_i128
356                    } else {
357                        1_i128
358                    };
359                    let target = i128::from(index) + direction * i128::from(*offset);
360                    if target < 0 || target >= i128::from(partition.len()) {
361                        Value::Null
362                    } else {
363                        let target_row = partition.get(u64::try_from(target).map_err(|_| {
364                            ExecError::Other("window offset target is out of range".into())
365                        })?)?;
366                        let target_view = partition_schema.view(&target_row);
367                        eval_scalar(
368                            expression,
369                            &ScalarEvalContext::from_row_lookup(&target_view, params),
370                        )?
371                    }
372                }
373                WindowKind::Ntile(buckets) => builtin_ntile(index, partition.len(), *buckets)?,
374                WindowKind::AggSum(_)
375                | WindowKind::AggCount(_)
376                | WindowKind::AggAvg(_)
377                | WindowKind::AggMin(_)
378                | WindowKind::AggMax(_) => aggregate_value.clone().ok_or_else(|| {
379                    ExecError::Other("aggregate window value was not precomputed".into())
380                })?,
381            };
382            window_values.push(value);
383        }
384        previous_order_key = Some(order_key);
385        pending.push(
386            row.append_values(window_values)
387                .project_slots(&output_slots)
388                .without_lock_origins(),
389        );
390        if pending.len() == crate::batch::DEFAULT_BATCH_SIZE {
391            output.push(Batch::from_physical_rows(
392                schema.clone(),
393                std::mem::take(&mut pending),
394            ))?;
395            pending = Vec::with_capacity(crate::batch::DEFAULT_BATCH_SIZE);
396        }
397    }
398    if !pending.is_empty() {
399        output.push(Batch::from_physical_rows(schema.clone(), pending))?;
400    }
401    Ok(())
402}
403
404impl PhysicalOperator for Window<'_> {
405    fn row_schema(&self) -> &RowSchema {
406        &self.schema
407    }
408
409    fn open(&mut self) -> ExecResult<()> {
410        self.child.open()?;
411        self.output_spilled = false;
412        if let Some(executor) = self.executor.as_mut() {
413            while let Some(batch) = self.child.next()? {
414                executor.consume(batch)?;
415            }
416            let mut output = executor.finish()?;
417            self.output_spilled = output.has_spilled();
418            self.output = Some(output.drain()?);
419            return Ok(());
420        }
421
422        let phase_budget = (self.work_mem_bytes / 3).max(1);
423        let mut input = crate::spill::SpillBuffer::new(phase_budget);
424        while let Some(batch) = self.child.next()? {
425            input.push(batch)?;
426        }
427        let scan: Box<dyn PhysicalOperator> = Box::new(crate::spill_scan::SpillScan::new(
428            self.child.row_schema().clone(),
429            input,
430        ));
431        let mut keys = self
432            .spec
433            .partition_by
434            .iter()
435            .cloned()
436            .map(|expr| SortKey {
437                expr,
438                descending: false,
439                nulls_first: None,
440            })
441            .collect::<Vec<_>>();
442        keys.extend(self.spec.order_by.iter().cloned());
443        let evaluator = DefaultExpressionEvaluator::shared(self.params.clone());
444        let mut sorted =
445            crate::external_sort::ExternalSort::new(scan, keys, evaluator, None, phase_budget);
446        sorted.open()?;
447
448        let partition_schema = sorted.row_schema().clone();
449        let mut current_partition_key: Option<Vec<Value>> = None;
450        let mut partition =
451            crate::spill::BufferedIndexedSpill::new(partition_schema.clone(), phase_budget);
452        let mut output = crate::spill::SpillBuffer::new(phase_budget);
453        let execution = (|| -> ExecResult<()> {
454            while let Some(batch) = sorted.next()? {
455                for row in batch.rows {
456                    let view = batch.schema.view(&row);
457                    let context = ScalarEvalContext::from_row_lookup(&view, &self.params);
458                    let key = self
459                        .spec
460                        .partition_by
461                        .iter()
462                        .map(|expression| eval_scalar(expression, &context))
463                        .collect::<Result<Vec<_>, _>>()?;
464                    if current_partition_key
465                        .as_ref()
466                        .is_some_and(|current| current != &key)
467                    {
468                        emit_builtin_window_partition(
469                            &mut partition,
470                            &self.spec,
471                            &self.functions,
472                            &self.params,
473                            &self.schema,
474                            &mut output,
475                        )?;
476                        partition = crate::spill::BufferedIndexedSpill::new(
477                            partition_schema.clone(),
478                            phase_budget,
479                        );
480                    }
481                    current_partition_key = Some(key);
482                    partition.push(&row)?;
483                }
484            }
485            if !partition.is_empty() {
486                emit_builtin_window_partition(
487                    &mut partition,
488                    &self.spec,
489                    &self.functions,
490                    &self.params,
491                    &self.schema,
492                    &mut output,
493                )?;
494            }
495            Ok(())
496        })();
497        let close = sorted.close();
498        crate::physical::with_cleanup(execution, close, "close window sort after failure")?;
499        self.output_spilled = output.has_spilled();
500        self.output = Some(output.drain()?);
501        Ok(())
502    }
503
504    fn next(&mut self) -> ExecResult<Option<Batch>> {
505        let Some(output) = self.output.as_mut() else {
506            return Ok(None);
507        };
508        output.next().transpose()
509    }
510
511    fn close(&mut self) -> ExecResult<()> {
512        self.output = None;
513        self.child.close()
514    }
515}