Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser

What will I learn?

Why an index you drive by calling insert and search from Zig is a library, not a database, and what the missing piece is: a language a human can actually type;
How to design a tiny SQL dialect -- CREATE TABLE, INSERT, SELECT ... WHERE -- small enough to build in one episode, real enough to feel like SQL;
Writing a lexer that turns raw characters into a clean stream of tokens, reusing the exact tokenizer discipline from the Markdown project in episodes 37-39 and the search-engine query parser in episode 127;
Case-insensitive keyword recognition, and why every SQL keyword is matched without regard to case;
Modeling statements as a tagged-union AST -- one variant per statement kind -- so the type system makes a malformed tree unrepresentable;
Recursive descent parsing: one small function per grammar rule, each consuming exactly the tokens it expects and handing back a node;
Turning parse failures into typed Zig errors (error.UnexpectedToken) instead of crashes or silently wrong answers;
Wiring the parsed statement into the B-tree engine from episodes 128 and 129, so a single line of text becomes an insert or a lookup on real pages.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
The Pager from episode 128 and the on-disk BTree from episode 129 fresh in mind -- today we put a query language on top of exactly those two modules;
The tokenizer and recursive-descent parser from the Markdown-to-HTML project (episodes 37 and 38) and the search-engine query parser (episode 127), because we reuse that same shape here;
Tagged unions from episode 6 and Zig's error handling from episode 4;
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser

Two episodes ago we built the floor of a database -- a Pager that turns a flat file into a durable array of 4096-byte pages. Last episode we built the thing that turns that heap of pages into an actual index: a B-tree whose every node is a page, that finds any key in three or four page reads and keeps its keys in sorted order. It persisted, it reopened, it survived two hundred reversed inserts without unbalancing. And I ended by saying the honest thing again: an index you drive by calling insert and search from Zig is a library, not a database. A database is something a human asks questions of, in a language.

That language is the missing brick, and it is the one we lay today. We are going to take a line of text like SELECT value FROM kv WHERE key = 42 and turn it into a small typed structure the engine can execute against the B-tree from last episode. The lovely part is that we already know how to do this -- we have built exactly this shape twice before in the series. We wrote a tokenizer and a recursive-descent parser for Markdown back in episodes 37 and 38, and we did it again for the search engine's query language in episode 127. A SQL parser is that same pattern pointed at a new grammar. Nothing here is magic; it is the most well-trodden path in all of computer science, and by the end you will have walked it a third time and it will feel like an old friend. Let's dive right in!

The grammar we are building

Real SQL is enormous -- the standard runs to thousands of pages and no two databases implement quite the same dialect. We are not building that. We are building the smallest slice of SQL that still feels like SQL and still exercises every idea a bigger parser would need. Our engine stores u64 keys mapped to u64 values, so our dialect speaks in exactly those terms. Three statements, that is the whole language:

CREATE TABLE kv;
INSERT INTO kv VALUES (42, 4200);
SELECT value FROM kv WHERE key = 42;

That is it. A CREATE TABLE that names a table, an INSERT that drops a key/value pair in, and a SELECT ... WHERE key = N that looks one up. It is a toy, but it is a representative toy -- keywords, identifiers, integer literals, punctuation, and a bit of nesting inside those parentheses. If you can parse this cleanly you can parse a much bigger dialect by adding more of the same, and never anything structurally new. Notice too that the shape maps one-to-one onto what the B-tree already does: INSERT becomes tree.insert, SELECT becomes tree.search. The parser's whole job is to bridge the gap between the string a person types and those two function calls.

Parsing splits cleanly into two stages, and keeping them separate is half the battle. First a lexer (or tokenizer) chews the raw characters into a stream of tokens -- the word SELECT, the symbol (, the number 42 -- throwing away whitespace and grouping characters into meaningful chunks. Then a parser consumes that token stream and builds a tree that captures the structure. Trying to do both at once, reading characters and reasoning about grammar in one tangled loop, is how you write a parser you cannot maintain. Two stages, two concerns.

The lexer: characters into tokens

A token is a tiny value: what kind of thing it is, plus the slice of source text it came from. We enumerate every kind our grammar can produce -- one variant per keyword, plus identifiers, numbers, the handful of punctuation symbols, and a special eof marker so the parser always has something to look at even at the end of input:

const std = @import("std");

const TokenKind = enum {
    kw_create, kw_table, kw_insert, kw_into, kw_values,
    kw_select, kw_from, kw_where,
    identifier, number,
    lparen, rparen, comma, semicolon, star, eq,
    eof,
};

const Token = struct {
    kind: TokenKind,
    text: []const u8, // a slice pointing straight into the source string
};

The text field is a slice into the original source, not a copy -- exactly the borrowing discipline from episode 5. The lexer allocates nothing; every token just remembers where in the input string it lives. That means the source string has to outlive the tokens, which for a single query parsed in one go is trivially true. No allocator, no frees, no lifetime headaches -- the input owns the bytes and the tokens borrow them.

Now the lexer itself. It holds the source and a cursor position, and its one real method, next, produces the token starting at the cursor and advances past it. The logic is a small ladder of cases: skip whitespace, check for end of input, then dispatch on the first character -- punctuation is a single-character token, a digit starts a number, a letter starts a word:

const Lexer = struct {
    src: []const u8,
    pos: usize = 0,

    fn isIdentChar(c: u8) bool {
        return std.ascii.isAlphanumeric(c) or c == '_';
    }

    fn next(self: *Lexer) !Token {
        while (self.pos < self.src.len and std.ascii.isWhitespace(self.src[self.pos])) : (self.pos += 1) {}
        if (self.pos >= self.src.len) return Token{ .kind = .eof, .text = "" };

        const c = self.src[self.pos];
        const single: ?TokenKind = switch (c) {
            '(' => .lparen,
            ')' => .rparen,
            ',' => .comma,
            ';' => .semicolon,
            '*' => .star,
            '=' => .eq,
            else => null,
        };
        if (single) |kind| {
            const t = Token{ .kind = kind, .text = self.src[self.pos .. self.pos + 1] };
            self.pos += 1;
            return t;
        }

        if (std.ascii.isDigit(c)) {
            const start = self.pos;
            while (self.pos < self.src.len and std.ascii.isDigit(self.src[self.pos])) : (self.pos += 1) {}
            return Token{ .kind = .number, .text = self.src[start..self.pos] };
        }

        if (std.ascii.isAlphabetic(c) or c == '_') {
            const start = self.pos;
            while (self.pos < self.src.len and isIdentChar(self.src[self.pos])) : (self.pos += 1) {}
            const word = self.src[start..self.pos];
            return Token{ .kind = keywordKind(word), .text = word };
        }

        return error.UnexpectedChar;
    }
};

Read the number and word branches side by side and you see the same maximal munch idea we used for the Markdown lexer: mark the start, walk forward as long as the character still belongs to this token, and slice from start to the new position. A number runs as far as the digits go; a word runs as far as the letters, digits and underscores go. Anything the ladder does not recognise -- a stray @ or # -- falls through to error.UnexpectedChar, a typed failure the caller must handle rather than a silent mystery. That is the episode-4 error philosophy showing up at the very first stage: the lexer cannot produce a garbage token, it produces a token or an error, and the type system makes you deal with the difference.

Recognising keywords without regard to case

There is one subtlety hiding in that last branch. When the lexer reads a word, it does not yet know whether that word is a keyword like SELECT or an ordinary identifier like a table name. Both look identical to the character-scanning loop -- letters and digits. The distinction is a dictionary lookup: if the word matches one of our reserved words, it is that keyword; otherwise it is an identifier. And crucially, SQL keywords are case-insensitive -- SELECT, select and SeLeCt are the same token -- while identifiers generally are not. So the lookup compares case-insensitively:

fn keywordKind(word: []const u8) TokenKind {
    const keywords = [_]struct { text: []const u8, kind: TokenKind }{
        .{ .text = "create", .kind = .kw_create },
        .{ .text = "table", .kind = .kw_table },
        .{ .text = "insert", .kind = .kw_insert },
        .{ .text = "into", .kind = .kw_into },
        .{ .text = "values", .kind = .kw_values },
        .{ .text = "select", .kind = .kw_select },
        .{ .text = "from", .kind = .kw_from },
        .{ .text = "where", .kind = .kw_where },
    };
    for (keywords) |kw| {
        if (std.ascii.eqlIgnoreCase(word, kw.text)) return kw.kind;
    }
    return .identifier;
}

std.ascii.eqlIgnoreCase does the case-folded comparison for us, so WHERE and where both land on .kw_where. Any word that matches nothing in the table is returned as .identifier -- the default that lets table names and column names through. This linear scan over eight keywords is perfectly fine; a real engine with a hundred-plus reserved words would reach for a perfect hash or a sorted binary search (episode 117 again), but for eight entries a straight loop is faster than the machinery you would build to avoid it. Premature cleverness here buys nothing.

Before we build the parser on top, let me prove the lexer actually chops a real statement into the right pieces. A test is worth more than my say-so -- I feed it a SELECT and check the exact sequence of kinds it hands back, ending in eof:

test "lexer splits a statement into tokens" {
    var lx = Lexer{ .src = "SELECT * FROM kv WHERE key = 42;" };
    const expected = [_]TokenKind{
        .kw_select, .star,       .kw_from, .identifier, .kw_where,
        .identifier, .eq,        .number,  .semicolon,  .eof,
    };
    for (expected) |kind| {
        const tok = try lx.next();
        try std.testing.expectEqual(kind, tok.kind);
    }
}

Ten tokens, in order, exactly as the grammar reads them: keyword, star, keyword, identifier (kv), keyword, identifier (key), equals, number (42), semicolon, and the sentinel eof. The lexer works. Now we can forget about characters entirely and think purely in tokens -- which is precisely the simplification the two-stage split bought us.

The AST: one variant per statement

Before writing the parser I want the target it is aiming at -- the abstract syntax tree, the typed structure a successful parse produces. Our grammar has three statement kinds, so the natural home is a tagged union with three variants, the exact tool from episode 6 and the state machine of episode 33. Each variant carries just the data that statement needs:

const Insert = struct {
    table: []const u8,
    key: u64,
    value: u64,
};

const Select = struct {
    table: []const u8,
    key: u64, // the N in WHERE key = N
};

const Statement = union(enum) {
    create_table: []const u8, // the table name
    insert: Insert,
    select: Select,
};

This is where Zig's type system earns its keep, and it is worth dwelling on for a second. A Statement is either a create_table carrying a name, or an insert carrying a table plus a key/value, or a select carrying a table plus a lookup key. It can never be two of those at once, and it can never be a fourth thing we forgot to define. When the executor later switches on it, the compiler forces a branch for every variant -- forget one and the code will not compile. Compare that to the classic C approach of a struct with a type integer and a union of payloads, where nothing stops you reading the insert fields of a select node and getting garbage. Here the malformed tree is not a bug you have to test for; it is a state the type system refuses to represent. The parser's job is now sharply defined: consume tokens, and hand back one of these three, or fail.

The parser core: look, expect, advance

Recursive descent is the friendliest parsing technique there is, and its whole engine is three tiny helpers. The parser holds the lexer and one token of lookahead -- the current token, the one we are about to decide on. advance pulls the next token from the lexer into cur. expect is the workhorse: it checks that cur is the kind we require, consumes it, and returns it -- or fails with error.UnexpectedToken if the input does not match the grammar. Here is the core:

const ParseError = error{ UnexpectedToken, InvalidNumber };

const Parser = struct {
    lexer: Lexer,
    cur: Token,

    fn init(src: []const u8) !Parser {
        var lx = Lexer{ .src = src };
        const first = try lx.next();
        return .{ .lexer = lx, .cur = first };
    }

    fn advance(self: *Parser) !void {
        self.cur = try self.lexer.next();
    }

    fn expect(self: *Parser, kind: TokenKind) !Token {
        if (self.cur.kind != kind) return error.UnexpectedToken;
        const t = self.cur;
        try self.advance();
        return t;
    }

    fn number(self: *Parser) !u64 {
        const t = try self.expect(.number);
        return std.fmt.parseInt(u64, t.text, 10) catch return error.InvalidNumber;
    }
};

init primes the pump by lexing the first token, so cur is always valid from the start -- there is never a moment where the parser has no current token to inspect. number is a small convenience: it demands a number token and then converts its text to an actual u64 with std.fmt.parseInt, folding an overflow (a number too big for 64 bits) into a clean error.InvalidNumber in stead of letting the raw parse error leak out. Everything the parser does is built from these three: look at cur, expect a specific kind, or advance past it. That is the entire mechanism. No tables, no generated code, no framework -- just functions calling functions.

One function per grammar rule

Here is the trick that gives recursive descent its name and its charm: you write one function per grammar rule, and each function reads almost exactly like the rule it implements. The top-level rule is "a statement is a CREATE, an INSERT, or a SELECT", so the dispatcher just peeks at the current token and routes to the matching sub-parser:

    fn statement(self: *Parser) !Statement {
        return switch (self.cur.kind) {
            .kw_create => self.parseCreate(),
            .kw_insert => self.parseInsert(),
            .kw_select => self.parseSelect(),
            else => error.UnexpectedToken,
        };
    }

    fn parseCreate(self: *Parser) !Statement {
        try self.advance(); // consume CREATE
        _ = try self.expect(.kw_table);
        const name = try self.expect(.identifier);
        return Statement{ .create_table = name.text };
    }

    fn parseInsert(self: *Parser) !Statement {
        try self.advance(); // consume INSERT
        _ = try self.expect(.kw_into);
        const name = try self.expect(.identifier);
        _ = try self.expect(.kw_values);
        _ = try self.expect(.lparen);
        const k = try self.number();
        _ = try self.expect(.comma);
        const v = try self.number();
        _ = try self.expect(.rparen);
        return Statement{ .insert = .{ .table = name.text, .key = k, .value = v } };
    }

Read parseInsert out loud and it is the grammar: after INSERT you expect INTO, then a name, then VALUES, then an open paren, a number, a comma, another number, a close paren. Each expect either consumes the required token or bails with a typed error, and because every one is guarded with try, the very first thing that does not match aborts the whole parse and propagates the error straight up to the caller. There is no "recover and guess" -- for a query language, the right response to a malformed statement is to reject it, not to soldier on and do something the user never asked for. The _ = try ... on the tokens we do not need to keep is Zig making us acknowledge that we are deliberately discarding those return values; the keyword VALUES matters for matching but carries no data we store.

SELECT is the richest rule, and it shows off a small choice point. After the keyword we accept either a * or a column name (we do not actually use which one -- our engine only ever returns the value column -- but a parser should accept the syntax people will naturally write), then FROM, a table name, WHERE, the key column, an =, and the lookup number:

    fn parseSelect(self: *Parser) !Statement {
        try self.advance(); // consume SELECT
        if (self.cur.kind == .star) {
            try self.advance(); // SELECT *
        } else {
            _ = try self.expect(.identifier); // SELECT value
        }
        _ = try self.expect(.kw_from);
        const name = try self.expect(.identifier);
        _ = try self.expect(.kw_where);
        _ = try self.expect(.identifier); // the column, e.g. key
        _ = try self.expect(.eq);
        const k = try self.number();
        return Statement{ .select = .{ .table = name.text, .key = k } };
    }

That if on .star is the parser making a genuine grammatical choice based on lookahead -- the one token of foresight is enough to decide which branch of the rule we are in. This is exactly why one-token lookahead recursive descent handles such a wide swath of real languages: most grammar decisions really can be made by glancing at the next token. When they cannot, you reach for more lookahead or a different technique, but you would be surprised how rarely a hand-written parser needs to.

Finally a top-level parse that ties it off: build a parser, read one statement, swallow an optional trailing semicolon, and insist that nothing but end-of-input follows. That last check is what catches trailing garbage -- SELECT ... FROM kv rubbish should be an error, not a half-accepted statement:

fn parse(src: []const u8) !Statement {
    var p = try Parser.init(src);
    const stmt = try p.statement();
    if (p.cur.kind == .semicolon) try p.advance();
    if (p.cur.kind != .eof) return error.UnexpectedToken;
    return stmt;
}

Proving the parser builds the right trees

Now the satisfying part -- watching text become structure. Because a Statement is a tagged union, a test switches on it to reach inside the variant it expects, and any other variant is an immediate failure. Here I parse an INSERT and a SELECT and check that every field landed where it should:

test "parse INSERT builds an Insert node" {
    const stmt = try parse("INSERT INTO kv VALUES (42, 4200);");
    switch (stmt) {
        .insert => |ins| {
            try std.testing.expectEqualStrings("kv", ins.table);
            try std.testing.expectEqual(@as(u64, 42), ins.key);
            try std.testing.expectEqual(@as(u64, 4200), ins.value);
        },
        else => return error.TestUnexpectedResult,
    }
}

test "parse SELECT builds a Select node" {
    const stmt = try parse("select value from kv where key = 7");
    switch (stmt) {
        .select => |sel| {
            try std.testing.expectEqualStrings("kv", sel.table);
            try std.testing.expectEqual(@as(u64, 7), sel.key);
        },
        else => return error.TestUnexpectedResult,
    }
}

Note the second test is written in all lowercase on purpose -- it proves the case-insensitive keyword matching from the lexer really works end to end, select and where recognised just as SELECT and WHERE would be. Both tests reach into the union with a switch, pull out the payload, and check the fields. This is the payoff of modeling the AST as a tagged union: the test cannot accidentally read a Select as an Insert, because the switch forces you to name which variant you are unpacking, and the compiler carries the payload type through for you.

Just as important is proving that bad input fails cleanly -- a parser that crashes on malformed SQL is worse than useless, it is a denial-of-service waiting to happen. Here a statement missing its opening parenthesis produces a typed error, caught and asserted with expectError, no crash anywhere in sight:

test "a malformed statement is a typed error, not a crash" {
    try std.testing.expectError(error.UnexpectedToken, parse("INSERT INTO kv VALUES 42, 4200)"));
    try std.testing.expectError(error.UnexpectedToken, parse("SELECT value FROM"));
}

The first case dies at the missing ( -- expect(.lparen) sees a number and returns error.UnexpectedToken. The second runs off the end of the input: after FROM the parser expects a table name but next hands back eof, whose kind is not .identifier, so expect fails the same clean way. That is the whole point of routing failures through the error system rather than assertions or sentinel values -- every malformed input, whether it is the wrong token or no token at all, funnels into the same handled, typed, non-crashing path. The caller gets an error it can report to the user and carry on serving the next query.

Wiring the parser into the engine

A parsed statement is inert until something runs it, and running it is almost anticlimactic -- which is exactly how it should feel, because all the hard machinery already exists in last episode's BTree. An executor is a switch over the statement that turns each variant into the calls we already wrote. Here it is, driving the very same on-disk B-tree from episode 129:

// `BTree` is the on-disk B-tree from episode 129, driving the episode-128 pager.
fn execute(tree: *BTree, stmt: Statement) !?u64 {
    switch (stmt) {
        .create_table => return null, // one implicit table in this toy: nothing to build
        .insert => |ins| {
            try tree.insert(ins.key, ins.value);
            return null;
        },
        .select => |sel| {
            return try tree.search(sel.key);
        },
    }
}

Look at how thin this is. INSERT becomes tree.insert, SELECT becomes tree.search, and CREATE TABLE does nothing at all because our toy has exactly one implicit table (a real engine would allocate a fresh root page here and record the table's name and root id in a catalog). The parser did the genuinely fiddly work -- validating the syntax, extracting the numbers, rejecting nonsense -- so that by the time a Statement reaches execute, every field is known-good and typed, and the executor is a three-line dispatch. That separation is the reason the design scales: you could bolt a DELETE onto this by adding one union variant, one parse function, and one switch arm, and never touch the lexer or the B-tree. Point this at the file from the last two episodes, feed it INSERT INTO kv VALUES (42, 4200) followed by SELECT value FROM kv WHERE key = 42, and you get 4200 back -- from a real page on a real disk, fetched through a real index, requested in something that genuinely reads like SQL. That is a database.

How C, Rust, and Go do it

The pattern you just wrote is not a teaching simplification of how real databases parse SQL -- it is how many of them parse SQL, at a bigger scale. SQLite hand-writes its tokenizer in C and generates its parser with a tool called Lemon (a cousin of yacc that ships in the SQLite tree), producing a table-driven state machine instead of our recursive functions -- but the two stages, characters-to-tokens then tokens-to-tree, are exactly ours. Its AST is a C struct Expr tree with a type tag, the untyped-union approach our tagged union improves on. Postgres takes the classic academic route: a flex lexer and a bison grammar (the gram.y file), which is a couple thousand lines of rules that compile to a parser producing a tree of Node structs. Same shape, generated rather than written by hand, because full SQL has hundreds of rules and maintaining that by hand would be a second job.

The hand-written camp is alive and well too. In Rust, the widely-used sqlparser-rs crate is a recursive-descent parser almost line-for-line the technique in this episode -- a Tokenizer, a Parser with a next_token, and one method per grammar production -- and its AST is a Rust enum, which is Rust's tagged union, the direct analogue of our Statement. In Go, the parser inside vitess (the sharded-MySQL layer behind a good chunk of the internet) is generated from a goyacc grammar, while plenty of smaller Go query engines hand-roll recursive descent because it is so approachable. Four ecosystems, two implementation styles -- generated table-driven versus hand-written recursive descent -- and both produce the same two-stage lex-then-parse pipeline into a typed tree. You picked the hand-written style, which is the one you can read, debug, and extend without a code generator in the loop, and for a dialect this size it is unambiguously the right call.

Zig's specific contribution is the one that has run through this whole mini-project: the failure modes are types, not conventions. An unrecognised character is error.UnexpectedChar, a grammar mismatch is error.UnexpectedToken, an oversized literal is error.InvalidNumber, and every one of them must be handled or explicitly propagated with try -- the compiler will not let a parse failure vanish into a forgotten return code the way it can in a C parser that returns -1 and hopes the caller checks. The AST is a real tagged union, so the executor's switch is exhaustive by force: add a statement kind and every place that consumes a Statement stops compiling until you handle the new case. And the tokens borrow the source with slices instead of copying, so the lexer is allocation-free and there is simply no token memory to leak. The parser is a place where C engines accumulate a long tail of subtle bugs -- unhandled edge cases, mismatched union access, use-after-free of token buffers -- and Zig turns most of that tail into compile errors.

Where this is heading

Step back and look at what these three episodes built. A file that is a durable array of pages. A balanced B-tree of those pages that finds a key in a few reads and keeps them sorted. And now a lexer and recursive-descent parser that turn a line of SQL into a typed statement the tree can execute -- INSERT to insert, SELECT to search, malformed input to a clean typed error rather than a crash. Wire the three together and you have the honest core of a database: storage, an index, and a language, each a module you understand top to bottom because you wrote every byte of it. That is not a cartoon of a database. It is a miniature of the real thing, sharing its architecture with SQLite, Postgres, redb and bbolt -- just with the constants turned down.

And here is the thing I want you to sit with. What we did today -- characters to tokens to a typed tree, one function per grammar rule -- is not a database technique at all. It is the technique, the one that turns any text a human writes into structure a machine can act on. It is how your shell reads a command line, how a config file becomes settings, how a compiler reads your source, how a template engine expands a page. We reached for it here to parse SQL, but the very same tokenizer-plus-recursive-descent skeleton parses arithmetic, a configuration format, or a small programming language of your own -- and once you can turn text into a tree, the natural next question is what you can do with that tree beyond looking one key up in a B-tree. Take the three modules from these episodes, point them at a file, and type real SQL at your own engine until it feels ordinary -- because the machinery underneath is now yours, and there is no better feeling in this craft than that. ;-)

Bedankt en tot de volgende keer! ;-)

@scipio

Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser

Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser

What will I learn?

Requirements

Difficulty

Curriculum (of the Learn Zig Series):

Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser

The grammar we are building

The lexer: characters into tokens

Recognising keywords without regard to case

The AST: one variant per statement

The parser core: look, expect, advance

One function per grammar rule

Proving the parser builds the right trees

Wiring the parser into the engine

How C, Rust, and Go do it

Where this is heading

Curriculum (of the `Learn Zig Series`):