LEARN DATABASE SYSTEMS DEEP DIVE

Learn Database Systems: From Zero to DBMS Engineer

Goal: Deeply understand the internal architecture and implementation details of modern relational database management systems (DBMS), inspired by CMU 15-445/645. You will build core components from scratch, gaining insights into storage, indexing, query processing, concurrency control, and crash recovery.

Why Learn Database Systems Internals?

Databases are the bedrock of nearly every significant software application. While using a DBMS is common, understanding how they work internally is a superpower. It allows you to:

Optimize Performance: Diagnose and fix performance bottlenecks effectively.
Design Better Systems: Understand the trade-offs in data modeling and system architecture.
Troubleshoot Complex Issues: Debug challenging problems related to data integrity, consistency, and availability.
Innovate: Develop novel database solutions or contribute to existing open-source projects.
Excel in Technical Interviews: Demonstrate a profound understanding of fundamental computer science principles.

After completing these projects, you will:

Comprehend the entire data lifecycle within a DBMS, from disk to query result.
Master complex data structures like B+Trees optimized for disk I/O.
Implement sophisticated algorithms for query execution and optimization.
Grasp the intricacies of concurrency control and transaction isolation.
Understand how databases guarantee durability and recover from crashes.
Be proficient in C++ for high-performance system programming.

Core Concept Analysis

Building a database system is a journey through several layers of abstraction, each solving critical problems efficiently and reliably.

The DBMS Architecture Stack

┌───────────────────────────────────────────────────────────┐
│               EXTERNAL APPLICATION / USER                 │
│                 (SQL Queries, API Calls)                  │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                    QUERY PARSER / OPTIMIZER               │
│         (SQL -> Relational Algebra -> Execution Plan)     │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                     QUERY EXECUTION ENGINE                │
│             (Operators: Scan, Join, Sort, Aggregate)      │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                  TRANSACTION MANAGER / LOCK MANAGER       │
│                (ACID Properties, Concurrency Control)     │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                     BUFFER POOL MANAGER                   │
│             (Caching disk pages in memory, replacement)   │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                  INDEX / ACCESS METHODS                   │
│                    (B+Trees, Hash Indexes)                │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                     STORAGE MANAGER                       │
│              (Pages, Tuples, Files, Disk I/O)             │
└───────────────────────────────────────────────────────────┘
                               │
                               ▼
┌───────────────────────────────────────────────────────────┐
│                DISK / PERSISTENT STORAGE                  │
└───────────────────────────────────────────────────────────┘

Key Concepts Explained

1. Storage Management: The Foundation

Data ultimately resides on persistent storage (disk). A DBMS manages this storage by breaking it down into fixed-size pages (e.g., 4KB, 8KB). Pages are the unit of I/O between disk and memory.

Page Formats: How are records (tuples) stored within a page?
- Slotted Pages: A common technique where records are stored contiguously, and a directory (slot array) at the end of the page stores offsets and lengths, allowing for variable-length records and efficient free space management.
Tuple Formats: How is a single record structured? Fixed vs. variable length attributes, null indicators.
Heap Files: A collection of pages that store records without any particular order. New records are simply appended to the end or placed in available free space.

2. Buffer Pool Management: Bridging the Speed Gap

Disk I/O is orders of magnitude slower than memory access. The buffer pool is a critical component that caches frequently accessed disk pages in main memory.

Page Frames: Slots in the buffer pool where disk pages are loaded.
Page Table: Maps page IDs to frame IDs.
Replacement Policies: When the buffer pool is full, which page should be evicted to make room for a new one? (e.g., LRU - Least Recently Used, Clock algorithm).
Dirty Pages: Pages modified in memory but not yet written back to disk.
Pinning/Unpinning: Preventing a page from being evicted if a transaction is actively using it.

3. Indexing: Fast Data Retrieval

To quickly locate specific records without scanning entire heap files, databases use indexes.

B+Trees: The workhorse index structure. A self-balancing tree optimized for disk-based systems.
- All data pointers are in leaf nodes, allowing for efficient range scans.
- Internal nodes only store keys to guide search.
Hash Indexes: Use a hash function to map keys directly to their storage location.
- Good for equality searches.
- Extendable Hashing: A dynamic hashing scheme that grows and shrinks gracefully.

4. Query Execution: Making Sense of Data

The query execution engine processes relational algebra operators (e.g., Selection, Projection, Join) on data.

Operators: Building blocks for query plans.
- Sequential Scan: Read every record in a table.
- Index Scan: Use an index to find specific records.
- Nested Loop Join: Simple join algorithm, iterates through outer table, then inner table.
- Hash Join: Builds a hash table for the inner relation, then probes it with the outer relation.
- Sort-Merge Join: Sorts both relations, then merges them.

5. Concurrency Control: Keeping Data Consistent

Multiple transactions can execute simultaneously. Concurrency control ensures that these concurrent executions do not lead to inconsistencies.

Transactions: A logical unit of work that ensures ACID properties (Atomicity, Consistency, Isolation, Durability).
Isolation Levels: Define the degree to which one transaction’s changes are visible to others (e.g., Read Uncommitted, Read Committed, Repeatable Read, Serializable).
Two-Phase Locking (2PL): A common locking protocol where transactions acquire all locks during a growing phase and release all locks during a shrinking phase.
Deadlock: A situation where two or more transactions are waiting for each other to release locks.

6. Recovery: Surviving Catastrophes

Databases must be resilient to failures (system crashes, power outages) and guarantee durability. Recovery management ensures that committed transactions remain permanent and incomplete transactions are undone.

Write-Ahead Logging (WAL): All changes to data must first be written to a log file before being applied to the data pages on disk.
UNDO/REDO: Log records contain enough information to undo (CLR - Compensation Log Records) or redo changes.
Checkpoints: A mechanism to reduce the amount of work needed during recovery by periodically flushing dirty pages and log records to disk.

Project List

These projects are designed to build a solid understanding of each major component of a DBMS. They are ordered to reflect the typical layering, starting from the low-level physical storage and progressing to transaction management and recovery.

Project 1: Disk-Oriented Storage Manager

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 2: Intermediate
Knowledge Area: Low-level I/O, Memory Management, Data Structures
Software or Tool: Unix-like OS with mmap (or _open, _lseek, _write, _read on Windows)
Main Book: “Database System Concepts” by Abraham Silberschatz, Henry F. Korth, S. Sudarshan

What you’ll build: A module that simulates physical disk storage and manages fixed-size data pages within a file. It will handle reading and writing pages from/to a file, allocating new pages, and deallocating existing ones.

Why it teaches DBMS internals: This project forces you to confront the reality of disk I/O. You’ll learn how a database system abstracts raw file storage into logical pages, which are the fundamental unit of data transfer. This is the absolute bottom layer of any DBMS.

Core challenges you’ll face:

Simulating disk storage with a file → maps to understanding memory-mapped files or direct file I/O operations
Managing page IDs and their mapping to file offsets → maps to implementing a simple lookup or calculation for page locations
Reading/writing fixed-size pages efficiently → maps to ensuring correct byte-level operations and handling read()/write() calls
Tracking available vs. used pages in the file → maps to implementing a header or a bitmap to manage free space within the data file

Key Concepts:

Pages and Blocks: “Database System Concepts” Chapter 10 - Silberschatz et al.
File Organization: “Database System Concepts” Chapter 10 - Silberschatz et al.
Direct I/O vs. Memory-Mapped I/O: Wikipedia - “Memory-mapped file”

Difficulty: Intermediate Time estimate: 1 week Prerequisites: Strong C++ fundamentals (pointers, classes, I/O streams), understanding of binary data representation.

Real world outcome: A C++ library that can:

Create a new “database file” (e.g., data.db).
Allocate a new, empty page and return its unique page ID.
Read any page into a byte array given its page ID.
Write a byte array representing a page to disk given its page ID.
Deallocate a page, marking its space as free for reuse.

// Example API:
class DiskManager {
public:
    DiskManager(const std::string& db_file);
    PageId AllocatePage(); // Returns a unique ID for the new page
    void DeallocatePage(PageId page_id);
    void ReadPage(PageId page_id, char* page_data); // Reads into provided buffer
    void WritePage(PageId page_id, const char* page_data); // Writes from buffer
private:
    std::fstream db_file_;
    std::atomic<PageId> next_page_id_; // For simple allocation
    // Other members for free page management (e.g., a free list or bitmap)
};

Implementation Hints:

Use std::fstream in binary mode for file operations.
Define a constant PAGE_SIZE (e.g., 4096 bytes).
Page ID 0 can be reserved for a header page that stores metadata, including the next_page_id and information about free pages.
To allocate a page, you might just append to the file and increment next_page_id_. For deallocation, you’d add the page ID to a free list and try to reuse those first.
Be mindful of _lseek (or std::fstream::seekp/seekg) to jump to the correct offset in the file for a given page ID. The offset for page_id would typically be page_id * PAGE_SIZE.

Learning milestones:

Implement basic page allocation and deallocation logic. → You understand how to manage logical units of disk space.
Successfully read and write pages from a simulated disk file. → You’ve mastered raw file I/O for persistent storage.
Manage file size and ensure data integrity across reads/writes. → You appreciate the challenges of low-level data persistence.

Project 2: Tuple and Page Manager

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 3: Genuinely Clever
Business Potential: 1. The “Resume Gold”
Difficulty: Level 2: Intermediate
Knowledge Area: Data Structures, Memory Layout, Serialization
Software or Tool: Your Disk-Oriented Storage Manager
Main Book: “Database System Concepts” Chapter 10 - Silberschatz et al.

What you’ll build: Modules to represent and manage individual tuples (records) and their storage within a single data page (likely using a slotted page format). This project builds directly on your Disk-Oriented Storage Manager.

Why it teaches DBMS internals: This project teaches you how raw bytes on a page are interpreted as structured records. You’ll design the in-memory representation of a tuple and how it gets serialized/deserialized to fit into a page, learning about variable-length data and efficient space utilization.

Core challenges you’ll face:

Designing a tuple header → maps to storing metadata like tuple length, null bitmask for attributes
Implementing variable-length attributes → maps to managing offsets and lengths within the tuple data
Designing a slotted page structure → maps to creating a header and slot array within a page to point to actual tuple data
CRUD operations (Create, Read, Update, Delete) for tuples on a page → maps to inserting new tuples, retrieving existing ones, compacting free space after deletions, and updating in-place or by relocation

Key Concepts:

Tuple Format: CMU 15-445 Lecture on Storage/Page Formats
Slotted Page Structure: “Database System Concepts” Chapter 10 - Silberschatz et al.
Serialization/Deserialization: Wikipedia - “Serialization”

Difficulty: Intermediate Time estimate: 1-2 weeks Prerequisites: Project 1, strong C++ data structure design skills, byte manipulation.

Real world outcome: A C++ library that can:

Define a Tuple class that holds attribute values (e.g., int, varchar).
A TablePage (or HeapPage) class that manages tuples within a PAGE_SIZE byte array.
Insert a Tuple into the TablePage, returning a RecordId (PageId, SlotId).
Retrieve a Tuple from the TablePage given a RecordId.
Delete a Tuple from the TablePage, reclaiming space.
Update a Tuple, potentially moving it within the page or storing new data.

// Example API:
struct RecordId {
    PageId page_id;
    int slot_id;
};

class Tuple {
public:
    // Represents a tuple with its attributes
    // e.g., Tuple(std::vector<Value> values, Schema* schema)
};

class TablePage { // Manages layout within a raw char* PAGE_DATA buffer
public:
    TablePage(PageId page_id, char* page_data);
    bool InsertTuple(const Tuple& tuple, RecordId& rid);
    bool GetTuple(RecordId rid, Tuple& tuple);
    bool DeleteTuple(RecordId rid);
    // ... methods for free space management, iterating slots
private:
    PageId page_id_;
    char* data_; // Raw buffer of PAGE_SIZE
    // Header information within data_ (e.g., free space pointer, slot array)
};

Implementation Hints:

Slotted Page Layout: The page will have a header (e.g., free_space_offset, num_slots) at one end and a slot array (offset, length, RecordId) at the other. Tuple data grows from the end of the header towards the slot array.
When inserting, find enough free space, add a new slot entry, and update the header.
When deleting, mark the slot as invalid and potentially compact data to reclaim fragmented space.
Consider how RecordId will be used. It’s essentially a pointer to a tuple’s location.

Learning milestones:

Design a tuple format that handles multiple data types and variable lengths. → You understand data serialization within a record.
Implement the slotted page structure correctly, including header and slot array. → You’ve mastered efficient in-page space management.
Perform CRUD operations on tuples within a single page, including free space management. → You can manipulate structured data at the byte level inside a page buffer.

Project 3: Buffer Pool Manager

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 3: Advanced
Knowledge Area: Caching, Concurrency (basic), Memory Management, OS Interaction
Software or Tool: Your Disk-Oriented Storage Manager
Main Book: “Database System Concepts” Chapter 11 - Silberschatz et al.

What you’ll build: A core component that manages a fixed-size pool of memory (the buffer pool) for caching disk pages. It will interact with your Disk-Oriented Storage Manager to fetch pages from disk and write dirty pages back. This project introduces critical concepts like page pinning and replacement policies.

Why it teaches DBMS internals: This is where you bridge the gap between slow disk storage and fast CPU processing. You’ll implement sophisticated caching strategies, handle concurrent access (using basic mutexes), and manage the lifecycle of pages in memory, which is fundamental to DBMS performance.

Core challenges you’ll face:

Implementing a page table → maps to using std::unordered_map to map PageId to FrameId
Managing page metadata (dirty flag, pin count) → maps to designing a Page class to hold status and data buffer
Implementing a page replacement policy (e.g., LRU, Clock) → maps to choosing and implementing a sophisticated caching algorithm
Handling concurrent access to the buffer pool (basic locking) → maps to using std::mutex to protect internal data structures from race conditions
Interfacing with the disk manager → maps to calling your DiskManager methods to read/write pages when needed

Key Concepts:

Buffer Pool: “Database System Concepts” Chapter 11 - Silberschatz et al.
Page Replacement Algorithms: CMU 15-445 Lecture on Buffer Pools
Concurrency Primitives (Mutexes): “C++ Concurrency in Action” by Anthony Williams

Difficulty: Advanced Time estimate: 2 weeks Prerequisites: Project 1, strong C++ (templates, smart pointers), basic understanding of multithreading concepts.

Real world outcome: A C++ library that can:

Request a page by its PageId (FetchPage), loading it from disk if not in memory.
Mark a page as “dirty” (MarkDirty), indicating it needs to be written to disk.
Unpin a page (UnpinPage), making it eligible for replacement.
Force a dirty page to be written to disk (FlushPage).
Evict a page using a chosen replacement policy when space is needed (EvictPage).
Allocate and deallocate pages, ensuring they are managed by the buffer pool.

// Example API:
struct Page {
    char data[PAGE_SIZE]; // Raw page data
    PageId page_id;       // What disk page this is
    int pin_count;        // Number of transactions using this page
    bool is_dirty;        // Has this page been modified?
    // Other metadata for replacement policy (e.g., timestamp, reference bit)
};

class BufferPoolManager {
public:
    BufferPoolManager(size_t pool_size, DiskManager* disk_manager);
    Page* FetchPage(PageId page_id);
    bool UnpinPage(PageId page_id, bool is_dirty);
    bool FlushPage(PageId page_id);
    PageId NewPage(); // Allocates a new page and fetches it
    bool DeletePage(PageId page_id);
private:
    size_t pool_size_;
    DiskManager* disk_manager_;
    std::vector<Page> pages_; // The actual memory pool
    std::unordered_map<PageId, FrameId> page_table_; // PageId -> FrameId map
    // Data structures for replacement policy (e.g., LRU list, Clock hand)
    std::mutex latch_; // Protects internal structures
};

Implementation Hints:

When FetchPage is called:
- Check page_table_. If found, increment pin_count and return the Page*.
- If not found, find a free frame (or evict one using the replacement policy if no free frames).
- Load the page from disk_manager_, update page_table_, initialize pin_count=1, is_dirty=false, and return.
UnpinPage decrements pin_count. If is_dirty is true, set the page’s is_dirty flag.
The replacement policy (e.g., LRU) needs to efficiently find the next page to evict. A std::list of FrameIds or a circular array with a “clock hand” can be used.

Learning milestones:

Implement a functional buffer pool with a simple replacement policy (e.g., LRU). → You understand the core caching mechanism of a DBMS.
Correctly handle page pinning, dirty flags, and flushing pages to disk. → You can manage the state and persistence of cached data.
Ensure thread-safety for basic operations using mutexes. → You’ve introduced fundamental concurrency control.

Project 4: B+Tree Index

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 5: Pure Magic (Super Cool)
Business Potential: 1. The “Resume Gold”
Difficulty: Level 4: Expert
Knowledge Area: Advanced Data Structures, Algorithms, Disk-Oriented Design
Software or Tool: Your Buffer Pool Manager, your Page/Tuple Manager
Main Book: “Database System Concepts” Chapter 14 - Silberschatz et al.

What you’ll build: A full-featured B+Tree index structure that stores keys and record identifiers (RecordId). This index will be “disk-oriented,” meaning it uses your Buffer Pool Manager to read and write its internal nodes and leaf pages.

Why it teaches DBMS internals: The B+Tree is arguably the most important data structure in relational databases. Implementing one from scratch forces you to optimize for disk I/O, handle complex tree balancing (splitting, merging), and manage its interaction with the buffer pool. This is a rite of passage for any aspiring DBMS engineer.

Core challenges you’ll face:

Designing B+Tree page formats (internal and leaf nodes) → maps to laying out keys and pointers efficiently within a PAGE_SIZE buffer
Implementing search, insert, and delete operations → maps to handling traversals, key comparisons, and maintaining tree properties
Managing page splits during insertion → maps to creating new pages, propagating keys upwards, and updating parent pointers
Managing page merges/redistribution during deletion → maps to handling underflow, balancing nodes with siblings, and updating parent pointers
Handling concurrent access to the B+Tree (latching/locking) → maps to implementing a robust latching protocol to ensure thread-safe operations

Key Concepts:

B+Tree Structure and Operations: “Database System Concepts” Chapter 14 - Silberschatz et al.
Disk-Oriented B+Trees: CMU 15-445 Lecture on B+Trees
Latch vs. Lock: CMU 15-445 Lecture on B+Tree Concurrency Control

Difficulty: Expert Time estimate: 3-4 weeks Prerequisites: Projects 1-3, master-level C++ (templates, inheritance, smart pointers), strong algorithmic thinking, familiarity with concurrency.

Real world outcome: A C++ library that can:

Create an empty B+Tree index.
Insert (key, RecordId) pairs into the tree, handling splits.
Search for a RecordId given a key (equality search).
Perform range scans (e.g., find all RecordIds for keys between X and Y).
Delete (key, RecordId) pairs, handling merges or redistributions.
Print a visual representation of the tree structure for debugging.

// Example API:
template <typename KeyType, typename ValueType, typename KeyComparator>
class BPlusTree {
public:
    BPlusTree(BufferPoolManager* bpm, KeyComparator comparator);
    bool Insert(const KeyType& key, const ValueType& value);
    bool Delete(const KeyType& key, const ValueType& value);
    bool GetValue(const KeyType& key, std::vector<ValueType>& result);
    // Iterator for range scans
private:
    BufferPoolManager* bpm_;
    KeyComparator comparator_;
    PageId root_page_id_;
    // Latching mechanisms (e.g., std::mutex per page, or a more sophisticated latching protocol)
};

// Internal/Leaf Page formats would be implemented using Page/Tuple Manager concepts
// to store keys/pointers within a raw char* page_data buffer.

Implementation Hints:

Page Formats: Define BPlusTreeInternalPage and BPlusTreeLeafPage classes that inherit from a common BPlusTreePage base. Each will manage its own PAGE_SIZE buffer, storing keys and child page IDs (internal) or keys and RecordIds (leaf).
Key Comparisons: Use a KeyComparator object to handle key comparisons, which can be specialized for different KeyTypes.
Recursion: Insert and Delete operations often involve recursive calls down the tree.
Concurrency: Start with a simple global mutex for the entire tree for correctness. Later, you’ll need to explore more granular latching (e.g., ‘Crabbing’ or ‘Latch Crabbing’) to allow concurrent operations.

Learning milestones:

Implement basic search and insertion, handling page splits correctly. → You grasp the core B+Tree structure and balancing.
Implement range scans efficiently using leaf node pointers. → You understand how B+Trees optimize for sequential access.
Implement deletion, including merging or redistribution of pages. → You’ve mastered the full lifecycle of a B+Tree.
Ensure thread-safety for concurrent operations using a latching protocol. → You can build a robust, high-performance data structure for multi-threaded environments.

Project 5: Hash Index (Extendable Hashing)

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 3: Genuinely Clever
Business Potential: 1. The “Resume Gold”
Difficulty: Level 3: Advanced
Knowledge Area: Hashing, Dynamic Data Structures, Disk-Oriented Design
Software or Tool: Your Buffer Pool Manager, your Page/Tuple Manager
Main Book: “Database System Concepts” Chapter 14 - Silberschatz et al.

What you’ll build: An index structure based on Extendable Hashing. This hash index will also be disk-oriented, utilizing your Buffer Pool Manager to store and retrieve its directory and bucket pages.

Why it teaches DBMS internals: While B+Trees are versatile, hash indexes excel at equality lookups. Implementing Extendable Hashing teaches you how to build a dynamic hash table that can grow and shrink without rehashing the entire structure, which is crucial for disk-based systems. You’ll compare its strengths and weaknesses against B+Trees.

Core challenges you’ll face:

Designing directory and bucket page formats → maps to efficiently storing pointers to buckets and key-value pairs within pages
Implementing a global and local depth mechanism → maps to understanding how the hash function is truncated based on directory/bucket size
Handling bucket splits → maps to creating new bucket pages and potentially doubling the directory when a bucket overflows
Concurrency control for directory and buckets → maps to using appropriate latching to protect against race conditions during splits and directory doubling

Key Concepts:

Hash Indexes: “Database System Concepts” Chapter 14 - Silberschatz et al.
Extendable Hashing: CMU 15-445 Lecture on Hash Indexes
Hash Functions: Wikipedia - “Hash function”

Difficulty: Advanced Time estimate: 2 weeks Prerequisites: Projects 1-3, strong C++ data structures, concurrency concepts.

Real world outcome: A C++ library that can:

Create an empty Extendable Hash Index.
Insert (key, RecordId) pairs, handling bucket splits and directory doubling.
Search for a RecordId given a key (equality search).
Delete (key, RecordId) pairs, potentially merging buckets or shrinking the directory.
Print a visual representation of the hash directory and its buckets for debugging.

// Example API:
template <typename KeyType, typename ValueType, typename KeyHasher, typename KeyComparator>
class ExtendableHashIndex {
public:
    ExtendableHashIndex(BufferPoolManager* bpm, KeyHasher hasher, KeyComparator comparator);
    bool Insert(const KeyType& key, const ValueType& value);
    bool Delete(const KeyType& key, const ValueType& value);
    bool GetValue(const KeyType& key, std::vector<ValueType>& result);
private:
    BufferPoolManager* bpm_;
    KeyHasher hasher_;
    KeyComparator comparator_;
    PageId directory_page_id_; // Root of the hash directory
    std::mutex latch_; // Protects global directory
    // Other data structures for managing bucket pages
};

// Directory and Bucket page formats would be implemented similarly to B+Tree pages.

Implementation Hints:

Directory Page: Stores an array of PageIds, each pointing to a bucket page. It also stores the global_depth.
Bucket Page: Stores local_depth and an array of (key, RecordId) pairs.
Hashing: The KeyHasher will convert KeyType to an integer. This integer is then truncated using bitwise operations based on global_depth and local_depth.
Bucket Splits: When a bucket overflows, if its local_depth is less than global_depth, you split it and redistribute its contents. If local_depth equals global_depth, you must double the directory.

Learning milestones:

Implement the basic structure of a hash directory and bucket pages. → You understand dynamic hash table components.
Correctly implement insertion, handling bucket splits and directory doubling. → You’ve mastered dynamic hash table resizing.
Implement search and deletion operations efficiently. → You can manage a hash index lifecycle.
Ensure thread-safety for concurrent operations. → You can build a concurrent hash index.

Project 6: Relational Algebra Executor (Operators)

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 3: Genuinely Clever
Business Potential: 1. The “Resume Gold”
Difficulty: Level 3: Advanced
Knowledge Area: Query Processing, Iterators, Relational Algebra
Software or Tool: Your Buffer Pool Manager, your Table/Page Manager, your B+Tree Index
Main Book: “Database System Concepts” Chapter 15 - Silberschatz et al.

What you’ll build: A set of operators that implement fundamental relational algebra operations (e.g., sequential scan, index scan, selection, projection). These operators will work together to form a basic query execution engine.

Why it teaches DBMS internals: This project takes you into the heart of query processing. You’ll learn how a DBMS executes queries by breaking them down into a tree of physical operators. The iterator model you’ll implement is a cornerstone of efficient query execution, allowing pipelining and on-demand data retrieval.

Core challenges you’ll face:

Designing an operator interface (iterator model) → maps to defining Open(), Next(), Close() methods for all operators
Implementing Sequential Scan → maps to iterating through all pages of a heap file via BufferPoolManager and TablePage
Implementing Index Scan → maps to using your B+Tree (or Hash Index) to retrieve RecordIds and then FetchPage from BufferPoolManager
Implementing Selection (Predicate Evaluation) → maps to filtering tuples based on conditions
Implementing Projection → maps to selecting specific columns and potentially removing duplicates

Key Concepts:

Query Execution Process: “Database System Concepts” Chapter 15 - Silberschatz et al.
Iterator Model (Volcano Model): CMU 15-445 Lecture on Query Execution
Relational Algebra: “Database System Concepts” Chapter 6 - Silberschatz et al.

Difficulty: Advanced Time estimate: 2 weeks Prerequisites: Projects 1-4 (or 1-3 + basic understanding of an index’s API), strong C++ object-oriented design.

Real world outcome: A C++ library where you can build an execution plan like this:

// Example: SELECT b FROM T1 WHERE a = 5;
// Assuming T1 has columns (a: INT, b: VARCHAR) and an index on 'a'

// 1. Index Scan on T1 for a = 5
IndexScanOperator* index_scan = new IndexScanOperator(bpm, T1_index, "a", Value(5));

// 2. Projection to get column 'b'
std::vector<int> project_cols = {1}; // Index of 'b'
ProjectionOperator* projection = new ProjectionOperator(index_scan, project_cols);

// Execute the plan
projection->Open();
Tuple result_tuple;
while (projection->Next(&result_tuple)) {
    // Print or process result_tuple
    std::cout << result_tuple.GetValue(0) << std::endl; // Assuming 'b' is first projected column
}
projection->Close();

Implementation Hints:

Define an abstract BaseOperator interface with Open(), Next(Tuple* result), and Close() methods. Next() should return true if a tuple is produced, false otherwise.
Each concrete operator (Scan, Select, Project) will implement this interface.
Operators will typically take a ChildOperator in their constructor (e.g., SelectionOperator takes a ScanOperator).
SelectionOperator::Next() will call child_->Next(), evaluate the predicate, and if true, return the tuple. Otherwise, it keeps calling child_->Next() until a matching tuple is found or the child is exhausted.
ProjectionOperator::Next() will call child_->Next() and then construct a new tuple with only the projected columns.

Learning milestones:

Implement the basic iterator model for operators. → You understand pipelined query execution.
Successfully implement sequential scan and index scan operators. → You can retrieve data efficiently from tables and indexes.
Implement selection and projection operators correctly. → You can process and transform data based on query requirements.
Chain operators together to execute simple query plans. → You’ve built a functional (albeit simple) query execution engine.

Project 7: Join Operators

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 4: Expert
Knowledge Area: Algorithms, Query Processing, Disk-Oriented Algorithms
Software or Tool: Your Buffer Pool Manager, your Relational Algebra Executor
Main Book: “Database System Concepts” Chapter 15 - Silberschatz et al.

What you’ll build: Implement several join algorithms, including Nested Loop Join, Hash Join, and Sort-Merge Join, as part of your query execution engine. These operators will combine data from two input relations (e.g., the output of two scan operators).

Why it teaches DBMS internals: Joins are typically the most expensive operations in a query, and their efficient implementation is crucial. By building multiple join algorithms, you’ll understand their computational complexities, I/O patterns, and the scenarios where each performs best, which is fundamental to query optimization.

Core challenges you’ll face:

Implementing Nested Loop Join → maps to the most straightforward but often least efficient join
Implementing Hash Join → maps to building and probing hash tables, potentially handling large relations that don’t fit in memory (external hashing)
Implementing Sort-Merge Join → maps to external sorting of large relations and then merging them
Handling different join types (inner, left/right outer) → maps to modifying algorithms to produce nulls for unmatched tuples
Integrating joins into the iterator model → maps to managing the state of two child operators within a single join operator

Key Concepts:

Join Algorithms: “Database System Concepts” Chapter 15 - Silberschatz et al.
External Sorting: CMU 15-445 Lecture on Query Execution
Hash Table Performance: “Introduction to Algorithms” Chapter 11 - Cormen et al.

Difficulty: Expert Time estimate: 3 weeks Prerequisites: Project 6, strong algorithmic skills, understanding of I/O costs.

Real world outcome: Your C++ query execution engine can now combine data from multiple tables efficiently:

// Example: SELECT * FROM T1 JOIN T2 ON T1.id = T2.id;
// T1 Scan -> NestedLoopJoin -> T2 Scan
// T1 Scan -> HashJoin -> T2 Scan
// T1 Scan -> SortMergeJoin -> T2 Scan

// 1. Scans for T1 and T2
SequentialScanOperator* t1_scan = new SequentialScanOperator(bpm, T1_table_oid);
SequentialScanOperator* t2_scan = new SequentialScanOperator(bpm, T2_table_oid);

// 2. Hash Join
HashJoinOperator* hash_join = new HashJoinOperator(t1_scan, t2_scan, t1_join_key_idx, t2_join_key_idx);

// Execute the join
hash_join->Open();
Tuple result_tuple;
while (hash_join->Next(&result_tuple)) {
    // Process joined tuple
    std::cout << result_tuple << std::endl;
}
hash_join->Close();

Implementation Hints:

Nested Loop Join: Next() will repeatedly call right_child_->Next(). When right_child_ is exhausted, call left_child_->Next() and reset right_child_.
Hash Join:
- Open(): Build phase. Iterate through the smaller relation (e.g., left_child_), hash its join key, and build an in-memory hash table of tuples (or RecordIds). If it doesn’t fit in memory, you’ll need external hashing (more advanced).
- Next(): Probe phase. Iterate through the larger relation (right_child_), hash its join key, and probe the hash table.
Sort-Merge Join:
- Open(): Sort both left_child_ and right_child_ based on their join keys. For large relations, this requires an external merge sort algorithm.
- Next(): Merge phase. Iterate through both sorted relations, advancing pointers based on key comparison.

Learning milestones:

Implement Nested Loop Join correctly. → You understand the basic mechanism of combining relations.
Implement Hash Join, including the build and probe phases. → You can leverage hash tables for efficient equality joins.
Implement Sort-Merge Join, including external sorting concepts. → You can handle large datasets for efficient joins and range comparisons.
Compare the performance characteristics of different join algorithms. → You gain a deep understanding of query execution costs.

Project 8: Simple Query Parser & Rule-Based Optimizer

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Python (for parser), Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 4: Expert
Knowledge Area: Compilers, Parsers, Query Optimization, Algorithms
Software or Tool: Flex/Bison (or hand-written parser), your Relational Algebra Executor
Main Book: “Compilers: Principles, Techniques, and Tools” (Dragon Book) by Aho et al.

What you’ll build: A component that can parse a simple SQL-like query string into an abstract syntax tree (AST), then convert the AST into a logical query plan (relational algebra), and finally transform that into a physical query plan (tree of operators) using a few simple optimization rules.

Why it teaches DBMS internals: This project pulls together the front-end of a DBMS. You’ll learn how a human-readable query is translated into an executable plan, encountering parsing, semantic analysis, and the initial stages of query optimization. This is a crucial step towards building a complete DBMS.

Core challenges you’ll face:

Designing an AST for SQL-like queries → maps to representing the hierarchical structure of a query
Implementing a lexical analyzer (tokenizer) → maps to breaking the input string into meaningful tokens
Implementing a parser (recursive descent or using Flex/Bison) → maps to building the AST from the token stream
Converting AST to a logical query plan (Relational Algebra) → maps to translating SQL constructs into a tree of relational operators
Applying simple optimization rules (e.g., predicate pushdown, index usage) → maps to transforming the logical plan into a more efficient physical plan

Key Concepts:

SQL Parsing: “Compilers: Principles, Techniques, and Tools” Chapters 2-4 - Aho et al.
Relational Algebra: “Database System Concepts” Chapter 6 - Silberschatz et al.
Query Optimization: “Database System Concepts” Chapter 16 - Silberschatz et al.
Predicate Pushdown: CMU 15-445 Lecture on Query Optimization

Difficulty: Expert Time estimate: 3 weeks Prerequisites: Project 7, strong C++ (knowledge of Flex/Bison if used), understanding of formal grammars.

Real world outcome: A C++ program that takes a query string: SELECT T1.b FROM T1 JOIN T2 ON T1.id = T2.id WHERE T1.a = 5; And outputs a tree of physical operators (e.g., Projection(HashJoin(IndexScan(T1, a=5), SequentialScan(T2)))).

// Example API:
class QueryParser {
public:
    std::shared_ptr<ASTNode> Parse(const std::string& query_string);
};

class LogicalPlanGenerator {
public:
    std::shared_ptr<LogicalOperator> GenerateLogicalPlan(std::shared_ptr<ASTNode> ast);
};

class RuleBasedOptimizer {
public:
    std::shared_ptr<PhysicalOperator> Optimize(std::shared_ptr<LogicalOperator> logical_plan);
private:
    // Collection of optimization rules (e.g., predicate pushdown rule, index scan rule)
};

// Query -> AST -> Logical Plan -> Physical Plan (Operators)

Implementation Hints:

Scope: Start with a very small subset of SQL: SELECT columns FROM table WHERE conditions; then add JOIN.
Lexer (Tokenizer): Can be hand-written (std::string::find, substr) or use flex.
Parser: Recursive descent is manageable for a small grammar. Each grammar rule becomes a function. Or use bison.
Logical Plan: Represent as a tree of LogicalOperator objects (e.g., LogicalScan, LogicalSelect, LogicalJoin).
Optimization Rules: Implement functions that take a LogicalOperator tree and return a PhysicalOperator tree.
- Rule 1: If WHERE clause exists, try to replace SequentialScan with IndexScan if an index is available on the predicate column.
- Rule 2: Push SELECT (predicate) operators down as far as possible in the plan tree (predicate pushdown).

Learning milestones:

Build a lexical analyzer that correctly tokenizes simple SQL queries. → You understand the first phase of compilation.
Implement a parser that constructs an AST for basic SELECT statements. → You can translate a language into a machine-readable structure.
Convert the AST into a logical query plan using relational algebra operators. → You bridge the gap between SQL and execution logic.
Apply at least two rule-based optimizations (e.g., index usage, predicate pushdown). → You can improve query efficiency before execution.

Project 9: Transaction Manager with Two-Phase Locking (2PL)

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 4: Expert
Knowledge Area: Concurrency Control, Operating Systems, Distributed Systems (concepts)
Software or Tool: Your Buffer Pool Manager, std::mutex, std::condition_variable
Main Book: “Database System Concepts” Chapter 18 - Silberschatz et al.

What you’ll build: A Transaction Manager responsible for enforcing the ACID properties (especially Atomicity and Isolation) using Two-Phase Locking (2PL). This will include a Lock Manager to grant and release locks on data items and a Deadlock Detector.

Why it teaches DBMS internals: This is the most complex aspect of building a reliable DBMS. You’ll delve deep into concurrency theory, ensuring that concurrent operations don’t corrupt data. Implementing 2PL, including deadlock handling, is a core demonstration of understanding distributed coordination and fault tolerance.

Core challenges you’ll face:

Defining transaction states (running, committing, aborting) → maps to managing the lifecycle of logical work units
Implementing a Lock Manager → maps to acquiring/releasing shared/exclusive locks on RecordIds (or PageIds)
Enforcing the two-phase rule → maps to ensuring transactions acquire all locks before releasing any
Detecting and resolving deadlocks → maps to building a wait-for graph and periodically checking for cycles, then aborting a victim transaction
Integrating with the Buffer Pool Manager (latch vs. lock) → maps to understanding when to use a fast, short-duration latch vs. a longer-duration lock

Key Concepts:

ACID Properties: “Database System Concepts” Chapter 17 - Silberschatz et al.
Two-Phase Locking (2PL): CMU 15-445 Lecture on Concurrency Control
Deadlock Detection: “Operating System Concepts” Chapter 7 - Silberschatz et al.
Latching vs. Locking: CMU 15-445 Lecture on B+Tree Concurrency Control

Difficulty: Expert Time estimate: 3 weeks Prerequisites: Project 3, master-level C++ concurrency (std::mutex, std::condition_variable), graph algorithms.

Real world outcome: A C++ system that can:

Begin a new transaction and assign it a unique TransactionId.
Acquire read (shared) and write (exclusive) locks on specific RecordIds.
Release locks when the transaction commits or aborts.
Automatically detect deadlocks among concurrent transactions.
Abort a “victim” transaction to break a deadlock, allowing others to proceed.
Demonstrate serializable isolation for multiple concurrent transactions on your TablePages.

// Example API:
enum class LockMode { SHARED, EXCLUSIVE };
enum class LockRequestState { WAITING, GRANTED };

struct LockRequest {
    TransactionId txn_id;
    LockMode lock_mode;
    LockRequestState state;
};

class LockManager {
public:
    bool LockShared(TransactionId txn_id, RecordId rid);
    bool LockExclusive(TransactionId txn_id, RecordId rid);
    bool Unlock(TransactionId txn_id, RecordId rid);
    void AddEdge(TransactionId t1, TransactionId t2); // For Wait-for Graph
    void RemoveEdge(TransactionId t1, TransactionId t2);
    std::vector<TransactionId> HasCycle(); // Deadlock Detection
private:
    std::unordered_map<RecordId, std::list<LockRequest>> lock_table_;
    std::unordered_map<TransactionId, std::set<RecordId>> txn_locks_; // What locks a txn holds
    std::mutex latch_;
    // Wait-for graph representation (e.g., adjacency list)
};

class Transaction {
public:
    TransactionId GetTransactionId();
    // ... methods to track state (growing/shrinking phase for 2PL)
};

class TransactionManager {
public:
    Transaction* Begin();
    void Commit(Transaction* txn);
    void Abort(Transaction* txn);
private:
    LockManager* lock_manager_;
    // ...
};

Implementation Hints:

Lock Table: A std::unordered_map<RecordId, std::list<LockRequest>> can store lock requests for each data item.
Wait-for Graph: An adjacency list (std::unordered_map<TransactionId, std::set<TransactionId>>) is suitable. Add an edge from T1 to T2 if T1 wants a lock held by T2.
Deadlock Detection: Periodically traverse the graph (e.g., DFS) to check for cycles. If a cycle is found, choose a victim (e.g., the youngest transaction, or the one holding fewest locks) and abort it.
2PL Enforcement: Track if a transaction has released any locks. If so, it’s in the shrinking phase and cannot acquire new locks.
Interaction with Buffer Pool: Ensure that a page is “latched” (short-duration mutex) by the buffer pool manager while reading/writing its internal structures, but “locked” (long-duration 2PL lock) by the transaction manager for logical data access.

Learning milestones:

Implement a Lock Manager that grants/denies shared/exclusive locks on data items. → You understand the core mechanism of controlling concurrent access.
Ensure transactions adhere to the Two-Phase Locking protocol. → You enforce strict isolation policies.
Implement a Deadlock Detector and a mechanism to resolve deadlocks. → You can build a robust system that handles contention gracefully.
Integrate transaction management with your query execution and buffer pool, demonstrating serializable isolation. → You connect theoretical concurrency to practical system behavior.

Project 10: Recovery Manager (UNDO/REDO Logging)

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 5: Pure Magic (Super Cool)
Business Potential: 1. The “Resume Gold”
Difficulty: Level 5: Master
Knowledge Area: Fault Tolerance, Persistence, Operating Systems (journaling)
Software or Tool: Your Buffer Pool Manager, your Transaction Manager
Main Book: “Database System Concepts” Chapter 19 - Silberschatz et al.

What you’ll build: A Recovery Manager that implements UNDO/REDO logging with a Write-Ahead Log (WAL). This module will ensure the ACID property of Durability and Atomicity even in the face of system crashes. You will implement the core recovery algorithms (Analysis, Redo, Undo).

Why it teaches DBMS internals: This is the pinnacle of DBMS reliability. You’ll learn how databases guarantee that committed data is never lost and that incomplete operations are rolled back perfectly, even after a catastrophic failure. Implementing WAL and the ARIES-like recovery protocol demonstrates a deep understanding of fault-tolerant systems design.

Core challenges you’ll face:

Designing log record formats → maps to storing enough information (LSN, TxnID, PageID, OldValue, NewValue) to undo/redo changes
Implementing Write-Ahead Logging (WAL) → maps to ensuring log records are flushed to disk before data pages
Managing the log buffer and flushing mechanism → maps to optimizing log I/O and ensuring log durability
Implementing the ARIES recovery protocol (Analysis, Redo, Undo phases) → maps to reconstructing the database state after a crash
Integrating with the Buffer Pool Manager (dirty pages, pageLSN) → maps to tracking which log records apply to which page states

Key Concepts:

Write-Ahead Logging (WAL): “Database System Concepts” Chapter 19 - Silberschatz et al.
UNDO/REDO Logging: CMU 15-445 Lecture on Crash Recovery
ARIES Recovery Algorithm: CMU 15-445 Lecture on ARIES
Checkpoints: “Database System Concepts” Chapter 19 - Silberschatz et al.

Difficulty: Master Time estimate: 4 weeks+ Prerequisites: Projects 1-3, 9, master-level C++ (concurrency, low-level I/O), understanding of state machines and complex algorithms.

Real world outcome: A C++ system that can:

Log all database modifications (inserts, updates, deletes) in a persistent log file.
Commit transactions, ensuring their changes are durable.
Abort transactions, ensuring their changes are undone atomically.
Recover the database to a consistent state after a simulated crash, applying an ARIES-like algorithm.
Perform periodic checkpoints to optimize recovery time.

// Example API:
// Log Record Structure
enum LogType { INSERT, DELETE, UPDATE, COMMIT, ABORT, CHECKPOINT_START, CHECKPOINT_END, CLR };

struct LogRecord {
    lsn_t lsn;         // Log Sequence Number
    txn_id_t txn_id;   // Transaction that generated this log
    LogType type;
    lsn_t prev_lsn;    // Previous log record for this transaction
    // Data specific to log type (e.g., page_id, offset, old_value, new_value, undo_next_lsn for CLR)
};

class LogManager {
public:
    LogManager(DiskManager* dm);
    lsn_t AppendLogRecord(LogRecord& record);
    void FlushLog(lsn_t lsn); // Flush log up to LSN
    void TruncateLog(lsn_t lsn); // Remove old log records
    // ... methods to read log records
private:
    DiskManager* dm_;
    char* log_buffer_;
    std::atomic<lsn_t> next_lsn_;
    std::mutex latch_;
    std::condition_variable cv_;
    // Background flusher thread
};

class RecoveryManager {
public:
    RecoveryManager(BufferPoolManager* bpm, LogManager* lm, TransactionManager* tm);
    void BeginCheckpoint();
    void EndCheckpoint();
    void Recover(); // Main recovery function (Analysis, Redo, Undo)
private:
    BufferPoolManager* bpm_;
    LogManager* lm_;
    TransactionManager* tm_;
    // Data structures for recovery (e.g., transaction table, dirty page table)
};

Implementation Hints:

Log Buffer: Maintain an in-memory buffer for log records. A background thread or a synchronous flush on commit will write this buffer to the persistent log file.
LSN (Log Sequence Number): A monotonically increasing identifier for log records. The pageLSN on each Page in the buffer pool tracks the LSN of the log record that last modified it.
Recovery Process (ARIES):
1. Analysis: Scan log from last checkpoint to determine active transactions and dirty pages at crash time.
2. Redo: Scan log from appropriate start point (determined in Analysis) and reapply all changes that were committed or might have been committed before the crash. Use pageLSN to avoid redoing already flushed changes.
3. Undo: Iterate through active transactions (from Analysis) backwards, undoing their changes using log records. Generate CLRs for each undo operation.

Learning milestones:

Design comprehensive log record formats for all database operations. → You understand what information is needed for fault tolerance.
Implement Write-Ahead Logging, ensuring log records are written before data pages. → You’ve mastered the critical WAL protocol.
Implement the Redo phase of recovery, replaying committed changes. → You can restore data to a durable state.
Implement the Undo phase of recovery, rolling back incomplete transactions with CLRs. → You can ensure atomicity after a crash.
Integrate checkpoints to optimize recovery time, demonstrating full ARIES-like recovery. → You’ve built a fault-tolerant database core.

Project 11: Multi-Version Concurrency Control (MVCC)

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 5: Pure Magic (Super Cool)
Business Potential: 1. The “Resume Gold”
Difficulty: Level 5: Master
Knowledge Area: Concurrency Control, Advanced Transaction Models, Operating Systems
Software or Tool: Your Buffer Pool Manager, your Transaction Manager, your Page/Tuple Manager
Main Book: “Database System Concepts” Chapter 18 - Silberschatz et al.

What you’ll build: Replace or augment your 2PL Lock Manager with a Multi-Version Concurrency Control (MVCC) mechanism. This will allow readers to not block writers, and writers to not block readers, greatly improving concurrency for many workloads.

Why it teaches DBMS internals: MVCC is a fundamental technique in modern high-performance databases (e.g., PostgreSQL, Oracle, most NoSQL stores). Implementing it deepens your understanding of isolation levels beyond simple locking, introducing the concept of different “snapshots” of the database state for different transactions.

Core challenges you’ll face:

Version storage (tuple chaining or copy-on-write) → maps to deciding how to store multiple versions of a tuple on pages
Transaction visibility rules (read/write timestamps) → maps to defining which versions of data a transaction can see based on its start timestamp
Garbage collection of old versions → maps to reclaiming space from versions no longer visible to any active transaction
Handling conflicts (writer-writer, reader-writer) → maps to implementing appropriate abortion or waiting logic when conflicts occur
Integrating with your existing transaction and storage managers → maps to adapting your system to handle multiple data versions transparently

Key Concepts:

Multi-Version Concurrency Control (MVCC): CMU 15-445 Lecture on MVCC
Snapshot Isolation: “Read Committed Isolation Level Does Not Prevent All Write Skew” by Adya et al.
Garbage Collection: Postgres Documentation - “Vacuuming”

Difficulty: Master Time estimate: 3-4 weeks Prerequisites: Projects 1-3, 9, strong C++ (concurrency), deep understanding of transaction semantics.

Real world outcome: Your C++ database system now supports highly concurrent workloads:

Readers never block writers, and writers never block readers.
Transactions operate on a consistent snapshot of the database.
Concurrent transactions can read old versions of data while new versions are being written.
A mechanism for garbage collecting old, unused data versions is in place.

// Example API:
struct TupleVersion {
    txn_id_t create_txn; // Transaction that created this version
    txn_id_t delete_txn; // Transaction that deleted this version (or INF)
    // Pointer to actual tuple data
};

class VersionManager { // Manages tuple versions on pages
public:
    TupleVersion* GetVisibleVersion(RecordId rid, Transaction* txn);
    RecordId CreateNewVersion(RecordId rid, const Tuple& new_tuple, Transaction* txn);
    void MarkVersionDeleted(RecordId rid, Transaction* txn);
    // ... garbage collection methods
};

class TransactionManagerMVCC : public TransactionManager {
public:
    Transaction* Begin();
    void Commit(Transaction* txn);
    void Abort(Transaction* txn);
private:
    VersionManager* version_manager_;
    std::atomic<txn_id_t> next_txn_id_;
    // Active transaction list for visibility checks and garbage collection
    // ... MVCC-specific locking/latching if needed for metadata
};

Implementation Hints:

Tuple Format Change: Your Tuple or RecordId will need to be augmented to point to a chain of versions or indicate which version is currently active. Each version will need create_txn and delete_txn timestamps (which are actually txn_ids or commit timestamps).
Visibility Check: For a given tuple version V and a reading transaction R:
- V is visible if V.create_txn < R.start_time AND (V.delete_txn = INF OR V.delete_txn > R.start_time) AND V.create_txn is committed.
- This is simplified; actual rules are more complex, considering ReadCommitted vs SnapshotIsolation.
Garbage Collection: Periodically identify versions that are no longer visible to any active or recently committed transaction and reclaim their space. This often requires tracking active transaction IDs.

Learning milestones:

Design a tuple versioning scheme within your page manager. → You understand how to store multiple versions of data.
Implement transaction visibility rules, allowing readers to access consistent snapshots. → You’ve mastered the core principle of MVCC.
Handle concurrent writes, ensuring correct version creation and conflict resolution. → You’ve built a robust, non-blocking writer mechanism.
Implement a basic garbage collection strategy for old data versions. → You can manage the lifecycle of versions and reclaim space.

Project 12: Simple Statistics and Cost-Based Optimizer

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Python (for statistical modeling), Rust
Coolness Level: Level 4: Hardcore Tech Flex
Business Potential: 1. The “Resume Gold”
Difficulty: Level 5: Master
Knowledge Area: Query Optimization, Statistics, Algorithms, Probability
Software or Tool: Your Query Parser/Executor
Main Book: “Database System Concepts” Chapter 16 - Silberschatz et al.

What you’ll build: Enhance your Query Parser and Executor with a module that collects basic statistics about tables and indexes, and then uses these statistics to estimate the cost of different physical query plans, selecting the cheapest one.

Why it teaches DBMS internals: This is the “brain” of the database. You’ll learn how a DBMS intelligently chooses the most efficient way to execute a query, which is far more complex than simply running operators. This involves understanding data distribution, estimating selectivities, and comparing the I/O and CPU costs of different execution strategies.

Core challenges you’ll face:

Collecting basic table statistics (tuple count, distinct values, min/max) → maps to scanning tables and indexes to gather aggregate data
Estimating predicate selectivity (e.g., WHERE col = val, WHERE col > val) → maps to using histograms or simple assumptions about data distribution
Estimating the cost of different operators (scan, join) → maps to assigning I/O and CPU costs to each operator based on estimated input/output sizes
Generating alternative physical plans → maps to exploring different join orders and access paths
Comparing plan costs and selecting the cheapest → maps to implementing a search algorithm to find the optimal plan

Key Concepts:

Cost-Based Optimization: “Database System Concepts” Chapter 16 - Silberschatz et al.
Statistics Collection: CMU 15-445 Lecture on Query Optimization
Selectivity Estimation: Wikipedia - “Selectivity (database)”
Join Order Optimization: “Introduction to Database Systems” by C.J. Date

Difficulty: Master Time estimate: 3-4 weeks Prerequisites: Projects 6-8, strong algorithmic thinking, basic probability and statistics.

Real world outcome: Your C++ database can now:

Analyze a table or index and store statistics (e.g., number of rows, number of distinct values for a column).
Take an SQL query and produce not just one physical plan, but multiple alternative plans.
Assign a numerical cost to each plan based on estimated I/O and CPU usage.
Execute the plan that has the lowest estimated cost.
Demonstrate significant performance differences between an unoptimized and an optimized query plan.

// Example API:
struct ColumnStatistics {
    size_t distinct_values;
    Value min_value;
    Value max_value;
    // Histograms (advanced)
};

struct TableStatistics {
    size_t tuple_count;
    std::unordered_map<std::string, ColumnStatistics> column_stats;
};

class StatisticsManager {
public:
    void CollectTableStatistics(TableOid table_oid);
    TableStatistics GetTableStatistics(TableOid table_oid);
    double EstimatePredicateSelectivity(const Predicate& predicate, const Schema& schema);
};

class CostModel {
public:
    double EstimateScanCost(ScanOperator* op);
    double EstimateJoinCost(JoinOperator* op, JoinAlgorithm algo); // Consider different algorithms
    // ...
};

class CostBasedOptimizer : public RuleBasedOptimizer {
public:
    std::shared_ptr<PhysicalOperator> Optimize(std::shared_ptr<LogicalOperator> logical_plan);
private:
    StatisticsManager* stats_manager_;
    CostModel* cost_model_;
    // Algorithms for generating alternative plans (e.g., dynamic programming for join order)
};

Implementation Hints:

Statistics Collection: Add a GatherStats command to your shell that scans a table (using your SequentialScanOperator) to count tuples, and compute min/max for simple column types.
Selectivity Estimation:
- col = val: 1.0 / stats.distinct_values (simple uniform assumption)
- col > val: (stats.max_value - val) / (stats.max_value - stats.min_value) (simple uniform assumption)
Cost Model: Assign arbitrary but consistent costs. E.g., scan_cost = num_pages * DISK_READ_COST + num_tuples * CPU_PROCESS_COST. join_cost will be more complex depending on the algorithm.
Plan Generation: For a simple SELECT-FROM-WHERE query, you’d compare SequentialScan vs. IndexScan. For joins, you’d compare NestedLoop, HashJoin, SortMerge and different join orders.

Learning milestones:

Collect basic statistics (tuple count, distinct values) for tables and columns. → You understand how to characterize data.
Implement simple selectivity estimation for common predicates. → You can predict the output size of filtering operations.
Develop a basic cost model for scan and join operators. → You can quantify the expense of query operations.
Generate and compare multiple physical plans, selecting the lowest-cost option. → You’ve built a rudimentary but functional cost-based query optimizer.

Final Overall Project: A Mini-Relational DBMS

File: LEARN_DATABASE_SYSTEMS_DEEP_DIVE.md
Main Programming Language: C++
Alternative Programming Languages: Rust
Coolness Level: Level 5: Pure Magic (Super Cool)
Business Potential: 5. The “Industry Disruptor”
Difficulty: Level 5: Master
Knowledge Area: Full-Stack DBMS Development, System Integration
Software or Tool: All components built in Projects 1-12
Main Book: The entire CMU 15-445/645 playlist and lecture notes.

What you’ll build: A functional, albeit simplified, relational database management system that integrates all the components you’ve built. This mini-DBMS will be able to:

Handle basic SQL DDL (CREATE TABLE, CREATE INDEX) and DML (INSERT, SELECT, DELETE, UPDATE).
Persist data to disk and recover from crashes.
Execute concurrent transactions with correct isolation.
Choose an efficient execution plan using a cost-based optimizer.

Why it teaches DBMS internals: This is the ultimate integration challenge. You’ll bring together every single piece you’ve built—storage, buffer pool, indexes, query executor, transaction manager, recovery manager, and optimizer—into a cohesive, working system. It’s a true culmination of everything learned, demonstrating mastery of the entire database stack.

Core challenges you’ll face:

System Integration → maps to ensuring all modules communicate correctly and handle edge cases across layers
Schema Management (Catalog) → maps to storing metadata about tables, columns, and indexes persistently
SQL Interface (REPL) → maps to creating a command-line interface to interact with your DBMS
Error Handling and Robustness → maps to making the system resilient to invalid inputs and unexpected conditions
Performance Tuning → maps to identifying and optimizing bottlenecks across the entire integrated system

Key Concepts:

Integrated DBMS Architecture: CMU 15-445 Lectures (all)
Database Catalog: “Database System Concepts” Chapter 17 - Silberschatz et al.
System Integration Testing: “The Pragmatic Programmer” by Andrew Hunt and David Thomas

Difficulty: Master Time estimate: 1-2 months+ Prerequisites: Completion of Projects 1-12, deep understanding of all individual components.

Real world outcome: A C++ command-line application that acts like a simplified SQL client:

$ ./minidb
minidb> CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(255));
Table 'users' created.

minidb> CREATE INDEX ON users (name);
Index 'name_idx' created on 'users'.

minidb> INSERT INTO users VALUES (1, 'Alice');
1 row inserted.

minidb> INSERT INTO users VALUES (2, 'Bob');
1 row inserted.

minidb> SELECT * FROM users WHERE name = 'Alice';
Query result:
id: 1, name: 'Alice'
(Using IndexScan on name_idx)

minidb> BEGIN TRANSACTION;
minidb> UPDATE users SET name = 'Alicia' WHERE id = 1;
minidb> SELECT * FROM users WHERE id = 1; -- Shows 'Alicia'
minidb> ROLLBACK;
minidb> SELECT * FROM users WHERE id = 1; -- Shows 'Alice' again (transaction aborted)

# Simulate a crash (e.g., kill -9 the process) and restart
$ ./minidb
minidb> Recovering database...
minidb> SELECT * FROM users WHERE id = 1; -- Still shows 'Alice' (committed data is durable)

Implementation Hints:

Main Loop: Create a REPL (Read-Eval-Print Loop) that reads SQL commands, passes them to your parser, gets an execution plan from the optimizer, and then runs the plan through the executor.
Catalog Manager: A persistent store (likely a dedicated table managed by your own system) that holds information about all tables (schema), columns (type, index), and indexes (type, key columns). This needs to interact with your DiskManager and BufferPoolManager.
Transaction Context: Ensure that every operation (e.g., inserting a tuple, fetching a page) is performed within the context of an active Transaction.
Recovery Integration: On startup, your RecoveryManager should automatically run its Recover() function before any user operations are allowed.
Testing: Write extensive unit tests for each component and integration tests for the full system. Test concurrent transactions and crash scenarios rigorously.

Learning milestones:

Successfully integrate all database components into a single, executable system. → You’ve built a complete (though simplified) DBMS.
Implement a basic SQL DDL/DML interpreter that interacts with your system. → You’ve created a user-facing interface for your database.
Demonstrate full ACID compliance through concurrent operations and crash recovery. → You’ve achieved the core reliability guarantees of a DBMS.
Showcase the benefits of your cost-based optimizer for query performance. → You’ve proven the intelligence of your database engine.

Summary

Project	Main Language	Difficulty
1. Disk-Oriented Storage Manager	C++	Intermediate
2. Tuple and Page Manager	C++	Intermediate
3. Buffer Pool Manager	C++	Advanced
4. B+Tree Index	C++	Expert
5. Hash Index (Extendable Hashing)	C++	Advanced
6. Relational Algebra Executor (Operators)	C++	Advanced
7. Join Operators	C++	Expert
8. Simple Query Parser & Rule-Based Optimizer	C++	Expert
9. Transaction Manager with Two-Phase Locking (2PL)	C++	Expert
10. Recovery Manager (UNDO/REDO Logging)	C++	Master
11. Multi-Version Concurrency Control (MVCC)	C++	Master
12. Simple Statistics and Cost-Based Optimizer	C++	Master
Final Overall Project: A Mini-Relational DBMS	C++	Master