# Columnar Execution for Analytical Queries
This module implements **column-oriented query execution** that avoids materializing full `Row` objects during table scans, providing significant performance improvements for aggregation-heavy analytical workloads.
## Overview
Instead of the traditional row-by-row approach:
```text
TableScan → Row{Vec<SqlValue>} → Filter(Row) → Aggregate(Row) → Vec<Row>
```
We use column-at-a-time processing:
```text
TableScan → ColumnRefs → Filter(native types) → Aggregate → Row
```
## Performance Benefits
- **Zero-copy**: Work with `&SqlValue` references instead of cloning data
- **Cache-friendly**: Access contiguous column data instead of scattered row data
- **Type-specialized**: Skip `SqlValue` enum matching overhead for filters/aggregates
- **Minimal allocations**: Only allocate result rows, not intermediate data
## Benchmark Results
Based on `benches/columnar_execution.rs`:
| TPC-H Q6 style (filtered aggregation) | 10,000 | ~850μs | ~95μs | **8.9x** |
| TPC-H Q6 style (filtered aggregation) | 100,000 | ~8.5ms | ~950μs | **8.9x** |
| Simple aggregation (no filter) | 10,000 | ~650μs | ~75μs | **8.7x** |
| Selective filtering (~1% match) | 100,000 | ~9.2ms | ~1.1ms | **8.4x** |
**Key finding**: Columnar execution provides **~8-10x speedup** for analytical aggregate queries.
## When to Use Columnar Execution
### ✅ **Best For:**
1. **Aggregate queries with filtering**:
```sql
SELECT SUM(l_extendedprice), COUNT(*)
FROM lineitem
WHERE l_quantity < 24
AND l_discount BETWEEN 0.05 AND 0.07;
```
2. **Simple predicates on numeric/date columns**:
- Equality: `column = value`
- Comparisons: `column < value`, `column >= value`
- Ranges: `column BETWEEN low AND high`
3. **Aggregates**: SUM, COUNT, AVG, MIN, MAX
4. **Large tables** (thousands to millions of rows)
5. **High selectivity** (predicates that filter out many rows)
### ❌ **Not Suitable For:**
1. **JOINs**: Currently only supports single-table scans
2. **Window functions**: Requires row-level context
3. **Complex subqueries**: Needs full SQL AST integration
4. **Small result sets** (< 1000 rows): Overhead not worth it
5. **Complex expressions**: Requires AST expression evaluation
6. **String pattern matching**: `LIKE`, regex (not yet optimized)
## Architecture
### Components
1. **`scan.rs`**: `ColumnarScan` - Zero-copy column extraction from row slices
```rust
let scan = ColumnarScan::new(&rows);
let prices: Vec<&SqlValue> = scan.column(2).collect();
```
2. **`filter.rs`**: Predicate evaluation with selection bitmaps
```rust
let predicates = vec![ColumnPredicate::LessThan { column_idx: 0, value: SqlValue::Integer(24) }];
let bitmap = create_filter_bitmap(&scan, &predicates)?;
```
3. **`aggregate.rs`**: Type-specialized aggregate computation
```rust
let result = compute_columnar_aggregate(&scan, column_idx, AggregateOp::Sum, Some(&bitmap))?;
```
4. **`mod.rs`**: Entry point orchestrating scan → filter → aggregate pipeline
```rust
let results = execute_columnar_aggregate(&rows, &predicates, &aggregates)?;
```
### Data Flow
```text
┌──────────────┐
│ Input Rows │
└──────┬───────┘
│
▼
┌──────────────────┐
│ ColumnarScan │ ← Zero-copy column extraction
│ (references) │
└──────┬───────────┘
│
▼
┌──────────────────┐
│ Filter Bitmap │ ← Evaluate predicates column-by-column
│ [true, false...] │
└──────┬───────────┘
│
▼
┌──────────────────┐
│ Aggregate │ ← Compute aggregates on filtered columns
│ Computation │
└──────┬───────────┘
│
▼
┌──────────────────┐
│ Result Row │ ← Single row with aggregate values
└──────────────────┘
```
## Usage Example
```rust
use vibesql_executor::select::columnar::{
execute_columnar_aggregate, AggregateOp, ColumnPredicate,
};
use vibesql_storage::Row;
use vibesql_types::SqlValue;
// Create test data
let rows = vec![
Row::new(vec![SqlValue::Integer(10), SqlValue::Double(100.0)]),
Row::new(vec![SqlValue::Integer(20), SqlValue::Double(200.0)]),
Row::new(vec![SqlValue::Integer(30), SqlValue::Double(300.0)]),
];
// Define predicates: col0 < 25
let predicates = vec![ColumnPredicate::LessThan {
column_idx: 0,
value: SqlValue::Integer(25),
}];
// Define aggregates: SUM(col1), COUNT(*)
let aggregates = vec![
(1, AggregateOp::Sum),
(0, AggregateOp::Count),
];
// Execute columnar query
let result = execute_columnar_aggregate(&rows, &predicates, &aggregates)?;
// Result: [SqlValue::Double(300.0), SqlValue::Integer(2)]
assert_eq!(result[0].get(0), Some(&SqlValue::Double(300.0))); // SUM = 100 + 200
assert_eq!(result[0].get(1), Some(&SqlValue::Integer(2))); // COUNT = 2
```
## Future Enhancements
1. **AST Integration**: Convert `vibesql_ast::Expression` to `ColumnPredicate`
- Currently uses simplified predicate interface
- Full SQL expression support requires AST traversal and type inference
2. **SIMD Vectorization**: Process multiple values per instruction
- Use `std::simd` for filter evaluation
- Batch aggregation operations
3. **Selection Vectors**: Track filtered row indices without copying
- Instead of bitmap, use integer indices
- More cache-efficient for high selectivity
4. **GROUP BY Support**: Extend to grouped aggregation
- Hash-based grouping
- Sort-based grouping
5. **Late Materialization**: Defer row construction until absolutely needed
- Project only required columns
- Minimize data movement
6. **Adaptive Execution**: Choose row vs columnar based on query characteristics
- Estimate selectivity from table statistics
- Fall back to row-by-row for complex predicates
## Testing
Run the columnar execution tests:
```bash
cargo test --package vibesql-executor --lib select::columnar
```
Run benchmarks:
```bash
cargo bench --bench columnar_execution
```
## References
- **DuckDB**: Columnar execution model inspiration
- **Velox**: Meta's vectorized execution engine
- **MonetDB**: Column-at-a-time execution pioneer
- **Apache Arrow**: Columnar memory format standard