SQL

A small SQL parser, handwritten on top of FE.

It lexes and parses a substantial subset of SQL into an arena-allocated AST, and can print that AST back out as SQL. The grammar spells out exactly which subset. Diagnostics carry precise path:row:col locations, and the parser recovers rather than giving up on the first error.

Just want to parse SQL in your own C++ project? Jump to Using It as a Library.

💡 Why?

This is a compact, readable example of a handwritten recursive-descent frontend:

• a UTF-8-aware lexer with a keyword table and one character of lookahead,
• a precedence-climbing expression parser with two tokens of lookahead,
• an arena-allocated AST that owns its nodes and streams itself back to SQL,
• a black-box test suite that holds the parser and the printer to each other.

It is deliberately small enough to read in one sitting.

🧭 Design: Parse Loosely, Check Later

SQL as standardized has a great many idiosyncrasies, and real-world SQL cheerfully ignores a good number of them. Rather than encoding every restriction in the grammar, this parser accepts a deliberately wider language and leaves the rest to a later check over the AST:

• Reserved words are accepted as identifiers. The standard reserves several hundred words, far more than any real dialect. SELECT ... AS character and FROM aka_title AS at both parse, as does a reference qualified by a reserved word, like at.movie_id. The exception is a name standing entirely on its own - a lone reference or a type name - where a reserved word would be indistinguishable from the clause it starts, so FROM "table" has to keep its quotes. The printer knows those three places and quotes there, and only there.
• Statements are expressions. Create, Select, Insert and friends all derive from Expr, so a subquery needs no separate node hierarchy. The grammar, though, keeps them apart: a statement is a schema, data, or transaction statement or a query expression, and a query expression starts with SELECT, VALUES, TABLE, WITH, or a parenthesis. 1 + 2; is a fine expression but no statement, and nothing can hang an ORDER BY off a CREATE TABLE.
• Grouping is not a node. Parentheses around a scalar expression are pure grouping and are dropped; around a query they are structural and are kept, because that is what makes it a subquery.
• Non-reserved words are recognized by Sym. LIMIT, CASCADE, NULLS, VIEW and the like lex as plain identifiers and only mean something in the one place that looks for them, so SELECT limit FROM view still parses as a query over a table. VALUE sits here too, against the standard, which reserves it: TPC-H Q11 names a column that, and so ORDER BY value has to work.

The upshot is that some things parse that a conforming implementation would reject. That is intentional: it keeps the grammar small, and a checking pass has the whole AST to work with.

The trailing ;, on the other hand, is not optional - <direct SQL statement> ends in one, and saying so gives a better diagnostic than running off the end of the file.

📜 Grammar

Every construct the parser accepts has a production in GRAMMAR.md, together with the precedence table that says how to read the ambiguous ones. It is the grammar this parser implements, not the standard's, which is both larger and stricter.

🚀 Building

If you have a GitHub account setup with SSH, just do this:

git clone --recurse-submodules git@github.com:leissa/sql.git

Otherwise, clone via HTTPS:

git clone --recurse-submodules https://github.com/leissa/sql.git

Then, build with:

cd sql
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j $(nproc)

For a Release build simply use -DCMAKE_BUILD_TYPE=Release.

This needs a C++23 compiler. Abseil and FE come along as submodules; nothing else is required.

To install the library, its headers, and its CMake package:

cmake --install build --prefix /usr/local

📦 Using It as a Library

Link sql::sql - via find_package against an install, or by pulling the repository into your build:

find_package(sql 0.1 REQUIRED)             # against `cmake --install`
# or: add_subdirectory(sql)                # as a submodule
# or: FetchContent_MakeAvailable(sql)      # straight from the repository

target_link_libraries(my_app PRIVATE sql::sql)

One header, one call:

#include <sql/sql.h>

auto res = sql::parse("SELECT a, b FROM t WHERE a > 42;");
if (!res) {
    res.report(std::cerr);       // `<input>:1:10: error: ...`, snippet and all
    return EXIT_FAILURE;
}

for (auto stmt : res.stmts())
    if (auto select = stmt->isa<sql::Select>())
        std::cout << select->elems().size() << " selected, " << select->froms().size() << " table refs\n";

std::cout << res << '\n';       // the AST, streamed back out as SQL

sql::parse_file(path) and sql::parse(std::istream&) read from a file or a stream instead; the former throws std::filesystem::filesystem_error if the file cannot be read. A complete program is in example/, and it builds on its own:

cmake -S example -B build-example -DCMAKE_PREFIX_PATH=/usr/local && cmake --build build-example

Lifetime

Every AST node is allocated in an arena and handed out as an AST<T> - a non-owning pointer. That arena belongs to the sql::Result, which is why the Result is what you keep: the whole AST dies with it, so returning an AST<T> from a function that let its Result go out of scope dangles. A Result moves freely, though, so returning it is fine.

Walking the AST

Statements are Exprs (see Design), and every node is an fe::RuntimeCast, so a dynamic check is isa and an assertion is as:

if (auto select = stmt->isa<sql::Select>()) /* ... */;   // nullptr if it is not a Select
auto& select = *stmt->as<sql::Select>();                 // asserts that it is

stream is virtual, so any node - not just a whole Prog - streams itself back out as SQL via operator<< or std::format.

Diagnostics

The parser recovers, so a Result with errors still carries an AST, just one with holes in it. res.errors() hands out the fe::Error::Msges themselves - each a Loc, a tag, the text, and its notes - while res.report(os) streams them the way the command-line tool does and returns how many errors there were. Nothing is printed unless you ask for it.

For finer control - a fe::Diag of your own, or parsing many inputs into a single arena - drop to sql::Driver and sql::Parser directly; sql::parse is a thin wrapper over exactly that, and res.driver() hands you the one it made.

🔧 Command-Line Tool

./build/bin/sql -d test/parse/select.sql   # parse and dump the AST back as SQL
./build/bin/sql --help                     # list all options
echo 'SELECT * FROM t;' | ./build/bin/sql -d -

Use - as the file to read from stdin. Diagnostics go to stderr and the exit status is non-zero if anything was rejected:

$ ./build/bin/sql test/error/missing_from.sql
test/error/missing_from.sql:1:10: error: expected 'FROM', got 't' while parsing SELECT expression
1 error(s) encountered

🛠️ Testing

The test suite is black box: every test runs the sql binary and inspects only its exit code, its dump, and its diagnostics. Nothing links against the parser.

ctest --test-dir build --output-on-failure

There are four kinds of test, one CTest entry per fixture:

Test	Fixtures	Asserts
parse/parse/<name>	test/parse/	Parses cleanly, and the dump matches the neighboring .out golden.
error/error/<name>	test/error/	Is rejected, with the diagnostics matching the neighboring .out golden.
reject/reject/<name>	test/reject/	Every query in the corpus, one per line, is rejected.
idempotent/...	test/parse/, test/job/, test/tpch/, test/hyrise/	Dumping a dump reproduces it verbatim.

That last one is the interesting one: it holds the printer and the parser to each other, since whatever the printer emits, the parser has to read back into the very same AST. It runs over the curated fixtures and over three real-world corpora that get no goldens of their own: test/job/, the Join Order Benchmark with its 113 queries plus their schema; test/tpch/, the 22 TPC-H queries; and test/hyrise/, the SQL the hyrise database itself runs - the 366 queries of its SQLiteTestRunner, the Star Schema Benchmark, and the TPC-H and TPC-DS schemas with their indexes.

The corpora under test/tpch/, test/reject/, and test/parse/hyrise.sql come from hyrise/sql-parser, the parser hyrise vendors, and the ones under test/hyrise/ from hyrise itself; each file says in its header what was adapted and what was left out.

To run a single test, or one group:

ctest --test-dir build -R '^parse/parse/expr$' --output-on-failure
ctest --test-dir build -R '^idempotent/job/' --output-on-failure

Benchmarking

test/bench/ times the parser over a corpus of .sql files. It is no CTest entry - a benchmark is not a pass/fail test - so build it on demand:

cmake --build build --target bench
./build/bin/bench test/job/*.sql            # a Driver and a Parser per file
./build/bin/bench --once test/job/*.sql     # the whole corpus through a single Parser
./build/bin/bench --lex test/job/*.sql      # lexing alone, with nothing built on top

The fixtures are small - a few hundred bytes each - so a run over them measures the per-statement overheads more than anything else. For a corpus where the arena, the SymPool, and the lexer's buffers get to amortize, generate one:

test/bench/gen.py --mb 64 -o /tmp/big.sql   # names out of the JOB and TPC-H vocabulary, reused
test/bench/gen.py --mb 64 --stress-names -o /tmp/big.sql   # every identifier distinct instead
./build/bin/bench --once /tmp/big.sql

The first two modes answer different questions. --each is what an embedding that parses one query at a time pays, setup included; --once pays the setup once and leaves parsing throughput. What is left between them is registering each source and constructing a Parser - both O(1), since the few hundred reserved and non-reserved words are interned once per Driver rather than once per Parser.

Against hyrise/sql-parser

hyrise/sql-parser makes a fair yardstick: a bison/flex parser of comparable scope, and the source of several of the corpora above. Both built Release with the same compiler and pinned to one 5.15 GHz Zen 5 core of a Ryzen AI 9 HX PRO 370, the machine otherwise idle. The wall clock is the best of five in-process timings over a corpus read up front, so no file system is in it; perf stat -e instructions gives the figure that does not drift between runs, normalized per input byte so that it does not depend on an iteration count either. On every corpus below both parsers accept every file and report the same number of statements, so they really are handed the same work.

• Throughput is more is better.
• Instructions per byte is fewer is better.
• The winner of each pair is in bold.

Corpus	Mode	Throughput (MB/s)		Instructions / byte
		Ours	Hyrise	Ours	Hyrise
JOB, 113 queries	--each	116.6	66.6	132.5	253.1
JOB	--once	183.2	74.3	105.4	255.5
TPC-H, 22 queries	--each	94.6	71.6	144.4	209.2
TPC-H	--once	165.5	82.7	107.6	214.4
generated, 32 MiB	--once	120.9	46.3	125.1	257.6
generated, 256 MiB	--once	116.4	41.5	140.8	259.4
generated, 32 MiB, --stress-names	--once	109.8	66.1	99.4	173.3

Lexing alone, against their flex scanner: 341.9 MB/s to 176.9 on JOB, and 228.9 to 136.8 on the 32 MiB corpus. That lead is won on instructions per cycle rather than on instruction count - their scanner retires a comparable number of instructions per byte, in fact fewer on three of the five corpora, yet wherever this one leads it does so at an IPC of 3.4 to 4.6 against their 2.5 to 3.2, a flex table walk being a chain of dependent loads the machine cannot run ahead of.

Peak resident set size - the RAM a process has actually touched, at its high-water mark - over 500k times SELECT a FROM t; is 127 MiB against their 285, or 267 bytes per statement to their 598. That is the number to watch for an embedding, because the AST is the output and is held for as long as the caller needs it.

Three things worth reading off that table. Throughput does not fall off as the corpus grows, because the per-statement footprint is small enough that the working set does not grow with it either. The margin is narrowest in --each, where registering each source and hashing its path is a larger share of the work than parsing - that, rather than anything in the parser, is what the two modes still differ by. And --stress-names is the worst case a design built on interning can be handed: with no name ever reused, lexing ties exactly - 162.7 MB/s to 164.0 - and parsing falls from a 2.6x lead to a 1.7x one over the same corpus with its names reused.

The two do not do quite the same work per byte, in both directions: their scanner recognizes keywords inside the DFA, where this one interns and looks up every word, but it is also byte-oriented and never decodes UTF-8, where this one decodes and validates every code point.

After deliberately changing what the parser accepts or how it prints, regenerate the goldens and review the resulting diff:

cmake --build build --target bless

🤝 Coding Style

Use the following coding conventions:

• class/type names in CamelCase
• constants as defined in an enum or via static const in Camel_Snake_Case
• macro names in SNAKE_IN_ALL_CAPS
• everything else like variables, functions, etc. in snake_case
• use a trailing underscore suffix for a private_or_protected_member_variable_
• don't do that for a public_member_variable
• use struct for plain old data
• use class for everything else
• visibility groups in this order:
  1. public
  2. protected
  3. private
• prefer // C++-style comments over /* C-style comments */
• use /// three slashes for Doxygen and group your methods into logical units if possible
• use Markdown-style Doxygen comments
• methods/functions that return a bool should be prefixed with is_
• methods/functions that return a std::optional or a pointer that may be nullptr should be prefixed with isa_

For all the other minute details like indentation width etc. use clang-format and the provided .clang-format file in the root of the repository. The format workflow checks this on every push:

clang-format --dry-run --Werror $(git ls-files '*.cpp' '*.h')

In order to run clang-format automatically on all changed files, switch to the provided pre-commit hook:

git config --local core.hooksPath .githooks/

Note that you can disable clang-format for a piece of code. In addition, you might want to check out plugins like the Vim integration.

⚖️ License

SQL is licensed under the MIT License.