GopherSQL

A fully functional, concurrent, relational SQL database built completely from scratch in Go.

This project explores the deep internals of database engineering. It implements the core architectures found in industry-standard databases like PostgreSQL and SQLite, starting from raw byte manipulation on disk all the way up to an interactive SQL REPL.

Features

• Storage Engine:
  • B-Tree data structure optimized for 4KB disk pages.
  • Memory Mapping (mmap) for lightning-fast reads without heavy disk I/O.
  • Atomic two-phase commits with crash recovery.
• Garbage Collection:
  • Disk space is reclaimed via an internal Freelist.
• Relational Layer:
  • Schema definitions (CREATE TABLE), strictly typed columns, and auto-managed system tables (@table, @meta).
  • Fast Point Queries and Range Scans (SeekLE).
  • Secondary Indexing: Auto-maintained indexes for fast lookups on non-primary columns.
• Concurrency (MVCC):
  • Multiversion Concurrency Control guarantees safe, lock-free parallel transactions.
  • Optimistic Conflict Detection aborts colliding writes while preserving read consistency.
• Query Engine:
  • Custom Lexer and Recursive Descent Parser to generate an Abstract Syntax Tree (AST).
  • Streaming Iterator pipeline to process queries with minimal memory footprint.
• Interactive REPL:
  • A command-line shell to execute raw SQL directly against the engine.

Getting Started

Prerequisites

• Go 1.20+ (developed on v1.26.4)

Run the Interactive Shell

Start the database engine and jump into the interactive REPL:

go run .

You will see the db> prompt, where you can type raw SQL commands. Your data is persisted locally in testdb.kv.

Example Usage

Welcome to the GopherSQL Interactive SQL Shell!
Type your SQL queries below. Type 'exit' or 'quit' to close.

db> CREATE TABLE employees (id INT64, name BYTES, age INT64, INDEX(id))
Success.

db> INSERT INTO employees (id, name, age) VALUES (1, 'Alice', 30)
Success.

db> INSERT INTO employees (id, name, age) VALUES (2, 'Bob', 25)
Success.

db> SELECT id, name, age FROM employees FILTER age > 20
id: 1 | name: Alice | age: 30
id: 2 | name: Bob | age: 25
(2 rows)

db> exit

Supported SQL Syntax

The custom parser currently supports a specialized subset of SQL:

• CREATE TABLE <name> (<col_name> <TYPE>, ..., INDEX(<col_name>))
• INSERT INTO <name> (<col_name>, ...) VALUES (<expr>, ...)
• SELECT <expr>, ... FROM <name> FILTER <condition>

Supported Types:

• INT64 (64-bit signed integer)
• BYTES (Strings / byte arrays)

Supported Expressions:

• Math: +, -, *, /
• Logic: AND, OR, NOT
• Comparisons: >, <, >=, <=, ==, !=

Architecture Overview

If you're curious about how this database works under the hood, the project is structured in logical layers:

1. Physical Storage (bnode.go, freelist.go): Raw byte manipulation, 4KB page chunking, B-Tree splitting/merging, and abandoned page recycling.
2. Transaction Management (kv.go): Memory mapping, flushing mmap chunks to disk, snapshot isolation, and conflict detection (MVCC).
3. Relational Abstraction (table.go, db.go): Order-preserving serialization (packing strings and integers into bytes while retaining alphabetical/numerical sorting), secondary index routing.
4. Query Execution (parser.go, execute.go, iterator.go, scanner.go): Tokenizing raw SQL strings into an AST, traversing the B-Tree efficiently, and streaming results through filter/select iterators.

---

References

This project was heavily inspired by and references the following excellent resources:

Book	Cover
Build Your Own Database From Scratch in Go by James Smith
Database Internals: A Deep-Dive into How Distributed Data Systems Work by Alex Petrov

---

Built from scratch as an exploration into database engine internals.