STAGE 6 · THE SQL DECK

The Front Desk

Text in, tokens, an AST, a plan, and then your planner picks your index on your B-tree over your pages.

What you're wiring up

Everything below this line speaks pages and trees; humans speak SQL. The pipeline is small and honest: a tokenizer turns text into tokens, a recursive-descent parser turns tokens into an AST, and an executor walks the AST using Stage 5's typed operations. Correct first, fast later.

Then comes the one genuinely magic step: the planner. When a WHERE clause touches an indexed column, seek that index; otherwise scan the table. That decision is made silently a billion times a day in every database on earth, and here is where you watch your own query get a hundred times faster because your planner chose your index.

The dialect stays small: CREATE TABLE, INSERT, SELECT with WHERE, ORDER BY and LIMIT, DELETE WHERE, CREATE INDEX. No joins. A nested-loop join is less code than you think, and by the end of this stage you will be able to point at exactly where it would go.

> EXPLAIN SELECT * FROM users WHERE name = 'ada';
plan: full-scan users

> CREATE INDEX ON users(name);
> EXPLAIN SELECT * FROM users WHERE name = 'ada';
plan: index-seek users.name

Assembly steps

[ 01 ]

Write the tokenizer: case-insensitive keywords, identifiers, integer and string literals, operators, and -- comments. It is about forty lines of switch.

hint

Carry a position on every token. An error like unexpected token ) at column 27 costs little now and is priceless while debugging the parser.

[ 02 ]

Write a recursive-descent parser producing the AST types the starter already defines: one function per grammar rule, comparisons binding tighter than AND.

hint

The starter ships a golden corpus of .sql files with their expected ASTs. Work through it file by file and let it drive you.

[ 03 ]

Build the executor for CREATE TABLE, INSERT, CREATE INDEX and a naive SELECT: full scan, filter each row against the WHERE AST, project the requested columns.

hint

Evaluate WHERE as a plain tree walk, eval(expr, row) returning a value. Resist compiling anything.

[ 04 ]

Add the planner: an equality or range on the primary key or an indexed column becomes a cursor seek, anything else stays a full scan. Then add ORDER BY (sorted in memory, free when you are already scanning that key) and a LIMIT that stops reading early.

hint

Make the choice observable: EXPLAIN prints one line naming the plan. The harness reads it, and so will your sense of triumph.

[ 05 ]

Ship the front desk: open a SQL REPL with aligned column output, support one-shot queries with -e, and make every error a clean one-liner rather than a stack trace.

hint

Pipe the harness's smoke.sql through -e yourself before running make check. It is the same script the final test replays.

Go deeper (after it passes)

The blueprint is solid ink: your planner, using your index, on your B-tree, over your pages, certified crash-safe. The tokenizer and parser you just wrote are the front half of build-your-own-interpreter, so take that track next and enjoy recognizing the machine. Then read DDIA on transactions to see which ACID letters you actually built and which ones need concurrency control you have not written yet.