ModakDB - Educational RDBMS in Python

"Reinventing the wheel to increase the gyrus sulcus" 🧠

A production-quality relational database management system built from scratch in Python for deep learning of database internals. This project is designed to be used by others while serving as a comprehensive educational resource.

---

📋 Table of Contents

1. Overview
2. System Architecture
3. Component Design
4. Implementation Roadmap
5. Testing Strategy
6. Development Guidelines

---

🎯 Overview

ModakDB is a full-featured RDBMS that implements core database concepts from first principles. While educational, it's architectured for real-world usage with proper error handling, testing, and performance considerations.

Core Features

• ✅ Storage Layer: Page-based heap file storage with efficient space management
• ✅ SQL Parser: Full SQL DML/DDL support (SELECT, INSERT, UPDATE, DELETE, CREATE, DROP)
• ✅ Query Execution: Volcano-style iterator model with push-based execution
• ✅ Indexing: B+ tree indexes for fast lookups and range queries
• ✅ Transactions: ACID compliance with MVCC (Multi-Version Concurrency Control)
• ✅ Buffer Pool: LRU-based page caching for performance
• ✅ Recovery: Write-Ahead Logging (WAL) for crash recovery
• ✅ Concurrency: Two-phase locking with deadlock detection

---

🏗️ System Architecture

High-Level Architecture

┌───────────────────────────────────────────────────────────┐
│                     Client Application                      │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                   SQL Interface Layer                       │
│  • Connection Management  • Session State  • Result Sets   │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                    Parser & Planner                         │
│  • Lexer & Parser  • AST  • Query Optimization             │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                   Query Executor                            │
│  • Scan  • Filter  • Join  • Aggregate  • Sort             │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│              Transaction & Concurrency Layer                │
│  • Transaction Manager  • Lock Manager  • MVCC             │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                  Buffer Pool Manager                        │
│  • Page Cache (LRU)  • Pin/Unpin  • Dirty Page Tracking   │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                   Storage Engine                            │
│  • Heap Files  • Page Layout  • Slotted Pages              │
└────────────────────────┬──────────────────────────────────┘
                         │
┌────────────────────────▼──────────────────────────────────┐
│                    Disk Manager                             │
│  • File I/O  • Page Allocation  • Free Space Tracking      │
└───────────────────────────────────────────────────────────┘

Data Flow Example: SELECT * FROM users WHERE age > 25

1. SQL String ──▶ Parser ──▶ AST
2. AST ──▶ Planner ──▶ Query Plan (Scan → Filter)
3. Executor starts iteration:
   a. Scan operator requests page from Buffer Pool
   b. Buffer Pool checks cache, if miss, loads from Storage
   c. Storage reads page from Heap File
   d. Filter operator evaluates predicate on each tuple
   e. Matching tuples returned to client

---

🔧 Component Design

1. Storage Layer (modakdb/storage/)

Heap File Structure

┌─────────────────────────────────────────┐
│           Database File (.mdb)           │
├─────────────────────────────────────────┤
│  Page 0: Header Page                     │
│    - DB Metadata                          │
│    - Free Page List                       │
├─────────────────────────────────────────┤
│  Page 1-N: Data Pages                    │
│    - Slotted Page Layout                 │
│    - Page Header (24 bytes)              │
│    - Slot Array (grows down)             │
│    - Free Space                           │
│    - Tuples (grow up)                     │
└─────────────────────────────────────────┘

Page Layout (4096 bytes)

PAGE_SIZE = 4096

Page Header (24 bytes):
  - page_id: 4 bytes (uint32)
  - lsn: 8 bytes (uint64) - Log Sequence Number
  - page_type: 1 byte (heap/index/meta)
  - num_slots: 2 bytes (uint16)
  - free_space_offset: 2 bytes (uint16)
  - free_space_size: 2 bytes (uint16)
  - next_page_id: 4 bytes (uint32)
  - checksum: 4 bytes (uint32)

Slot Array (variable):
  Each slot: (offset: 2 bytes, length: 2 bytes)
  
Tuples (variable):
  - Grow from end of page upward
  - Variable length records

Key Classes

• Page: Represents a single page in memory
• HeapFile: Manages collection of pages for a table
• SlottedPage: Implements slotted page layout
• DiskManager: Handles file I/O operations

---

2. Catalog Layer (modakdb/catalog/)

Schema Management

Catalog Structure:
  Database
    ├─ Tables (dict)
    │   ├─ TableSchema
    │   │   ├─ table_name: str
    │   │   ├─ columns: List[Column]
    │   │   ├─ indexes: List[Index]
    │   │   └─ heap_file_id: int
    │   └─ Column
    │       ├─ name: str
    │       ├─ type: ColumnType
    │       ├─ nullable: bool
    │       ├─ primary_key: bool
    │       └─ default: Any
    └─ Indexes (dict)

Supported Data Types

class ColumnType(Enum):
    INT = "INT"              # 4 bytes
    BIGINT = "BIGINT"        # 8 bytes
    FLOAT = "FLOAT"          # 4 bytes
    DOUBLE = "DOUBLE"        # 8 bytes
    VARCHAR = "VARCHAR"      # Variable (max length specified)
    CHAR = "CHAR"            # Fixed length
    BOOLEAN = "BOOLEAN"      # 1 byte
    DATE = "DATE"            # 4 bytes (days since epoch)
    TIMESTAMP = "TIMESTAMP"  # 8 bytes (microseconds)
    BLOB = "BLOB"            # Variable length binary

---

3. Parser Layer (modakdb/parser/)

SQL Grammar (using Lark)

Supported SQL Statements:
  - CREATE TABLE table_name (columns...)
  - DROP TABLE table_name
  - INSERT INTO table_name VALUES (...)
  - SELECT columns FROM table WHERE condition
  - UPDATE table SET col=val WHERE condition
  - DELETE FROM table WHERE condition
  - CREATE INDEX index_name ON table(column)

Expression Support:
  - Arithmetic: +, -, *, /, %
  - Comparison: =, !=, <, >, <=, >=
  - Logical: AND, OR, NOT
  - Functions: COUNT, SUM, AVG, MIN, MAX
  - Aggregations with GROUP BY and HAVING

AST Structure

Abstract Syntax Tree Nodes:
  - Statement (base class)
    ├─ SelectStatement
    │   ├─ columns: List[Expression]
    │   ├─ from_table: str
    │   ├─ where: Expression
    │   ├─ group_by: List[Expression]
    │   ├─ having: Expression
    │   └─ order_by: List[(Expression, ASC/DESC)]
    ├─ InsertStatement
    ├─ UpdateStatement
    ├─ DeleteStatement
    └─ DDLStatement (CREATE/DROP)

---

4. Executor Layer (modakdb/executor/)

Volcano Iterator Model

class Operator(ABC):
    @abstractmethod
    def open(self): ...      # Initialize operator
    
    @abstractmethod
    def next(self) -> Tuple: # Get next tuple (iterator protocol)
    
    @abstractmethod
    def close(self): ...     # Clean up resources

Operator Tree Example:
    ProjectionOp (name, age)
         │
    FilterOp (age > 25)
         │
    SeqScanOp (users table)

Execution Operators

Physical Operators:
  • SeqScan: Sequential table scan
  • IndexScan: Index-based lookup
  • Filter: Predicate evaluation
  • Project: Column projection
  • NestedLoopJoin: Nested loop join
  • HashJoin: Hash-based join
  • Sort: External merge sort
  • Aggregate: Grouping and aggregation
  • Limit: Result limiting

---

5. Buffer Pool (modakdb/buffer/)

LRU Cache Design

Buffer Pool:
  - Fixed size array of page frames
  - Hash table: page_id → frame_id
  - LRU replacement policy (doubly-linked list)
  - Pin counter for each frame
  - Dirty bit tracking

Operations:
  • FetchPage(page_id) → Page
  • UnpinPage(page_id, is_dirty)
  • FlushPage(page_id)
  • FlushAllPages()
  • NewPage() → Page

Eviction Policy:
  1. Find unpinned page with pin_count = 0
  2. If dirty, write to disk
  3. Remove from buffer pool
  4. Load new page

---

6. Transaction Management (modakdb/transaction/)

ACID Properties

Atomicity:

• Undo logging for rollback
• Transaction abort on errors

Consistency:

• Constraint checking
• Referential integrity

Isolation:

• MVCC (Multi-Version Concurrency Control)
• Snapshot isolation level

Durability:

• Write-Ahead Logging (WAL)
• Checkpoint mechanism

MVCC Implementation

Tuple Structure with Versioning:
  Tuple:
    - data: bytes
    - xmin: Transaction ID (creator)
    - xmax: Transaction ID (deleter, NULL if active)
    - is_deleted: bool

Visibility Rules:
  A tuple is visible to transaction T if:
    1. xmin < T.start_timestamp AND
    2. (xmax IS NULL OR xmax > T.start_timestamp)

Transaction States:
  ACTIVE → COMMITTED
         → ABORTED

---

7. Indexing (modakdb/index/)

B+ Tree Structure

B+ Tree Properties:
  - Order M (max children per node)
  - All records in leaf nodes
  - Leaves linked for range queries
  - Search time: O(log n)

Node Layout:
  Internal Node:
    - Keys: [K1, K2, ..., Kn]
    - Children: [P0, P1, ..., Pn]
    - P0 < K1 ≤ P1 < K2 ≤ ... < Kn ≤ Pn
  
  Leaf Node:
    - Keys: [K1, K2, ..., Kn]
    - Records: [R1, R2, ..., Rn]
    - Next pointer: Link to sibling

---

8. Recovery (modakdb/recovery/)

Write-Ahead Logging (WAL)

Log Record Types:
  - BEGIN: Transaction start
  - COMMIT: Transaction commit
  - ABORT: Transaction rollback
  - UPDATE: Tuple modification (before/after)
  - INSERT: Tuple insertion
  - DELETE: Tuple deletion
  - CHECKPOINT: System checkpoint

Recovery Algorithm (ARIES):
  1. Analysis Pass: Scan log to find dirty pages
  2. Redo Pass: Replay all operations (idempotent)
  3. Undo Pass: Rollback uncommitted transactions

---

🗺️ Implementation Roadmap

Phase 1: Foundation (Weeks 1-2)

□ Storage Layer
  □ Page structure and layout
  □ Disk manager (file I/O)
  □ Heap file implementation
  □ Slotted page management
  
□ Catalog Layer
  □ Data type definitions
  □ Table schema management
  □ Column definitions
  □ Catalog persistence

Phase 2: Query Processing (Weeks 3-4)

□ Parser Layer
  □ SQL grammar definition (Lark)
  □ Lexer and parser
  □ AST construction
  □ Statement validation
  
□ Executor Layer
  □ Operator interface
  □ Sequential scan
  □ Filter operator
  □ Projection operator
  □ Simple DML execution

Phase 3: Buffer Management (Week 5)

□ Buffer Pool Manager
  □ Page frame allocation
  □ LRU replacement policy
  □ Pin/unpin mechanism
  □ Dirty page tracking
  □ Flush policies

Phase 4: Indexing (Weeks 6-7)

□ B+ Tree Index
  □ Node structure
  □ Insert operation
  □ Search operation
  □ Delete operation
  □ Range scan
  □ Index scan operator

Phase 5: Transactions (Weeks 8-9)

□ Transaction Management
  □ Transaction context
  □ Begin/Commit/Abort
  □ Undo logging
  □ MVCC implementation
  
□ Concurrency Control
  □ Lock manager
  □ Two-phase locking
  □ Deadlock detection

Phase 6: Recovery (Week 10)

□ Write-Ahead Logging
  □ Log manager
  □ Log record formats
  □ Log buffering
  □ Checkpoint mechanism
  
□ Recovery
  □ ARIES algorithm
  □ Crash recovery
  □ Transaction rollback

Phase 7: Advanced Features (Weeks 11-12)

□ Query Optimization
  □ Cost model
  □ Join ordering
  □ Index selection
  
□ Advanced Operators
  □ Hash join
  □ Sort-merge join
  □ Aggregation
  □ GROUP BY / HAVING
  
□ Performance
  □ Query caching
  □ Statistics collection
  □ Profiling tools

---

🧪 Testing Strategy

Unit Tests Structure

tests/unit/
  ├── test_storage.py
  │   ├── TestPage
  │   ├── TestSlottedPage
  │   ├── TestHeapFile
  │   └── TestDiskManager
  │
  ├── test_catalog.py
  │   ├── TestColumnType
  │   ├── TestColumn
  │   ├── TestTableSchema
  │   └── TestCatalog
  │
  ├── test_parser.py
  │   ├── TestLexer
  │   ├── TestParser
  │   ├── TestSelectStatement
  │   └── TestDDLStatements
  │
  ├── test_executor.py
  │   ├── TestSeqScan
  │   ├── TestFilter
  │   ├── TestProjection
  │   └── TestJoinOperators
  │
  ├── test_buffer.py
  │   ├── TestBufferPool
  │   ├── TestLRUReplacer
  │   └── TestPageEviction
  │
  └── test_transaction.py
      ├── TestTransactionManager
      ├── TestMVCC
      └── TestLockManager

Integration Tests Structure

tests/integration/
  ├── test_end_to_end.py
  │   ├── test_create_table_and_insert
  │   ├── test_query_execution
  │   ├── test_updates_and_deletes
  │   └── test_complex_queries
  │
  ├── test_transactions.py
  │   ├── test_acid_properties
  │   ├── test_concurrent_transactions
  │   ├── test_deadlock_detection
  │   └── test_rollback
  │
  ├── test_recovery.py
  │   ├── test_crash_recovery
  │   ├── test_wal_replay
  │   └── test_checkpoint
  │
  └── test_performance.py
      ├── benchmark_insert
      ├── benchmark_scan
      └── benchmark_index_lookup

Test Coverage Goals

• Unit Tests: 90%+ coverage
• Integration Tests: All major workflows
• Performance Tests: Regression detection
• Edge Cases: Null values, boundary conditions, concurrent access

---

💻 Development Guidelines

Project Structure

modakdb/
├── __init__.py                 # Package initialization
├── api/                        # Public API
│   ├── __init__.py
│   ├── database.py            # Database class (main entry)
│   └── exceptions.py          # Custom exceptions
├── storage/                    # Storage layer
│   ├── __init__.py
│   ├── disk_manager.py        # File I/O operations
│   ├── page.py                # Page structure
│   ├── heap_file.py           # Heap file management
│   └── slotted_page.py        # Slotted page layout
├── catalog/                    # Schema management
│   ├── __init__.py
│   ├── types.py               # Data types
│   ├── schema.py              # Table schemas
│   └── catalog.py             # System catalog
├── parser/                     # SQL parsing
│   ├── __init__.py
│   ├── grammar.lark           # SQL grammar
│   ├── parser.py              # Parser implementation
│   └── ast_nodes.py           # AST definitions
├── planner/                    # Query planning
│   ├── __init__.py
│   ├── planner.py             # Query planner
│   └── optimizer.py           # Query optimizer
├── executor/                   # Query execution
│   ├── __init__.py
│   ├── operator.py            # Base operator class
│   ├── scan.py                # Scan operators
│   ├── filter.py              # Filter operator
│   ├── projection.py          # Projection operator
│   ├── join.py                # Join operators
│   ├── aggregate.py           # Aggregation
│   └── sort.py                # Sort operator
├── buffer/                     # Buffer pool
│   ├── __init__.py
│   ├── buffer_pool.py         # Buffer pool manager
│   └── replacer.py            # LRU replacer
├── transaction/                # Transactions
│   ├── __init__.py
│   ├── transaction.py         # Transaction context
│   ├── lock_manager.py        # Lock management
│   └── mvcc.py                # MVCC implementation
├── recovery/                   # Recovery
│   ├── __init__.py
│   ├── log_manager.py         # WAL manager
│   ├── log_record.py          # Log records
│   └── recovery.py            # Recovery algorithm
└── index/                      # Indexing
    ├── __init__.py
    ├── index.py               # Base index interface
    └── btree.py               # B+ tree implementation

Code Style

# Use type hints
def insert_tuple(self, table_name: str, values: List[Any]) -> int:
    """Insert a tuple into a table.
    
    Args:
        table_name: Name of the table
        values: List of column values
        
    Returns:
        Row ID of inserted tuple
        
    Raises:
        TableNotFoundError: If table doesn't exist
    """
    pass

# Use dataclasses for structured data
@dataclass
class Page:
    page_id: int
    data: bytearray
    is_dirty: bool = False
    pin_count: int = 0

# Use enums for constants
class PageType(Enum):
    HEAP_PAGE = 1
    INDEX_PAGE = 2
    META_PAGE = 3

Error Handling

# Custom exception hierarchy
class ModakDBError(Exception):
    """Base exception for all ModakDB errors"""
    pass

class StorageError(ModakDBError):
    """Storage layer errors"""
    pass

class ParseError(ModakDBError):
    """SQL parsing errors"""
    pass

class ExecutionError(ModakDBError):
    """Query execution errors"""
    pass

Example Usage

from modakdb import Database

# Create database
db = Database("mydb.mdb")

# Create table
db.execute("""
    CREATE TABLE users (
        id INT PRIMARY KEY,
        name VARCHAR(100),
        age INT,
        email VARCHAR(255)
    )
""")

# Insert data
db.execute("INSERT INTO users VALUES (1, 'Alice', 30, 'alice@example.com')")
db.execute("INSERT INTO users VALUES (2, 'Bob', 25, 'bob@example.com')")

# Query data
result = db.execute("SELECT name, age FROM users WHERE age > 25")
for row in result:
    print(f"{row['name']}: {row['age']}")

# Transactions
with db.transaction() as txn:
    txn.execute("UPDATE users SET age = 31 WHERE name = 'Alice'")
    txn.execute("DELETE FROM users WHERE name = 'Bob'")
    # Automatically commits if no exception

db.close()

---

📚 Learning Resources

Recommended Reading

1. Database System Concepts - Silberschatz, Korth, Sudarshan
2. Database Management Systems - Ramakrishnan, Gehrke
3. Architecture of a Database System - Hellerstein, Stonebraker, Hamilton
4. The Internals of PostgreSQL - Hironobu SUZUKI (online)

Key Papers

• ARIES Recovery Algorithm (Mohan et al.)
• B+ tree Implementations (Comer)
• MVCC in PostgreSQL (PostgreSQL Documentation)

---

🚀 Quick Start

# Clone repository
git clone https://github.com/rohitwtbs/modakdb.git
cd modakdb

# Install in development mode
pip install -e ".[dev]"

# Run tests
pytest tests/ -v

# Run with coverage
pytest --cov=modakdb --cov-report=html tests/

# Type checking
mypy modakdb/

# Linting
ruff check modakdb/

---

📝 License

MIT License - See LICENSE for details

---

🤝 Contributing

This is an educational project, but contributions are welcome! Please:

1. Write tests for new features
2. Follow the existing code style
3. Update documentation
4. Add type hints

---

Happy Database Building! 🚀

"The best way to understand databases is to build one."

MIT License - See LICENSE file