1use 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
38pub trait WindowExecutor: Send {
42 fn consume(&mut self, batch: Batch) -> ExecResult<()>;
45
46 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 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 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}