DuckDB SQL

github.com/ornew/pego/parsers/duckdb parses the SQL dialect of DuckDB, as DuckDB 1.5.6 parses it: the statements of its grammar (a fork of PostgreSQL's) with the syntax that DuckDB adds (FROM-first queries, PIVOT, QUALIFY, ASOF joins, lambdas, list comprehensions, struct and map literals, COLUMNS(...), GROUP BY ALL, SELECT * EXCLUDE ..., COPY, ATTACH, secrets and the rest), and the scanner that goes with it. The parser is generated by PEGO from duckdb.pego. It depends only on the standard library, and not on DuckDB.

go get github.com/ornew/pego/parsers/duckdb

#Use

// The script as typed values, each node with its Span in the input.
script, err := duckdb.ParseAST(`SELECT region, sum(amount) AS total FROM sales WHERE year = 2024 GROUP BY region`)
sel := script.Statements[0].(*duckdb.Select)
core := sel.Body.(*duckdb.SelectCore)
for _, item := range core.Items {
	fmt.Println(item.Span.Start, item.Span.End) // 7 13, then 15 35
}

// The script as DuckDB cuts it: the statements, each with the text DuckDB keeps for it, and its type.
statements, err := duckdb.Split("CREATE TABLE t (a INT); INSERT INTO t VALUES (1), (2); FROM t")
for _, s := range statements {
	fmt.Println(duckdb.Kind(s.Statement), s.Text) // CREATE, INSERT, SELECT
}

// Visit the nodes in the order of the input.
duckdb.Walk(script, func(n any) bool {
	if t, ok := n.(*duckdb.BaseTable); ok {
		fmt.Println(strings.Join(t.Name.Names(), "."))
	}
	return true
})

// Only check.
err = duckdb.Recognize("SELECT 1 UNION")      // a *duckdb.SyntaxError with Line, Col, Pos

Positions are in code points by default; duckdb.ParseAST(src, duckdb.Bytes) counts bytes (Split uses bytes).

#The syntax tree

The types follow the grammar of DuckDB, without the details of how the Bison grammar is organized:

• Statements: Select (the query: With, Body, OrderBy, Limit, Offset, Locking; the body is a SelectCore, ValuesClause, TableQuery, PivotQuery, UnpivotQuery, SetOp or ParenQuery), InsertStmt, UpdateStmt, DeleteStmt, MergeStmt, CreateTableStmt, CreateTableAsStmt, CreateViewStmt, CreateIndexStmt, CreateSchemaStmt, CreateSequenceStmt, CreateTypeStmt, CreateMacroStmt, CreateSecretStmt, AlterTableStmt and the other ALTERs, DropStmt, CopyStmt, CopyDatabaseStmt, ExportStmt, ImportStmt, AttachStmt, DetachStmt, UseStmt, LoadStmt, PragmaStmt, SetStmt, ResetStmt, ShowStmt, ExplainStmt, PrepareStmt, ExecuteStmt, DeallocateStmt, TransactionStmt, VacuumStmt, AnalyzeStmt, CheckpointStmt, CallStmt, CommentStmt and UpdateExtensionsStmt.
• Expressions (the Expr union): literals, ColumnRef, Star with its EXCLUDE, REPLACE and RENAME, Binary, Unary, Not, IsExpr, Between, In, Like, AnyAll, Cast, Case, FuncCall (with FILTER, ORDER BY, WITHIN GROUP and OVER), SpecialCall (EXTRACT, SUBSTRING, TRIM, POSITION, ...), Lambda, ListLit, StructLit, MapLit, ListComp, Indirection (field access, subscripts and slices), Subquery, Exists, IntervalLit, TypedLit and the rest. Operators are Binary nodes whose Op is the text of the operator as the scanner cut it; the precedence is in the shape of the tree.
• Tables (TableRef): BaseTable, SubqueryRef, FuncTable, ValuesRef, Join, ParenTable, PivotRef, UnpivotRef, with their aliases, sampling and AT clauses.
• Types (Type): the name as written, the modifiers, the fields of STRUCT and UNION, the key and value of MAP and the array dimensions.

A rule that matches a keyword or a punctuation sign without building a node gives a Match, with the matched text; fields of a node that hold such text (Op, Kind, Quantifier) are strings.

#Names and literals

DuckDB keeps the case of an identifier and compares names without regard to the case of ASCII letters: compare Fold() of two identifiers, or use EqualFold. A name is an Ident whose Text is as written: a word, a quoted identifier, a U&"..." identifier, or a string where DuckDB accepts one as a name ('t' after AS, in COPY, ...). Which words are names where is decided by the category of the keyword, as DuckDB does: year and type name columns and functions, left and join name functions but not columns, select and from name nothing without quotes except after AS and after a dot.

The scanner is part of the grammar. It reads nested /* */ comments, -- comments, $$...$$ and $tag$...$tag$ strings, E'...', U&'...', B'...' and X'...' literals, N'...', numbers with _ between digits (1_000), the operators as PostgreSQL's scanner cuts them (the trailing + and - of an operator without a special character are not part of it), the parameters ?, ?1, $1 and $name, and the Unicode white space characters that DuckDB replaces by spaces.

#Conformance

The tests compare the parser with DuckDB 1.5.6 on 158,605 texts, all vendored in testdata/reference:

go test checks, for each text, what DuckDB's extract_statements says, and for each accepted text how it splits the script; for the SELECT statements of tests and exprs it also compares the AST (below). The numbers (go test -v -run 'TestReference'):

The parser and DuckDB agree on every text where DuckDB's parser itself finds a syntax error or none, but the thirteen known deviations (below). The third row counts the texts that DuckDB's parser rejects in the step after the Bison grammar, when it transforms the syntax tree into its own: the grammar cannot know. They are 1,575 texts, of which about 1,150 name a window that does not exist, 133 are an empty select list in a context the grammar accepts (cte2 AS (SELECT )), and the others are checks such as VALUES lists of different lengths (19), U&'...' and \u escapes, which DuckDB reads but does not implement (28), a type modifier that is not a constant (13), LIMIT or ORDER BY in a recursive query (16), PIVOT ON NULL (11), if() with another number of arguments than three (11), EXCLUDE or FILTER with a window function that does not allow them (19), a foreign key with CASCADE (6), generated columns added to a table (6), SELECT INTO (4), FOR UPDATE (4), duplicate names in a macro, a CTE or an EXCLUDE list, and about fifty more that occur once or twice.

For the statements of the scripts that DuckDB accepts, the number of statements, their types and their texts agree (Split and Kind): 44,949 scripts of tests (44,678 statements with the same text, and 523 scripts not compared because DuckDB expands a statement into several: PIVOT makes a CREATE TYPE first, COPY FROM DATABASE is four statements, and ALTER TABLE ... ADD COLUMN ... DEFAULT is five), 852 of lexical and 3,842 of mutants. The text DuckDB keeps for a statement is what lies between the semicolons that surround it, comments and white space included, and with the Unicode white space of the text replaced by spaces.

#The AST

For a SELECT statement, json_serialize_sql returns the AST that DuckDB's transformer builds. The tests contain a mapping (shape_*_test.go) that builds the same JSON from the syntax tree of this module, reduced to a canonical form (no locations; no key whose value is null, empty or false), and compare the two. It reproduces what the transformer does to the syntax: function names in lower case, count(*) as count_star, x IN (list) and x IN y, NOT turned into the opposite comparison, BETWEEN, LIKE as ~~, a ~ b as regexp_full_match, IF as CASE, windows with their frames and the named windows they refer to, the lambdas and list comprehensions as calls of list_apply and list_filter, intervals as to_days(CAST(trunc(CAST('1' AS DOUBLE)) AS INTEGER)), ANY and ALL as subqueries, GROUPING SETS, ROLLUP and CUBE as lists of sets, chains of UNION as a tree whose operands are paired from the left, the type of every number literal from its digits, and so on.

A statement is not compared when it has a construct that the mapping does not cover (the most common are PIVOT and UNPIVOT, which DuckDB expands, SAMPLE clauses, LATERAL, the VARIANT and GEOMETRY types, WITHIN GROUP, ARRAY(...) with an ORDER BY, and DESCRIBE). The two statements that differ are WITH RECURSIVE t(b) AS MATERIALIZED ((WITH helper(c) AS (SELECT 5) SELECT ... (the aliases that DuckDB puts in a recursive CTE written with a parenthesized WITH) and a NOT applied to NOT BETWEEN in a fuzzer-made expression. The mapping is test code: it is not an API of the module.

The precedence and the associativity of the operators were checked further with 250,000 random expressions made with other seeds than the corpus (REFERENCE_FILE, see testdata/README.md): the same acceptance, and the same AST in all of the 114,000 SELECT statements that they make.

#Known deviations and limits

• Thirteen texts (testdata/deviations.jsonl, each with its reason) on which the parser and DuckDB differ in acceptance. Six come from the pass with which DuckDB replaces Unicode white space before it parses: it does not close a dollar-quoted string when a letter follows the closing tag (select $a$b$a$x<U+3000>x), so it leaves the white space inside the name that follows, where the parser reads a space. One is the spelling of an unreserved keyword (below). Six are constructs that are not understood: DuckDB accepts the words IN and AND and, after GROUPS BETWEEN, a lone dot as the first bound of a frame (before PRECEDING), rejects NOT at the start of that bound and SETOF before a qualified type, and accepts a percent sign after a postfix operator (LIMIT -1| %). The other differences that mutating the tests found, in 1.4 million texts, were fixed and are in the corpus found.
• The checks after parsing (above) are not made: a text such as SELECT sum(x) OVER w where the window w is not defined is accepted. A function that checks the most common of them is not part of this module.
• Split and statements that DuckDB expands: PIVOT, COPY FROM DATABASE and ALTER TABLE ... ADD COLUMN ... DEFAULT are one statement here and several for DuckDB, which also gives them other texts.
• Input that is not UTF-8: DuckDB takes text, and the parser reads each invalid byte as U+FFFD in the positions of code points (the default), where two different bytes are the same character (a dollar-quoted string can open with $\xa5$ and close with $\xb1$); with Bytes they are different, and Split counts bytes.
• PRAGMA statements are rewritten by DuckDB into others (PRAGMA name = value is a SET, a call is a SELECT); Kind of a PragmaStmt is PRAGMA and its text is the text as written.
• Nesting is limited by the depth limit of the generated parser, 100,000 rule calls: 16,600 levels of parentheses, 14,200 of lists, 12,500 of CASE, 11,100 of derived tables, 10,000 of function calls, 7,100 of subqueries and 99,980 prefix operators in a chain (NOT NOT ... a, - - ... a). Deeper input fails with an error.
• Unreserved keywords as names: a word that is not a keyword at all is required in a few places (an alias without AS, the dotted name of a type, the setting of ALTER DATABASE, ...). The 330 unreserved keywords are recognized there in lower case, upper case and capitalized (text, TEXT, Text) and not in any other spelling: SELECT 1 tExT is accepted as an alias, where DuckDB rejects it. The other keywords are matched in every case everywhere. Matching the 330 in every case would add 140,000 lines to the parser and half as much again to its compile time.
• Compile time and size: the generated parser.go is 13.2 MB (643,000 lines), because the generator writes about 50 lines for each node of the grammar, and the grammar has some 12,000 of them. The first build takes about a minute (63 s of wall-clock time and 112 s of CPU with an empty build cache, on the machine of the benchmarks); the Go build cache makes the next ones free.
• DuckDB's extensions (the parsers that extensions add, such as PRQL) and the settings that change how DuckDB parses (SET of an option of the parser) are not covered.

#Grammar

duckdb.pego follows the grammar of DuckDB (third_party/libpg_query/grammar, the Bison files) and its scanner (scan.l). The ways in which it departs from the structure of the Bison grammar, where a PEG needs it or where it measurably pays, are commented in the grammar:

• The scanner is in the grammar. A rule for a token matches the token only; white space and comments are skipped (ws) where a rule needs them. The operators are cut as scan.l cuts them, with the lookahead that decides where a run of operator characters ends. The keywords are rules of their own, generated by internal/refgen/keywords.py from DuckDB's lists, which also write the tries that tell, for each kind of name, whether a word is a keyword that the kind forbids.
• Precedence and associativity are those of the %left, %right and %nonassoc declarations, in a pratt block of levels: comparisons do not associate (a < b < c is an error, also on the right of AND), the operators of the LIKE, IN and BETWEEN level do not either, ->> has the precedence of a token that completes the expression on its left but takes an arithmetic expression on its right, and a postfix operator (a !) is read where the Bison grammar would shift it. NOT before BETWEEN, IN, LIKE, ILIKE and SIMILAR, NULLS before FIRST and LAST, and WITH before TIME and ORDINALITY are tokens of their own in the Bison grammar (NOT_LA, NULLS_LA, WITH_LA): the rules look at the word that follows.
• Where a keyword may be a name is decided by its category (unreserved, column_name, type_function, reserved), with the exceptions of the grammar: CUBE, ROLLUP, ENUM, BETWEEN and OPERATOR that the parser shifts as keywords in some positions.
• A rule has one action: where the Bison grammar gives alternatives different actions, they are rules of their own, so that every node has its type. Optional parts are *T fields, repeated parts []T.
• Alternatives are tried only where they can match: an identifier that cannot begin a call, a typed literal or a E'...' string is read by a rule that needs no lookahead (plain_column), the operators of an expression look at the character they begin with, and a function call is tried before the typed literal that looks like one (DECIMAL(10, 2) '1.5').
• Joins associate to the left, and INTERSECT binds tighter than UNION and EXCEPT, which associate to the left.

#Performance

Parsing a script of 256 KB (1,271 statements: tables, CTEs with joins, aggregates, window functions, subqueries, CASE, casts, lists and structs, set operations and DML; the benchmark writes it with BENCH_SCRIPT=file go test -run TestWriteBenchScript), go test -bench . on an Apple M3 Max:

DuckDB's time is the best of ten runs of extract_statements (the parser of DuckDB, and the step that makes its statement objects) on the script that the test wrote, with the Python module of DuckDB 1.5.6:

BENCH_SCRIPT=/tmp/bench.sql go test -run TestWriteBenchScript
python3 -c "
import duckdb, time
sql = open('/tmp/bench.sql').read()
con = duckdb.connect()
best = 1e9
for i in range(10):
    t = time.perf_counter()
    statements = con.extract_statements(sql)
    best = min(best, time.perf_counter() - t)
print(len(statements), 'statements', round(best * 1000, 1), 'ms', round(len(sql) / best / 1e6), 'MB/s')"

DuckDB's parser is C++ and parses the same script about four times as fast. The time here is mostly the cost of a grammar that has to decide, at each token, among the alternatives that the Bison automaton chooses by a table: the ordered choice of a PEG tries them one after the other. In the CPU profile of ParseAST, about a tenth of the time is spent recording what each failed alternative expected (for the error message), another tenth in the memo table, and another in the allocator and the garbage collector. Recognize builds nothing and is not faster than ParseAST, whose rules the generator compiles into direct code (see the code generation guide). Tuning the grammar took ParseAST from 4.1 MB/s to 5.6 MB/s: the operators of the expressions are tried only when the character that follows could begin them, a function call is not parsed twice to find that no string literal follows it, IN, LIKE, IS and the rest are one operator each, and a word is compared with the unreserved keywords that begin with its letter, not with all 330 (that alone made a CREATE TABLE with a TEXT column 5 times as fast). BenchmarkStatements gives the speed on 35 kinds of statement, from 2.5 MB/s (SELECT [1, 2, 3], {'a': 1, 'b': 2}, x[1], x.y) to 19 MB/s (ATTACH 'f.db' AS db).

#Development

go generate ./parsers                 # regenerate parser.go after changing duckdb.pego (from the repository root)
go test ./parsers                     # parser.go up to date; golden files on every backend of the engine
cd parsers/duckdb && go test ./...    # conformance against the vendored data, the examples, the other tests
go test -short                        # a fraction of the texts
go test -bench .                      # benchmarks
go test -fuzz FuzzParse               # fuzz the parser (ParseAST and Recognize agree, nothing panics)
NESTING_LIMITS=1 go test -v -run TestNesting   # the depth at which each construct fails

The reference data is made by internal/refgen and is described in testdata/README.md, with the command that makes it again from a checkout of DuckDB v1.5.6 and its Python module. Only the data is part of the module; DuckDB is not a dependency of anything that is built or tested here.