第3章 查询处理
查询处理是 PostgreSQL中最为复杂的子系统。如 PostgreSQL官方文档所述，PostgreSQL支持SQL2011标准中的大多数特性，查询处理子系统能够高效地处理这些SQL。本章概述了查询处理的流程，特别关注了查询优化的部分。
本章包括下列三个部分：
· 第一部分：第3.1节
这一部分会简单介绍PostgreSQL中查询处理的流程。
· 第二部分：第3.2～3.4节
这一部分会描述获取单表查询上最优执行计划的步骤。第3.2节讨论代价估计的过程，第3.3节描述创建计划树的过程，第3.4节将简要介绍执行器的工作过程。
· 第三部分：第3.5～3.6节
这一部分会描述获取多表查询上最优执行计划的步骤。第3.5节介绍了三种连接算法，分别是嵌套循环连接、归并连接和散列连接。第 3.6 节将介绍为多表查询创建计划树的过程。
PostgreSQL 支持三种技术上很有趣也很实用的功能，分别是外部数据包装（Foreign Data Wrapper，FDW）、并行查询及版本 11.0即将支持的 JIT编译。前两者将在第 4章中描述，JIT编译超出本书的范围，更多内容见官方文档。
3.1 概览
尽管PostgreSQL在9.6版本后有了基于多个后台工作进程的并行查询，但大体上来讲，还是每个连接对应一个后端进程。后端进程由以下5个子系统组成：
1.解析器，根据SQL语句生成一棵语法解析树（parse tree）。
2.分析器，对语法解析树进行语义分析，生成一棵查询树（query tree）。
3.重写器，按照规则系统中存在的规则对查询树进行改写。
4.计划器，基于查询树生成一棵执行效率最高的计划树（plan tree）。
5.执行器，按照计划树中的顺序访问表和索引，执行相应查询。
图3.1是查询处理的大概流程。
图3.1 查询处理
本节将概述这些子系统。计划器和执行器很复杂，后面的章节会对这些函数的细节进行描述。
PostgreSQL的查询处理在官方文档中有详细的描述。
3.1.1 解析器
解析器基于SQL语句的文本，生成一棵后续子系统可以理解的语法解析树。下面是一个具体的例子。
考虑以下查询：
testdb=# SELECT id, data FROM tbl_a WHERE id < 300 ORDER BY data;
语法解析树的根节点是一个定义在parsenodes.h中的SelectStmt数据结构。图3.2（1）展示了一个查询，图3.2（2）则是该查询对应的语法解析树。
typedef struct SelectStmt
{
NodeTag type;
/＊ 这些字段只会在SelectStmts“叶节点”中使用 ＊/
List ＊distinctClause; /＊ NULL, DISTINCT ON表达式列表 ＊/
IntoClause ＊intoClause; /＊ SELECT INTO 的目标 ＊/
List ＊targetList; /＊ 结果目标列表 (ResTarget) ＊/
List ＊fromClause; /＊ FROM 子句 ＊/
Node ＊whereClause; /＊ WHERE 限定条件 ＊/
List ＊groupClause; /＊ GROUP BY 子句 ＊/
Node ＊havingClause; /＊ HAVING 条件表达式 ＊/
List ＊windowClause; /＊ WINDOW window_name AS (...), ... ＊/
/＊ 在一个表示值列表的叶节点中，上面的字段全都为空，而这个字段会被设置
＊ 注意，这个子列表中的元素都没有ResTarget的修饰的表达式类型。
＊还需要注意，无论值列表的上下文是什么，列表元素都可能为DEFAULT (表示一个 SetToDefault 节点)
＊ 由分析阶段决定是否合法并拒绝 ＊/
List ＊valuesLists; /＊ 未转换的表达式列表 ＊/
/＊ 这些字段会同时在SelectStmts叶节点与SelectStmts上层节点中使用 ＊/
List ＊sortClause; /＊ 排序子句 (排序依据的列表) ＊/
Node ＊limitOffset; /＊ 需要跳过的元组数目 ＊/
Node ＊limitCount; /＊ 需要返回的元组数目 ＊/
List ＊lockingClause; /＊ FOR UPDATE (锁子句的列表) ＊/
WithClause ＊withClause; /＊ WITH 子句 ＊/
/＊ 这些字段只会在上层的 SelectStmts 中出现 ＊/
SetOperation op; /＊ set 操作的类型 ＊/
bool all; /＊ 是否指明了 ALL 选项 ＊/
struct SelectStmt ＊larg; /＊ 左子节点 ＊/
struct SelectStmt ＊rarg; /＊ 右子节点 ＊/
} SelectStmt;
图3.2是语法解析树的例子。
图3.2 语法解析树的例子
SELECT 查询中的元素和语法解析树中的元素有着对应关系。比如，（1）是目标列表中的一个元素，与目标表的'id'列相对应，（4）是一个WHERE子句，诸如此类。
当解析器生成语法分析树时只会检查语法，只有当查询中出现语法错误时才会返回错误。解析器并不会检查输入查询的语义，举个例子，如果查询中包含一个不存在的表名，解析器并不会报错，那么语义检查由分析器负责。
3.1.2 分析器
分析器对解析器产出的语法解析树进行语义分析，并产出一棵查询树。
查询树的根节点是parsenode.h中定义的Query数据结构，这个结构包含着对应查询的元数据，比如命令的类型（SELECT/INSERT等），还包括一些叶子节点，叶子节点由列表或树组成，包含了与特定子句相对应的数据。
/＊
＊ Query -
＊ 解析与分析过程会将所有的语句转换为一棵查询树，供重写器与计划器用于进一步的处理
＊ 功能语句（即不可优化的语句）会设置utilityStmt字段，而Query结构本身基本上是空的
＊ DECLARE CURSOR 是一个特例：它的形式与SELECT类似，但原始的DeclareCursorStmt会
＊ 被放在 utilityStmt 字段中
＊ 计划过程会将查询树转换为一棵计划树，计划树的根节点是一个PlannedStmt结构
＊ 执行器不会用到查询树结构
＊/
typedef struct Query
{
NodeTag type;
CmdType
commandType;
/＊ select|insert|update|delete|utility ＊/
QuerySource querySource;
/＊ 我来自哪里 ＊/
uint32
queryId;
/＊ 查询标识符 (可由插件配置) ＊/
bool
canSetTag;
/＊ 我设置了命令结果标签吗 ＊/
Node
＊utilityStmt;
/＊ 这是一条DECLARE CURSOR或不可优化的语句 ＊/
int
resultRelation;
/＊ 对增删改语句而言是目标关系的索引，SELECT为0 ＊/
bool
hasAggs;
/＊ 是否在目标列表或having表达式中指定了聚合函数 ＊/
bool
hasWindowFuncs; /＊ tlist是否包含窗口函数 ＊/
bool
hasSubLinks;
/＊ 是否包含子查询SubLink ＊/
bool
hasDistinctOn;
/＊ 是否包含来自DISTINCT ON的distinct子句 ＊/
bool
hasRecursive;
/＊ 是否制定了WITH RECURSIVE ＊/
bool
hasModifyingCTE; /＊ 是否在WITH子句中包含了INSERT/UPDATE/DELETE ＊/
bool
hasForUpdate;
/＊ 是否指定了FOR [KEY] UPDATE/SHARE＊/
bool
hasRowSecurity; /＊ 是否应用了行安全策略 ＊/
List
＊cteList;
/＊ CTE列表 ＊/
List
＊rtable;
/＊ 范围表项目列表 ＊/
FromExpr
＊jointree;
/＊ 表连接树 (FROM 与 WHERE 子句) ＊/
List
＊targetList;
/＊ 目标列表 (TargetEntry的列表) ＊/
List
＊withCheckOptions; /＊ WithCheckOption的列表 ＊/
OnConflictExpr
＊onConflict; /＊ ON CONFLICT DO [NOTHING | UPDATE] ＊/
List
＊returningList;
/＊ 返回值列表(TargetEntry的列表) ＊/
List
＊groupClause;
/＊ SortGroupClause的列表 ＊/
List
＊groupingSets;
/＊ 如果query带group语句，那么这里有GroupingSet的列表 ＊/
Node
＊havingQual;
/＊ 分组的Having条件列表 ＊/
List
＊windowClause;
/＊ 窗口子句列表 ＊/
List
＊distinctClause; /＊ SortGroupClause列表 ＊/
List
＊sortClause;
/＊ SortGroupClause列表 ＊/
Node
＊limitOffset;
/＊ Offset跳过元组数目 (int8 表达式) ＊/
Node
＊limitCount;
/＊ Limit返回元组数目 (int8 表达式) ＊/
List
＊rowMarks;
/＊ RowMarkClause列表 ＊/
Node
＊setOperations;/＊ 如果是UNION/INTERSECT/EXCEPT的顶层查询，则为集合操作列表 ＊/
List
＊constraintDeps; /＊ 确认查询语义是否合法时，所依赖约束对象的oid列表 ＊/
} Query;
图3.3是查询树的例子。
图3.3 查询树
接下来对图3.3的查询树进行简要介绍：
· targetlist 是查询结果中列的列表。在本例中该列表包含id 和data 两列。如果在输入的查询树中使用了*（星号），分析器就会将其显式替换为所有具体的列。
· 范围表rtable是该查询所用到关系的列表。本例中该变量包含了表tbl_a的信息，如该表的表名与oid。
· 连接树jointree存储着与FROM和WHERE子句相关的信息。
· 排序子句sortClause是SortGroupClause结构体的列表。
更多查询树的细节可查阅官方文档。
3.1.3 重写器
PostgreSQL的规则系统正是基于重写器实现的。当需要时，重写器会根据存储在pg_rules中的规则对查询树进行转换。规则系统本身也是一个很有趣的系统，不过本章略去了关于规则系统和重写器的描述，以免内容过于冗长。
视图
在PostgreSQL中，视图是基于规则系统实现的。当使用CREATE VIEW命令定义一个视图时，PostgreSQL就会创建相应的规则，并存储到系统目录中。
假设下面的视图已经被定义，而pg_rule中也存储了相应的规则。
sampledb=# CREATE VIEW employees_list
sampledb-# AS SELECT e.id, e.name, d.name AS department
sampledb-# FROM employees AS e, departments AS d WHERE e.department_id = d.id;
当执行一个包含该视图的查询时，解析器会创建一棵语法解析树。
sampledb=# SELECT ＊ FROM employees_list;
在该阶段，重写器会基于pg_rule中存储的视图规则将rangetable节点重写为一棵查询子树，与子查询相对应。
图3.4是重写阶段的例子。
图3.4 重写阶段
因为PostgreSQL使用这种机制实现视图，所以直到9.2版本，视图都是不能更新的。虽然9.3及更高版本可以对视图进行更新，但对视图的更新仍然存在很多限制，具体细节请参考官方文档。
3.1.4 计划器与执行器
计划器从重写器获取一棵查询树，基于查询树生成一棵能被执行器高效执行的（查询）计划树。
在PostgreSQL中，计划器是完全基于代价估计的，它不支持基于规则的优化与提示。计划器是RDBMS中最复杂的部分，因此本章的后续内容会对计划器做一个概述。
pg_hint_plan
PostgreSQL不支持 SQL中的提示（hint），并且永远也不会去支持。如果你想在查询中使用提示，可以考虑使用pg_hint_plan扩展，具体细节请参考官方文档。
与其他RDBMS类似，PostgreSQL中的EXPLAIN命令会显示命令的计划树。下面给出了一个具体的例子。
testdb=# EXPLAIN SELECT ＊ FROM tbl_a WHERE id < 300 ORDER BY data;
QUERY PLAN
---------------------------------------------------------------
Sort (cost=182.34..183.09 rows=300 width=8)
Sort Key: data
-> Seq Scan on tbl_a (cost=0.00..170.00 rows=300 width=8)
Filter: (id < 300)
(4 rows)
图3.5展示了一棵简单的计划树及其与EXPLAIN命令的关系。
图3.5 一棵简单的计划树及其与EXPLAIN命令的关系
计划树由被许多称为计划节点的元素组成，这些节点挂在 PlannedStmt 结构对应的计划树上。这些元素的定义在plannodes.h中，第3.3.3节与第3.5.4.2节会解释相关细节。
每个计划节点都包含着执行器进行处理所需要的信息，在单表查询的场景中，执行器会按照从终端节点往根节点的顺序依次处理这些节点。
比如图 3.5 中的计划树就是一个列表，包含一个排序节点和一个顺序扫描节点，因而执行器会首先对表tbl_a执行顺序扫描，并对获取的结果进行排序。
执行器会通过将在第 8章介绍的缓冲区管理器来访问数据库集簇的表和索引。当处理一个查询时，执行器会使用预先分配的内存空间，比如temp_buffers和work_mem，必要时还会创建临时文件。
图3.6显示了执行器、缓冲管理器和临时文件之间的关系。
图3.6 执行器、缓冲管理器和临时文件之间的关系
除此之外，当访问元组的时候，PostgreSQL还会使用并发控制机制来维护运行中事务的一致性和隔离性。第5章将介绍并发控制机制。