openGauss数据库源码解析系列文章——SQL引擎源码解析（1.2）

二、SQL解析

1970年，埃德加·科德（Edgar Frank Codd）发表了关系模型的论文，奠定了关系数据库的理论基础，随后在1974年，Boyce和Chamber在关系模型的基础上推出了Sequel语言，后来演进成了SQL（structured auery language，结构化查询语言）语言。SQL语言是一种基于关系代数和关系演算的非过程化语言，它指定用户需要对数据操作的内容，而不指定如何去操作数据，具有非过程化、简单易学、易迁移、高度统一等特点。因此，SQL语言在推出之后就快速地成为数据库中占比最高的语言。

SQL语句在数据库管理系统中的编译过程符合编译器实现的常规过程，需要进行词法分析、语法分析和语义分析。

（1） 词法分析：从查询语句中识别出系统支持的关键字、标识符、操作符、终结符等，确定每个词自己固有的词性。常用工具如flex。

（2） 语法分析：根据SQL语言的标准定义语法规则，使用词法分析中产生的词去匹配语法规则，如果一个SQL语句能够匹配一个语法规则，则生成对应的抽象语法树（abstract synatax tree，AST）。常用工具如Bison。

（3） 语义分析：对抽象语法树进行有效性检查，检查语法树中对应的表、列、函数、表达式是否有对应的元数据，将抽象语法树转换为查询树。

openGuass的SQL解析代码主流程可以用图2来表示。执行SQL命令的入口函数是exec_simple_query。用户输入的SQL命令会作为字符串sql_query_string传给raw_parser函数，由raw_parser函数调用base_yyparse进行词法分析和语法分析，生成语法树添加到链表parsetree_list中。完成语法分析后，对于parsetree_list中的每一颗语法树parsetree，openGuass会调用parse_analyze函数进行语义分析，根据SQL命令的不同，执行对应的入口函数，最终生成查询树。

图2 SQL解析代码主流程

词法结构和语法结构分别由scan.l和gram.y文件定义，并通过flex和bison分别编译成scan.cpp和gram.cpp文件。SQL解析的相关源文件说明如表1所示。

表1 词法结构和语法结构源文件说明

（一） 词法分析

openGauss采用flex和bison两个工具来完成词法分析和语法分析的主要工作。对于用户输入的每个SQL语句，它首先交由flex工具进行词法分析。flex工具通过对已经定义好的词法文件进行编译，生成词法分析的代码。

openGauss中的词法文件是scan.l，它根据SQL语言标准对SQL语言中的关键字、标识符、操作符、常量、终结符进行了定义和识别。

其中的operator即为操作符的定义，从代码中可以看出，operator是由多个op_chars组成的，而op_chars则是[\~\!\@\#\^\&\|\`\?\+\-\*\/\%\<\>\=]中的任意一个符号。

但这样的定义还不能满足SQL的词法分析的需要，因为并非多个op_chars的组合就能形成一个合法的操作符，因此在scan.l中会对操作符进行更明确的定义（或者说检查）。

从operator的定义过程中可以看到其中有一些以yy开头的变量和函数，它是Lex工具的内置变量和函数，如表2所示。

表2 变量和函数说明

在编译的过程中，scan.l会被编译成scan.cpp文件，从parser目录的Makefile文件中可以看到编译的命令。

词法分析将一个SQL划分成多个不同的token，每个token会有自己的词性，在scan.l中定义了如下词性。词性说明请参考表3。

表3 词法分析词性说明

openGauss在kwlist.h中定义了大量的关键字，按照字母的顺序排列，方便在查找关键字时通过二分法进行查找。

在scan.l中处理“标识符”时，会到关键字列表中进行匹配，如果一个标识符匹配到关键字，则认为是关键字，否则才是标识符，即关键字优先。

（二） 语法分析

openGuass中定义了bison工具能够识别的语法文件gram.y，同样在Makefile中可以通过bison工具对gram.y进行编译，生成gram.cpp文件。

在openGauss中，根据SQL语言的不同定义了一系列表达Statement的结构体（这些结构体通常以Stmt作为命名后缀），用来保存语法分析结果。

这个结构体可以看作一个多叉树，每个叶子节点都表达了SELECT查询语句中的一个语法结构，对应到gram.y中，它会有一个SelectStmt。

simple_select除了上面的基本形式，还可以表示为其他形式，如VALUES子句、关系表达式、多个SELECT语句的集合操作等，这些形式会进一步的递归处理，最终转换为基本的simple_select形式。

从simple_select语法分析结构可以看出，一条简单的查询语句由以下子句组成：去除行重复的distinctClause、目标属性targetList、SELECT INTO子句intoClause、FROM子句fromClause、WHERE子句whereClause、GROUP BY子句groupClause、HAVING子句havingClause、窗口子句windowClause和plan_hint子句。在成功匹配simple_select语法结构后，将会创建一个Statement结构体，将各个子句进行相应的赋值。对simple_select而言，目标属性、FROM子句、WHERE子句是最重要的组成部分。

目标属性对应语法定义中的target_list，由若干个target_el组成。target_el可以定义为表达式、取别名的表达式和“*”等。

当成功匹配到一个target_el后，会创建一个ResTarget结构体，用于存储目标对象的全部信息。

FROM子句对应语法定义中的from_clause，由FROM关键字和from_list组成，而from_list则由若干个table_ref组成。table_ref可以定义为关系表达式、取别名的关系表达式、函数、SELECT语句、表连接等形式。

以FROM子句中的关系表达式为例，最终会定义为ColId的相关形式，表示为表名、列名等的定义。

在捕获到ColId后，会创建一个RangeVar结构体，用来存储相关信息。RangeVar结构如下。

WHERE子句给出了元组的约束信息，对应语法定义中的where_clause，由WHERE关键字和一个表达式组成。

表达式可以为一个常量表达式或者属性，也可以为子表达式的运算关系。

对于运算关系，会调用makeSimpleA_Expr函数生成A_Expr结构体，存储表达式的相关信息。A_Expr结构如下，字段lexpr和rexpr分别保存左、右两个子表达式的相关信息。

simple_select的其他子句，如distinctClause、groupClause、havingClause等，语法分析方式类似。而其他SQL命令，如CREATE、INSERT、UPDATE、DELETE等，处理方式与SELECT命令类似，这里不做一一说明。

对于任何复杂的SQL语句，都可以拆解为多个基本的SQL命令执行。在完成词法分析和语法分析后，raw_parser函数会将所有的语法分析树封装为一个List结构，名为raw_parse_tree_list，返回给exec_simple_query函数，用于后面的语义分析、查询重写等步骤，该List中的每个ListCell包含一个语法树。

（三） 语义分析

语义分析模块在词法分析和语法分析之后执行，用于检查SQL命令是否符合语义规定，能否正确执行。负责语义分析的是parse_analyze函数，位于analyze.cpp下。parse_analyze会根据词法分析和语法分析得到的语法树，生成一个ParseState结构体用于记录语义分析的状态，再调用transformStmt函数，根据不同的命令类型进行相应的处理，最后生成查询树。

ParseState保存了许多语义分析的中间信息，如原始SQL命令、范围表、连接表达式、原始WINDOW子句、FOR UPDATE/FOR SHARE子句等。该结构体在语义分析入口函数parse_analyze下被初始化，在transformStmt函数下根据不同的Stmt存储不同的中间信息，完成语义分析后再被释放。

在语义分析过程中，语法树parseTree使用Node节点进行包装。Node结构只有一个类型为NodeTag枚举变量的字段，用于识别不同的处理情况。比如SelectStmt 对应的NodeTag值为T_SelectStmt。Node结构如下。

typedef struct Node {    
NodeTag type;
} Node;

transformStmt函数会根据NodeTag的值，将语法树转化为不同的Stmt结构体，调用对应的语义分析函数进行处理。openGauss在语义分析阶段处理的NodeTag情况有九种，详细请参考表4。

表4 NodeTag情况说明

以处理基本SELECT命令的transformSelectStmt函数为例，其处理流程如下。

（1） 创建一个新的Query节点，设置commandType为CMD_SELECT。

（2） 检查SelectStmt是否存在WITH子句，存在则调用transformWithClause处理。

（3） 调用transformFromClause函数处理FROM子句。

（4） 调用transformTargetList函数处理目标属性。

（5） 若存在操作符“+”则调用transformOperatorPlus转为外连接。

（6） 调用transformWhereClause函数处理WHERE子句和HAVING子句。

（7） 调用transformSortClause函数处理ORDER BY子句。

（8） 调用transformGroupClause函数处理GROUP BY子句。

（9） 调用transformDistinctClause函数或者transformDistinctOnClause函数处理DISTINCT子句。

（10） 调用transformLimitClause函数处理LIMIT和OFFSET子句。

（11） 调用transformWindowDefinitions函数处理WINDOWS子句。

（12） 调用resolveTargetListUnknowns函数将其他未知类型作为text处理。

（13） 调用transformLockingClause函数处理FOR UPDATE子句。

（14） 处理其他情况，如insert语句、foreign table等。

（15） 返回查询树。

下面对FROM子句、目标属性、WHERE子句的语义分析过程进行说明，SELECT语句的其他部分语义分析方式与此类似，不做赘述。

处理目标属性的入口函数是transformTargetList，函数的传参包括结构体ParseState和目标属性链表targetlist。transformTargetList会调用transformTargetEntry来处理语法树下目标属性的每一个ListCell，最终将语法树ResTarget结构体的链表转换为查询树TargetEntry结构体的链表，每一个TargetEntry表示查询树的一个目标属性。

TargetEntry结构如下。其中resno保存目标属性的编号（从1开始计数），resname保存属性名，resorigtbl和resorigcol分别保存目标属性源表的OID和编号。

FROM子句由transformFromClause函数进行处理，最后生成范围表。该函数的主要传参除了结构体ParseState，还包括分析树SelectStmt的fromClause字段。fromClause是List结构，由FROM子句中的表、视图、子查询、函数、连接表达式等构成，由transformFromClauseItem函数进行检查和处理。

transformFromClauseItem会根据fromClause字段的每个Node生成一个或多个RangeTblEntry结构，加入ParseState的p_rtable字段指向的链表中，最终生成查询树的rtable字段也会指向该链表。

处理WHERE子句的入口函数是transformWhereClause，该函数调用transformExpr将分析树SelectStmt下whereClause字段表示的WHERE子句转换为一颗表达式树，然后将ParseState的p_joinlist所指向的链表和从WHERE子句得到的表达式树包装成FromExpr结构，存入查询树的jointree。

transformStmt函数完成语义分析后会返回查询树。一条SQL语句的每个子句的语义分析结果会保存在Query的对应字段中，比如targetList存储目标属性语义分析结果，rtable存储FROM子句生成的范围表，jointree的quals字段存储WHERE子句语义分析的表达式树。

（四） 解析流程分析

在了解了SQL解析的大致流程后，通过一个具体的案例了解一下SQL解析过程中的具体代码流程。首先创建基表warehouse，语句如下。

CREATE TABLE warehouse
(
    w_id SMALLINT PRIMARY KEY,
    w_name VARCHAR(10) NOT NULL,
    w_street_1 VARCHAR(20) CHECK(LENGTH(w_street_1)<>0),
    w_street_2 VARCHAR(20) CHECK(LENGTH(w_street_2)<>0),
    w_city VARCHAR(20),
    w_state CHAR(2) DEFAULT 'CN',
    w_zip CHAR(9),
    w_tax DECIMAL(4,2),
    w_ytd DECIMAL(12,2)
);

warehouse表被创建之后，会在pg_class系统表中生成一条元数据，元数据中的OID属性用来用来代表这个表，比如在pg_attribute表中就通过这个OID来标明这些属性是属于哪个表的。假设warehouse的OID为16000，下面以查询语句SELECT w_name FROM warehouse WHERE w_no = 1为例，来分析SQL分析的整体流程。

如表5所示，scan.l会划分SQL语句中的各个token及其词性，利用关键字列表匹配到关键字SELECT、FROM、WHERE，并将其他单词w_name、warehouse、w_no标记为标识符，将符号“=”识别为操作符，“1”识别为整数型常量。

表5 token及其词性

在完成SQL语句的词法分析后，scan.l生成词法分析结果，代码如下：

SELECT IDENT FROM IDENT WHERE IDENT “=” ICONST

gram.y文件会利用语法规则进行解析，生成语法树。如图3所示，对于本节给出的SQL语句，openGauss会匹配SelectStmt下的simple_select语法生成语法树，进而根据目标属性、FROM子句和WHERE子句创建ResTarget、RangeVar、A_Expr三个结构体，这三个结构体分别存储在语法树的target_list、from_clause、where_clause字段下，如果没有其他子句，对应字段为空。

图3 gram.y文件解析流程

图4给出了语法树的内存组织结构。一个查询语法树SelectStmt的目标属性是包含若干ResTarget的targetList链表、fromClause和whereClause。

（1） targetList链表中ResTarget字段val会根据目标属性的类型，指向不同的结构体。对于本节给出的用例，val指向结构体ColumnRef，存储目标属性在源表中的具体信息。

（2） fromClause存储FROM子句的指向对象，同样是包含若干个RangeVar结构体的链表，每个RangeVar存储范围表的具体信息。对于本节给出的用例，只有一个RangeVar结构体，字段relname值为warehouse。

（3） whereClause为Node结构，存储WHERE子句包含的范围表达式，根据表达式的不同，使用不同的结构体存储，如列引用ColumnRef、参数引用ParamRef、前缀/中缀/后缀表达式A_Expr、常量A_Const。对于本节给出的用例，使用A_Expr来存储表达式对象，并分别使用ColumnRef和A_Const存储左、右两个子表达式的具体信息。

图4 语法树内存组织结构图

在完成词法分析和语法分析后，parse_analyze函数会根据语法树的类型，调用transformSelectStmt将parseTree改写为查询树。在改写过程中，parse_analyze除了会检查SQL命令是否符合语义规定，还会根据语法树对象获得更有利于执行的信息，比如表的OID、列的编号等。对于本节给出的用例，查询树对应的内存组织结构如图5所示，目标属性、FROM子句和WHERE子句的语义分析结果会分别保存在结构体TargetEntry、RangeTblEntry、FromExpr中。

图5 查询树内存组织结构图

完成语义分析后，SQL解析过程完成，SQL引擎开始执行查询优化。