sql-query-engine

A small but complete SQL query engine, written from scratch in Go.

Lexer → Parser → Planner → Volcano executor · hash join · aggregation · three-valued NULL logic · differential testing against SQLite

It lexes and parses a SELECT subset, plans it, and executes it with a volcano (pull-based) operator model including a real hash join. Tables are CSV files described by a small schema; you query them from a REPL.

What it is: a readable, tested implementation of how a query gets from text to rows — parsing, planning, and execution — with its results checked against SQLite on tens of thousands of generated queries.

What it is not: a database. There is no storage engine, no persistence, no transactions, no indexes, and no query optimizer. See Scope.

Why this project

The interesting part of a SQL engine is not the SELECT statement. It is turning SQL text into an executable plan, resolving every name and type before a row is read, preserving SQL's three-valued logic in the places it is counter-intuitive, and executing that plan without re-scanning an input per row.

Those are the parts this project is about. Each of them was a decision with alternatives, and the reasoning is written up in docs/design-notes.md rather than left in the commit log.

Features

Query language

• SELECT with expressions, WHERE, INNER JOIN, GROUP BY, HAVING, ORDER BY, LIMIT
• COUNT, SUM, AVG, MIN, MAX, including COUNT(*)

Execution

• Volcano execution model — every operator pulls rows from its child through Next(), so LIMIT stops the scan early without any operator knowing that LIMIT exists
• Hash join — INNER JOIN runs build/probe over a hash table rather than a nested loop, in one pass over each input

Correctness

• Three-valued NULL logic — comparisons involving NULL are unknown, and WHERE keeps only rows that are exactly true
• Plan-time name and type resolution — unknown columns, ambiguous references, and type mismatches are rejected before a single row is read
• Differential testing against SQLite — a seeded generator produces queries and both engines must agree

Quick start

go run ./cmd/minisql -data examples

The bundled examples/ directory holds this schema:

users(id INT, name TEXT, age INT, city TEXT)
orders(id INT, user_id INT, total INT)

backed by users.csv and orders.csv:

1,alice,30,berlin
2,bob,15,paris
3,carol,40,berlin
4,dan,,london

A session (output is verbatim):

minisql — one SQL statement per line (Ctrl-D to exit)
SELECT name, age FROM users WHERE age >= 18 ORDER BY age DESC
name  | age
------+----
carol | 40
alice | 30
(2 rows)

SELECT city, COUNT(id), AVG(age) FROM users GROUP BY city HAVING COUNT(id) > 1
city   | COUNT(id) | AVG(age)
-------+-----------+---------
berlin | 2         | 35
(1 row)

SELECT users.name, orders.total FROM users JOIN orders ON users.id = orders.user_id ORDER BY orders.total DESC
name  | total
------+------
alice | 300
carol | 250
alice | 100
(3 rows)

SELECT name, age FROM users WHERE age IS NULL
name | age
-----+-----
dan  | NULL
(1 row)

SELECT bogus FROM users
error: unknown column "bogus"

Note what the join left out: order 13 has an empty user_id, and a NULL key never matches, so it appears in no result row.

How it works

                         SQL text
                            │
                            ▼
                    ┌───────────────┐
                    │     Lexer     │  text → tokens
                    └───────┬───────┘
                            ▼
                    ┌───────────────┐
                    │    Parser     │  recursive descent
                    └───────┬───────┘  tokens → AST
                            ▼
                    ┌───────────────┐
                    │    Planner    │  resolve names to indexes,
                    └───────┬───────┘  check types against the catalog
                            ▼
                    ┌───────────────┐
                    │ Operator tree │  scan · filter · project · join
                    └───────┬───────┘  sort · limit · aggregate
                            ▼
                    ┌───────────────┐
                    │   Executor    │  volcano: each Next() pulls
                    └───────┬───────┘  from its child
                            ▼
                           Rows

1. Lexing turns SQL text into tokens.

2. Parsing is recursive descent, producing an AST that can render itself back to SQL — which is how a generated query gets a stable label.

3. Planning is where the engine earns most of its guarantees. The planner walks the AST and turns every column reference into an index into the row, checking types as it goes. An unknown column, a bare name that is ambiguous across two joined tables, or a comparison between text and a number all fail here, before the first row is read. Operators downstream index into a row rather than looking up names, so the hot path has no map lookups and no error handling for something the planner already proved cannot happen.

4. Execution is volcano: every operator exposes Next() and pulls rows from its children. Nothing is materialised that does not have to be, and LIMIT stopping early propagates back through the tree on its own — no operator is written to know that LIMIT is above it.

cmd/minisql/        entrypoint
internal/lexer/     tokenizer
internal/parser/    recursive-descent parser
internal/ast/       syntax tree and its rendering
internal/catalog/   table schemas
internal/csv/       schema-aware CSV reader
internal/plan/      AST → operator tree, name and type resolution
internal/exec/      operators (scan, filter, project, hash join, sort, limit, aggregate)
internal/value/     typed values and three-valued logic
internal/repl/      read-eval-print loop
internal/difftest/  test-only: SQLite oracle, query generator, differential runner

Hash join

A nested-loop join is four lines and O(n·m), with a full re-scan of one input per row of the other. This engine drains the right input once into a hash table, then streams the left input and probes it — one pass over each, O(n+m).

     build side                        probe side
  orders (right)                     users (left)
        │                                 │
        ▼                                 ▼
  ┌───────────┐                      hash the key
  │ hash table│◀─────── probe ───────────┘
  │ key → []  │
  └─────┬─────┘
        ▼
   joined rows

The price is memory: the whole build side is resident while probing, which is why the build side should be the smaller input — a choice a query optimizer would make and this engine does not, since it always builds from the right.

Two details the tests pin down: a key maps to a slice of rows, so duplicate keys emit every match rather than silently dropping rows; and NULL keys never match, dropped during build and skipped during probe. That second one is semantics, not an optimization — NULL = NULL is unknown, so a NULL key matches nothing, including another NULL.

SQL NULL semantics

NULL is not a value, it is the absence of one, so any comparison with it answers unknown rather than true or false:

NULL = NULL	unknown
NOT unknown	unknown
false AND unknown	false — nothing can rescue it
true AND unknown	unknown
WHERE keeps	only rows that are exactly true

The consequence that surprises people:

SELECT name FROM users WHERE age > 10;
SELECT name FROM users WHERE NOT (age > 10);

Both exclude dan, whose age is NULL. Between them they do not cover the table — which looks like a bug until you remember that neither statement is true when the age is unknown.

Then GROUP BY does the opposite: every NULL city lands in a single group, even though NULL = NULL is not true. SQL treats NULL as a value there and as an unknown everywhere else. The engine implements both, because both are correct about different things. internal/plan/null_test.go states all of it as executable specification.

Supported SQL

SELECT <* | expr [, expr ...]>
FROM <table>
[[INNER] JOIN <table> ON <column> = <column>]
[WHERE <condition>]
[GROUP BY <column> [HAVING <condition>]]
[ORDER BY <expr> [ASC | DESC] [, ...]]
[LIMIT <n>]

Expressions support column references (name, users.name), literals, = <> < <= > >=, + - * /, AND OR NOT, IS [NOT] NULL, and the aggregate functions COUNT, SUM, AVG, MIN, MAX (including COUNT(*)).

Feature
SELECT, expressions, WHERE	supported
INNER JOIN (hash join)	supported
GROUP BY, HAVING	supported
ORDER BY, LIMIT	supported
COUNT SUM AVG MIN MAX	supported
three-valued NULL logic	supported
DISTINCT	not supported
subqueries	not supported
OUTER / CROSS joins	not supported
window functions	not supported
DDL / DML	not supported

A projection that is not a bare column is labelled with its source expression, so SELECT COUNT(id) reports a column named COUNT(id).

Data format

A schema file declares one table per line as name(col TYPE, ...) with types INT, FLOAT, TEXT, or BOOL. Each table reads <name>.csv from the same directory. CSV files have no header row, and an empty field is NULL — which is how the examples above get a NULL age and a NULL join key.

examples/
├── schema.txt
├── users.csv
└── orders.csv

Verification

50,000 generated queries compared against SQLite with zero disagreements — ten seeds at 5,000 queries each, about 15,000 of them joins.

        seeded generator
               │
      ┌────────┴────────┐
      ▼                 ▼
  this engine         SQLite
      │                 │
      └────────┬────────┘
               ▼
      compare as multisets
       (order-insensitive,
        duplicate-sensitive)

go test -race ./...

Three layers:

• Golden tests per package — a query and fixture in, exact rows out.
• A NULL semantics suite (internal/plan/null_test.go) stating three-valued behaviour explicitly: unknown comparisons excluded by WHERE, NOT unknown still excluded, NULL join keys dropped, aggregates skipping NULLs, and GROUP BY collapsing NULL keys into one group.
• Differential tests against SQLite — a seeded generator emits queries from a bounded grammar, both engines run them over identical data, and the results must match as multisets.

Run a wider sweep or replay a specific run:

go test ./internal/difftest/ -run Differential -seed 31337 -queries 5000

Every failure prints the exact query and seed.

That the joins are ~30% of the sweep is asserted, not assumed: the runner fails if joins fall below one in twenty, because an earlier version of the generator only ever queried a single table, which left the hash join — the most intricate operator here — outside the oracle entirely.

Comparison ignores row order, because SQL leaves it unspecified without ORDER BY, but duplicate counts still have to match. ORDER BY correctness is covered by the deterministic golden tests instead.

modernc.org/sqlite is pure Go and is imported only by internal/difftest, which nothing outside its own tests imports, so the engine binary carries no SQLite driver:

go list -deps ./cmd/minisql | grep -c sqlite   # 0

SQLite compatibility

SQLite is used as a correctness oracle, but the engine deliberately defines a smaller and more explicit type system in a few places. These are design choices, not bugs, and the query generator avoids them so they cannot mask a real disagreement:

Area	SQLite	This engine
/ on two integers	integer division (5/2 = 2)	float division (2.5)
comparing a text column to a number	coerced dynamically	rejected at plan time
booleans	stored as integers 0/1	a distinct BOOL type

Scope

This is a query engine, not a database. Deliberately absent:

no storage engine        no subqueries
no persistence           no OUTER / CROSS joins
no transactions          no DISTINCT
no indexes               no window functions
no query optimizer       no DDL or DML

It reads CSV files and answers SELECT queries.

Possible future work

Cost-based optimization (choosing the smaller build side would be its first job), an index scan operator, additional join strategies, subqueries, DISTINCT and outer joins. All of these are out of scope for the current engine rather than half-finished in it.

Requirements

Go 1.25 or newer. The engine itself uses only the standard library; the SQLite driver used by the differential tests is what sets the Go version floor.

License

MIT. See LICENSE.