![License: None](https://img.shields.io/badge/License-None-red)

> [!WARNING]
> **No License** - This project is protected by copyright. The code may only be viewed, but not used, modified, or redistributed. See [LICENSE](./LICENSE).

---

# PaulDB 🏳️‍🌈🔀📊

Handcrafted HTAP database in C and C++  
*Delta-merge meets columnar analytics, crafted for everyone*

Row+Column Storage, Delta-Merge, inspired by SAP HANA. A long-term artisan project where every data structure is designed from scratch.

`Status: 🌱 Vision Phase` · `Languages: C (Storage Engine) + C++ (Engine Logic & SQL)` · `Model: In-Memory HTAP`

---

## About

I'm Paul, 21, an aspiring SAP developer, and databases are my favorite topic.
Not because I have to use them, but because I want to know **why** they work the way they work.
Storing knowledge, structuring it, finding it again - to me that's almost philosophy.

PaulDB is my most personal project. No assignment, no homework, no client work.
Just me and the question: **Can I build a database from scratch?**

This repo lives on my own Gitea server - `git.paulvincenthorn.de` - because the infrastructure belongs to me too. Self-built, self-hosted.

---

## What is PaulDB?

PaulDB is my attempt to write a database from the ground up.
Not because the world needs another database, but because I want to know **why** databases work the way they work.

The guiding question is concrete and ambitious:

> **How do you keep OLTP and OLAP fast in a single system simultaneously - HTAP - and how does SAP HANA do it with Delta and Main?**

PaulDB is the answer I give myself in code. My "Crafting Interpreters", but for databases.

---

## Why C and C++?

A deliberate decision - not out of habit, but with intent:

| Layer | Language | Why |
|---|---|---|
| **Storage Engine** | **C** | Full control over bytes, pages, memory layout. No overhead, no abstraction loss. A storage engine lives at the byte level - C is made for that. |
| **Engine Logic & SQL** | **C++** | STL, RAII, class hierarchies for AST, higher abstractions for Parser, Planner, MVCC. The complexity of the upper layers deserves a more expressive language. |
| **Interface** | **C ABI** | `extern "C"` - zero overhead, clean boundary. C++ calls C functions as if they were its own. |

```mermaid
graph LR
    subgraph C ["C - Storage Engine"]
        SP[Slotted Pages]
        BP[Buffer Pool]
        BT[B+Tree Pages]
        WAL[Write-Ahead Log]
        AR[Arena Allocator]
        FSM[Free Space Map]
    end
    subgraph CPP ["C++ - Engine Logic"]
        QR[Query Router]
        DM[Delta-Merge]
        MVCC[MVCC Manager]
        EX[Query Executor]
    end
    subgraph SQL ["C++ - SQL Frontend"]
        TOK[Tokenizer]
        PAR[Parser]
        AST[AST]
        PL[Planner]
    end
    C -->|"storage.h (extern C)"| CPP
    TOK --> PAR --> AST --> PL --> EX
```

---

## The North Star: HTAP

Classic systems force a choice between two worlds:

| Workload | Optimized for | Storage form | Example query |
|---|---|---|---|
| **OLTP** | many small read/write operations | Row-Store (rows) | `INSERT ...` - `SELECT ... WHERE id = 42` |
| **OLAP** | few large aggregations | Column-Store (columns) | `SELECT cat, SUM(val) ... GROUP BY cat` |

**HTAP** (Hybrid Transactional/Analytical Processing) wants *both* in one system.
This is the only benchmark against which PaulDB measures every decision: what sharpens the HTAP proof comes first. Everything else waits.

---

## The HANA Blueprint: Delta & Main

SAP HANA solves HTAP elegantly via two areas per table:

```mermaid
flowchart LR
    W[Writes] --> DELTA["DELTA<br/>Row-Store - write-optimized"]
    R[Read analytics] --> MAIN["MAIN<br/>Column-Store - read-optimized, compressed"]
    DELTA -- "Delta-Merge (periodic)" --> MAIN
```

- **Delta** - write-optimized, takes in new data quickly (OLTP side).
- **Main** - read-optimized, heavily compressed, ideal for analytics (OLAP side).
- **Delta-Merge** - periodically pushes Delta into Main, keeping reads fast.

This principle is the heart of PaulDB.

### The Merge Process in Detail

```mermaid
sequenceDiagram
    participant Client
    participant Router as Query Router
    participant Delta as Delta (Row)
    participant Merge as Merge Worker
    participant Main as Main (Column)
    Client->>Router: INSERT INTO products VALUES(...)
    Router->>Delta: Write row (row format)
    Delta-->>Router: OK
    Note over Delta,Main: Time passes... Delta grows
    Merge->>Delta: Read all new rows
    Merge->>Merge: Transpose Row -> Column
    Merge->>Merge: Build dictionary encoding
    Merge->>Merge: Apply advanced compression
    Merge->>Main: Write compressed columns
    Merge->>Delta: Delete merged rows
    Client->>Router: SELECT cat, SUM(val) GROUP BY cat
    Router->>Main: Column scan (compressed, cache-friendly)
    Router->>Delta: Check unmerged rows
    Router-->>Client: Delta union Main result
```

---

## Architecture (In-Memory, HTAP-centric)

In-Memory is **not a compromise** here - it is authentic: HANA is primarily in-memory, Delta and Main live in RAM. Persistence to disk is therefore an *optional* later stage, not the foundation.

```mermaid
flowchart TD
    SQL["SQL Frontend (C++)<br/>Tokenizer -> AST -> Planner"]
    ROUTER{"Query Router (C++)<br/>OLTP or OLAP?"}
    DELTA["DELTA - Row-Store (C)<br/>(in-memory, write-optimized)"]
    MAIN["MAIN - Column-Store (C)<br/>(in-memory, compressed)"]
    MERGE["Delta-Merge Worker (C++)<br/>(periodic)"]
    SQL --> ROUTER
    ROUTER -->|"INSERT / point-SELECT"| DELTA
    ROUTER -->|"GROUP BY / aggregation"| MAIN
    DELTA -. "Read queries see Delta union Main" .-> MAIN
    DELTA ==>|merge| MERGE ==> MAIN
```

### PaulDB Layers

```mermaid
graph TD
    subgraph "Layer 5 - SQL Frontend (C++)"
        A[Tokenizer] --> B[Parser] --> C[AST] --> D[Planner]
    end
    subgraph "Layer 4 - Engine Logic (C++)"
        E[Query Executor]
        F[Query Router]
        G[Delta-Merge Orchestrator]
        H[MVCC Transaction Manager]
    end
    subgraph "Layer 3 - Storage Engine (C)"
        I[Slotted Pages]
        J[B+Tree Pages]
        K[Buffer Pool + LRU]
        L[Free Space Map]
        M[Catalog Page]
    end
    subgraph "Layer 2 - Memory Management (C)"
        N[Arena Allocator]
        O[Page Allocator]
    end
    subgraph "Layer 1 - Persistence (C + C++)"
        P[WAL - Write-Ahead Log]
        Q[Snapshot + Recovery]
    end
    subgraph "Layer 0 - Runtime"
        R[C Standard Library + C++ STL]
        S[mmap - fsync - POSIX]
    end
    D --> E --> F
    F --> I & J
    G --> I & J
    H --> E
    I & J --> K --> N & O
    K --> P
    P --> Q
    N & O --> R & S
```

---

## Core Ideas in Detail

### Delta (Row) vs. Main (Column)

Writing a row into the **Delta** store is cheap - you just append it.
Aggregating over a **column** in the **Main** store is cheap - all values of one column lie contiguously and cache-friendly in memory. PaulDB leverages both strengths and bridges them with the merge.

### Slotted Pages - The Foundation (C)

Every page is a 4 KiB byte array. The layout from low to high address:

| Address range | Content | Direction |
|---|---|---|
| `[0]` | Page Header: `page_id`, `num_slots`, `free_space_offset` | fixed |
| `[sizeof(Header) ...]` | Slot array: `(offset, length)` per inserted tuple | grows toward end --> |
| `[...]` | Free space | - |
| `[... PAGE_SIZE]` | Tuple data: raw bytes, newest at lowest address | <-- grows toward start |

Slots and tuple data grow toward each other. When they meet, the page is full.

### B+Tree - Indexes (C)

```mermaid
graph TD
    ROOT["Root Node<br/>[30]"]
    L["Inner Node<br/>[10, 20]"]
    R["Inner Node<br/>[40, 50]"]
    LL["Leaf<br/>[1,5,8]"]
    LM["Leaf<br/>[10,15,18]"]
    LR["Leaf<br/>[20,25,28]"]
    RL["Leaf<br/>[30,35,38]"]
    RM["Leaf<br/>[40,45,48]"]
    RR["Leaf<br/>[50,55,60]"]
    ROOT --> L & R
    L --> LL & LM & LR
    R --> RL & RM & RR
    LL -.-> LM -.-> LR -.-> RL -.-> RM -.-> RR
```

- **Inner Nodes:** Separator keys and pointers to children only.
- **Leaf Nodes:** Contain `(key, page_id, slot_id)` - pointing to the actual data.
- **Linked List:** Leaf nodes are chained for range scans.
- **Lookup:** O(log n) instead of O(n) - the difference that makes OLTP fast.

### Compression in the Column-Store

Two-stage compression model mirroring HANA:

**Stage 1 - Dictionary Encoding (always):**
Each column gets a sorted dictionary of its distinct values. The actual column becomes a vector of **integer value-IDs** (index into the dictionary). This alone makes the column small *and* makes scans/aggregations fast, because you iterate over compact integers instead of strings.

```mermaid
graph LR
    subgraph "Raw data"
        O1["'ABAP'"]
        O2["'HANA'"]
        O3["'ABAP'"]
        O4["'Fiori'"]
        O5["'ABAP'"]
    end
    subgraph "Dictionary"
        D0["0 -> 'ABAP'"]
        D1["1 -> 'Fiori'"]
        D2["2 -> 'HANA'"]
    end
    subgraph "Value-ID vector"
        V["[0, 2, 0, 1, 0]"]
    end
    O1 & O2 & O3 & O4 & O5 --> D0 & D1 & D2 --> V
```

**Stage 2 - Advanced Compression** on the value-ID vector. The cheapest method is chosen per column:

| Method | Idea | Best for | Example |
|---|---|---|---|
| **Prefix** | store dominant start value once | columns with one dominant value | status column: 95% = "active" |
| **Run-Length (RLE)** | "value x count" instead of repetitions | long runs of repeated values | sorted columns |
| **Cluster** | blocks of recurring patterns | locally clustered values | time series |
| **Sparse** | omit most frequent value, store only exceptions | sparse columns | columns with many NULLs |
| **Indirect** | reference common values across blocks indirectly | medium cardinality | category columns |

### Query Router = The HTAP Proof

The router is the moment where PaulDB visibly becomes HTAP: the same engine serves a `SELECT ... WHERE id = ...` via the row path (Delta + Main) and a `... GROUP BY ...` via the column path (Main). A read query always sees **Delta union Main**, so freshly written data immediately appears in analytics.

```mermaid
flowchart LR
    Q1["SELECT * FROM t<br/>WHERE id = 42"] -->|"Point query"| ROW["Row path<br/>(Delta -> B+Tree lookup)"]
    Q2["SELECT cat, SUM(val)<br/>FROM t GROUP BY cat"] -->|"Aggregation"| COL["Column path<br/>(Main -> column scan)"]
    ROW --> RESULT["Result:<br/>Delta union Main"]
    COL --> RESULT
```

### MVCC - Multi-Version Concurrency Control

```mermaid
sequenceDiagram
    participant T1 as Transaction 1 (Writer)
    participant T2 as Transaction 2 (Reader)
    participant Delta as Delta Store
    T1->>Delta: BEGIN - INSERT (id=1, val='ABAP')
    T2->>Delta: BEGIN - SELECT * FROM t
    Note over T2,Delta: T2 sees snapshot BEFORE T1's INSERT
    T1->>Delta: COMMIT (version=5)
    Note over T2,Delta: T2 still sees old snapshot
    T2->>Delta: COMMIT
    Note over T2,Delta: Next transaction sees version=5
```

---

## Layer Responsibilities

| Component | Language | Why |
|---|---|---|
| Slotted Pages | C | Byte-level operations, fixed layout |
| B+Tree Pages | C | Split/merge at page level, pointer arithmetic |
| Free Space Map | C | Bitmap, simple and performant |
| Arena Allocator | C | Bulk allocation, no `free()` needed |
| Buffer Pool (LRU) | C | Page cache, pin/unpin, eviction |
| WAL | C | Sequential writes, byte format |
| Query Router | C++ | Decision logic, pattern matching |
| SQL Parser + AST | C++ | `std::string`, class hierarchy, Visitor pattern |
| Delta-Merge Orchestrator | C++ | Coordination, reads C-Delta, writes C-Main |
| MVCC Manager | C++ | Snapshot management, transaction IDs |
| Query Executor | C++ | Iterator model (Volcano), polymorphic operators |

### The Bridge: `storage.h`

```c
/* storage.h - the C-ABI boundary between the worlds */
#ifndef PAULDB_STORAGE_H
#define PAULDB_STORAGE_H
#include <stdint.h>
#include <stddef.h>
#ifdef __cplusplus
extern "C" {
#endif

/* --- Page Management --- */
typedef struct Page Page;
Page*    page_create(uint32_t page_id);
int      page_insert(Page* p, const void* data, size_t len);
void*    page_get(Page* p, uint16_t slot_id, size_t* out_len);
void     page_free(Page* p);

/* --- Heap (Multi-Page Row Store) --- */
typedef struct Heap Heap;
Heap*    heap_create(void);
int      heap_insert(Heap* h, const void* data, size_t len);
void     heap_full_scan(Heap* h, void (*callback)(const void*, size_t));
void     heap_free(Heap* h);

/* --- B+Tree Index --- */
typedef struct BTree BTree;
BTree*   btree_create(void);
int      btree_insert(BTree* bt, int64_t key, uint32_t page_id, uint16_t slot_id);
int      btree_lookup(BTree* bt, int64_t key, uint32_t* out_page, uint16_t* out_slot);
void     btree_free(BTree* bt);

#ifdef __cplusplus
}
#endif
#endif /* PAULDB_STORAGE_H */
```

---

## Roadmap

Step by step - each stage is a complete learning goal in itself.

```mermaid
gantt
    title PaulDB Development Phases
    dateFormat YYYY-MM
    axisFormat %b %Y
    section Foundation
        E0 - Project structure + CMake + CI          :e0, 2026-06, 2026-07
    section Storage Engine (C)
        E1 - Row-Store (Slotted Pages, Heap)         :e1, after e0, 60d
        E3 - Column-Store (Dictionary + Compression) :e3, after e1, 60d
    section SQL Frontend (C++)
        E2 - Mini-SQL Parser (INSERT + SELECT)       :e2, after e0, 90d
        E6 - SQL extensions (GROUP BY, JOIN)         :e6, after e5, 60d
    section HTAP Core
        E4 - Delta-Merge                             :crit, e4, after e3, 45d
        E5 - Query Router (HTAP proof)               :crit, e5, after e4, 30d
    section Advanced
        E7 - MVCC / Transactions                     :e7, after e5, 45d
        E8 - Persistence (WAL + Recovery)            :e8, after e7, 60d
```

### Stages in Detail

- [ ] **E0 - Project Structure + Build System**
    - CMake project: compile and link C and C++ together
    - Directory structure: `src/`, `include/`, `test/`, `docs/`, `examples/`
    - CI: Gitea Actions with `cmake --build` + `ctest`
    - First exercise: compile a C file and a C++ file and link them via `extern "C"`

- [ ] **E1 - In-Memory Row-Store / Delta (C)**
    - Slotted Page: 4 KiB byte array, header, slots, `page_insert()` / `page_get()`
    - Heap: multiple Slotted Pages, `heap_insert()` / `heap_full_scan()`
    - C++ wrapper: `RowStore` class encapsulating C functions
    - Tests: insert, scan, page overflow

- [ ] **E2 - Mini-SQL Parser (C++)**
    - Tokenizer: `SELECT`, `INSERT`, `WHERE`, identifiers, integers, strings
    - Parser: recursive descent -> AST (class hierarchy with Visitor pattern)
    - Executor: `INSERT INTO t VALUES(...)` + `SELECT ... WHERE id = ?`
    - Tests: parse roundtrips, executor integration

- [ ] **E3 - In-Memory Column-Store / Main (C)**
    - Column vectors: one array per column instead of per row
    - Dictionary encoding: sorted dictionary + value-ID vector
    - Advanced compression: Prefix, RLE, Cluster, Sparse, Indirect
    - C++ wrapper: `ColumnStore` class
    - Tests: measure compression ratio, scan performance

- [ ] **E4 - Delta-Merge**
    - Periodic merge: Delta (Row) -> Main (Column)
    - Row-to-column transposition
    - Rebuild dictionary, apply compression
    - Merge trigger: threshold (e.g. every 1000 inserts)
    - Tests: data identical before/after merge, compression takes effect

- [ ] **E5 - Query Router (HTAP Proof)**
    - Point query -> row path (Delta, then B+Tree on Main)
    - Aggregation -> column path (Main scan)
    - Read queries always see Delta union Main
    - Tests: same query, both paths, same result

- [ ] **E6 - SQL Extensions (C++)**
    - `GROUP BY` + aggregate functions: `SUM`, `COUNT`, `AVG`, `MIN`, `MAX`
    - `JOIN` (nested loop, then hash join)
    - `ORDER BY` + `LIMIT`
    - Tests: TPC-H inspired mini queries

- [ ] **E7 - MVCC / Transactions (C++)**
    - Snapshot isolation: each transaction sees a consistent state
    - Transaction IDs and version chains
    - Consistent read view during Delta-Merge
    - Tests: concurrent read + write, isolation verified

- [ ] **E8 - *(optional)* Persistence (C + C++)**
    - WAL: Write-Ahead Log in C (sequential writes)
    - Snapshot: periodic checkpoint
    - Recovery: WAL replay after crash
    - Turning "proof" into "real DB"

---

## Design Decisions (Mini-ADR)

Deliberate choices that everything aligns with:

| # | Decision | Rationale |
|---|---|---|
| 1 | **North star = HTAP proof** | Every stage serves the goal of demonstrating Delta-Merge + Row/Column in one engine. That is why Delta-Merge is at E4, not the end. |
| 2 | **In-Memory first** | Authentic to HANA, faster success. Disk is optional (E8). |
| 3 | **C + C++ instead of Rust** | Full byte-level control in C for the storage engine; C++ for higher abstractions. Both connected via C ABI. More reference material available (CMU 15-445, SQLite, etc.). |
| 4 | **Full SQL as long-term goal** | Start with mini-SQL (E2), deliberately building toward `GROUP BY`/`JOIN` (E6) - because without aggregations you cannot demonstrate the OLAP side. |
| 5 | **No external dependencies** | Everything built from scratch. No SQLite, no RocksDB, no third-party library. Only C stdlib and C++ STL. |

### Complexity Overview

| Operation | Without Index | With B+Tree |
|---|---|---|
| Point lookup | O(n) full scan | O(log n) |
| Range scan | O(n) | O(log n + k) |
| Insert (Row/Delta) | O(1) append | O(log n) index update |
| Aggregation (Column) | O(n) column scan | O(n) - but cache-friendly + compressed |

---

## Theoretical Foundation

The shoulders PaulDB stands on:

```mermaid
mindmap
  root((PaulDB Theory))
    Relational Theory
      Codd's 12 Rules
      Relational Algebra sigma pi join div
      Functional Dependencies
      Normal Forms
    Storage Models
      NSM / Row-Store
      DSM / Column-Store
      PAX / Hybrid
      Delta-Merge (HANA)
    Index Structures
      B+Tree
      Hash Index
      LSM Tree
    Compression
      Dictionary Encoding
      RLE
      Prefix
      Cluster / Sparse / Indirect
    Query Processing
      Parsing + AST
      Planner + Optimizer
      Volcano / Iterator Model
      Join Algorithms
    Transactions
      ACID
      MVCC
      Snapshot Isolation
      WAL + ARIES
    Operating Systems
      Virtual Memory / mmap
      Page Cache
      fsync / Durability
      Concurrency / Threads
```

---

## Tooling

| Category | Tool | Purpose |
|---|---|---|
| Build | **CMake** | C and C++ mixed, platform-independent |
| Package Manager | **Conan 2** | Dependency management + private registry on Gitea |
| Tests | **CTest** | Test runner, integrated into CMake |
| CI/CD | **Gitea Actions** | Automatic build + test on every push |
| Debugging | **GDB / LLDB** | Breakpoints, memory inspection |
| Sanitizer | **AddressSanitizer** | Buffer overflows, use-after-free |
| Sanitizer | **UndefinedBehaviorSanitizer** | Detect undefined behavior |
| Memory | **Valgrind** | Find memory leaks |
| Format | **clang-format** | Consistent code style |
| Versioning | **Git + Gitea** | Own server: git.paulvincenthorn.de |

---

## Learning Resources

| Resource | Topic | Link |
|---|---|---|
| 📘 **Database Internals** - Alex Petrov | Storage engines, B-Trees, MVCC, WAL | [databass.dev](https://www.databass.dev/) |
| 📗 **Crafting Interpreters** - Robert Nystrom | Tokenizer, AST - for the SQL frontend | [craftinginterpreters.com](https://craftinginterpreters.com/) |
| 🎓 **CMU 15-445** - Andy Pavlo | The best database course in the world, free | [15445.courses.cs.cmu.edu](https://15445.courses.cs.cmu.edu/) |
| 💻 **cstack/db_tutorial** | A DB step by step in C | [cstack.github.io/db_tutorial](https://cstack.github.io/db_tutorial/) |
| 🗃️ **SQLite Source Code** | The blueprint for "small, robust, complete" | [sqlite.org/src](https://sqlite.org/src/) |
| 🟧 **SAP HANA Administration Guide** | Delta-Merge & Column-Store compression in the original | [help.sap.com](https://help.sap.com/) |

---

## Status

🌱 **Vision Phase.** PaulDB is currently a home for a dream that deliberately waits until my SAP foundation is in place. That is not falling behind - that is sequencing.

An empty repo with a clear plan is not overreaching. It is a promise to myself.

---

<sub>by Paul Horn - built to understand - on the way to BC 🏔️</sub>