We will keep analyzing the key technologies behind database implementation — the SQL engine, the storage engine, transactions, and so on. Inside the SQL engine, the very first job is to recognize the user’s SQL.
The SQL Parser
We know that database users operate the database through SQL. But how does the database recognize SQL? Take select * from t for example. Compiler theory gives us the answer: the compilation of an SQL statement inside a DBMS follows the same standard pipeline as a conventional compiler — it needs lexical analysis, syntax analysis, and semantic analysis.
- Lexical analysis: Recognize the keywords, identifiers, operators, and terminals supported by the system from the query string, and determine the inherent “part of speech” of each token. Lexical analysis is the first step of parsing SQL; common tools include
flex. - Syntax analysis: According to the standard grammar rules that define the SQL language, use the tokens produced by lexical analysis to match the grammar rules. If an SQL statement matches a grammar rule, a corresponding Abstract Syntax Tree (AST) is generated. Common tools include
Bison. - Semantic analysis: Validate the abstract syntax tree — check whether the tables, columns, functions, and expressions in the tree actually have corresponding metadata — and transform the AST into a query tree.
Let’s look at a very popular open-source database, PostgreSQL. In PostgreSQL’s implementation, the lexical analysis is done with flex, so we need to learn a bit about flex first.
flex
flex is a lexical-analyzer generator, usually working together with bison. It’s not just PostgreSQL — the lexer and parser of many databases’ SQL parsers are implemented with flex and bison. There are two ways to build a database SQL parser: automatic generation and hand-written, each with its own trade-offs. PostgreSQL chose flex and bison.
- Automatic generation: Use tools like
flexandbisonto generate the lexer and parser code in a target language such as C or C++. - Hand-written: Don’t use a generator; write this part of the code yourself. The benefit is better performance and more room for SQL-specific code optimization; the downside is a large development effort, the need for long, large-scale testing before it stabilizes, and very high demands on the developers.
The source code is at flex git source, roughly 10,000 lines in total. The core principle is the automaton; reading the source helps a lot when writing flex’s .l files.
Lex resolves conflicts with two rules: when several prefixes of the input match one or more patterns, Lex uses the following rules to pick the correct lexeme:
- Always choose the longest prefix.
- If the longest possible prefix matches multiple patterns, always choose the pattern that is listed first in the Lex program.
Regular Expressions
Before applying flex you need to understand regular expressions. What does a regular expression do, and why did it come about? A regular expression is a formal way of describing the structural patterns of strings. Let’s look at a few examples:
. matches any single character except the newline ("\n")
* matches zero or more copies of the preceding expression
[] a character class that matches any character inside the brackets
[a-zA-Z]+ // matches a word
{} when the brackets contain one or two digits, indicates how many
times the preceding pattern is allowed to match, e.g. `A{1,3}`
matches the letter A one to three times
+ matches one or more occurrences of the preceding regular expression
?There is much more to regular expressions, for example matching rules:
^: the pattern matches only strings that start with^, e.g.^oncematches strings beginning withonce.$: matches strings that end with the given pattern, e.g.bucket$.
We won’t cover more here. Next, let’s look at a few flex examples.
flex Examples
First, the simplest example:
/* The simplest flex program: echo */
%{
#include<stdio.h>
%}
%%
. | \n ECHO // match any character; the special action ECHO outputs the matched pattern
%%
void main() {
yylex();
}Its function is “print whatever you type.” Now let’s look at a more meaningful example — essentially you write a regular expression and say what to do after a match.
/* simple flex example: word-count fbcount.l */
// Declaration section: content between %{ and %} is copied verbatim into the generated C file
%{
#include<stdio.h>
int chars = 0;
int words = 0;
int lines = 0;
%}
// Rules section
%%
[a-zA~Z]+ { words++; chars += strlen(yytext); } // yytext always points to the matched input text
\n { chars++; lines++; } // match a newline
. { chars++; } // match any character
%%
void main() {
printf("%8d%8d%8d\n", lines, words, chars); // print the statistics
}Run flex count.l to generate the C program lex.yy.c, then compile it with gcc lex.yy.c -lfl, and run echo "asdf asd" | ./a.out to see the result.
Another example: recognizing words with flex.
%{
/* Word recognition program */
#include<stdio.h>
%}
%%
[\t ]+ ; // ignore whitespace
red |
blue |
green |
yellow { printf("%s: is a color. \n", yytext); } // match a color
[a-zA-Z]+ { printf("%s: is not a color. \n", yytext); } // match other words
. |
\n { ECHO;}
%%
void main() {
yylex();
}Once you understand the examples above, you can start reading PostgreSQL’s source file scan.l.
The Parser in PostgreSQL
The SQL parser’s main job is to recognize the user’s SQL statement and transform it into the query-tree structure that the optimizer needs later. Concretely, this means converting SQL into a RawStmt structure via bison, and then converting RawStmt into a Query structure. The code lives mainly under postgres/src/backend/parser, roughly fewer than 40,000 lines in total.
[postgres@slpc parser]$ ls
analyze.c parse_clause.c parse_expr.c parse_partition_lt.c parse_utilcmd.c
check_keywords.pl parse_coerce.c parse_func.c parser.c README
gram.y parse_collate.c parse_node.c parse_relation.c scan.l
Makefile parse_cte.c parse_oper.c parse_target.c scansup.c
parse_agg.c parse_enr.c parse_param.c parse_type.c
[postgres@slpc parser]$ cloc .
25 text files.
24 unique files.
2 files ignored.
github.com/AlDanial/cloc v 1.70 T=0.24 s (95.4 files/s, 234155.3 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 19 3757 9706 22455
yacc 1 1295 2190 15241
lex 1 164 457 897
Perl 1 43 28 166
make 1 15 20 37
-------------------------------------------------------------------------------
SUM: 23 5274 12401 38796
-------------------------------------------------------------------------------Taking a SELECT statement as an example: at this stage, select * from t1 is turned into a SelectStmt, which then becomes the abstract syntax tree RawStmt — the SQL text string is converted into a data structure the database can understand.
typedef struct RawStmt
{
NodeTag type;
Node *stmt; /* raw parse tree */
int stmt_location; /* start location, or -1 if unknown */
int stmt_len; /* length in bytes; 0 means "rest of string" */
} RawStmt;
typedef struct SelectStmt
{
NodeTag type;
/*
* These fields are used only in "leaf" SelectStmts.
*/
List *distinctClause; /* NULL, list of DISTINCT ON exprs, or
* lcons(NIL,NIL) for all (SELECT DISTINCT) */
IntoClause *intoClause; /* target for SELECT INTO */
List *targetList; /* the target list (of ResTarget) */
List *fromClause; /* the FROM clause */
Node *whereClause; /* WHERE qualification */
List *groupClause; /* GROUP BY clauses */
bool groupDistinct; /* Is this GROUP BY DISTINCT? */
Node *havingClause; /* HAVING conditional-expression */
List *windowClause; /* WINDOW window_name AS (...), ... */
/*
* In a "leaf" node representing a VALUES list, the above fields are all
* null, and instead this field is set. Note that the elements of the
* sublists are just expressions, without ResTarget decoration. Also note
* that a list element can be DEFAULT (represented as a SetToDefault
* node), regardless of the context of the VALUES list. It's up to parse
* analysis to reject that where not valid.
*/
List *valuesLists; /* untransformed list of expression lists */
/*
* These fields are used in both "leaf" SelectStmts and upper-level
* SelectStmts.
*/
List *sortClause; /* sort clause (a list of SortBy's) */
Node *limitOffset; /* # of result tuples to skip */
Node *limitCount; /* # of result tuples to return */
LimitOption limitOption; /* limit type */
List *lockingClause; /* FOR UPDATE (list of LockingClause's) */
WithClause *withClause; /* WITH clause */
/*
* These fields are used only in upper-level SelectStmts.
*/
SetOperation op; /* type of set op */
bool all; /* ALL specified? */
struct SelectStmt *larg; /* left child */
struct SelectStmt *rarg; /* right child */
/* Eventually add fields for CORRESPONDING spec here */
} SelectStmt;While reading the PostgreSQL source, every README is a must-read. Here is the README for the parser part:
/*
src/backend/parser/README
Parser
======
The most important sentence: parse the SQL statement into a Query structure,
for use by the Optimizer and executor.
This directory does more than tokenize and parse SQL queries. It also
creates Query structures for the various complex queries that are passed
to the optimizer and then executor.
parser.c things start here
scan.l break query into tokens
scansup.c handle escapes in input strings
gram.y parse the tokens and produce a "raw" parse tree
analyze.c top level of parse analysis for optimizable queries
parse_agg.c handle aggregates, like SUM(col1), AVG(col2), ...
parse_clause.c handle clauses like WHERE, ORDER BY, GROUP BY, ...
parse_coerce.c handle coercing expressions to different data types
parse_collate.c assign collation information in completed expressions
parse_cte.c handle Common Table Expressions (WITH clauses)
parse_expr.c handle expressions like col, col + 3, x = 3 or x = 4
parse_func.c handle functions, table.column and column identifiers
parse_node.c create nodes for various structures
parse_oper.c handle operators in expressions
parse_param.c handle Params (for the cases used in the core backend)
parse_relation.c support routines for tables and column handling
parse_target.c handle the result list of the query
parse_type.c support routines for data type handling
parse_utilcmd.c parse analysis for utility commands (done at execution time)
See also src/common/keywords.c, which contains the table of standard
keywords and the keyword lookup function. We separated that out because
various frontend code wants to use it too.
*/In other words, what the parser solves is converting a valid SQL statement into the Query structure used later by the optimizer or executor. Generally, DDL and command statements don’t need optimization, so they skip the optimizer and go straight to the executor. How do we check whether an input statement is valid? First, at the grammar-definition stage: gram.y defines the syntax rules, so the statement must conform to the SQL syntax rules. Second, it must conform to the semantic rules — for example, the table being queried must exist. This is checked by looking up the relevant table and column information in system catalogs such as pg_class and pg_attribute.
On the code side, the function that converts SQL into the abstract syntax tree RawStmt is pg_parse_query, which then calls parse_analyze to turn RawStmt into the query tree Query.
/* Analyze a raw parse tree and transform it to Query form.*/
Query *parse_analyze(RawStmt *parseTree, const char *sourceText,Oid *paramTypes, int numParams,QueryEnvironment *queryEnv)
{
ParseState *pstate = make_parsestate(NULL);
Query *query;
Assert(sourceText != NULL); /* required as of 8.4 */
pstate->p_sourcetext = sourceText;
if (numParams > 0)
parse_fixed_parameters(pstate, paramTypes, numParams);
pstate->p_queryEnv = queryEnv;
query = transformTopLevelStmt(pstate, parseTree);
if (post_parse_analyze_hook)
(*post_parse_analyze_hook) (pstate, query);
free_parsestate(pstate);
return query;
}I also strongly recommend the book openGauss Database Core Technology — Chapter 7, “openGauss SQL Engine,” is well worth a deep read.
Background Knowledge
To understand the SQL parser you must understand the relevant parts of compiler theory. Here is some supplementary compiler-theory material:
- Terminal: Loosely speaking, a symbol that cannot appear alone on the left side of a production — that is, a terminal cannot be derived any further.
- Nonterminal: Anything that is not a terminal; think of it as a splittable element, whereas a terminal is the indivisible smallest element.
- Shift: When the parser reads a token that cannot yet complete a rule, it pushes that token onto its internal stack.
- Reduce: When the symbols pushed onto the stack already form the right-hand side of a rule, it pops all the right-hand-side symbols and pushes the corresponding left-hand-side symbol; after a reduction, the code associated with the rule is executed.
Shift/Reduce Conflicts and Operator Precedence
- Precedence can be described separately from the grammar rules. The order in which
%left,%right, and%noassocappear determines precedence from low to high. %leftmeans left-associative,%rightmeans right-associative,%noassocmeans non-associative.- Don’t overuse precedence rules. Except for expression grammars or resolving the “dangling else” conflict in
if/then/elsestructures, try to fix the grammar itself to resolve conflicts. - There are two kinds of conflicts: shift/reduce and reduce/reduce.
- Embedded actions: an action placed in the middle of a rule is turned into a new rule of its own; this can sometimes cause a shift/reduce conflict.
Precedence and associativity declarations resolve grammar ambiguity. The %prec declaration sets a rule’s precedence. On a shift/reduce conflict, the parser compares the precedence of the shift token with that of the reduce rule; if the precedence is equal, it checks associativity — left-associative means reduce, right-associative means shift. The classic application is if/then/else (the dangling-else ambiguity).
Suppose we are analyzing a language that has both if-then and if-then-else statements, with the following rules:
if_stmt: IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;Here we assume IF, THEN, and ELSE are special keyword terminals. When the ELSE terminal is read in as a lookahead token, the contents of the stack (assuming the input is valid) can already be reduced onto the first rule. But shifting it onto the stack is also valid, because then — following the second rule — it would eventually lead to a reduction. In this situation, both shifting and reducing are legal; this is called a shift-reduce conflict. Bison’s design is to resolve the conflict by shifting, unless there is an operator-precedence declaration. To explain why this choice is made, let’s compare it with the alternatives.
What to Do When You Hit a shift/reduce Conflict?
When you hit one, first locate where the conflict occurs. You can run bison -v (which generates an .out log file) and inspect gram.out (generated from gram.y) to locate the problem, then fix it.
Debugging the Query-Analysis Module
To print the bison syntax-analysis trace:
Remove the comment on line 7 and change it to define YYDEBUG 1;