DuckDB V2 PEG-based SQL parser

DuckDB v2.0: Your Database Deserves a Better Parser TL;DR: DuckDB v2.0 replaces its PostgreSQL-derived SQL parser with a PEG-based parser that is easier to evolve and can be extended at runtime. At DuckDB, one of our goals is to make working with a database system as easy as possible. Users interact with the system through the widely understood Structured Query Language (SQL). Previous blog posts have covered DuckDB’s friendly SQL, including GROUP BY ALL and column selection using SELECT * EXCLUDE (...) . Before DuckDB can execute a query using these features, however, it first has to determine whether its syntax is valid. That is the job of the parser, and in DuckDB v2.0 we are completely replacing it without you noticing. What is the Role of a Parser? At a high level, DuckDB processes a SQL query through the following stages: In this blog, we focus on the tokenizer, parser, and transformer: - Tokenizer: This is the first step and is responsible for splitting up the raw input string into tokens. These can be of various categories, for example: KEYWORD ,NUMBER , orIDENTIFIER . It is also where comments, in SQL denoted with either-- or/* / , are recognized and skipped. - Parser: The parser determines whether these tokens follow DuckDB's grammar and produces a ParseResult tree. - Transformer: Converts the generic parse results into DuckDB’s internal abstract syntax tree (AST), forming structures such as SQLStatement ,TableRef , andParsedExpression . The resulting AST is passed on to the binder. The parser determines whether a query is syntactically valid, while the binder determines whether the tables, columns, and functions it refers to actually exist. Consider the following query: SELECT * WHERE true FROM range(1); Parser Error: syntax error at or near "FROM" LINE 3: FROM range(1); ^^^^ Every individual token in this query is valid, but the clauses occur in an order that DuckDB’s grammar does not accept. Friendly SQL allows both SELECT -first and FROM -first syntax, but it does not allow the clauses to appear in an arbitrary order. By comparison, the following query is syntactically valid, so it passes the parser and transformer. However, it fails later in the binder because the table missing_table does not exist. FROM missing_table; Catalog Error: Table with name missing_table does not exist! LINE 1: FROM missing_table; ^^^^^^^^^^^^^ The DuckDB SQL Dialect Although a SQL standard exists, every database system supports different parts of the standard and adds its own syntax and behavior. The resulting variants are commonly referred to as SQL dialects. Examples include the dialects supported by PostgreSQL, Oracle, GoogleSQL for BigQuery, MySQL, MariaDB, SQLite, Spark SQL, and, of course, DuckDB. DuckDB’s SQL closely follows PostgreSQL conventions, but it has evolved considerably over the years. We have added features of our own, such as GROUP BY ALL , as well as features inspired by other database systems. At the same time, DuckDB does not implement every aspect of PostgreSQL’s behavior. DuckDB therefore speaks its own SQL dialect, which we will refer to as DuckSQL in this post, even though it remains strongly influenced by PostgreSQL. This distinction is important when talking about the parser. The SQL dialect that DuckDB accepts and the implementation used to parse that SQL are two separate things. For DuckDB v2.0, we are replacing the parser implementation and rewriting its grammar. What we are not replacing is DuckSQL itself. Outgrowing the PostgreSQL-Derived Parser When DuckDB started out, it made a lot of sense to use the PostgreSQL-derived parser and grammar. This parser was already part of the first commit to DuckDB in 2018. It gave DuckDB a mature, battle-tested SQL grammar based on syntax that many users were already familiar with. We adapted the parser to our needs and added a Transformer that converted the resulting PostgreSQL-style parse tree into DuckDB’s internal AST. However, over the years this parser also came with some downsides. Extending DuckSQL meant modifying the underlying YACC/Bison grammar. Because Bison generates an LALR(1) parser, seemingly small additions to the grammar can interact with existing rules and introduce shift/reduce or reduce/reduce conflicts. As DuckSQL grew, making changes to the grammar therefore became increasingly difficult. This was one of the motivations behind our earlier blog post on runtime-extensible SQL parsers. In that post and the accompanying CIDR paper, we explored whether Parsing Expression Grammars (PEGs) could provide a better foundation for an extensible database parser. At the time, the PEG parser was still an experimental prototype capable of parsing only a subset of SQL. A Primer on PEG Parsers Before looking at how we turned the prototype into a production parser, let us briefly revisit how a PEG describes a language. A PEG consists of named rules that describe how an input should be matched. Consider the following rules from DuckDB’s new grammar: SelectFrom ' AS (...); REGISTER EXTERNAL RESOURCE ' ' AS FROM ; SHOW EXTERNAL RESOURCES; CONNECT TO EXTERNAL RESOURCE ; DESTROY EXTERNAL RESOURCE ; We have also extended COPY TO with PARTITION BY and ORDER BY syntax: COPY orders TO 'orders' ( FORMAT parquet, PARTITION BY (year, month), ORDER BY (order_date) ); These additions would also have been possible with the old PostgreSQL-derived parser, but adding them would have been considerably more cumbersome. The PEG grammar makes it easier for us to continue evolving DuckSQL. So far, these rules are all part of DuckSQL itself. The next step is allowing extensions to add rules of their own. Extending the Parser Extensions are a central part of DuckDB. They can already add scalar and table functions, optimizer rules, query-plan rewrites, and even custom physical operators. Extensions that add new syntax already exist, such as psql and duckpgq , but under the hood they work as fallback parsers. DuckDB first tries to parse the query itself and only calls the extension if that fails. This works well for self-contained syntax, but an extension that wants to add syntax inside SQL also has to parse the surrounding SQL itself. These fallback parsers also make it impossible to combine the syntax of multiple extensions. With the PEG parser, extensions can instead extend individual parts of DuckDB’s parser. They can extend the tokenizer, add grammar rules, and register custom matchers while continuing to reuse the rest of DuckSQL. Warning The API shown below is still a preview and may change before DuckDB v2.0. You can follow the ongoing development on GitHub. To make this concrete, we use Google’s pipe query syntax. This is an extension to SQL that adds piped data flow syntax. Pipe syntax expresses a query as a sequence of operators, where each operator consumes the result of the previous one. FROM produce |> WHERE item != 'bananas' AND category IN ('fruit', 'nut') |> AGGREGATE COUNT() AS num_items, SUM(sales) AS total_sales GROUP BY item |> ORDER BY item DESC; A simplified PEG grammar for this needs a handful of rules: PipeSelectAtom ' PipeOperator PipeOperator TransformPipeSelectAtom(PEGTransformer &transformer, ParseResult &parse_result) { auto &pipe = parse_result.Cast (); // PipeSelectAtom (1); for (auto &stage : stages.GetChildren()) { ApplyPipeStage(transformer, stage.get(), *statement); } return statement; } The shape of the ParseResult follows the grammar rule we defined earlier. PipeSelectAtom contains a PipeSource and one or more PipeStage s. We first transform the PipeSource into a DuckDB SelectStatement . Each PipeStage is then applied to that statement in order. The resulting SelectStatement is then returned and can continue through the rest of the parser's pipeline and eventually on to the binder. This is where reusing DuckDB's existing grammar becomes especially useful. The extension only needs to transform the new syntax it introduced. When it reuses an existing DuckDB grammar rule, such as GroupByClause , it can also reuse the corresponding transform function instead of having to implement GROUP BY itself. This is an important difference from the fallback parsers that are available today. An extension no longer needs to implement expressions, table references, GROUP BY clauses, and the rest of SQL itself. Instead, it can add only the syntax it needs and reuse DuckDB’s grammar and transformations for everything else. Executing Pipe SQL With the extension registered, we can now execute queries using the new pipe syntax. For example, we can combine the pipe operators added by the extension with existing DuckSQL features such as range() and prefix aliases: FROM range(6) t(i) |> WHERE i % 2 = 0 |> SELECT i, doubled: i * 2 |> ORDER BY i DESC; ┌───────┬─────────┐ │ i │ doubled │ │ int64 │ int64 │ ├───────┼─────────┤ │ 4 │ 8 │ │ 2 │ 4 │ │ 0 │ 0 │ └───────┴─────────┘ The extension only defines the pipe-specific syntax. Expressions, table references, WHERE , SELECT , ORDER BY , and other reused rules are still parsed and transformed by DuckDB itself. This means that new syntax can be combined with DuckSQL without the extension having to implement the rest of SQL again. To Conclude With DuckDB v2.0, we are replacing the PostgreSQL-derived parser with a new PEG parser. Existing DuckSQL queries should continue working as before. Under the hood, however, the new parser gives us something that is easier to evolve and designed for runtime extensibility. The runtime grammar extension API shown in this post is still a preview and may change before v2.0 is released. However, the underlying idea is already working. Extensions can add their own syntax directly to DuckDB's grammar while reusing its existing rules and transformations. This means they no longer need to parse the rest of SQL themselves. We are excited to see what new syntax the community will create. In the meantime, we will continue evolving DuckSQL and improving the parser. If you do find an existing q