SQL解析器

我们将持续分析数据库实现中涉及到的关键技术，SQL引擎、存储引擎、事务等，在SQL引擎中，第一件事就是识别用户的SQL。

SQL解析器

我们知道数据库用户通过SQL来操作数据库，那么数据库怎么识别出SQL呢？比如select * from t。编译原理好像告诉了我们答案。SQL语句在数据库管理系统中的编译过程符合编译器实现的常规过程，需要进行词法分析、语法分析和语义分析。

词法分析：从查询语句中识别出系统支持的关键字、标识符、操作符、终结符等，确定每个词自己固有的词性。词法分析是解析SQL语句的第一步，常用工具如flex。
语法分析：根据SQL语言的标准定义语法规则，使用词法分析中产生的词去匹配语法规则，如果一个SQL语句能够匹配一个语法规则，则生成对应的抽象语法树（abstract synatax tree，AST）。常用工具如Bison。
语义分析：对抽象语法树进行有效性检查，检查语法树中对应的表、列、函数、表达式是否有对应的元数据，将抽象语法树转换为查询树。

我们看一下非常流行的开源数据库PostgreSQL的实现，在PostgreSQL数据库的实现中，具体的词法分析是用flex实现的，所以我们需要学习一下flex。

flex

flex，词法分析工具，通常与bison一起协同工作。不止PG，其他很多数据库的SQL Parser中的词法语法分析部分就是用的flex和bison实现的。而数据库SQL解析器的开发有两种方案，自动生成和自己手工编写，各有利弊，PostgreSQL选择用flex和bison实现。

自动生成：利用flex，bison等工具生成C、C++目标语言的词法、语法代码。
手工编写：不用自动生成工具，自己编写这一部分的代码，好处是性能更好，针对SQL有更多的代码优化空间，不足是开发工作量大，需要长时间、大规模的测试才能趋于稳定，对开发人员要求很高。

源码在flex git source，整个代码量在1万行左右。核心原理是自动机，可以看一下源码，会对编写flex的.l文件帮助很大。

Lex解决冲突的两个规则：当输入的多个前缀与一个或多个模式匹配时，Lex用如下规则选择正确的词素：

总是选择最长的前缀
如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式

正则表达式

在应用flex前中需要理解正则表达式。那么正则表达式是干什么的呢？为什么会有正则表达式出现呢？正则表达式就是一种描述字符串结构模式的形式化表达方法。我们看几个例子：

.       匹配除换行符（“\n”）以外的任何单个字符
*       匹配前面表达式的零个或多个拷贝
[]      匹配括号中的任意字符的字符类
[a-zA-Z]+       // 匹配单词
{}      当括号中包含一个或2个数字时，指示前面的模式被允许匹配多少次，例如`A{1,3}`，表示匹配字母A一次到3次。
+       匹配前面的正则表达式的一次或多次出现。
？

正则表达式还有很多内容，比如匹配规则：

^ : 表示该模式只匹配那些以^开头的字符串,例如^once表示该模式只匹配那些以once开头的字符串
$ : 用来匹配那些以给定模式结尾的字符串，例如bucket$。

更多的我们不再叙述，接下来我们看几个flex的例子。

flex例子

先看一下最简单的例子，

/* 最简单的flex程序，echo */
%{
#include<stdio.h>
%}

%%

. | \n  ECHO        // 匹配任意字符，特殊动作ECHO输出匹配的模式

%%

void main() {
    yylex();
}

功能类似于输入什么就输出什么，下面我们看一个有实际意义的例子。其实就是写正则表达式，匹配后需要做什么工作等。

/* simple flex example 字数统计例子  fbcount.l*/

// 声明部分, 会将 %{   %} 之间的内容直接拷贝到生成的C文件
%{
#include<stdio.h>

int chars = 0;
int words = 0;
int lines = 0;
%}

// 规则部分
%%
[a-zA~Z]+   { words++; chars += strlen(yytext); }   // 变量yytext总是被设为指向本次匹配的输入文本
\n          { chars++; lines++; }                   // 匹配换行符
.           { chars++; }                            // 匹配任意字符

%%

void main() {
    printf("%8d%8d%8d\n", lines, words, chars);     // 输出统计信息
}

通过flex count.l生成lex.yy.cC程序，再编译c程序，gcc lex.yy.c -lfl，运行echo "asdf asd" | ./a.out即可查看运行结果。

再看一个例子，用flex识别单词。

%{
/* 单词识别程序 */
#include<stdio.h>

%}

%%

[\t ]+    ;  // 忽略空白      

red | 
blue | 
green |  
yellow  { printf("%s: is a color. \n",  yytext); }   // 匹配颜色

[a-zA-Z]+  { printf("%s: is not a color. \n", yytext); }  // 匹配其他单词
. | 
\n    { ECHO;}      


%%

void main() {
    yylex();
}

看懂了上面几个例子后就可以分析一下PG源码scan.l了。

PostgreSQL中的解析器

SQL解析器主要是识别用户输入的SQL语句，并将其转化为后续优化器所需要的查询树结构。对应的就是将SQL通过bison转换为RawStmt的结构，再将RawStmt转换为Query结构。代码主要在postgres/src/backend/parser这一部分，大概不到4W行代码左右。

[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
-------------------------------------------------------------------------------

以SELECT语句为例，在这一阶段，会将select * from t1转化为SelectStmt，进而转为抽象语法树RawStmt，把SQL文本字符串转为数据库可以理解的数据结构。

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;

在阅读PG源码的过程中，每个README都是必读的，下面是对应解析器部分的README：

/*
src/backend/parser/README

Parser
======
这句话最重要，解析SQL语句转换为Query结构，给Optimizer和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.
*/

也就是说，解析器解决的问题就是将合法的SQL语句转换为后续优化器或者执行器用到的Query结构。一般DDL，command等语句无需优化所以无需经过优化器可直接在执行器中执行。怎么检测输入语句是否合法呢?一个是在语法定义阶段，主要是gram.y定义了语法规则，首先要符合语法规则，这个语法规则指的是符合SQL语法规则，其次是要符合语义规则，比如要查询的表必须要存在，这就要靠检查pg_class、pg_attribute等系统表中是否有相关的表信息，列信息等进行判断。

代码部分的话，将SQL转换为抽象语法树RawStmt是pg_parse_query函数，之后调用parse_analyze将RawStmt转换为查询树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;
}

到这里一定要读一下openGauss的博文openGauss数据库源码解析系列文章——SQL引擎源码解析（一）。写的非常之好，我就不用再写了。另外非常推荐《openGauss数据库核心技术》一书，书中第7章“openGauss SQL引擎”一章值得深读。

背景知识

理解SQL解析器，就必须理解编译原理中相关的内容，这里补充一些编译原理的内容：

终结符：通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导。
非终结符：不是终结符的都是非终结符，可理解为一个可拆分元素，而终结符是不可拆分的最小元素。
移进：当语法分析器读到的记号无法结束一条规则时，将该记号压入内部堆栈；
归约：当压入堆栈的语法符号已经可以组成规则的右部时，弹出所有右部符号，把对应的左部符号入栈；归约后会执行规则关联的代码

移进/归约冲突和操作符优先级

可以在语法规则外单独描述优先级，%left %right %noassoc的出现顺序决定了由低到高的优先级
%left表示左结合、%right右结合、%noassoc表示没有结合性
不要滥用优先级规则，除了表达式语法或者解决if/then/else语言结构的”dangling else”冲突；尽量修正语法解决冲突
冲突类型有两种：移进/归约和归约/归约
嵌入动作：规则中间的动作，被构造一条新的规则。但有时会造成移进归约冲突

优先级和结合性声明：解决语法歧义和冲突。%prec声明规则的优先级，移进和归约冲突时，比较移进记号和归约规则的优先级，若优先级相同则检查结合性，左结合则归约，右结合则移进。典型应用：if/then/else dangling else ambiguity 假定我们正在分析一个语言，其中有if-then和if-then-else语句，对应的规则如下：

if_stmt: IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;

这里我们假设IF，THEN和ELSE是特别的关键字终结符。当ELSE终结符读入后作为一个预读终结符时，堆栈中的内容（假设输入是合法的）正好可以归约到第一条规则上。但是把它移进堆栈也是合理的，因为那样根据第二条规则就会导致最后的归约。在这种情况下，移进或者归约都是合法的，称为移进-归约冲突（shift-reduce conflict）。Bison的设计是，用移进来解决冲突，除非有操作符优先级声明的指令。为了解释如此选择的理由，让我们与其它可选办法进行一个比较。

遇到shift/reduce conflict怎么办？

遇到这个，首先是定位哪里出现的冲突，可通过bison -v（生成.out日志文件）查看（gram.y）生成的gram.out 从这里去定位问题发生在哪里，然后解决。

查询分析模块调试

打印bison语法分析过程：

去掉7注释，变为define YYDEBUG 1；