背景
He3DB for PostgreSQL是受Aurora论文启发，基于开源数据库PostgreSQL 改造的数据库产品。架构上实现计算存储分离，并进一步支持数据的冷热分层，大幅提升产品的性价比。
He3DB for PostgreSQL中查询编译的主要任务是根据用户的查询语句生成数据库中最优执行计划，在此过程中要考虑视图、规则以及表的连接路径等问题。
一、概述
查询分析中词法分析和语法分析分别借助词法分析工具Lex和语法分析工具 Yacc来完成各自的工作。涉及的主要函数如下所示：
1.exec_simple_query;
2. |->pg_parse_query;
3. |->raw_parser;
- exec_simple_query函数(在src/backend/tcop/postgres.c下)调用函数pg_parse_query进入词法分析和语法分析的主过程，函数pg_parse_query再调用词法分析和语法分析的入口函数raw_parser生成分析树；
- 函数pg_parse_query返回分析树(raw_parsetree_list)给exec_simple_query；
postgres命令的词法分析和语法分析是由Unix工具Lex和Yacc制作的。
1）Lex为词法分析工具，用来识别一个一个模式，例如数字、字符串、特殊符号等。
2）Yacc为语法分析工具，用来识别数字、字符串、特殊符号的组合
它们依赖的文件定义在src\backend\parser下的scan.l和gram.y。
其中：Lex词法器在文件 scan.l里定义。负责识别标识符，SQL 关键字等，对于发现的每个关键字或者标识符都会生成一个记号并且传递给分析器;
Yacc分析器在文件 gram.y里定义。包含一套语法规则和触发规则时执行的动作.
在raw_parser函数(在src/backend/parser/parser.c下)中，主要通过调用Lex和Yacc配合生成的base_yyparse函数来实现词法分析和语法分析的工作。
重要的文件如下：
值得一提的是，如果你想修改postgresql的语法，你要关注下两个文件“gram.y”和“kwlist.h”。简要地说就是将新添加的关键字添加到kwlist.h中，同时修改gram.y文件中的语法规则，然后重新编译即可。
文件间的调用关系，如下图所示：
二、语法分析树
查询命令在经过此法与与语法分析后会生成语法分析树、语法分析树的根节点是一个定义在parsenodes.h中的SelectStmt数据结构。图(a)展示了一个查询，而图(b)则是该查询对应的语法解析树（抽象语法树AST）。
1.typedef struct SelectStmt
2.{
3. NodeTag type;
4.
5. /* 这些字段只会在SelectStmts“叶节点”中使用 */
6. List *distinctClause; /* NULL, DISTINCT ON表达式列表, 或
7. 对所有的(SELECT DISTINCT)为lcons(NIL,NIL) */
8. IntoClause *intoClause; /* SELECT INTO 的目标 */
9. List *targetList; /* 结果目标列表 (ResTarget) */
10. List *fromClause; /* FROM 子句 */
11. Node *whereClause; /* WHERE 限定条件 */
12. List *groupClause; /* GROUP BY 子句 */
13. Node *havingClause; /* HAVING 条件表达式 */
14. List *windowClause; /* WINDOW window_name AS (...), ... */
15.
16. /* 在一个表示值列表的叶节点中，上面的字段全都为空，而这个字段会被设置。
17. * 注意这个子列表中的元素仅仅是表达式，没有ResTarget的修饰，还需要注意列表元素可能为
18. * DEFAULT (表示一个 SetToDefault 节点)，而无论值列表的上下文。
19. * 由分析阶段决定否合法并拒绝。 */
20. List *valuesLists; /* 未转换的表达式列表 */
21.
22. /* 这些字段会同时在SelectStmts叶节点与SelectStmts上层节点中使用 */
23. List *sortClause; /* 排序子句 (排序依据的列表) */
24. Node *limitOffset; /* 需要跳过的元组数目 */
25. Node *limitCount; /* 需要返回的元组数目 */
26. List *lockingClause; /* FOR UPDATE (锁子句的列表) */
27. WithClause *withClause; /* WITH 子句 */
28.
29. /* 这些字段只会在上层的 SelectStmts 中出现 */
30. SetOperation op; /* set 操作的类型 */
31. bool all; /* 是否指明了 ALL 选项? */
32. struct SelectStmt *larg; /* 左子节点 */
33. struct SelectStmt *rarg; /* 右子节点 */
34.} SelectStmt;
SELECT查询中的元素和语法解析树中的元素有着对应关系。比如，(1)是目标列表中的一个元素，与目标表的’id’列相对应，(4)是一个WHERE子句，诸如此类。
当解析器生成语法分析树时只会检查语法，只有当查询中出现语法错误时才会返回错误。解析器并不会检查输入查询的语义，举个例子，如果查询中包含一个不存在的表名，解析器并不会报错，语义检查由分析器负责。
三、具体函数分析
3.1 raw_parser
1.List *raw_parser(const char *str, RawParseMode mode) {
2. // 定义Flex扫描器的上下文
3. core_yyscan_t yyscanner;
4. // 定义Bison解析器的额外数据结构
5. base_yy_extra_type yyextra;
6. // 定义变量，用于存储Bison解析器的返回结果
7. int yyresult;
8. // 初始化Flex扫描器
9. yyscanner = scanner_init(str, &yyextra.core_yy_extra, &ScanKeywords, ScanKeywordTokens);
10. // 根据传入的解析模式设置前瞻标记
11. if (mode == RAW_PARSE_DEFAULT) {
12. // 默认模式，不使用前瞻标记
13. yyextra.have_lookahead = false;
14. } else {
15. // 非默认模式，使用前瞻标记
16. yyextra.have_lookahead = true;
17. // 定义一个静态数组，存储不同模式对应的标记
18. static const int mode_token[] = {
19. 0, // RAW_PARSE_DEFAULT
20. MODE_TYPE_NAME, // RAW_PARSE_TYPE_NAME
21. MODE_PLPGSQL_EXPR, // RAW_PARSE_PLPGSQL_EXPR
22. MODE_PLPGSQL_ASSIGN1, // RAW_PARSE_PLPGSQL_ASSIGN1
23. MODE_PLPGSQL_ASSIGN2, // RAW_PARSE_PLPGSQL_ASSIGN2
24. MODE_PLPGSQL_ASSIGN3 // RAW_PARSE_PLPGSQL_ASSIGN3
25. };
26. // 设置前瞻标记为对应模式的值
27. yyextra.lookahead_token = mode_token[mode];
28. // 初始化前瞻标记的位置信息
29. yyextra.lookahead_yylloc = 0;
30. // 初始化前瞻标记的结束位置
31. yyextra.lookahead_end = NULL;
32. }
33. // 初始化Bison解析器，传入额外数据结构的地址
34. parser_init(&yyextra);
35. // 调用Bison解析器进行解析，并将结果存储在yyresult中
36. yyresult = base_yyparse(yyscanner);
37. // 清理Flex扫描器使用的资源
38. scanner_finish(yyscanner);
39. // 如果解析失败（yyresult非零），返回NIL表示没有解析树
40. if (yyresult) return NIL;
41. // 如果解析成功，返回解析生成的解析树
42. return yyextra.parsetree;
43.}
1.
List *raw_parser(const char *str, RawParseMode mode)
函数声明，返回一个列表指针，接收两个参数：一个字符串str和一个枚举类型RawParseMode的mode。
(1) RawParseMode 是一个枚举类型，它在 raw_parser 函数中定义了不同的解析模式。
(2) RAW_PARSE_DEFAULT: 默认解析模式，不使用前瞻标记，解析器将根据输入的文本内容进行标准解析。
(3) RAW_PARSE_TYPE_NAME: 用于解析类型名称的模式。这可能涉及到特定的语法规则，比如在某些语言中类型名称可能有特定的格式或关键字。
(4) RAW_PARSE_PLPGSQL_EXPR: 用于解析 PL/pgSQL 表达式的模式。PL/pgSQL 是 PostgreSQL 数据库的过程语言，这个模式可能用于解析特定的 SQL 表达式结构。
(5) RAW_PARSE_PLPGSQL_ASSIGN1,RAW_PARSE_PLPGSQL_ASSIGN2, RAW_PARSE_PLPGSQL_ASSIGN3: 这些模式可能用于解析 PL/pgSQL 中的赋值语句，每个模式可能对应不同的赋值语法或上下文。
例子：
本文使用如下例子作为相关示例
CREATE TABLE tbl_a (
id INT PRIMARY KEY,
data VARCHAR(255) -- 假设data是字符串，长度限制为255
);
INSERT INTO tbl_a (id, data) VALUES
(1, 'Apple'),
(50, 'Banana'),
(150, 'Cherry'),
(250, 'Date'),
(299, 'Elderberry');
SELECT id, data FROM tbl_a WHERE id < 300 ORDER BY data;
2.
core_yyscan_t yyscanner; base_yy_extra_type yyextra;
core_yyscan_t为void *，base_yy_extra_type为一个结构体。
Flex和Bison是两个在编译领域广泛使用的工具，它们通常配合使用来构建编译器的前端。Flex是一个用于生成词法分析器（lexical analyzer）的工具对应于Lex，而Bison是一个用于生成语法分析器（parser）的工具,对应于Yacc。
3.
yyscanner = scanner_init(...)
调用scanner_init函数位于scan.c文件中，用于初始化Flex扫描器，传入字符串str，yyextra的地址，以及关键词和关键字对应的标记。
4.
if (mode == RAW_PARSE_DEFAULT) {
// 默认模式，不使用前瞻标记
yyextra.have_lookahead = false;
} else {
// 非默认模式，使用前瞻标记
yyextra.have_lookahead = true;
// 定义一个静态数组，存储不同模式对应的标记
static const int mode_token[] = {
0, // RAW_PARSE_DEFAULT
MODE_TYPE_NAME, // RAW_PARSE_TYPE_NAME
MODE_PLPGSQL_EXPR, // RAW_PARSE_PLPGSQL_EXPR
MODE_PLPGSQL_ASSIGN1, // RAW_PARSE_PLPGSQL_ASSIGN1
MODE_PLPGSQL_ASSIGN2, // RAW_PARSE_PLPGSQL_ASSIGN2
MODE_PLPGSQL_ASSIGN3 // RAW_PARSE_PLPGSQL_ASSIGN3
};
// 设置前瞻标记为对应模式的值
yyextra.lookahead_token = mode_token[mode];
// 初始化前瞻标记的位置信息
yyextra.lookahead_yylloc = 0;
// 初始化前瞻标记的结束位置
yyextra.lookahead_end = NULL;
代码片段中，yyextra.have_lookahead是一个标志，用于指示是否使用前瞻标记。如果mode设置为RAW_PARSE_DEFAULT，则不使用前瞻标记，yyextra.have_lookahead被设置为false。否则，将使用前瞻标记，并且yyextra.have_lookahead被设置为true。
static const int mode_token[]是一个静态数组，它定义了不同模式对应的标记。这个数组用于根据当前的解析模式来确定应该使用哪种类型的token作为前瞻。例如，如果当前模式是RAW_PARSE_TYPE_NAME，则mode_token[RAW_PARSE_TYPE_NAME]将提供对应的token类型。
使用前瞻标记的一些好处包括：
a.解决歧义：前瞻可以帮助解析器解决语法中的歧义问题，特别是在复杂的语言结构中。
b.提高效率：在某些情况下，使用前瞻可以避免回溯，提高解析的效率。
c.增强灵活性：前瞻允许解析器根据更多的上下文信息来做出决策，从而增强解析器的灵活性。
在实际应用中，前瞻标记通常与解析器的设计紧密相关，它们是构建高效、健壮解析器的关键技术之一。
5. 最终输出
3.2 pg_parse_query
1.List *pg_parse_query(const char *query_string)
2.{
3. List *raw_parsetree_list; /* 用于存储原始分析树的列表 */
4. /*
5. * 该宏用于跟踪和记录查询解析过程的开始
6. */
7. TRACE_POSTGRESQL_QUERY_PARSE_START(query_string);
8. /*
9. * 用来指示是否应该记录解析器的统计信息，log_parser_stats默认为false
10. * ResetUsage用来重置某些统计信息的使用计数器或状态。
11. */
12. if (log_parser_stats)
13. ResetUsage();
14. /*
15. * 调用 raw_parser 函数分析查询字符串。
16. * RAW_PARSE_DEFAULT 表示使用默认的分析器标志。
17. */
18. raw_parsetree_list = raw_parser(query_string, RAW_PARSE_DEFAULT);
19. /*
20. * 如果记录分析器统计信息，显示统计结果。
21. */
22. if (log_parser_stats)
23. ShowUsage("PARSER STATISTICS");
24. /*
25. * 如果定义了 COPY_PARSE_PLAN_TREES，则执行以下调试检查：
26. *使用 copyObject 函 数复制 raw_parsetree_list 并存储在 new_list 中。
27. *使用 equal 函数比较 new_list 和 raw_parsetree_list 是否相等。
28. *如果不相等，使用 elog 函数记录一个警告。
29. *如果相等，将 raw_parsetree_list 指向 new_list。
30. */
31. #ifdef COPY_PARSE_PLAN_TREES
32. {
33. List *new_list = copyObject(raw_parsetree_list);
34. if (!equal(new_list, raw_parsetree_list))
35. elog(WARNING, "copyObject() failed to produce an equal raw parse tree");
36. else
37. raw_parsetree_list = new_list; }
38.#endif
39. /*
40. * 该宏用于跟踪和记录查询解析过程的结束
41. */
42. TRACE_POSTGRESQL_QUERY_PARSE_DONE(query_string);
43. /*
44. * 返回分析树列表。
45. */
46. return raw_parsetree_list;
47.}
总的来说，pg_parse_query函数是用于解析SQL查询字符串，它首先记录解析开始，然后调用解析器获取解析树，如果启用了统计信息记录，会显示解析统计结果。此外，如果启用了调试宏COPY_PARSE_PLAN_TREES，函数还会进行解析树的复制和比较，确保复制操作的正确性。最后，记录解析结束并返回解析树列表。
作者介绍
葛文龙，移动云数据库工程师，负责云原生数据库He3DB的研发。
