Skip to content

PHASE_8_ANALYTICS.md

Latest commit

 

History

History
71 lines (59 loc) · 6.09 KB

PHASE_8_ANALYTICS.md

File metadata and controls

71 lines (59 loc) · 6.09 KB

Phase 8: Analytics Performance (Columnar & Vectorized)

Overview

Phase 8 introduced native columnar storage and a vectorized execution engine to drastically improve the performance of analytical workloads.

Key Components

1. Columnar Storage Layer (src/storage/columnar_table.cpp)

Implemented a high-performance column-oriented data store.

  • Binary Column Files: Stores data in contiguous binary files on disk, one per column.
  • Batch Read/Write: Optimized I/O paths for loading and retrieving large blocks of data efficiently.
  • Schema-Defined Layout: Automatically organizes data based on the table's schema definition.

2. Vectorized Data Structures (include/executor/types.hpp)

Developed SIMD-friendly contiguous memory buffers for batch processing.

  • ColumnVector & NumericVector: Specialized C++ templates for storing a "vector" of data for a single column.
  • StringVector: Variable-length string storage for TEXT/VARCHAR/CHAR columns.
  • VectorBatch: A collection of ColumnVector objects representing a chunk of rows (typically 1024 rows).

3. Vectorized Execution Engine (include/executor/vectorized_operator.hpp)

Built a batch-at-a-time physical execution model.

  • Vectorized Operators: Implemented Scan, Filter, Project, Aggregate, and GroupBy operators designed for chunk-based execution.
  • Batch-at-a-Time Interface: Operators pass entire VectorBatch objects between themselves, minimizing virtual function call overhead.

4. High-Performance Aggregation

Optimized global analytical queries (COUNT, SUM).

  • Vectorized Global Aggregate: Aggregates entire batches of data with minimal branching and high cache locality.
  • Type-Specific Aggregation: Leverages C++ templates to generate highly efficient aggregation logic for different data types.

5. Vectorized GROUP BY

Added VectorizedGroupByOperator for hash-based grouped aggregation.

  • Hash-Based Grouping: Uses OpenAddressHashAgg with linear probing for efficient group key lookup with collision-safe key encoding.
  • Two-Phase Processing: Input phase builds hash table from batches; Output phase serves grouped results incrementally.
  • DirectIndexAgg: For single INT64 column GROUP BY with keys in -128 to 127 range, uses direct array indexing (O(1) lookup).
  • Supported Aggregates: COUNT(*), SUM, MIN, and MAX with INT64/FLOAT64 columns.
  • Type-Specific Accumulators: SUM uses separate sums_int64 and sums_float64 accumulators to preserve precision for large INT64 values.
  • Collision-Safe Key Encoding: Group keys use binary encoding [type_tag][data...] with dedicated markers (0x01=NULL, 0x02=INT64, 0x04=STRING).
  • Pre-resolved Column Indices: Group-by column indices computed once in constructor to avoid repeated lookups.
  • Parallel Aggregation: Optional ThreadPool support partitions rows by hash % num_threads_, each thread builds local OpenAddressHashAgg, merged at output phase (9-15x speedup vs DuckDB on Q6).

6. Vectorized Hash Join (VectorizedHashJoinOperator)

Implemented a vectorized hash join with graceful partitioning and batch-based processing.

  • Graceful Hash Partitioning: Right table is partitioned into 64 hash buckets (NUM_BUCKETS) for collision-safe key-based partitioning.
  • Two-Phase Processing: BuildRight phase constructs hash table from right relation; ProbeLeft phase probes with left rows.
  • Resumable Bucket Scanning: Uses resuming_bucket_scan_, resumed_bucket_idx_, resumed_entry_idx_, and resumed_key_val_ to resume interrupted bucket scans when batch capacity is reached, preventing batch overflow during multi-match probes.
  • Batch Size: Output batches use BATCH_SIZE (1024 rows) for memory-efficient processing.
  • Join Type Support: INNER, LEFT, RIGHT, and FULL outer joins supported.
    • INNER: Only matched rows emitted.
    • LEFT: Unmatched left rows emitted with NULLs for right columns.
    • RIGHT: Unmatched right rows emitted with NULLs for left columns; uses right_matched_ bitmap and right_bucket_rows_ global storage during probe to track matched right rows.
    • FULL: Combines LEFT and RIGHT logic — unmatched left rows emitted during probe, unmatched right rows emitted at end via emit_unmatched_right_rows().
  • Matched Row Tracking: left_matched_in_batch_ tracks matched rows within the current batch for LEFT join unmatched emission. right_matched_ bitmap tracks matched right rows for RIGHT/FULL joins across all probe batches. right_bucket_rows_ provides global row storage for unmatched right row emission.

7. Parallel Vectorized Execution

Added ThreadPool class and parallel operator variants for multi-threaded batch processing.

  • ThreadPool (include/executor/thread_pool.hpp): Fixed-size thread pool for parallel task execution with wait/timeout support.
  • ParallelVectorizedSeqScanOperator: Multi-threaded scan over ColumnarTable using ThreadPool for parallel batch processing.
  • VectorizedGroupByOperator with ThreadPool: Parallel hash-based grouped aggregation leveraging ThreadPool for concurrent group processing.
  • QueryExecutor Integration: set_parallel(true) mode enables vectorized batch execution via build_vectorized_plan(). Queries with ORDER BY or LIMIT fall back to Volcano path since SortOperator/LimitOperator do not inherit from VectorizedOperator.
  • Batch Iteration: Vectorized path uses next_batch(VectorBatch&) instead of next(Tuple&), converting batches to result rows for QueryResult output.

Recent Improvements (Engine Benchmarking)

As of our latest sprint, we have established a high-performance baseline for the engine's core scanning logic:

  • Baseline Speed: 181M rows/s (Sequential Scan).
  • Core Technology: Zero-allocation TupleView classes and lazy deserialization.
  • Comparison: Outperforms SQLite by 9x in raw scan throughput.

This provides the necessary groundwork for future SIMD and full vectorized optimizations.

Status: 100% Test Pass

Successfully verified the end-to-end vectorized pipeline, including columnar data persistence and complex analytical query patterns, through dedicated integration tests.