MiniDB — A Storage Engine in Go

A mini SQLite/Postgres-style database engine built from scratch in Go.

Components

Component	Package	Description
REPL	`cmd/minidb`	Interactive single-user command-line interface.
TCP Server	`cmd/minidb-server`	Multi-client TCP server (like PostgreSQL). Each client gets its own session.
Server Core	`internal/server`	Per-client goroutine, shared storage layers, auto-rollback on disconnect.
Parser	`internal/parser`	Lexer & recursive descent parser that builds an Abstract Syntax Tree (AST).
Optimizer	`internal/optimizer`	Cost-based query planner. Chooses index scans, hash joins, and pushes down limits.
Executor	`internal/engine`	Query evaluator. Coordinates B+ tree searches, joins, inserting, and secondary index maintenance.
Catalog	`internal/catalog`	Manages schemas, tables, and secondary indexes. Persisted as JSON.
B+ Tree	`internal/btree`	O(log n) ordered key-value storage. Used for primary tables and secondary indexes.
Buffer Pool	`internal/buffer`	In-memory page cache with LRU eviction policy. Manages page pinning for concurrent access.
Disk Manager	`internal/disk`	Handles raw file I/O for 4KB pages.
Row Store	`internal/engine/rowstore.go`	Disk-backed append-only heap file for storing row data.
WAL	`internal/wal`	Write-Ahead Log for durability and transaction rollback.
Transaction Mgr	`internal/txn`	Session-level `BEGIN` / `COMMIT` / `ROLLBACK` with in-memory undo log.
Lock Manager	`internal/lock`	Two-Phase Locking (2PL) — blocking `Lock()` with timeout + `TryLock()`.

Quick Start

Single-User REPL (SQLite-style)

go run cmd/minidb/main.go [database_file]

Multi-Client TCP Server (PostgreSQL-style)

# Start the server (defaults: db=minidb.db, port=5433, lock-timeout=5s)
go run cmd/minidb-server/main.go

# With options
go run cmd/minidb-server/main.go -db mydb.db -addr :5433 -lock-timeout 10

# Connect with any TCP client (nc, telnet, custom driver)
nc localhost 5433

Protocol: Send SQL ending with ; followed by newline. The server responds with the result rows, then a READY line to signal it's ready for the next command — identical to PostgreSQL's ReadyForQuery concept.

Multi-Client Demo

Setup (Terminal 1 — start the server)

go run cmd/minidb-server/main.go -db bank.db
# [minidb-server] Listening on :5433

Client A (Terminal 2)

nc localhost 5433
# MiniDB ready. Send SQL statements terminated with ';'.
# READY

CREATE TABLE accounts (id INT, balance INT);
# 1 row(s) affected
# READY

INSERT INTO accounts VALUES (1, 1000);
INSERT INTO accounts VALUES (2, 500);

BEGIN;
# READY
UPDATE accounts SET balance = 900 WHERE id = 1;
# 1 row(s) updated
# READY

Client A now holds an EXCLUSIVE lock on accounts and has NOT committed yet.

Client B (Terminal 3) — concurrent session

nc localhost 5433
# READY

BEGIN;
UPDATE accounts SET balance = 400 WHERE id = 1;
# (blocks — waiting for Client A's EXCLUSIVE lock)

Back in Client A (Terminal 2)

COMMIT;
# transaction committed
# READY

Client B immediately unblocks and its UPDATE succeeds:

1 row(s) updated
READY

# Client B
COMMIT;
SELECT * FROM accounts;
# +----+---------+
# | id | balance |
# +----+---------+
# | 1  | 400     |
# | 2  | 500     |
# +----+---------+
# 2 row(s)

Example Session (Single REPL)

Basic CRUD + New Types

minidb> CREATE TABLE users (id INT, name TEXT, age INT);
minidb> INSERT INTO users VALUES (1, 'karim', 30);
minidb> INSERT INTO users VALUES (2, 'hassan', 25);
minidb> SELECT * FROM users WHERE age > 25;
minidb> UPDATE users SET age = 31 WHERE id = 1;
minidb> DELETE FROM users WHERE id = 2;

-- FLOAT and BOOL columns
minidb> CREATE TABLE products (id INT, name TEXT, price FLOAT, active BOOL);
minidb> INSERT INTO products VALUES (1, 'apple', 1.99, TRUE);
minidb> INSERT INTO products VALUES (2, 'candy', 0.50, FALSE);
minidb> SELECT * FROM products WHERE price > 1.0;
minidb> SELECT * FROM products WHERE active = TRUE;

Transactions (ACID)

-- Create a table for the demo
minidb> CREATE TABLE accts (id INT, bal INT);
minidb> INSERT INTO accts VALUES (1, 1000);
minidb> INSERT INTO accts VALUES (2, 500);

-- Successful multi-statement transaction
minidb> BEGIN;
transaction started
minidb(txn)> INSERT INTO accts VALUES (3, 250);
1 row inserted
minidb(txn)> UPDATE accts SET bal = 900 WHERE id = 1;
1 row(s) updated
minidb(txn)> COMMIT;
transaction committed
minidb> SELECT * FROM accts;   -- 3 rows; id=1 has bal=900

-- Transaction that is rolled back
minidb> BEGIN;
transaction started
minidb(txn)> DELETE FROM accts WHERE id = 3;
1 row(s) deleted
minidb(txn)> ROLLBACK;
transaction rolled back
minidb> SELECT * FROM accts;   -- still 3 rows (DELETE was undone)

Note: The prompt changes to minidb(txn)> while inside an active transaction. Without BEGIN, every statement auto-commits.

JOIN Queries

minidb> CREATE TABLE users (id INT, name TEXT);
minidb> CREATE TABLE orders (id INT, user_id INT, item TEXT);
minidb> INSERT INTO users VALUES (1, 'Alice');
minidb> INSERT INTO users VALUES (2, 'Bob');
minidb> INSERT INTO orders VALUES (1, 1, 'book');
minidb> INSERT INTO orders VALUES (2, 1, 'pen');
minidb> INSERT INTO orders VALUES (3, 99, 'ghost');  -- no matching user

-- INNER JOIN: only matched rows
minidb> SELECT * FROM orders INNER JOIN users ON orders.user_id = users.id;

-- LEFT JOIN: all left rows, NULL where no match
minidb> SELECT * FROM orders LEFT JOIN users ON orders.user_id = users.id;

Secondary Indexes

minidb> CREATE TABLE employees (id INT, name TEXT, dept INT);
minidb> INSERT INTO employees VALUES (1, 'Alice', 10);
minidb> INSERT INTO employees VALUES (2, 'Bob', 20);
minidb> INSERT INTO employees VALUES (3, 'Carol', 10);

-- Create a secondary index on 'dept'
minidb> CREATE INDEX idx_dept ON employees (dept);
Index "idx_dept" created on employees(dept)

-- O(log n) index-accelerated lookup
minidb> SELECT name FROM employees WHERE dept = 10;
+-------+
| name  |
+-------+
| Alice |
| Carol |
+-------+

-- UNIQUE index — enforces uniqueness
minidb> CREATE UNIQUE INDEX idx_name ON employees (name);
minidb> INSERT INTO employees VALUES (4, 'Alice', 30);
Error: UNIQUE constraint violation on index "idx_name"

minidb> SHOW INDEXES FROM employees;
minidb> DROP INDEX idx_dept ON employees;

Query Optimizer & EXPLAIN

MiniDB features a rule-based Query Optimizer (internal/optimizer) that selects the most efficient execution plan for your queries. It supports:

PkIndexScan (O(log n)): Chosen when filtering by the primary key (WHERE id = ?).
SecondaryIndexScan (O(log n)): Chosen when filtering by a secondary index column.
SeqScan (O(n)): Fallback sequential table scan.
HashJoin (O(n + m)): Chosen for equi-joins (ON t1.col = t2.col).
Limit Pushdown: Stops table scans early if LIMIT is specified without an ORDER BY.

You can use the EXPLAIN keyword to see the execution plan chosen by the optimizer:

Optimization Examples

minidb> CREATE TABLE users (id INT, age INT, name TEXT);
minidb> CREATE INDEX idx_age ON users (age);

-- 1. Sequential Scan (no index on 'name')
minidb> EXPLAIN SELECT * FROM users WHERE name = 'Alice';
+------------------------------------+
| plan                               |
+------------------------------------+
| Scan: SeqScan | Cost: O(n)         |
+------------------------------------+

-- 2. Primary Key Index Scan
minidb> EXPLAIN SELECT * FROM users WHERE id = 10;
+------------------------------------+
| plan                               |
+------------------------------------+
| Scan: PkIndexScan | Cost: O(log n) |
+------------------------------------+

-- 3. Secondary Index Scan
minidb> EXPLAIN SELECT * FROM users WHERE age = 30;
+--------------------------------------------------------------+
| plan                                                         |
+--------------------------------------------------------------+
| Scan: SecondaryIndexScan (index=idx_age, column=age) | Cost: O(log n) |
+--------------------------------------------------------------+

-- 4. Limit Pushdown
minidb> EXPLAIN SELECT * FROM users LIMIT 5;
+-------------------------------------------------------+
| plan                                                  |
+-------------------------------------------------------+
| Scan: SeqScan | LimitPushdown: true | Cost: O(n)      |
+-------------------------------------------------------+

-- 5. Hash Join
minidb> CREATE TABLE orders (id INT, user_id INT);
minidb> EXPLAIN SELECT * FROM orders INNER JOIN users ON orders.user_id = users.id;
+----------------------------------+
| plan                             |
+----------------------------------+
| Join: HashJoin | Cost: O(n + m)  |
+----------------------------------+

Concurrency: Two-Phase Locking (2PL)

MiniDB implements strict Two-Phase Locking (2PL) at the table level to guarantee Serializable isolation across all concurrent sessions.

Lock Modes

Operation	Lock Acquired	Behaviour
`SELECT`	SHARED	Multiple readers can hold shared locks simultaneously
`INSERT` / `UPDATE` / `DELETE`	EXCLUSIVE	Blocks all other readers and writers on that table

Lock Lifecycle

BEGIN        → Growing Phase: acquire locks on each DML statement
COMMIT /     → Shrinking Phase: ALL locks released at once
ROLLBACK

What happens on conflict?

Unlike older versions that returned an immediate error, MiniDB now blocks the waiting transaction (like PostgreSQL) until:

The holder commits or rolls back → waiter is immediately unblocked and proceeds.
The lock timeout expires (default 5 seconds) → waiter receives a timeout error.

Testing 2PL with the TCP server

# Terminal 1 — start server
go run cmd/minidb-server/main.go

# Terminal 2 — Session A
nc localhost 5433
CREATE TABLE t (id INT, val INT);
INSERT INTO t VALUES (1, 100);
BEGIN;
UPDATE t SET val = 200 WHERE id = 1;  -- acquires EXCLUSIVE lock

# Terminal 3 — Session B (runs while A holds the lock)
nc localhost 5433
BEGIN;
UPDATE t SET val = 300 WHERE id = 1;  -- BLOCKS here, waiting for A

# Back in Terminal 2 — Session A
COMMIT;   -- Session B immediately proceeds

# Terminal 3 — Session B shows:
# 1 row(s) updated   (unblocked by A's COMMIT)
# READY

Disconnect auto-rollback

If a client closes its connection mid-transaction, the server automatically rolls back the open transaction and releases all its locks, preventing other clients from being stuck forever.

Running Tests

# All tests
go test ./tests/... -v -count=1

# Concurrency / 2PL tests
go test ./tests/ -run TestConcurrency -v

# Multi-client server tests
go test ./tests/ -run TestServer -v

# Transaction (ACID) tests
go test ./tests/ -run TestTransaction -v

# Individual test suites
go test ./tests/ -run TestBTree -v
go test ./tests/ -run TestWAL -v
go test ./tests/ -run TestParser -v
go test ./tests/ -run TestEngine -v

# Benchmarks
go test ./tests/ -bench=. -benchmem

Server test coverage

Test	What it verifies
`TestServer_SingleClient`	Basic CRUD over TCP
`TestServer_ConcurrentReads`	Two clients `SELECT` simultaneously — both succeed
`TestServer_WriteConflict_Timeout`	Second writer blocks then times out
`TestServer_WriteUnblocksAfterCommit`	Writer B unblocks after Writer A commits
`TestServer_RollbackReleasesLocks`	`ROLLBACK` releases locks immediately
`TestServer_DisconnectReleasesLocks`	Force-closing connection triggers auto-rollback
`TestServer_MultipleClients_IndependentTables`	Writes to different tables never block each other

Architecture Deep Dive

Multi-Client Architecture

┌─────────────────────────────────────────────────────────┐
│                   minidb-server (TCP)                   │
│                                                         │
│  Client A ─► goroutine A ─► Executor A ─► TxManager A ─┤
│  Client B ─► goroutine B ─► Executor B ─► TxManager B ─┤
│  Client C ─► goroutine C ─► Executor C ─► TxManager C ─┤
│                                            │            │
│                                    ┌───────▼────────┐   │
│                                    │  LockManager   │   │  ← shared 2PL
│                                    │  (sync.Cond)   │   │
│                                    └───────┬────────┘   │
│                              ┌─────────────┼──────────┐ │
│                         BufferPool    Catalog     WAL  │ │  ← shared storage
│                         (LRU cache)  (JSON)  (fsync)  │ │
└─────────────────────────────────────────────────────────┘

Data Flow: INSERT INTO users VALUES (1, 'Alice', 30)

1. REPL / TCP client sends SQL
2. Parser.ParseSQL() → InsertStmt AST
3. Executor.executeInsert():
   a. TxManager.AcquireLock("users", EXCLUSIVE)  ← blocks if held by another txn
   b. Look up "users" schema in Catalog
   c. Validate column count
   d. If TxManager.IsActive():
      → WAL.LogInsert(activeTxID, ...)   ← shared TxID from BEGIN
      → BTree.Insert(pk, encodedRow)
      → TxManager.RecordInsert()         ← undo op saved for possible ROLLBACK
   e. Else (auto-commit):
      → WAL.Begin() → LogInsert() → BTree.Insert() → WAL.Commit()
4. ResultSet("1 row inserted") → client

Data Flow: ROLLBACK

1. Parser.ParseSQL() → RollbackStmt AST
2. Executor.executeRollback():
   a. TxManager.Rollback()
   b. Walk undo log in reverse (last-in, first-out):
      - UndoInsert  → tree.Delete(key)
      - UndoDelete  → tree.Insert(key, oldValue)
      - UndoUpdate  → tree.Delete(key) + tree.Insert(key, oldValue)
   c. LockManager.ReleaseAll(txID)     ← wakes all waiting goroutines
   d. WAL.Abort(txID, nil)

WAL Recovery (crash safety)

If the process crashes mid-transaction:

Analysis: scan log → find active (uncommitted) transactions
Redo: replay all log records → restore state as of crash
Undo: reverse all uncommitted transaction changes

B+ Tree Structure

                    [50 | 150]              ← root (internal)
                   /     |      \
            [20|30]    [80|100]  [180|200]  ← internal nodes
           /  |  \    /  |   \   ...
         [.] [.] [.][.] [.] [.]            ← leaf nodes (hold data)
              ↑─────────────────↑ linked list for range scans

Supported SQL Syntax

-- Data Definition
CREATE TABLE name (col1 INT, col2 TEXT, col3 FLOAT, col4 BOOL);

-- Data Manipulation (DML)
INSERT INTO table_name VALUES (v1, v2, ...);
SELECT * FROM table_name [WHERE expr] [ORDER BY col [ASC|DESC]] [LIMIT n];
SELECT col1, col2 FROM table_name [WHERE expr];
UPDATE table_name SET col=val [WHERE expr];
DELETE FROM table_name [WHERE expr];

-- Joins
SELECT * FROM t1 INNER JOIN t2 ON t1.col = t2.col;
SELECT * FROM t1 LEFT JOIN t2 ON t1.col = t2.col;

-- Indexes
CREATE [UNIQUE] INDEX index_name ON table_name (column_name);
DROP INDEX index_name ON table_name;
SHOW INDEXES [FROM table_name];

-- Transactions (ACID)
BEGIN [TRANSACTION];
COMMIT [TRANSACTION];
ROLLBACK [TRANSACTION];

-- WHERE operators
=  !=  <  >  <=  >=  AND  OR  NOT

-- Data types
INT    -- 64-bit signed integer
TEXT   -- variable-length string
FLOAT  -- 64-bit IEEE 754 double (literals: 3.14, -0.5)
BOOL   -- boolean (literals: TRUE, FALSE)

Key Design Decisions

Page size: 4096 bytes (matches OS virtual memory page = efficient I/O).
Index structure: B+ Tree (O(log n) point lookup + O(log n + k) range scan).
Cache policy: LRU (simple, effective for most workloads).
WAL: Ensures durability (crash recovery) and allows transactions to be rolled back.
Strict 2PL: All locks held until COMMIT/ROLLBACK. Prevents dirty reads, lost updates, and write skew (Serializable isolation).
Blocking locks: Lock(ctx) uses sync.Cond to sleep and wake — no spin-waiting, no CPU waste.
Disconnect safety: Server automatically rolls back and releases locks when a client disconnects, preventing lock leaks.
Secondary Indexes: Stored as separate B+ trees with composite keys (indexed_value << 32 | PK).
Heap Persistence: RowStore on buffer pool pages — durable, multi-session visible.

Changelog

v5.0 — Query Optimizer & Hash Joins (2026-04-04)

New Features

Query Optimizer (internal/optimizer): Added a proper rule-based query optimizer that separates logical planning from execution. It inspects table schemas and indexes to choose between PkIndexScan, SecondaryIndexScan, and SeqScan.
Hash Joins: Replaced the previous O(n × m) nested loop join with an O(n + m) in-memory Hash Join for equi-joins (JOIN ON t1.col = t2.col). Handles both INNER and LEFT joins.
EXPLAIN Statement: Added EXPLAIN <query> support to the parser allowing users to inspect the query plan, join strategy, and estimated time complexity.
LIMIT Pushdown: The optimizer enables limit pushdown for queries using LIMIT without ORDER BY, allowing the executor to stop sequential and index scans early to save I/O and CPU.

Files Changed

File	Change
`internal/optimizer/optimizer.go`	[NEW] Optimizer module, plan types, and selection rules
`internal/parser/lexer.go`	Added `EXPLAIN` token
`internal/parser/ast.go`	Added `ExplainStmt` AST node
`internal/parser/parser.go`	Added `parseExplain()` to support `EXPLAIN` SQL syntax
`internal/engine/executor.go`	Added `executeExplain()`, `executeHashJoin()`, and optimizer-driven scan dispatch
`tests/optimizer_test.go`	[NEW] 10+ comprehensive test scenarios for plan selection and joins

v4.0 — Multi-Client TCP Server (2026-04-02)

New Features

TCP Server (cmd/minidb-server): Start with go run cmd/minidb-server/main.go. Accepts multiple simultaneous client connections like PostgreSQL/MySQL. Each client gets an independent session (Executor + TxManager). One shared LockManager coordinates 2PL across all sessions.
Blocking Lock() with timeout: Replaced the immediate-error-on-conflict approach with a blocking Lock(ctx, ...) using sync.Cond. Waiting transactions are notified the instant the holder releases the lock. Default timeout: 5 seconds (configurable with -lock-timeout flag).
TryLock() for immediate failure: The non-blocking path is preserved as TryLock() for internal testing and admin paths.
SetLockTimeout() per session: Each session can configure its own lock wait limit.
Auto-rollback on disconnect: When a client drops its TCP connection mid-transaction, the server detects the EOF and automatically rolls back to release all locks.
READY protocol marker: Server sends READY\n after each response so clients know when to send the next command.

Files Changed

File	Change
`internal/lock/lock_manager.go`	Blocking `Lock(ctx)` with `sync.Cond`, `TryLock()`, `ReleaseAll` broadcasts
`internal/txn/manager.go`	`AcquireLock` uses `context.WithTimeout`, new `SetLockTimeout()`
`internal/engine/executor.go`	New `SetLockTimeout()` wrapper, `time` import
`internal/server/server.go`	[NEW] TCP server: `Listen()`, `ListenOn()`, `handleConn()` per-client goroutine
`cmd/minidb-server/main.go`	[NEW] Server binary with `-db`, `-addr`, `-lock-timeout` flags
`tests/concurrency_test.go`	Updated to use `TryLock()` for immediate-conflict tests, added `time` import
`tests/server_test.go`	[NEW] 7 multi-client integration tests

v3.0 — Persistent Architecture & Concurrency Control (2026-03-27)

New Architecture

RowStore Heap Persistence: Completely removed in-memory rowCache map and moved to a 4KB BufferPool page-backed continuous heap file.
Secondary Index Composite Keys: Fixed primary key constraint collisions. Secondary indexes now store keys as (indexed_value << 32 | primary_key).
BufferPool Edge Case Fixes: Prevented memory page tracking eviction bugs.

Files Changed

File	Change
`internal/txn/manager.go`	[NEW] `TxManager`: `Begin()`, `Commit()`, `Rollback()`, undo log
`internal/lock/lock_manager.go`	[NEW] 2PL lock manager (table-level, strict 2PL)
`internal/parser/lexer.go`	4 new tokens: `BEGIN`, `COMMIT`, `ROLLBACK`, `TRANSACTION`
`internal/engine/executor.go`	`txm *TxManager` field; dual auto-commit/explicit mode in INSERT/UPDATE/DELETE
`tests/transaction_test.go`	[NEW] 12 ACID tests
`tests/concurrency_test.go`	[NEW] Lock compatibility and 2PL integration tests

v2.0 — JOIN + FLOAT/BOOL Types (2026-03-19)

New Data Types

Type	Storage	Literals
`FLOAT`	8-byte IEEE 754 (tag `2` in WAL)	`3.14`, `-0.5`
`BOOL`	1 byte (tag `3` in WAL)	`TRUE`, `FALSE`

New SQL Features

INNER JOIN — Nested Loop Join
LEFT JOIN — all left rows; unmatched right columns are NULL
Qualified column references — table.column syntax
Float and Boolean literals

References

CMU 15-445 Database Systems — free lectures + labs
Database Internals — Alex Petrov (O'Reilly)
BoltDB — real B+ tree in Go
Designing Data-Intensive Applications — Kleppmann

Name		Name	Last commit message	Last commit date
cmd		cmd
internal		internal
tests		tests
.gitignore		.gitignore
README.md		README.md
go.mod		go.mod
guide.md		guide.md
minidb.db		minidb.db
minidb.db.catalog.json		minidb.db.catalog.json
minidb.db.wal		minidb.db.wal

Latest commit

History

Folders and files

Repository files navigation

MiniDB — A Storage Engine in Go

Components

Quick Start

Single-User REPL (SQLite-style)

Multi-Client TCP Server (PostgreSQL-style)

Multi-Client Demo

Setup (Terminal 1 — start the server)

Client A (Terminal 2)

Client B (Terminal 3) — concurrent session

Back in Client A (Terminal 2)

Example Session (Single REPL)

Basic CRUD + New Types

Transactions (ACID)

JOIN Queries

Secondary Indexes

Query Optimizer & EXPLAIN

Optimization Examples

Concurrency: Two-Phase Locking (2PL)

Lock Modes

Lock Lifecycle

What happens on conflict?

Testing 2PL with the TCP server

Disconnect auto-rollback

Running Tests

Server test coverage

Architecture Deep Dive

Multi-Client Architecture

Data Flow: INSERT INTO users VALUES (1, 'Alice', 30)

Data Flow: ROLLBACK

WAL Recovery (crash safety)

B+ Tree Structure

Supported SQL Syntax

Key Design Decisions

Changelog

v5.0 — Query Optimizer & Hash Joins (2026-04-04)

New Features

Files Changed

v4.0 — Multi-Client TCP Server (2026-04-02)

New Features

Files Changed

v3.0 — Persistent Architecture & Concurrency Control (2026-03-27)

New Architecture

Files Changed

v2.0 — JOIN + FLOAT/BOOL Types (2026-03-19)

New Data Types

New SQL Features

References

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages