查询编译
概述
查询处理器是数据库管理系统的一个部件集合，它允许用户使用 SQL 语言表达查询。查询处理分为查询编译和查询执行。
-
查询编译：根据用户的查询语句生成最优执行计划
-
查询执行：考虑执行计划中采用的算法等问题
查询分析
查询分析是查询编译的第一个模块，将用户输入的 SQL 命令转换成查询树，基本流程如下图：
查询分析中主要函数调用：
因此，查询分析的处理过程如下：
-
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； -
exec_simple_query函数调用函数pg_analyze_and_rewrite进行语义分析(调用parse_analyze函数，返回查询树)和查询重写(调用pg_rewrite_query函数)； -
返回查询树链表给
exec_simple_query。
词法分析和语法分析
在 "raw_parser" 中，通过 Lex 和 Yacc 生成的代码进行词法和语法分析生成分析树。通过调用 Lex 和 Yacc 预生成的函数 base_yyparse 来实现词法和语法分析。
-
Lex 用来生成扫描器，识别数字、字符串、特殊符号等，然后传给 Yacc
-
Yacc 用来生成语法分析器
它们通过内置变量 yylval 传递表达的值
1、词法分析工具 Lex
词法分析主要工作是利用正则表达式在给定字符序列中进行模式匹配，这些正则表达式写在后缀为 ".l" 的文件（Lex文件）中，通过 Lex 命令可以从 Lex 文件生成一个包含扫描器的C语言源码，其他源码可以调用该扫描器来实现词法分析。
Lex 文件分为三段，各段之间用 %% 分隔：
-
定义段：包含 C头文件、符号说明等，直接拷贝到生成的扫描器代码文件
-
规则段：利用正则表达式来匹配模式。每当成功匹配一个模式，就对应其后的 { } 代码段
-
代码段：可以是任意C代码，但是其中必须要调用 Lex 提供的函数
2、语法分析工具 Yacc
Yacc 将语法的定义和必要C代码写在 ".y" 文件（Yacc文件）中，然后使用 Yacc 命令由该文件生成具有语法分析功能的C代码。
Yacc 文件分为三段，各段之间用 %% 分隔：
-
定义段：可以是C代码如头文件和函数声明，也可以定义 Yacc 内部标志
-
规则段：表示语法规则。每识别一个语法规则后，根据其后的 { } 代码进行相应的处理操作
-
代码段：包含C代码，被直接拷贝到生成的C文件中。也包含 Yacc 函数和一些 Lex 传给 Yacc 的变量
Yacc 是无法单独运行的，要配合 Lex 使用，其相互调用关系如下图所示。
语义分析
语义分析检查命令中是否有不符合语义规定的成分，比如表、属性是否存在，聚集函数是否合法使用。
exec_simply_query从词法和语法分析获取了 parsetree_list 之后，会对每棵分析树调用 pg_analyze_and_rewrite进行语义分析和查询重写。负责语义分析的是函数parse_analyze，该函数会根据分析树生成一个对应的查询树。在 parse_analyze 函数中，根据分析树的 node_Tag，函数 transformStmt 将命令分为若干种情况处理，经过语义分析之后会生成查询树（Query结构）。其中 SELECT/INSERT/DELETE/UPDATE 这四种情况生成的查询树会经由查询重写和查询优化做进一步处理。
查询重写
在完成语义分析得到查询树之后，会立刻对查询树进行查询重写处理。查询重写的入口函数是 pg_rewrite_query。
pg_rewrite_query函数通过调用QueryRewrite函数来完成查询树的重写。QueryRewrite函数是查询重写模块的主过程，完成了以下操作：-
用非SELECT规则将一个查询重写为0个或多个查询，此处调用
RewriteQuery函数 -
对上一步得到的每个查询分别使用 RIR 规则进行重写，此处调用
fireRIRrules函数 -
返回重写后的查询树
RewriteQuery函数的作用是处理 SELECT 以外的语句：-
首先寻找含有 INSERT/UPDATE/DELETE 的 WITH 子句。如果存在，那么就调用自身递归地重写它们
-
对 INSERT/UPDATE/DELETE 语句，调整它们的 TargetList，然后执行对应的重写规则
-
得到0个或多个查询并返回
非 SELECT 规则处理完了，调用
fireRIRrules函数执行 SELECT 规则的重写：-
对查询树的每一个范围表(RTE)：如果RTE是子查询，调用自身递归地重写它们；如果是一个表，并且在查询树中被引用了，则调用
ApplyRetrieveRule函数处理它 -
对于公共表表达式(CTE)，也递归地调用
fireRIRrules函数重写 -
对于查询树的子查询，调用
query_tree_walker遍历子查询，调用fireRIRonSubLink函数进行查询重写 -
返回重写后的查询树
查询规划
查询分析工作完成之后，其最终产物——查询树链表被移交给查询规划模块，该模块入口函数为
pg_plan_queries，它负责对每个查询树进行处理，并将生成的 PlannedStmt 结构体构成链表（执行计划链表）返回。pg_plan_query中负责实际计划生成的是planner函数，从planner函数开始就进入了执行计划的生成阶段。
planner函数会调用standard_planner函数进入标准的查询规划处理。预处理按照“先做选择，后做连接”的思想改造查询树。预处理完成后，当要处理的表存在继承关系时函数
inheritance_planner会将其处理成非继承关系的表，然后调用函数grouping_planner处理。函数
grouping_planner将查询信息规范化，传递给函数query_planner，生成代价最小路径 cheapest_path 和 排序路径 sorted_path。后续通过相关算法将生成的完整计划经过计划树整理之后就可以交给查询执行器去执行。
查询执行
查询编译器将用户提交的 SQL 查询语句转变成执行计划之后，由执行器继续执行查询的处理过程。
执行器四个主要子模块：策略选择、两种执行方式（Executor、功能处理器 ProcessUtility）、特定功能子模块
在 PG 中，SQL 语句被分为两类：
-
可优化语句：主要包括 DML 语句，可优化语句包含一个或多个经过重写和优化过的查询计划树，使用执行器（Executor）进行处理。
-
数据定义语句：包括数据表创建等操作，使用功能处理器模块（ProcessUtility）进行处理。
查询执行策略
从查询编译器输出执行计划，到执行计划被具体的执行部件处理这一过程，被称为执行策略的选择。PG 定义了四种执行策略，定义为执行策略枚举类型
PortalStrategy-
PORTAL_ONE_SELECT：处理 SELECT 语句
-
PORTAL_ONE_RETURNING：面向 UPDATE/INSERT/DELETE 等需要进行元组操作且需要缓存结果的语句
-
PORTAL_UTIL_SELECT：面向单一数据定义语句
-
PORTAL_MULTI_QUERY：前面三种类型的混合策略，可以处理多个原子操作
执行策略选择器会使用数据结构 PortalData 存储计划树链表以及最后选中的执行策略，查询执行器执行一个 SQL 语句都以一个 Portal 作为输入数据。
typedef struct PortalData
{
const char *name; // Portal 的名称
const char *sourceText; // 原始 SQL 语句
List *stmts; // 查询编译器输出的查询计划树链表
PortalStrategy strategy; // 当前查询选择的执行策略
PortalStatus status; // Portal 的状态
QueryDesc *queryDesc; // 查询描述符，存储执行查询所需的所有信息
TupleDesc tupDesc; // tupDesc 描述可能的返回元组的结构
...;
};PortalData;执行策略的选择通过函数
ChoosePortalStrategy("src/backend/tcop/pquery.c")实现，其输入为List *stmts（PortalData 的 stmts 计划树链表），输出的是预先定义的执行策略枚举类型 PortalStrategy。Protal的执行过程：
数据定义语句执行流程
数据定义语句用于定义数据模式、函数等功能性语句。数据定义语句的执行流程最终都会进入到 ProcessUtility 处理器，
ProcessUtility通过判断数据结构中 NodeTag 字段的值来区分不同节点，并进入相应处理函数。
可优化语句执行
可优化语句的共同特点是它们被查询编译器处理后都会生成查询计划树，这一类语句由执行器（Executor）处理。该模块对外提供了三个接口：ExecutorStart、ExecutorRun 和 ExecutorEnd，其输入是包含查询计划树的数据结构 QueryDesc，输出则是相关执行信息或结果数据。
执行器对查询计划树的处理，最终转换为针对计划树上每个节点的处理。每种节点表示一种物理代数（Physical Algebra）操作，PG 对其进行初始化、处理、清理的过程。
节点的处理被设计为需求驱动模式，父节点使用孩子节点提供的数据作为输入，并向其上层节点返回处理结果。实际执行时，从根节点开始处理，每个节点的执行过程会根据需求自动调用孩子节点的执行过程来获取输入数据（一般为元组），从而层层递归执行，实现整个计划树的遍历执行。节点的初始化和处理也被设计成相同的模式，这种设计模式使得节点处理的代码简洁统一。
物理代数与执行器模型
PG 使用 SQL 语句，而执行时需要使用物理代数，所以对于一个可优化语句，PG执行前会给出与之等价的物理代数表示的查询计划。逻辑操作符与物理操作符并不是简单的一一对应关系，前面的查询编译器将 SQL语句转换为物理代数。
对于一个查询计划实例，如上图所示，PG 中物理操作符被定义有0~2个输入，1个输出，对应二叉树结构。数据（元组）从底向上流动，直至根节点。PG 中执行器采用火山模型，该计算模型将关系代数中每一种操作抽象为一个 Operator，将整个 SQL 构建成一个 Operator 树，从根节点到叶子结点自上而下地递归调用 next() 函数获取数据行。
在 PG 中，通过 ExecInitNode 、ExecProcNode、ExecEndNode 三个接口函数来统一对节点进行初始化、执行和清理。这三个函数会根据所处理节点的实际类型调用相应的初始化、执行、清理函数，例如 ExecInitSeqScan 函数用于完成 SeqScan 节点的初始化。
同时 ExecInitNode 、ExecProcNode、ExecEndNode 这三个函数也是递归调用的：
-
对根节点的初始化会递归地对下层节点初始化；
-
在根节点调用 ExecProcNode 获取结果时也会递归地对下层节点进行执行以获取上层节点所需的数据；
-
执行完后只需对根节点处理，下层节点也会被递归地清理。
执行器的执行
PG 中提供三个接口函数用于调用执行器：
ExecutorStart、ExecutorRun、ExecutorEnd
一条 SQL 语句的执行过程：
