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 引擎开始执行查询优化。