mini-sql-engine

A from-scratch SQL execution engine in C++17, built layer by layer from disk pages up to query execution: buffer-pooled storage, a B+ Tree index, ARIES-style write-ahead logging, MVCC snapshot isolation, and a Volcano-model executor with an equi-join optimizer.

Architecture

SQL text -> Lexer -> Parser -> AST
                                 |
                                 v
                    Optimizer (join pushdown / predicate pushdown)
                                 |
                                 v
              Volcano executors (scan / filter / join) --- open/next/close
                                 |
                                 v
   Catalog + TableHeap  <-->  BufferPoolManager (LRU-K)  <-->  DiskManager
                                 |
                    B+ Tree index (buffer-pooled pages)
                                 |
        MVCC (versioned rows, snapshot reads)   Log/Recovery Manager (ARIES-style WAL)

Highlights

• Buffer pool: fixed-size page cache with an LRU-K replacement policy and RAII page guards
• B+ Tree index: search, insert, and delete over buffer-pooled pages (own test suite for each operation)
• Storage: slotted TablePage / TableHeap layout on top of a raw DiskManager
• Recovery: ARIES-style WAL — log records, checkpointing, and crash recovery replay
• Concurrency: MVCC with newest-first version chains and snapshot-isolated reads
• Query execution: Volcano-model (open/next/close) iterators for scan, filter, and join, fed by a hand-rolled SQL lexer/parser/AST
• Optimizer: join and predicate pushdown for two-table equi-joins
• Differential testing: a Python reference engine (reference/reference_engine.py) plus a fuzz harness cross-check engine behavior

Build & test

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build

Sanitizers:

cmake -S . -B build-asan -DMINISQL_SANITIZER=address
cmake --build build-asan -j && ctest --test-dir build-asan

Benchmarks (Google Benchmark, incl. a YCSB-style workload):

./build/mini_sql_bench

Layout

• include/mini_sql/ — storage, buffer, index (B+ Tree), catalog, concurrency (MVCC), recovery (WAL), execution (executors, optimizer), sql (lexer/parser/AST)
• src/ — implementation for each module
• tests/ — GoogleTest unit tests per component (buffer pool, B+ Tree insert/search/delete, WAL, MVCC, recovery, parser, executor, join pushdown)
• benchmarks/ — Google Benchmark microbenchmarks for the B+ Tree and a YCSB-style workload
• reference/ — standalone Python reference engine + fuzz harness for differential testing

Each engine layer (storage, buffer pool, B+ Tree, WAL, MVCC, executors) is independently tested; the interactive mini_sql REPL binary is a work in progress toward wiring the parser through to full query execution.