DuckDB v2.0: Uw database verdient een betere parser

TL;DR: DuckDB v2.0 vervangt de SQL-parser die was afgeleid van PostgreSQL door een PEG-gebaseerde parser die gemakkelijker te evolueren is en tijdens runtime kan worden uitgebreid.

Bij DuckDB is een van onze doelen om het werken met een databasesysteem zo eenvoudig mogelijk te maken. Gebruikers communiceren met het systeem via de algemeen bekende Structured Query Language (SQL). In eerdere blogposts hebben we DuckDB's gebruiksvriendelijke SQL behandeld, inclusief GROUP BY ALL en kolomselectie met SELECT * EXCLUDE (...). Voordat DuckDB een query kan uitvoeren met deze functies, moet het systeem echter eerst bepalen of de syntaxis geldig is. Dat is de taak van de parser, en in DuckDB v2.0 vervangen we deze volledig, zonder dat u daar direct iets van merkt.

Wat is de rol van een parser?

Op een hoog niveau verwerkt DuckDB een SQL-query via de volgende fasen:

In deze blog richten we ons op de tokenizer, parser en transformer:

  • Tokenizer: Dit is de eerste stap en is verantwoordelijk voor het opdelen van de ruwe inputstring in tokens. Deze kunnen tot verschillende categorieën behoren, zoals KEYWORD, NUMBER of IDENTIFIER. Hier worden ook commentaren (in SQL aangeduid met -- of / /) herkend en overgeslagen.
  • Parser: De parser bepaalt of deze tokens voldoen aan de grammatica van DuckDB en produceert een ParseResult-boom.
  • Transformer: Zet de generieke parse-resultaten om in de interne abstract syntax tree (AST) van DuckDB, waardoor structuren ontstaan zoals SQLStatement, TableRef en ParsedExpression. De resulterende AST wordt doorgegeven aan de binder.

De parser bepaalt of een query syntactisch geldig is, terwijl de binder bepaalt of de tabellen, kolommen en functies waarnaar wordt verwezen daadwerkelijk bestaan.

Overweeg de volgende query:

SELECT *
WHERE true
FROM range(1);

Parser Error: syntax error at or near "FROM" LINE 3: FROM range(1);

Elk individueel token in deze query is geldig, maar de clausules verschijnen in een volgorde die de grammatica van DuckDB niet accepteert. "Friendly SQL" staat zowel een syntax met SELECT eerst als FROM eerst toe, maar staat niet toe dat de clausules in een willekeurige volgorde verschijnen.

Ter vergelijking: de volgende query is syntactisch geldig, waardoor hij door de parser en transformer komt. Hij faalt echter later in de binder omdat de tabel missing_table niet bestaat.

FROM missing_table;

Catalog Error: Table with name missingtable does not exist! LINE 1: FROM missingtable;

Het SQL-dialect van DuckDB

Hoewel er een SQL-standaard bestaat, ondersteunt elk databasesysteem verschillende delen van die standaard en voegt het eigen syntaxis en gedrag toe. De resulterende varianten worden gemeenschappelijk aangeduid als SQL-dialecten. Voorbeelden hiervan zijn de dialecten van PostgreSQL, Oracle, GoogleSQL voor BigQuery, MySQL, MariaDB, SQLite, Spark SQL en natuurlijk DuckDB.

De SQL van DuckDB volgt nauwgezet de conventies van PostgreSQL, maar is in de loop der jaren aanzienlijk geëvolueerd. We hebben eigen functies toegevoegd, zoals GROUP BY ALL, en functies die geïnspireerd zijn door andere databasesystemen. Tegelijkertijd implementeert DuckDB niet elk aspect van het gedrag van PostgreSQL. DuckDB spreekt daarom zijn eigen SQL-dialect, dat we in dit bericht zullen aanduiden als DuckSQL, ook al blijft het sterk beïnvloed door PostgreSQL.

Dit onderscheid is belangrijk bij het bespreken van de parser. Het SQL-dialect dat DuckDB accepteert en de implementatie die wordt gebruikt om die SQL te parsen, zijn twee verschillende zaken. Voor DuckDB v2.0 vervangen we de implementatie van de parser en herschrijven we de grammatica. Wat we niet vervangen, is DuckSQL zelf.

Het overgroeien van de PostgreSQL-parser

Toen DuckDB begon, was het logisch om de parser en grammatica afgeleid van PostgreSQL te gebruiken. Deze parser maakte al deel uit van de eerste commit van DuckDB in 2018. Het gaf DuckDB een volwassen, beproefde SQL-grammatica gebaseerd op syntaxis die veel gebruikers al kenden. We hebben de parser aangepast aan onze behoeften en een Transformer toegevoegd die de resulterende parse-boom in PostgreSQL-stijl omzette naar de interne AST van DuckDB.

In de loop der jaren bracht deze parser echter ook nadelen met zich mee. Het uitbreiden van DuckSQL betekende het wijzigen van de onderliggende YACC/Bison-grammatica. Omdat Bison een LALR(1)-parser genereert, kunnen schijnbaar kleine toevoegingen aan de grammatica interageren met bestaande regels en shift/reduce of reduce/reduce conflicten veroorzaken. Naarmate DuckSQL groeide, werd het therefore steeds moeilijker om wijzigingen in de grammatica aan te brengen.

Dit was een van de motivaties achter ons eerdere blogbericht over runtime-uitbreidbare SQL-parsers. In dat bericht en het bijbehorende CIDR-paper onderzochten we of Parsing Expression Grammars (PEG's) een betere basis konden bieden voor een uitbreidbare database-parser. Op dat moment was de PEG-parser nog een experimenteel prototype dat slechts een subset van SQL kon parsen.

Een introductie tot PEG-parsers

Voordat we kijken naar hoe we het prototype hebben omgezet in een productie-parser, blikken we kort terug op hoe een PEG een taal beschrijft.

Een PEG bestaat uit benoemde regels die beschrijven hoe een input gematcht moet worden. Beschouw de volgende regels uit de nieuwe grammatica van DuckDB:

SelectFrom <- SelectFromClause / FromSelectClause SelectFromClause <- SelectClause FromClause? FromSelectClause <- FromClause SelectClause?

De <- operator definieert een regel, / specificeert een keuze tussen alternatieven, en ? maakt een element optioneel. Samen stellen deze regels dat DuckSQL zowel een traditionele SELECT-eerst query accepteert:

SELECT *
FROM range(1);

Als ook het FROM-eerst equivalent van DuckDB's Friendly SQL:

FROM range(1)
SELECT *;

Een PEG evalueert alternatieven in volgorde. Bij het matchen van SelectFrom probeert de parser eerst SelectFromClause. Als dat niet matcht, probeert hij FromSelectClause. Het eerste succesvolle alternatief wordt geselecteerd. Als gevolg hiervan hebben PEG-grammatica's niet dezelfde shift/reduce en reduce/reduce conflicten als LALR-grammatica's. In plaats daarvan zijn alternatieven expliciet geordend, en die volgorde maakt deel uit van het gedrag van de grammatica.

We zijn niet de enigen die overstappen op een PEG-gebaseerde parser. Python stapte in Python 3.9 over van een LL(1)-parser naar een PEG-gebaseerde parser, eveneens gemotiveerd door de extra flexibiliteit die PEG biedt om de taal te evolueren.

In DuckDB werken deze regels op de tokens die door de tokenizer zijn geproduceerd. De matcher past de grammaticaregels toe op deze tokens en construeert een generieke ParseResult-boom, die vervolgens wordt getransformeerd naar de interne AST van DuckDB.

Van prototype naar productie

Het research-prototype bewees dat een PEG-gebaseerde SQL-parser haalbaar was. Het vervangen van de bestaande parser van DuckDB vereiste echter aanzienlijk meer dan het parsen van een subset van SQL. De nieuwe parser moest de volledige DuckSQL accepteren en dezelfde AST produceren die door de binder van DuckDB wordt verwacht.

De PEG-grammatica werd voor het eerst geïntroduceerd in DuckDB v1.2, waar het autocomplete in de CLI afhandelde. Later, in DuckDB v1.5, introduceerden we de volledige PEG-parser als een experimentele, opt-in functie. We gebruikten het ook voor een 1 april-grap waarbij DuckDB Nederlands sprak. Sindsdien zijn de grammatica, matcher en transformer gestaag verbeterd om de PEG-parser de standaard te maken voor DuckDB v2.0.

Onder andere zaken moest de parser het volgende ondersteunen:

  • Elk statement- en expressietype: Het ondersteunen van het volledige DuckSQL-dialect omvat zowel veelvoorkomende syntaxis als minder vaak gebruikte statements en expressies.
  • Operatorprecedentie en associativiteit: Bijvoorbeeld: SELECT true OR true AND false; moet worden geïnterpreteerd als (true OR (true AND false)), omdat AND sterker bindt dan OR.
  • Correcte classificatie van trefwoorden: Sommige trefwoorden, zoals SELECT, zijn RESERVED en kunnen niet worden gebruikt als ongequoteerde tabel- of kolomnamen. Andere trefwoorden kunnen als identifiers worden gebruikt, afhankelijk van hun context.
  • Compatibiliteit met de interne AST van DuckDB: De PEG-transformer moet dezelfde DuckDB AST-structuren produceren als de transformer voor de PostgreSQL-afgeleide parse-nodes, overal waar het taalgedrag ongewijzigd moet blijven.
  • Correcte foutrapportage: Bij een ongeldige query moet de parser rapporteren waar het parsen misging en, indien mogelijk, context en een nuttige indicatie geven van wat er fout ging, bij voorkeur zonder te verwijzen naar een handleiding.
  • Prestaties bij ongebruikelijke input: Naast het snel houden van normaal parsen, moesten we er ook zeker van zijn dat malformed queries niet plotseling zeer lang duren om te parsen.

Herhaald werk voorkomen met Packrat Parsing

Een probleem waar we tegenaan liepen, was herhaald werk tijdens het backtracking. Een naïve PEG-matcher kan dezelfde grammaticaregel op dezelfde tokenpositie vele malen evalueren terwijl hij verschillende alternatieven probeert. Voor bepaalde malformed inputs kan de hoeveelheid herhaald werk exponentieel groeien.

We merkten dit bij queries met een groot aantal niet-gematchte openende haakjes:

SELECT ((((((((((((((((((;

Met de experimentele PEG-parser in v1.5 verdubbelde het toevoegen van één extra openend haakje ongeveer de parstijd:

  • 18 openende haakjes: 5,303 seconden
  • 19 openende haakjes: 10,640 seconden

We hebben dit opgelost met packrat parsing, een memoizatietechniek die algemeen wordt gebruikt bij PEG-parsers. Voor elke gememoiseerde matcher slaan we het resultaat op van het toepassen ervan op een specifieke tokenpositie. Als de parser later dezelfde matcher op dezelfde positie probeert, wordt het gecachte resultaat hergebruikt in plaats van het opnieuw te evalueren.

Met packrat parsing ingeschakeld werd dezelfde malformed query bijna onmiddellijk afgewezen:

  • 19 openende haakjes: 0,001 seconden

Als gevolg hiervan wordt een gememoiseerde matcher maximaal één keer geëvalueerd op een specifieke tokenpositie, waardoor het herhaalde werk dat tot het exponentiële gedrag leidde, is verwijderd. Dit vereist extra geheugen tijdens het parsen, maar dat is een waardevolle afweging om dit soort gevallen te voorkomen.

Het omzetten van het prototype naar een productie-parser hield veel meer in dan het vertalen van de grammatica. De nieuwe parser moest het volledige DuckSQL-dialect dekken, de bestaande AST van DuckDB behouden, compatibel blijven met bestaande queries en zowel geldige als malformed input efficiënt afhandelen.

De resulterende architectuur vervangt de PostgreSQL-afgeleide parser-front-end, terwijl de binder en de rest van de query-verwerkingspijplijn van DuckDB blijven werken op dezelfde interne AST.

DuckSQL evolueren

Nu de PEG-parser is geïmplementeerd voor DuckDB v2.0, zijn we DuckSQL ook blijven uitbreiden met nieuwe syntaxis.

Een voorbeeld is de nieuwe expression-statement syntaxis. Tot nu toe vereiste het uitvoeren van een query die alleen uit expressies bestond altijd het schrijven van een SELECT:

SELECT date: current_date(), time: current_localtime();

Met een expression statement kan de SELECT worden weggelaten:

date: current_date(), time: current_localtime();

Als bonus werkt dit ook met prefix-aliassen.

Een ander voorbeeld is het nieuwe CONNECT statement, geïntroduceerd voor Quack. Hiermee kunt u verbinding maken met een externe database en daaropvolgende queries ernaartoe routeren totdat u DISCONNECT uitvoert:

CONNECT 'postgres://localhost/mydb';
SELECT count(*) FROM orders; -- Draait op de PostgreSQL-server
DISCONNECT;

Er komt ook nieuwe syntaxis voor het werken met externe resources. Hiermee kunt u resources beheren die buiten DuckDB leven via een extensie. U kunt een resource aanmaken, registreren, inspecteren, verbinden of vernietigen, allemaal vanuit DuckDB:

CREATE EXTERNAL RESOURCE '<resource-type>' AS <name> (...);
REGISTER EXTERNAL RESOURCE '<resource-type>' AS <name> FROM <handle>;
SHOW EXTERNAL RESOURCES;
CONNECT TO EXTERNAL RESOURCE <name>;
DESTROY EXTERNAL RESOURCE <name>;

We hebben ook COPY TO uitgebreid met PARTITION BY en ORDER BY syntaxis:

COPY orders TO 'orders'
(
  FORMAT parquet,
  PARTITION BY (year, month),
  ORDER BY (order_date)
);

Deze toevoegingen zouden ook mogelijk zijn geweest met de oude PostgreSQL-parser, maar het toevoegen ervan zou aanzienlijk omslachtiger zijn geweest. De PEG-grammatica maakt het voor ons gemakkelijker om DuckSQL te blijven evolueren.

Tot nu toe maken deze regels allemaal deel uit van DuckSQL zelf. De volgende stap is om extensies toe te staan hun eigen regels toe te voegen.

De parser uitbreiden

Extensies zijn een centraal onderdeel van DuckDB. Ze kunnen al scalaire en tabel-functies, optimizer-regels, query-plan herschrijvingen en zelfs aangepaste fysieke operators toevoegen.

Er bestaan al extensies die nieuwe syntaxis toevoegen, zoals psql en duckpgq, maar onder de motorkap werken deze als fallback parsers. DuckDB probeert eerst de query zelf te parsen en roept de extensie pas aan als dat mislukt. Dit werkt goed voor zelfstandige syntaxis, maar een extensie die syntaxis binnen SQL wil toevoegen, moet ook de omringende SQL zelf parsen. Deze fallback-parsers maken het bovendien onmogelijk om de syntaxis van meerdere extensies te combineren.

Met de PEG-parser kunnen extensies in plaats daarvan individuele delen van de parser van DuckDB uitbreiden. Ze kunnen de tokenizer uitbreiden, grammaticaregels toevoegen en aangepaste matchers registreren, terwijl ze de rest van DuckSQL blijven hergebruiken.

Waarschuwing: De hieronder getoonde API is nog een preview en kan veranderen vóór de release van DuckDB v2.0.

Om dit concreet te maken, gebruiken we de pipe query syntax van Google. Dit is een extensie van SQL die een gepipede dataflow-syntaxis toevoegt. Pipe-syntaxis drukt een query uit als een reeks operatoren, waarbij elke operator het resultaat van de vorige consumeert.

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;

Een vereenvoudigde PEG-grammatica hiervoor heeft een handvol regels nodig:

PipeSelectAtom <- PipeSource PipeStage+ PipeSource <- FromClause / SelectStatementType / SelectParens PipeStage <- '|>' PipeOperator PipeOperator <- PipeAggregate / PipeAggregateGroupOnly / PipeWhere / PipeSelect / PipeExtend / PipeDistinct / PipeOrderBy / PipeLimit PipeWhere <- WhereClause PipeSelect <- 'SELECT' TargetList PipeExtend <- 'EXTEND' TargetList PipeDistinct <- 'DISTINCT' PipeOrderBy <- OrderByClause PipeLimit <- LimitClause OffsetClause? PipeAggregate <- 'AGGREGATE' TargetList GroupByClause? PipeAggregateGroupOnly <- 'AGGREGATE' GroupByClause

Hier betekent + dat PipeStage één of meer keer moet voorkomen; een pipe-query moet dus minstens één pipe-operator bevatten.

Deze grammatica kan bestaande regels hergebruiken, zoals GroupByClause, om de hoeveelheid grammatica die de extensie moet definiëren te verminderen. Een extensie kan nog steeds zijn eigen regel definiëren waar de bestaande syntaxis van DuckDB niet past.

De grammatica registreren

Het enkel definiëren van de PEG-regels maakt ze nog niet onderdeel van de grammatica van DuckDB. De extensie moet ook specificeren (1) welke bestaande grammaticaregel hij wil uitbreiden en (2) de transformer-regels die de nieuwe syntaxis omzetten in de AST van DuckDB.

In het huidige prototype bieden bepaalde grammaticaregels uitbreidingspunten. Pipe SQL registreert PipeSelectAtom als een extra alternatief voor SelectAtom, samen met de nieuwe trefwoorden AGGREGATE en EXTEND.

static void LoadInternal(ExtensionLoader &loader) {
    ParserExtension extension;
    extension.grammar_extension.grammar = PIPE_SQL_GRAMMAR;
    extension.grammar_extension.select_atom_rule = "PipeSelectAtom";
    extension.grammar_extension.RegisterSelectAtomTransformer(
        "PipeSelectAtom",
        TransformPipeSelectAtom
    );
    loader.RegisterKeyword(
        "aggregate",
        ExtensionKeywordCategory::RESERVED
    );
    loader.RegisterKeyword(
        "extend",
        ExtensionKeywordCategory::RESERVED
    );
    loader.RegisterParserExtension(std::move(extension));
}

Door dit alternatief te registreren, is de resulterende grammatica effectief:

SelectAtom <- PipeSelectAtom / SelectParens / SelectStatementType

Het alternatief van de extensie wordt nu als eerste geprobeerd. Als er geen pipe-syntaxis aanwezig is, faalt dit zonder tokens te consumeren en wordt de query geparsed met de ingebouwde alternatieven.

Het resultaat transformeren

Het toevoegen van een grammaticaregel brengt ons slechts tot een ParseResult. De extensie moet dit resultaat vervolgens transformeren naar de DuckDB AST die door de binder wordt verwacht. Aangezien PipeSelectAtom de SelectAtom uitbreidt, retourneert de transformer een SelectStatement:

static unique_ptr<SelectStatement>
TransformPipeSelectAtom(PEGTransformer &transformer, ParseResult &parse_result) {
    auto &pipe = parse_result.Cast<ListParseResult>();
    // PipeSelectAtom <- PipeSource PipeStage+
    auto statement = TransformPipeSource(transformer, pipe.GetChild(0));
    auto &stages = pipe.Child<RepeatParseResult>(1);
    for (auto &stage : stages.GetChildren()) {
        ApplyPipeStage(transformer, stage.get(), *statement);
    }
    return statement;
}

De vorm van de ParseResult volgt de grammaticaregel die we eerder definieerden. PipeSelectAtom bevat een PipeSource en één of meer PipeStages. We transformeren eerst de PipeSource naar een DuckDB SelectStatement. Elke PipeStage wordt vervolgens in volgorde op dat statement toegepast. Het resulterende SelectStatement wordt vervolgens geretourneerd en kan door de rest van de parser-pijplijn naar de binder gaan.

Dit is waar het hergebruiken van de bestaande grammatica van DuckDB bijzonder nuttig wordt. De extensie hoeft alleen de nieuwe syntaxis die hij introduceerde te transformeren. Wanneer hij een bestaande DuckDB-grammaticaregel hergebruikt, zoals GroupByClause, kan hij ook de bijbehorende transformatiefunctie hergebruiken in plaats van GROUP BY zelf te implementeren.

Dit is een belangrijk verschil met de fallback-parsers die vandaag de dag beschikbaar zijn. Een extensie hoeft niet langer expressies, tabelreferenties, GROUP BY-clausules en de rest van SQL zelf te implementeren. In plaats daarvan kan hij alleen de syntaxis toevoegen die hij nodig heeft en de grammatica en transformaties van DuckDB hergebruiken voor altijd het andere.

Pipe SQL uitvoeren

Met de geregistreerde extensie kunnen we nu queries uitvoeren met de nieuwe pipe-syntaxis. We kunnen bijvoorbeeld de pipe-operators van de extensie combineren met bestaande DuckSQL-functies zoals range() en prefix-aliassen:

FROM range(6) t(i)
|> WHERE i % 2 = 0
|> SELECT i, doubled: i * 2
|> ORDER BY i DESC;

Resultaat:

idoubled
48
24
00

De extensie definieert alleen de pipe-specifieke syntaxis. Expressies, tabelreferenties, WHERE, SELECT, ORDER BY en andere hergebruikte regels worden nog steeds geparsed en getransformeerd door DuckDB zelf. Dit betekent dat nieuwe syntaxis kan worden gecombineerd met DuckSQL zonder dat de extensie de rest van SQL opnieuw hoeft te implementeren.

Conclusie

Met DuckDB v2.0 vervangen we de PostgreSQL-afgeleide parser door een nieuwe PEG-parser. Bestaande DuckSQL-queries zouden moeten blijven werken zoals voorheen. Onder de motorkap geeft de nieuwe parser ons echter iets dat gemakkelijker te evolueren is en is ontworpen voor runtime-uitbreidbaarheid.

De runtime grammar extension API die in dit bericht wordt getoond, is nog een preview en kan veranderen vóór de release van v2.0. Het onderliggende idee werkt echter al. Extensies kunnen hun eigen syntaxis direct toevoegen aan de grammatica van DuckDB, terwijl ze de bestaande regels en transformaties hergebruiken. Dit betekent dat ze de rest van SQL niet langer zelf hoeven te parsen.

We zijn benieuwd welke nieuwe syntaxis de community zal creëren. Ondertussen zullen we DuckSQL blijven evolueren en de parser verbeteren.

Mocht u een bestaande query vinden die zich anders gedraagt met de PEG-parser, laat het ons dan weten door een issue in te dienen.