1pub mod aggregate;
4pub mod filter;
5pub mod join;
6pub(crate) mod like;
7pub mod scan;
8pub mod sort;
9pub mod spatial_funcs;
10
11pub use spatial_funcs::evaluate_spatial_function;
12
13pub mod window;
14
15pub use window::{OrderKey, WindowFunction, WindowSpec, evaluate_window, evaluate_window_batch};
16
17use crate::error::{QueryError, Result};
18use crate::parser::ast::*;
19use aggregate::{Aggregate, AggregateFunc, AggregateFunction};
20use filter::{Filter, Value, evaluate_expr_for_row};
21use join::Join;
22use scan::{ColumnData, DataSource, Field, RecordBatch, Schema, TableScan};
23use sort::Sort;
24use std::collections::HashMap;
25use std::sync::Arc;
26
27pub struct Executor {
29 data_sources: HashMap<String, Arc<dyn DataSource>>,
31}
32
33impl Executor {
34 pub fn new() -> Self {
36 Self {
37 data_sources: HashMap::new(),
38 }
39 }
40
41 pub fn register_data_source(&mut self, name: String, source: Arc<dyn DataSource>) {
43 self.data_sources.insert(name, source);
44 }
45
46 pub async fn execute(&self, stmt: &Statement) -> Result<Vec<RecordBatch>> {
48 match stmt {
49 Statement::Select(select) => self.execute_select(select).await,
50 }
51 }
52
53 async fn execute_select(&self, select: &SelectStatement) -> Result<Vec<RecordBatch>> {
55 let mut batches = if let Some(ref table_ref) = select.from {
57 self.execute_table_reference(table_ref).await?
58 } else {
59 return Err(QueryError::semantic("SELECT without FROM not supported"));
60 };
61
62 if let Some(ref selection) = select.selection {
64 batches = self.execute_filter(batches, selection)?;
65 }
66
67 let aggregated = !select.group_by.is_empty()
70 || self.has_aggregates(&select.projection)
71 || select
72 .having
73 .as_ref()
74 .is_some_and(|h| self.expr_has_aggregate(h));
75 if aggregated {
76 batches = self.execute_aggregate(batches, select)?;
77 } else if select.having.is_some() {
78 return Err(QueryError::semantic(
79 "HAVING requires an aggregate query (GROUP BY or aggregate functions)",
80 ));
81 }
82
83 if !select.order_by.is_empty() {
85 batches = self.execute_sort(batches, &select.order_by)?;
86 }
87
88 if select.limit.is_some() || select.offset.is_some() {
90 batches = self.execute_limit_offset(batches, select.limit, select.offset)?;
91 }
92
93 if !aggregated {
100 batches = self.execute_projection(batches, &select.projection)?;
101 }
102
103 Ok(batches)
104 }
105
106 async fn execute_table_reference(
108 &self,
109 table_ref: &TableReference,
110 ) -> Result<Vec<RecordBatch>> {
111 match table_ref {
112 TableReference::Table { name, .. } => {
113 let source = self
114 .data_sources
115 .get(name)
116 .ok_or_else(|| QueryError::TableNotFound(name.clone()))?;
117
118 let scan = TableScan::new(name.clone(), source.clone());
119 scan.execute().await
120 }
121 TableReference::Join {
122 left,
123 right,
124 join_type,
125 on,
126 } => {
127 let left_batches = Box::pin(self.execute_table_reference(left)).await?;
129 let right_batches = Box::pin(self.execute_table_reference(right)).await?;
130
131 let join = Join::new(*join_type, on.clone());
132 let mut result = Vec::new();
133
134 for left_batch in &left_batches {
135 for right_batch in &right_batches {
136 result.push(join.execute(left_batch, right_batch)?);
137 }
138 }
139
140 Ok(result)
141 }
142 TableReference::Subquery { query, .. } => Box::pin(self.execute_select(query)).await,
143 }
144 }
145
146 fn execute_filter(
148 &self,
149 batches: Vec<RecordBatch>,
150 predicate: &Expr,
151 ) -> Result<Vec<RecordBatch>> {
152 let filter = Filter::new(predicate.clone());
153 let mut result = Vec::new();
154
155 for batch in batches {
156 result.push(filter.execute(&batch)?);
157 }
158
159 Ok(result)
160 }
161
162 fn execute_aggregate(
173 &self,
174 batches: Vec<RecordBatch>,
175 select: &SelectStatement,
176 ) -> Result<Vec<RecordBatch>> {
177 let mut agg_funcs: Vec<AggregateFunction> = Vec::new();
181 let mut name_map: HashMap<(AggregateFunc, String), String> = HashMap::new();
182
183 for item in &select.projection {
184 if let SelectItem::Expr { expr, alias } = item
185 && let Some((func, column)) = self.extract_aggregate(expr)
186 {
187 let key = (func, column.clone());
188 if let std::collections::hash_map::Entry::Vacant(e) = name_map.entry(key) {
189 let name = alias
190 .clone()
191 .unwrap_or_else(|| canonical_agg_name(func, &column));
192 e.insert(name.clone());
193 agg_funcs.push(AggregateFunction {
194 func,
195 column,
196 alias: Some(name),
197 });
198 }
199 }
200 }
201
202 let visible_agg_count = agg_funcs.len();
203 let group_count = select.group_by.len();
204
205 if let Some(having) = select.having.as_ref() {
207 let mut having_aggs = Vec::new();
208 self.collect_aggregates(having, &mut having_aggs);
209 for (func, column) in having_aggs {
210 let key = (func, column.clone());
211 if let std::collections::hash_map::Entry::Vacant(e) = name_map.entry(key) {
212 let name = canonical_agg_name(func, &column);
213 e.insert(name.clone());
214 agg_funcs.push(AggregateFunction {
215 func,
216 column,
217 alias: Some(name),
218 });
219 }
220 }
221 }
222
223 let aggregate = Aggregate::new(select.group_by.clone(), agg_funcs);
224 let visible_cols = group_count + visible_agg_count;
225 let mut result = Vec::new();
226
227 for batch in batches {
228 let mut agg_batch = aggregate.execute(&batch)?;
229
230 if let Some(having) = select.having.as_ref() {
231 let rewritten = self.rewrite_having(having, &name_map)?;
232 agg_batch = Filter::new(rewritten).execute(&agg_batch)?;
233 }
234
235 if agg_batch.columns.len() > visible_cols {
238 agg_batch = self.keep_leading_columns(&agg_batch, visible_cols)?;
239 }
240
241 result.push(agg_batch);
242 }
243
244 Ok(result)
245 }
246
247 fn collect_aggregates(&self, expr: &Expr, out: &mut Vec<(AggregateFunc, String)>) {
250 if let Some(agg) = self.extract_aggregate(expr) {
251 out.push(agg);
252 return;
253 }
254 match expr {
255 Expr::BinaryOp { left, right, .. } => {
256 self.collect_aggregates(left, out);
257 self.collect_aggregates(right, out);
258 }
259 Expr::UnaryOp { expr, .. } => self.collect_aggregates(expr, out),
260 Expr::Function { args, .. } => {
261 for arg in args {
262 self.collect_aggregates(arg, out);
263 }
264 }
265 Expr::Between {
266 expr, low, high, ..
267 } => {
268 self.collect_aggregates(expr, out);
269 self.collect_aggregates(low, out);
270 self.collect_aggregates(high, out);
271 }
272 Expr::InList { expr, list, .. } => {
273 self.collect_aggregates(expr, out);
274 for item in list {
275 self.collect_aggregates(item, out);
276 }
277 }
278 Expr::Case {
279 operand,
280 when_then,
281 else_result,
282 } => {
283 if let Some(op) = operand {
284 self.collect_aggregates(op, out);
285 }
286 for (when, then) in when_then {
287 self.collect_aggregates(when, out);
288 self.collect_aggregates(then, out);
289 }
290 if let Some(else_expr) = else_result {
291 self.collect_aggregates(else_expr, out);
292 }
293 }
294 Expr::Cast { expr, .. } => self.collect_aggregates(expr, out),
295 Expr::IsNull(inner) | Expr::IsNotNull(inner) => self.collect_aggregates(inner, out),
296 _ => {}
297 }
298 }
299
300 fn expr_has_aggregate(&self, expr: &Expr) -> bool {
302 let mut out = Vec::new();
303 self.collect_aggregates(expr, &mut out);
304 !out.is_empty()
305 }
306
307 fn rewrite_having(
311 &self,
312 expr: &Expr,
313 name_map: &HashMap<(AggregateFunc, String), String>,
314 ) -> Result<Expr> {
315 if let Some((func, column)) = self.extract_aggregate(expr) {
317 let name = name_map.get(&(func, column.clone())).ok_or_else(|| {
318 QueryError::internal(format!(
319 "HAVING references aggregate {} that was not planned",
320 canonical_agg_name(func, &column)
321 ))
322 })?;
323 return Ok(Expr::Column {
324 table: None,
325 name: name.clone(),
326 });
327 }
328
329 Ok(match expr {
330 Expr::BinaryOp { left, op, right } => Expr::BinaryOp {
331 left: Box::new(self.rewrite_having(left, name_map)?),
332 op: *op,
333 right: Box::new(self.rewrite_having(right, name_map)?),
334 },
335 Expr::UnaryOp { op, expr } => Expr::UnaryOp {
336 op: *op,
337 expr: Box::new(self.rewrite_having(expr, name_map)?),
338 },
339 Expr::Between {
340 expr,
341 low,
342 high,
343 negated,
344 } => Expr::Between {
345 expr: Box::new(self.rewrite_having(expr, name_map)?),
346 low: Box::new(self.rewrite_having(low, name_map)?),
347 high: Box::new(self.rewrite_having(high, name_map)?),
348 negated: *negated,
349 },
350 Expr::InList {
351 expr,
352 list,
353 negated,
354 } => {
355 let mut new_list = Vec::with_capacity(list.len());
356 for item in list {
357 new_list.push(self.rewrite_having(item, name_map)?);
358 }
359 Expr::InList {
360 expr: Box::new(self.rewrite_having(expr, name_map)?),
361 list: new_list,
362 negated: *negated,
363 }
364 }
365 Expr::Case {
366 operand,
367 when_then,
368 else_result,
369 } => {
370 let operand = match operand {
371 Some(op) => Some(Box::new(self.rewrite_having(op, name_map)?)),
372 None => None,
373 };
374 let mut new_when_then = Vec::with_capacity(when_then.len());
375 for (when, then) in when_then {
376 new_when_then.push((
377 self.rewrite_having(when, name_map)?,
378 self.rewrite_having(then, name_map)?,
379 ));
380 }
381 let else_result = match else_result {
382 Some(e) => Some(Box::new(self.rewrite_having(e, name_map)?)),
383 None => None,
384 };
385 Expr::Case {
386 operand,
387 when_then: new_when_then,
388 else_result,
389 }
390 }
391 Expr::Cast { expr, data_type } => Expr::Cast {
392 expr: Box::new(self.rewrite_having(expr, name_map)?),
393 data_type: *data_type,
394 },
395 Expr::IsNull(inner) => Expr::IsNull(Box::new(self.rewrite_having(inner, name_map)?)),
396 Expr::IsNotNull(inner) => {
397 Expr::IsNotNull(Box::new(self.rewrite_having(inner, name_map)?))
398 }
399 other => other.clone(),
400 })
401 }
402
403 fn keep_leading_columns(&self, batch: &RecordBatch, count: usize) -> Result<RecordBatch> {
405 let fields = batch.schema.fields[..count].to_vec();
406 let columns = batch.columns[..count].to_vec();
407 let schema = Arc::new(Schema::new(fields));
408 RecordBatch::new(schema, columns, batch.num_rows)
409 }
410
411 fn execute_projection(
413 &self,
414 batches: Vec<RecordBatch>,
415 projection: &[SelectItem],
416 ) -> Result<Vec<RecordBatch>> {
417 if projection.iter().all(|item| {
420 matches!(
421 item,
422 SelectItem::Wildcard | SelectItem::QualifiedWildcard(_)
423 )
424 }) {
425 return Ok(batches);
426 }
427
428 let mut result = Vec::with_capacity(batches.len());
429 for batch in batches {
430 result.push(self.project_batch(&batch, projection)?);
431 }
432 Ok(result)
433 }
434
435 fn project_batch(&self, batch: &RecordBatch, projection: &[SelectItem]) -> Result<RecordBatch> {
437 let mut fields: Vec<Field> = Vec::new();
438 let mut columns: Vec<ColumnData> = Vec::new();
439
440 for item in projection {
441 match item {
442 SelectItem::Wildcard | SelectItem::QualifiedWildcard(_) => {
443 for (field, column) in batch.schema.fields.iter().zip(&batch.columns) {
446 fields.push(field.clone());
447 columns.push(column.clone());
448 }
449 }
450 SelectItem::Expr { expr, alias } => {
451 if let Expr::Column { name, .. } = expr {
452 let idx = batch
455 .schema
456 .index_of(name)
457 .ok_or_else(|| QueryError::ColumnNotFound(name.clone()))?;
458 let src_field = &batch.schema.fields[idx];
459 let field_name = alias.clone().unwrap_or_else(|| name.clone());
460 fields.push(Field::new(
461 field_name,
462 src_field.data_type,
463 src_field.nullable,
464 ));
465 columns.push(batch.columns[idx].clone());
466 } else {
467 let mut values = Vec::with_capacity(batch.num_rows);
469 for row in 0..batch.num_rows {
470 values.push(evaluate_expr_for_row(expr, batch, row)?);
471 }
472 let (column, data_type) = values_to_projection_column(&values)?;
473 let nullable = values.iter().any(|v| matches!(v, Value::Null));
474 let name = alias.clone().unwrap_or_else(|| expr.to_string());
475 fields.push(Field::new(name, data_type, nullable));
476 columns.push(column);
477 }
478 }
479 }
480 }
481
482 let schema = Arc::new(Schema::new(fields));
483 RecordBatch::new(schema, columns, batch.num_rows)
484 }
485
486 fn extract_aggregate(&self, expr: &Expr) -> Option<(AggregateFunc, String)> {
488 if let Expr::Function { name, args } = expr {
489 let func = match name.to_uppercase().as_str() {
490 "COUNT" => Some(AggregateFunc::Count),
491 "SUM" => Some(AggregateFunc::Sum),
492 "AVG" => Some(AggregateFunc::Avg),
493 "MIN" => Some(AggregateFunc::Min),
494 "MAX" => Some(AggregateFunc::Max),
495 _ => None,
496 }?;
497
498 if let Some(arg) = args.first() {
499 match arg {
500 Expr::Column { name, .. } => {
501 return Some((func, name.clone()));
502 }
503 Expr::Wildcard => {
504 return Some((func, "*".to_string()));
506 }
507 _ => {}
508 }
509 } else if matches!(func, AggregateFunc::Count) {
510 return Some((func, "*".to_string()));
512 }
513 }
514 None
515 }
516
517 fn has_aggregates(&self, projection: &[SelectItem]) -> bool {
519 for item in projection {
520 if let SelectItem::Expr { expr, .. } = item
521 && self.extract_aggregate(expr).is_some()
522 {
523 return true;
524 }
525 }
526 false
527 }
528
529 fn execute_sort(
531 &self,
532 batches: Vec<RecordBatch>,
533 order_by: &[OrderByExpr],
534 ) -> Result<Vec<RecordBatch>> {
535 let sort = Sort::new(order_by.to_vec());
536 let mut result = Vec::new();
537
538 for batch in batches {
539 result.push(sort.execute(&batch)?);
540 }
541
542 Ok(result)
543 }
544
545 fn execute_limit_offset(
547 &self,
548 batches: Vec<RecordBatch>,
549 limit: Option<usize>,
550 offset: Option<usize>,
551 ) -> Result<Vec<RecordBatch>> {
552 let offset = offset.unwrap_or(0);
553 let mut current_row = 0;
554 let mut result = Vec::new();
555 let mut remaining = limit;
556
557 for batch in batches {
558 if let Some(rem) = remaining
559 && rem == 0
560 {
561 break;
562 }
563
564 let start = if current_row < offset {
565 let skip = (offset - current_row).min(batch.num_rows);
566 current_row += skip;
567 skip
568 } else {
569 0
570 };
571
572 let end = if let Some(rem) = remaining {
573 (start + rem).min(batch.num_rows)
574 } else {
575 batch.num_rows
576 };
577
578 if start < end {
579 let slice_batch = self.slice_batch(&batch, start, end)?;
580 let slice_rows = slice_batch.num_rows;
581 result.push(slice_batch);
582
583 if let Some(rem) = &mut remaining {
584 *rem = rem.saturating_sub(slice_rows);
585 }
586 }
587
588 current_row += batch.num_rows;
589 }
590
591 Ok(result)
592 }
593
594 fn slice_batch(&self, batch: &RecordBatch, start: usize, end: usize) -> Result<RecordBatch> {
596 let mut sliced_columns = Vec::new();
597
598 for column in &batch.columns {
599 sliced_columns.push(self.slice_column(column, start, end));
600 }
601
602 RecordBatch::new(batch.schema.clone(), sliced_columns, end - start)
603 }
604
605 fn slice_column(
607 &self,
608 column: &scan::ColumnData,
609 start: usize,
610 end: usize,
611 ) -> scan::ColumnData {
612 use scan::ColumnData;
613
614 match column {
615 ColumnData::Boolean(data) => ColumnData::Boolean(data[start..end].to_vec()),
616 ColumnData::Int32(data) => ColumnData::Int32(data[start..end].to_vec()),
617 ColumnData::Int64(data) => ColumnData::Int64(data[start..end].to_vec()),
618 ColumnData::Float32(data) => ColumnData::Float32(data[start..end].to_vec()),
619 ColumnData::Float64(data) => ColumnData::Float64(data[start..end].to_vec()),
620 ColumnData::String(data) => ColumnData::String(data[start..end].to_vec()),
621 ColumnData::Binary(data) => ColumnData::Binary(data[start..end].to_vec()),
622 }
623 }
624}
625
626fn canonical_agg_name(func: AggregateFunc, column: &str) -> String {
629 let fname = match func {
630 AggregateFunc::Count => "COUNT",
631 AggregateFunc::Sum => "SUM",
632 AggregateFunc::Avg => "AVG",
633 AggregateFunc::Min => "MIN",
634 AggregateFunc::Max => "MAX",
635 };
636 format!("{}({})", fname, column)
637}
638
639fn values_to_projection_column(values: &[Value]) -> Result<(ColumnData, scan::DataType)> {
647 use scan::DataType as Dt;
648
649 let mut has_string = false;
650 let mut has_float = false;
651 let mut has_int = false;
652 let mut has_bool = false;
653
654 for v in values {
655 match v {
656 Value::Null => {}
657 Value::String(_) => has_string = true,
658 Value::Float32(_) | Value::Float64(_) => has_float = true,
659 Value::Int32(_) | Value::Int64(_) => has_int = true,
660 Value::Boolean(_) => has_bool = true,
661 Value::Geometry(_) => {
662 return Err(QueryError::unsupported(
663 "projecting a geometry-valued expression is not supported (no geometry column storage)",
664 ));
665 }
666 }
667 }
668
669 let mismatch = || QueryError::execution("projection expression produced mixed value types");
670
671 if has_string {
672 let col = values
673 .iter()
674 .map(|v| match v {
675 Value::String(s) => Ok(Some(s.clone())),
676 Value::Null => Ok(None),
677 _ => Err(mismatch()),
678 })
679 .collect::<Result<Vec<_>>>()?;
680 return Ok((ColumnData::String(col), Dt::String));
681 }
682 if has_float {
683 let col = values
684 .iter()
685 .map(|v| match v {
686 Value::Float64(f) => Ok(Some(*f)),
687 Value::Float32(f) => Ok(Some(*f as f64)),
688 Value::Int64(i) => Ok(Some(*i as f64)),
689 Value::Int32(i) => Ok(Some(*i as f64)),
690 Value::Null => Ok(None),
691 _ => Err(mismatch()),
692 })
693 .collect::<Result<Vec<_>>>()?;
694 return Ok((ColumnData::Float64(col), Dt::Float64));
695 }
696 if has_int {
697 let col = values
698 .iter()
699 .map(|v| match v {
700 Value::Int64(i) => Ok(Some(*i)),
701 Value::Int32(i) => Ok(Some(*i as i64)),
702 Value::Null => Ok(None),
703 _ => Err(mismatch()),
704 })
705 .collect::<Result<Vec<_>>>()?;
706 return Ok((ColumnData::Int64(col), Dt::Int64));
707 }
708 if has_bool {
709 let col = values
710 .iter()
711 .map(|v| match v {
712 Value::Boolean(b) => Ok(Some(*b)),
713 Value::Null => Ok(None),
714 _ => Err(mismatch()),
715 })
716 .collect::<Result<Vec<_>>>()?;
717 return Ok((ColumnData::Boolean(col), Dt::Boolean));
718 }
719
720 Ok((
722 ColumnData::Int64(values.iter().map(|_| None).collect()),
723 Dt::Int64,
724 ))
725}
726
727impl Default for Executor {
728 fn default() -> Self {
729 Self::new()
730 }
731}
732
733#[cfg(test)]
734mod tests {
735 use super::*;
736 use crate::executor::scan::{DataType, Field, MemoryDataSource, Schema};
737 use crate::parser::sql::parse_sql;
738
739 #[tokio::test]
740 async fn test_executor_simple_query() -> Result<()> {
741 let schema = Arc::new(Schema::new(vec![
742 Field::new("id".to_string(), DataType::Int64, false),
743 Field::new("value".to_string(), DataType::Int64, false),
744 ]));
745
746 let columns = vec![
747 scan::ColumnData::Int64(vec![Some(1), Some(2), Some(3)]),
748 scan::ColumnData::Int64(vec![Some(10), Some(20), Some(30)]),
749 ];
750
751 let batch = RecordBatch::new(schema.clone(), columns, 3)?;
752 let source = Arc::new(MemoryDataSource::new(schema, vec![batch]));
753
754 let mut executor = Executor::new();
755 executor.register_data_source("test_table".to_string(), source);
756
757 let sql = "SELECT * FROM test_table";
758 let stmt = parse_sql(sql)?;
759
760 let result = executor.execute(&stmt).await?;
761 assert!(!result.is_empty());
762
763 Ok(())
764 }
765}