Skip to main content
Back to the garden
·🌳 15 min · Deep dive

Building MuriukiDB from scratch

Why I wrote my own SQL lexer, recursive-descent parser, and B-Tree index instead of leaning on a library — and what I would do differently next time.

SystemsParsersDatabasesTypeScript

Why a relational database in 2026

Most full-stack engineers can wire up Postgres. Far fewer can explain the path from text to result — how a query string becomes a token stream, an AST, a validated execution plan, and finally a row set against an indexed store. I built MuriukiDB to prove I understood that path end to end, not just at a wave-of-the-hand level.

It was submitted to the Pesapal Junior Dev Challenge 2026 — as a job application, not a competition entry. (Important distinction: I want hiring teams to evaluate the engineering, not pattern-match on "competition winner.")

The pipeline

SQL string
  ↓
Lexer (token stream)
  ↓
Parser (AST)
  ↓
Validator (schema-aware)
  ↓
Executor (against the in-memory store + B-Tree index)
  ↓
Result rows

Every stage has its own test suite and can be exercised in isolation from the REPL. That separation paid for itself the first time I had a parser bug — I could feed bad input to the lexer alone, confirm tokens were right, then point the finger at parsing without rebuilding the whole pipeline in my head.

Lexer

A hand-written lexer that emits typed tokens: KEYWORD, IDENTIFIER, LITERAL_INT, LITERAL_TEXT, OPERATOR, PUNCTUATION. It tracks line and column for every token so parser errors report a useful location.

Decisions:

  • Whitespace is skipped, not emitted as a token. Some lexers preserve whitespace for round-trip formatting; this engine doesn't reformat SQL, so dropping it simplifies the parser.
  • String literals support single quotes only. Sticking to a single quoting convention removes a class of escaping bugs.
  • Keywords are case-insensitive on input, normalised to upper case in tokens. select, SELECT, and SeLeCt all parse identically.

Parser

Recursive descent, one function per grammar production. parseStatement() dispatches on the leading keyword to parseSelect(), parseInsert(), parseUpdate(), parseDelete(), parseCreateTable(). Each returns an AST node typed in TypeScript.

I picked recursive descent over a parser generator (PEG / yacc-style) precisely because it forces you to understand the grammar. A generator hides the most interesting part — how SELECT, WHERE, JOIN, and ORDER BY actually compose into a parse tree.

The trade-off: error messages are good (you can drop helpful diagnostics in any production), but the parser is bigger than a grammar file would be. I think that's the right trade for a portfolio piece.

B-Tree index

Hand-written B-Tree with node splits and rebalancing on insert. Supports range scans for indexed columns (WHERE id BETWEEN 100 AND 200). Keys are typed: INTEGER, TEXT, REAL, BOOLEAN, DATE.

Why B-Tree over a hash index?

Because hash gives you O(1) point lookups but breaks on range queries — the kind of query a portfolio reviewer is most likely to ask about. B-Trees keep keys ordered, which means WHERE id > 50 is a tree walk from key 50 forward, not a full scan.

REPL

Terminal-style input with syntax highlighting (the same lexer powers it), command history, and result tables that respect column type — INTEGER right-aligns, TEXT left-aligns, BOOLEAN displays as t/f. Small touches, but they're what make a database feel like a database instead of a JS toy.

Persistence and per-user state ride on Supabase, so saved tables survive across sessions; the engine itself is in-memory while the REPL is open.

What I'd do differently

The engine is in-memory only. No persistence across sessions. No ACID transactions. Last-write-wins concurrency. No nested SELECT subqueries. Limited type coverage (no DECIMAL, no JSON, no arrays).

A v2 should land WAL-style persistence and proper transaction semantics before adding more SQL surface area. Building parsers for new clauses is the cheap part; making them correct under crash recovery is the hard part. Better to push depth before breadth.

Why TypeScript instead of a systems language

The point was to demonstrate engineering depth, not maximum throughput. TypeScript meant the focus stayed on the algorithm and its tests — readers can audit the lexer in their browser. If I'd chosen Rust or C, half the questions would have been about my unsafe blocks instead of about how the parser disambiguates a SELECT statement.

There's a v2 in Rust on the someday-list. For now, the lesson MuriukiDB had to teach was about query execution, not about memory management.

The full source is on GitHub and the live REPL is at rdbms-muriuki.vercel.app. If you're a hiring team for a backend or systems role, the lexer + parser tests are the best place to start — they show how I think about ambiguity, edge cases, and error reporting.