vibesql_executor/select/executor/
arena_execution.rs

1//! Arena-based SELECT execution for zero-allocation prepared statement execution.
2//!
3//! This module provides arena-based execution of SELECT statements, enabling
4//! zero-allocation query execution for prepared statements with inline
5//! placeholder resolution.
6//!
7//! # Usage
8//!
9//! ```text
10//! use bumpalo::Bump;
11//! use vibesql_parser::arena_parser::ArenaParser;
12//!
13//! let arena = Bump::new();
14//! let stmt = ArenaParser::parse_sql("SELECT * FROM users WHERE id = ?", &arena)?;
15//! let params = &[SqlValue::Integer(42)];
16//! let result = executor.execute_select_arena(stmt, params)?;
17//! ```
18//!
19//! # Performance
20//!
21//! Arena-based execution provides:
22//! - Zero malloc/free overhead per query execution
23//! - Inline placeholder resolution (no AST cloning)
24//! - Direct evaluation without intermediate allocations
25//!
26//! This is particularly beneficial for OLTP workloads with high query rates.
27
28use std::{
29    cmp::Ordering,
30    collections::{HashMap, HashSet},
31};
32
33use vibesql_ast::arena::{
34    ArenaInterner, Expression as ArenaExpression, ExtendedExpr as ArenaExtendedExpr,
35    SelectItem as ArenaSelectItem, SelectStmt as ArenaSelectStmt,
36};
37use vibesql_storage::Row;
38use vibesql_types::SqlValue;
39
40use super::builder::SelectExecutor;
41use crate::{
42    errors::ExecutorError,
43    evaluator::{window::compare_values, ArenaExpressionEvaluator},
44    schema::CombinedSchema,
45};
46
47impl SelectExecutor<'_> {
48    /// Execute an arena-allocated SELECT statement with inline placeholder resolution.
49    ///
50    /// This method provides zero-allocation query execution for prepared statements.
51    /// Parameters are resolved inline during evaluation, avoiding AST cloning.
52    ///
53    /// # Arguments
54    ///
55    /// * `stmt` - Arena-allocated SELECT statement
56    /// * `params` - Parameter values for placeholder resolution
57    ///
58    /// # Returns
59    ///
60    /// Vector of result rows.
61    ///
62    /// # Limitations
63    ///
64    /// Currently supports simple SELECT queries without:
65    /// - JOINs (single table only)
66    /// - Subqueries
67    /// - Aggregates, GROUP BY, HAVING
68    /// - Window functions
69    /// - CTEs (WITH clause)
70    ///
71    /// For unsupported features, returns an error. Fall back to standard execution.
72    pub fn execute_select_arena<'arena>(
73        &self,
74        stmt: &ArenaSelectStmt<'arena>,
75        params: &[SqlValue],
76        interner: &'arena ArenaInterner<'arena>,
77    ) -> Result<Vec<Row>, ExecutorError> {
78        // Check for unsupported features
79        if stmt.with_clause.is_some() {
80            return Err(ExecutorError::UnsupportedExpression(
81                "Arena execution does not support WITH clause".to_string(),
82            ));
83        }
84
85        if stmt.set_operation.is_some() {
86            return Err(ExecutorError::UnsupportedExpression(
87                "Arena execution does not support set operations".to_string(),
88            ));
89        }
90
91        if stmt.group_by.is_some() || stmt.having.is_some() {
92            return Err(ExecutorError::UnsupportedExpression(
93                "Arena execution does not support GROUP BY/HAVING".to_string(),
94            ));
95        }
96
97        if stmt.distinct {
98            return Err(ExecutorError::UnsupportedExpression(
99                "Arena execution does not support DISTINCT".to_string(),
100            ));
101        }
102
103        // Check for aggregates in select list
104        if self.has_arena_aggregates(&stmt.select_list) {
105            return Err(ExecutorError::UnsupportedExpression(
106                "Arena execution does not support aggregate functions".to_string(),
107            ));
108        }
109
110        // Execute based on FROM clause
111        match &stmt.from {
112            Some(from) => self.execute_arena_with_from(stmt, from, params, interner),
113            None => self.execute_arena_without_from(stmt, params, interner),
114        }
115    }
116
117    /// Execute SELECT without FROM clause (expression-only).
118    fn execute_arena_without_from<'arena>(
119        &self,
120        stmt: &ArenaSelectStmt<'arena>,
121        params: &[SqlValue],
122        interner: &'arena ArenaInterner<'arena>,
123    ) -> Result<Vec<Row>, ExecutorError> {
124        // Create an empty schema and row for expression evaluation
125        let schema = CombinedSchema {
126            table_schemas: HashMap::new(),
127            total_columns: 0,
128            hidden_columns: HashSet::new(),
129            outer_schema: None,
130            duplicate_aliases: HashSet::new(),
131            joined_columns: HashSet::new(),
132            using_coalesce_indices: HashMap::new(),
133            column_replacement_map: HashMap::new(),
134            alias_tables: HashSet::new(),
135            shadowed_tables: HashMap::new(),
136        };
137        let empty_row = Row::new(vec![]);
138        let evaluator = ArenaExpressionEvaluator::new(&schema, params, interner);
139
140        // Evaluate each select item
141        let mut values = Vec::with_capacity(stmt.select_list.len());
142        for item in stmt.select_list.iter() {
143            match item {
144                ArenaSelectItem::Expression { expr, .. } => {
145                    let value = evaluator.eval(expr, &empty_row)?;
146                    values.push(value);
147                }
148                ArenaSelectItem::Wildcard { .. } | ArenaSelectItem::QualifiedWildcard { .. } => {
149                    // Wildcard without FROM is typically an error, but we'll skip it
150                    continue;
151                }
152            }
153        }
154
155        // Apply LIMIT/OFFSET (for expression-only, limit defaults to 1 row)
156        let rows = vec![Row::new(values)];
157        let limit = self.evaluate_arena_limit(&stmt.limit)?;
158        let offset = self.evaluate_arena_offset(&stmt.offset)?;
159        Ok(self.apply_arena_limit_offset(rows, limit, offset))
160    }
161
162    /// Execute SELECT with FROM clause.
163    fn execute_arena_with_from<'arena>(
164        &self,
165        stmt: &ArenaSelectStmt<'arena>,
166        from: &vibesql_ast::arena::FromClause<'arena>,
167        params: &[SqlValue],
168        interner: &'arena ArenaInterner<'arena>,
169    ) -> Result<Vec<Row>, ExecutorError> {
170        use vibesql_ast::arena::FromClause;
171
172        // Currently only support simple table reference
173        let (table_name, alias) = match from {
174            FromClause::Table { name, alias, .. } => (*name, *alias),
175            FromClause::Join { .. } => {
176                return Err(ExecutorError::UnsupportedExpression(
177                    "Arena execution does not support JOINs yet".to_string(),
178                ));
179            }
180            FromClause::Subquery { .. } => {
181                return Err(ExecutorError::UnsupportedExpression(
182                    "Arena execution does not support subqueries in FROM".to_string(),
183                ));
184            }
185        };
186
187        // Resolve table name symbol to string
188        let table_name_str = interner.resolve(table_name);
189
190        // Get the table
191        let table = self
192            .database
193            .get_table(table_name_str)
194            .ok_or_else(|| ExecutorError::TableNotFound(table_name_str.to_string()))?;
195
196        // Build schema - use alias if provided, otherwise table name
197        let schema_alias_str = alias.map(|a| interner.resolve(a)).unwrap_or(table_name_str);
198        let schema = CombinedSchema::from_table(schema_alias_str.to_string(), table.schema.clone());
199
200        // Create evaluator
201        let evaluator =
202            ArenaExpressionEvaluator::with_database(&schema, params, self.database, interner);
203
204        // Scan table and filter (only live rows)
205        // Issue #3790: Use scan_live() to filter out deleted rows
206        let mut results = Vec::new();
207        for (_, row) in table.scan_live() {
208            // Apply WHERE clause filter
209            if let Some(where_clause) = &stmt.where_clause {
210                let filter_result = evaluator.eval(where_clause, row)?;
211                let is_truthy = match filter_result {
212                    SqlValue::Boolean(b) => b,
213                    SqlValue::Null => false,
214                    SqlValue::Integer(n) => n != 0,
215                    SqlValue::Smallint(n) => n != 0,
216                    SqlValue::Bigint(n) => n != 0,
217                    SqlValue::Float(f) => f != 0.0,
218                    SqlValue::Real(f) => f != 0.0,
219                    SqlValue::Double(f) => f != 0.0,
220                    SqlValue::Numeric(f) => f != 0.0,
221                    // String types (SQLite coerces strings to numeric for boolean context)
222                    SqlValue::Varchar(ref s) | SqlValue::Character(ref s) => string_to_truthy(s),
223                    other => {
224                        return Err(ExecutorError::TypeError(format!(
225                            "WHERE clause must evaluate to boolean, got {:?}",
226                            other
227                        )));
228                    }
229                };
230                if !is_truthy {
231                    continue;
232                }
233            }
234
235            // Project columns
236            let projected =
237                self.project_arena_row(&stmt.select_list, row, &schema, &evaluator, interner)?;
238            results.push(projected);
239
240            // Check timeout periodically
241            if results.len() % 1000 == 0 {
242                self.check_timeout()?;
243            }
244        }
245
246        // Apply ORDER BY if present
247        if let Some(order_by) = &stmt.order_by {
248            self.sort_arena_results(&mut results, order_by.as_slice(), &schema, params, interner)?;
249        }
250
251        // Apply LIMIT/OFFSET
252        let limit = self.evaluate_arena_limit(&stmt.limit)?;
253        let offset = self.evaluate_arena_offset(&stmt.offset)?;
254        Ok(self.apply_arena_limit_offset(results, limit, offset))
255    }
256
257    /// Project a row according to the SELECT list.
258    fn project_arena_row<'arena>(
259        &self,
260        select_list: &[ArenaSelectItem<'arena>],
261        row: &Row,
262        schema: &CombinedSchema,
263        evaluator: &ArenaExpressionEvaluator<'_, 'arena>,
264        interner: &'arena ArenaInterner<'arena>,
265    ) -> Result<Row, ExecutorError> {
266        let mut values = Vec::with_capacity(select_list.len());
267
268        for item in select_list.iter() {
269            match item {
270                ArenaSelectItem::Expression { expr, .. } => {
271                    let value = evaluator.eval(expr, row)?;
272                    values.push(value);
273                }
274                ArenaSelectItem::Wildcard { .. } => {
275                    // Unqualified wildcard (*) - expand all columns
276                    values.extend(row.values.iter().cloned());
277                }
278                ArenaSelectItem::QualifiedWildcard { qualifier, .. } => {
279                    // Qualified wildcard (table.*) - expand columns from specific table
280                    let qualifier_str = interner.resolve(*qualifier);
281                    if let Some(&(start, ref tbl_schema)) = schema.get_table(qualifier_str) {
282                        for i in 0..tbl_schema.columns.len() {
283                            if let Some(val) = row.get(start + i) {
284                                values.push(val.clone());
285                            }
286                        }
287                    } else {
288                        // Table not found - expand all as fallback
289                        values.extend(row.values.iter().cloned());
290                    }
291                }
292            }
293        }
294
295        Ok(Row::new(values))
296    }
297
298    /// Sort results according to ORDER BY clause.
299    fn sort_arena_results<'arena>(
300        &self,
301        results: &mut Vec<Row>,
302        order_by: &[vibesql_ast::arena::OrderByItem<'arena>],
303        schema: &CombinedSchema,
304        params: &[SqlValue],
305        interner: &'arena ArenaInterner<'arena>,
306    ) -> Result<(), ExecutorError> {
307        use vibesql_ast::arena::OrderDirection;
308
309        // Create evaluator for order by expressions
310        let evaluator =
311            ArenaExpressionEvaluator::with_database(schema, params, self.database, interner);
312
313        // Pre-compute order by values for each row to avoid repeated evaluation
314        let mut keyed_rows: Vec<(Vec<SqlValue>, Row)> = results
315            .drain(..)
316            .map(|row| {
317                let keys: Result<Vec<_>, _> =
318                    order_by.iter().map(|item| evaluator.eval(&item.expr, &row)).collect();
319                keys.map(|k| (k, row))
320            })
321            .collect::<Result<_, _>>()?;
322
323        // Sort by keys with proper NULL handling
324        keyed_rows.sort_by(|(keys_a, _), (keys_b, _)| {
325            for (i, (key_a, key_b)) in keys_a.iter().zip(keys_b.iter()).enumerate() {
326                let order_item = order_by.get(i);
327                let asc = order_item.is_some_and(|o| matches!(o.direction, OrderDirection::Asc));
328
329                // Determine NULL ordering:
330                // - If explicitly specified via NULLS FIRST/LAST, use that
331                // - Default: SQLite treats NULL as smallest value, so:
332                //   - ASC: NULL comes first (smallest first)
333                //   - DESC: NULL comes last (smallest last)
334                let nulls_first = match order_item.and_then(|o| o.nulls_order) {
335                    Some(vibesql_ast::arena::NullsOrder::First) => true,
336                    Some(vibesql_ast::arena::NullsOrder::Last) => false,
337                    None => asc, // Default: NULLS FIRST for ASC, NULLS LAST for DESC
338                };
339
340                // Handle NULLs according to nulls_first setting
341                let cmp = match (key_a.is_null(), key_b.is_null()) {
342                    (true, true) => Ordering::Equal,
343                    (true, false) => {
344                        if nulls_first {
345                            return Ordering::Less; // NULL sorts before non-NULL
346                        } else {
347                            return Ordering::Greater; // NULL sorts after non-NULL
348                        }
349                    }
350                    (false, true) => {
351                        if nulls_first {
352                            return Ordering::Greater; // non-NULL sorts after NULL
353                        } else {
354                            return Ordering::Less; // non-NULL sorts before NULL
355                        }
356                    }
357                    (false, false) => {
358                        // Compare non-NULL values, respecting direction
359                        let cmp = compare_values(key_a, key_b);
360                        if asc {
361                            cmp
362                        } else {
363                            cmp.reverse()
364                        }
365                    }
366                };
367
368                if cmp != Ordering::Equal {
369                    return cmp;
370                }
371            }
372            Ordering::Equal
373        });
374
375        // Move sorted rows back to results
376        results.extend(keyed_rows.into_iter().map(|(_, row)| row));
377
378        Ok(())
379    }
380
381    /// Evaluate an arena LIMIT expression to a raw i64 value
382    /// Returns the raw integer value for further processing
383    fn evaluate_arena_limit_offset_expr_raw(
384        &self,
385        expr: &vibesql_ast::arena::Expression,
386    ) -> Result<i64, ExecutorError> {
387        match expr {
388            vibesql_ast::arena::Expression::Literal(vibesql_types::SqlValue::Integer(n)) => Ok(*n),
389            _ => Err(ExecutorError::InvalidLimitOffset {
390                clause: "LIMIT/OFFSET".to_string(),
391                value: "<expression>".to_string(),
392                reason: "must be a constant integer".to_string(),
393            }),
394        }
395    }
396
397    /// Evaluate optional arena LIMIT expression to Option<usize>
398    /// SQLite compatibility: any negative LIMIT means unlimited (returns None)
399    fn evaluate_arena_limit(
400        &self,
401        limit: &Option<vibesql_ast::arena::Expression>,
402    ) -> Result<Option<usize>, ExecutorError> {
403        match limit.as_ref().map(|e| self.evaluate_arena_limit_offset_expr_raw(e)).transpose()? {
404            Some(n) if n < 0 => Ok(None), // Any negative value means unlimited
405            Some(n) => Ok(Some(n as usize)),
406            None => Ok(None),
407        }
408    }
409
410    /// Evaluate optional arena OFFSET expression to Option<usize>
411    /// SQLite compatibility: any negative OFFSET is treated as 0
412    fn evaluate_arena_offset(
413        &self,
414        offset: &Option<vibesql_ast::arena::Expression>,
415    ) -> Result<Option<usize>, ExecutorError> {
416        match offset.as_ref().map(|e| self.evaluate_arena_limit_offset_expr_raw(e)).transpose()? {
417            Some(n) if n < 0 => Ok(Some(0)), // Negative offset treated as 0
418            Some(n) => Ok(Some(n as usize)),
419            None => Ok(None),
420        }
421    }
422
423    /// Apply LIMIT and OFFSET to results.
424    fn apply_arena_limit_offset(
425        &self,
426        mut results: Vec<Row>,
427        limit: Option<usize>,
428        offset: Option<usize>,
429    ) -> Vec<Row> {
430        // Apply offset first
431        if let Some(off) = offset {
432            if off >= results.len() {
433                return vec![];
434            }
435            results = results.into_iter().skip(off).collect();
436        }
437
438        // Apply limit
439        if let Some(lim) = limit {
440            results.truncate(lim);
441        }
442
443        results
444    }
445
446    /// Check if select list contains aggregate functions.
447    fn has_arena_aggregates<'arena>(&self, select_list: &[ArenaSelectItem<'arena>]) -> bool {
448        for item in select_list.iter() {
449            if let ArenaSelectItem::Expression { expr, .. } = item {
450                if self.arena_expr_has_aggregate(expr) {
451                    return true;
452                }
453            }
454        }
455        false
456    }
457
458    /// Check if an arena expression contains an aggregate function.
459    fn arena_expr_has_aggregate<'arena>(&self, expr: &ArenaExpression<'arena>) -> bool {
460        match expr {
461            // Hot-path inline variants
462            ArenaExpression::BinaryOp { left, right, .. } => {
463                self.arena_expr_has_aggregate(left) || self.arena_expr_has_aggregate(right)
464            }
465            ArenaExpression::UnaryOp { expr, .. } => self.arena_expr_has_aggregate(expr),
466            ArenaExpression::IsNull { expr, .. } => self.arena_expr_has_aggregate(expr),
467            ArenaExpression::IsDistinctFrom { left, right, .. } => {
468                self.arena_expr_has_aggregate(left) || self.arena_expr_has_aggregate(right)
469            }
470            ArenaExpression::IsTruthValue { expr, .. } => self.arena_expr_has_aggregate(expr),
471            ArenaExpression::Conjunction(children) | ArenaExpression::Disjunction(children) => {
472                children.iter().any(|c| self.arena_expr_has_aggregate(c))
473            }
474            ArenaExpression::Literal(_)
475            | ArenaExpression::Placeholder(_)
476            | ArenaExpression::NumberedPlaceholder(_)
477            | ArenaExpression::NamedPlaceholder(_)
478            | ArenaExpression::ColumnRef { .. }
479            | ArenaExpression::Wildcard
480            | ArenaExpression::CurrentDate
481            | ArenaExpression::CurrentTime { .. }
482            | ArenaExpression::CurrentTimestamp { .. }
483            | ArenaExpression::Default => false,
484            // Cold-path extended variants
485            ArenaExpression::Extended(ext) => self.arena_extended_has_aggregate(ext),
486        }
487    }
488
489    /// Check if an extended expression contains an aggregate function.
490    fn arena_extended_has_aggregate<'arena>(&self, ext: &ArenaExtendedExpr<'arena>) -> bool {
491        match ext {
492            ArenaExtendedExpr::AggregateFunction { .. } => true,
493            ArenaExtendedExpr::Function { args, .. } => {
494                args.iter().any(|a| self.arena_expr_has_aggregate(a))
495            }
496            ArenaExtendedExpr::Case { operand, when_clauses, else_result, .. } => {
497                operand.as_ref().is_some_and(|o| self.arena_expr_has_aggregate(o))
498                    || when_clauses.iter().any(|w| {
499                        w.conditions.iter().any(|c| self.arena_expr_has_aggregate(c))
500                            || self.arena_expr_has_aggregate(&w.result)
501                    })
502                    || else_result.as_ref().is_some_and(|e| self.arena_expr_has_aggregate(e))
503            }
504            ArenaExtendedExpr::Between { expr, low, high, .. } => {
505                self.arena_expr_has_aggregate(expr)
506                    || self.arena_expr_has_aggregate(low)
507                    || self.arena_expr_has_aggregate(high)
508            }
509            ArenaExtendedExpr::InList { expr, values, .. } => {
510                self.arena_expr_has_aggregate(expr)
511                    || values.iter().any(|v| self.arena_expr_has_aggregate(v))
512            }
513            ArenaExtendedExpr::Cast { expr, .. } => self.arena_expr_has_aggregate(expr),
514            ArenaExtendedExpr::Like { expr, pattern, .. } => {
515                self.arena_expr_has_aggregate(expr) || self.arena_expr_has_aggregate(pattern)
516            }
517            _ => false,
518        }
519    }
520}
521
522/// Convert string to boolean using SQLite semantics
523#[inline(always)]
524fn string_to_truthy(s: &str) -> bool {
525    if s.is_empty() {
526        return false;
527    }
528    let trimmed = s.trim();
529    if trimmed.is_empty() {
530        return false;
531    }
532    // Parse leading numeric portion
533    let mut end = 0;
534    let mut has_dot = false;
535    let mut has_digit = false;
536    let chars: Vec<char> = trimmed.chars().collect();
537    if !chars.is_empty() && (chars[0] == '-' || chars[0] == '+') {
538        end = 1;
539    }
540    while end < chars.len() {
541        let c = chars[end];
542        if c.is_ascii_digit() {
543            has_digit = true;
544            end += 1;
545        } else if c == '.' && !has_dot {
546            has_dot = true;
547            end += 1;
548        } else {
549            break;
550        }
551    }
552    if !has_digit {
553        return false;
554    }
555    let num_str: String = chars[..end].iter().collect();
556    num_str.parse::<f64>().map(|n| n != 0.0).unwrap_or(false)
557}
vibesql_executor/select/executor/arena_execution.rs

vibesql_executor/select/executor/
arena_execution.rs
