Build your own SQL database from scratch

SQL feels like magic because one short line of English-ish text turns into rows. Pull the magic apart and it is three ordinary pieces: something that reads the query, something that holds the data, and something that runs the query against the data. Build those three and SELECT stops being magic.

The one idea

A database engine is a pipeline: text becomes a plan, and a plan is executed against storage. Everything else, indexes, transactions, joins, is optimization and safety bolted onto that spine. We will build the spine.

Storage: a table is a list of dicts

Skip the disk for now. A table is rows, and a row is a mapping from column name to value.

class Table:
    def __init__(self, columns):
        self.columns = columns
        self.rows = []
    def insert(self, values):
        self.rows.append(dict(zip(self.columns, values)))

users = Table(["id", "name", "age"])
users.insert([1, "Ada", 36])
users.insert([2, "Alan", 41])
users.insert([3, "Grace", 44])

Parsing: text becomes a plan

We support one shape: SELECT cols FROM table WHERE col op value. A plan is just a dict describing intent. Parsing is reading tokens and filling that dict.

import re

def parse(sql):
    m = re.match(
        r"SELECT (.+) FROM (\w+)(?: WHERE (\w+)\s*(=|>|<)\s*(.+))?
quot;,
        sql.strip(), re.IGNORECASE)
    if not m:
        raise SyntaxError(f"cannot parse: {sql}")
    cols, table, wcol, wop, wval = m.groups()
    cols = [c.strip() for c in cols.split(",")]
    where = None
    if wcol:
        val = wval.strip().strip("'\"")
        val = int(val) if val.isdigit() else val
        where = (wcol, wop, val)
    return {"cols": cols, "table": table, "where": where}

A real parser tokenizes and builds a tree, but the job is identical: turn a string into a structure the engine can walk. Ours already handles the important part, a WHERE clause parsed into (column, operator, value).

Execution: run the plan against storage

The engine walks rows, keeps the ones that pass WHERE, then projects the requested columns.

OPS = {"=": lambda a, b: a == b,
       ">": lambda a, b: a > b,
       "<": lambda a, b: a < b}

def execute(plan, db):
    table = db[plan["table"]]
    rows = table.rows
    if plan["where"]:
        col, op, val = plan["where"]
        rows = [r for r in rows if OPS[op](r[col], val)]
    cols = table.columns if plan["cols"] == ["*"] else plan["cols"]
    return [{c: r[c] for c in cols} for r in rows]

def run(sql, db):
    return execute(parse(sql), db)

Prove it returns rows

db = {"users": users}
print(run("SELECT name, age FROM users WHERE age > 40", db))
print(run("SELECT * FROM users WHERE name = 'Ada'", db))

[{'name': 'Alan', 'age': 41}, {'name': 'Grace', 'age': 44}]
[{'id': 1, 'name': 'Ada', 'age': 36}]

Those are real query results. The filter, the projection, the comparison operators, all yours, in under fifty lines.

What the real thing adds (and why)

Our engine does a full scan for every query, which is why the next thing every database grows is an index: a sorted structure (usually a B-tree) so WHERE id = 2 jumps straight to the row instead of scanning all of them. Add persistence (write rows to a file and page them back in), a query planner that reorders operations to touch less data, joins that combine two tables, and transactions so half-finished writes never become visible, and you have Postgres in outline.

But none of that changes the spine you just built. When a query is slow, you now know the three places to look: the plan the parser produced, the amount of data storage had to touch, and the order the engine touched it in. That is the mental model the data engineering track is built on: databases are not magic, they are pipelines you can reason about.