Full RDBMS Engine

# Full RDBMS Engine PRD

## Overview
Build a complete relational database management system from scratch that supports SQL parsing, query optimization, B-tree indexing, ACID-compliant transactions, and persistent storage with crash recovery.

## Requirements
- SQL parser supporting: CREATE TABLE, DROP TABLE, INSERT, SELECT (with WHERE, ORDER BY, GROUP BY, HAVING, LIMIT, OFFSET), UPDATE, DELETE
- JOIN support: INNER JOIN, LEFT JOIN, RIGHT JOIN with ON conditions
- Subquery support in WHERE clauses and FROM clauses (derived tables)
- Query planner with cost-based optimization (choose between sequential scan vs index scan based on selectivity)
- B-tree index implementation: CREATE INDEX, DROP INDEX, automatically used by query planner when beneficial
- ACID transactions: BEGIN, COMMIT, ROLLBACK with proper isolation
- Write-ahead log (WAL) for crash recovery — replay uncommitted transactions on startup
- Page-based storage engine: data stored in fixed-size pages (e.g., 4KB) on disk
- Buffer pool manager with LRU eviction policy for caching pages in memory
- Table schemas with typed columns: INT, TEXT, FLOAT, BOOLEAN, TIMESTAMP
- Proper NULL handling: IS NULL, IS NOT NULL, NULL propagation in expressions
- Aggregate functions: COUNT, SUM, AVG, MIN, MAX (work with GROUP BY)
- PRIMARY KEY constraint (unique, not null, auto-creates index)
- UNIQUE constraint enforcement on insert and update
- Foreign key constraints with ON DELETE CASCADE and ON UPDATE CASCADE
- EXPLAIN command that outputs the query execution plan
- Concurrent read access: multiple readers can query simultaneously without blocking
- Data persistence: all data survives process restart by reading from disk files
- Interactive CLI REPL interface for executing SQL statements
- Handle tables with 10,000+ rows efficiently (index scans should be O(log n))
- CREATE DATABASE and DROP DATABASE support for managing multiple databases

## Tech Stack
- TypeScript/Node.js, Python, Go, Rust, or C++
- No database libraries, SQL parsers, or storage engines — build everything from scratch
- File system for persistence (no SQLite, LevelDB, etc.)

## Scoring Criteria
- **Functional (40%)**: SQL parsing works, queries return correct results, joins work, transactions provide isolation
- **Quality (20%)**: Clean architecture (parser, planner, executor, storage layers), handles malformed SQL gracefully, no data corruption
- **Fidelity (25%)**: All features implemented including WAL recovery, B-tree indexes, EXPLAIN, foreign keys, concurrent reads
- **Speed (15%)**: Time bonus