1use 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 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
58struct 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 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
154fn 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
215struct PreparedSlot {
217 state: WindowFunctionState,
218 start_offset: Option<FrameOffset>,
219 end_offset: Option<FrameOffset>,
220}
221
222struct 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 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 (
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 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
567fn 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 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;