概述

并行查询使用多个后台进程，但后端进程基本上处理连接的客户端发出的所有查询。改后端有五个子系统组成。

fig-3-01.png

解析器

解析器生成一个解析树，后续子系统可以从纯文本的 SQL 语句中读取该解析树。

如下面的查询：

testdb =# SELECT id , data FROM tbl_a WHERE id < 300 ORDER BY data ; 

解析树是其根节点是定义在parsenodes.h中的[SelectStmt](javascript:void(0))结构的树。

fig-3-02.png

SELECT 查询的元素和解析树的相应元素编号相同。例如，(1) 是第一个目标列表的一个项目，它是表的“id”列，(4) 是 WHERE 子句，依此类推。

由于解析器在生成解析树时只检查输入的语法，因此只有在查询中出现语法错误时才会返回错误。

解析器不检查输入查询的语义。例如，即使查询包含不存在的表名，解析器也不会返回错误。语义检查由分析器/分析器完成。

分析器

分析器运行由解析器生成的解析树的语义分析并生成查询树。

查询树的根是定义在parsenodes.h中的[查询](javascript:void(0))结构；此结构包含其相应查询的元数据，例如此命令的类型（SELECT、INSERT 或其他）和几个叶子；每个叶子形成一个列表或树，并保存各个特定子句的数据。

fig-3-03.png

述查询树简述如下。

• targetlist 是作为此查询结果的列的列表。在此示例中，此列表由两列组成：'id'和'data'。如果输入查询树使用 '*'（星号），分析器/分析器会将其显式替换为所有列。
• 范围表是在此查询中使用的关系列表。在这个例子中，这个表保存了表' tbl_a '的信息，例如这个表的oid和这个表的名字。
• 连接树存储 FROM 子句和 WHERE 子句。
• sort 子句是 SortGroupClause 的列表。

重写器

重写器是实现规则系统的系统，必要时根据存储在pg_rules系统目录中的规则变换查询树。

PostgreSQL 中的视图是使用规则系统实现的。当视图由CREATE VIEW命令定义时，相应的规则会自动生成并存储在目录中。

假设已经定义了以下视图，并且对应的规则存储在pg_rules系统目录中。

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_rules中。

fig-3-04.png

计划器和执行器

计划器从重写器接收查询树并生成可以由执行器最有效地处理的（查询）计划树。

PostgreSQL 中的计划器是基于纯成本优化的；它不支持基于规则的优化和提示。这个规划器是 RDBMS 中最复杂的子系统

与其他 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)

他对应的计划树：

fig-3-05.png

每个计划节点都有执行器需要处理的信息，单表查询的情况下，执行器从计划树的末端到根进行处理。

单表查询的成本估计

PostgreSQL 的查询优化是基于成本的。成本是无量纲值，它们不是绝对的绩效指标，而是比较运营相对绩效的指标。成本由costsize.c中定义的函数估算。执行器执行的所有操作都有相应的成本函数。例如，顺序扫描和索引扫描的成本分别由 cost_seqscan() 和 cost_index() 估算。

有三种成本，启动成本，执行成本以及总成本。其中总成本 = 启动成本 + 执行成本。

1. 启动成本(start-up cost)：从sql语句开始执行算子，到该算子输出第一条元组为止，所需要的成本成为启动成本。有的算子启动成本很小，比如基本表上的扫描算子，一旦开始读取数据也就可以输出元组，因为启动代价为0.有的算子的启动成本相对较大，比如排序算子，他需要把所有下层算子的输出全部读取，并且把这些元组排序之后，才能输出第一条元组，因此他的启动成本比较大。

2. 执行成本(run cost)：从输出第一条元组开始至查询结束，所需要的成本部称为执行成本。这个成本中又可以包含CPU成本，IO成本和通信成本。执行代价的大小与算子需要处理的数据量有关，与每个算子完成的功能有关。处理的数据量越大、算子需要完成的任务越重，则执行成本越大。

3. 总成本(total cost)：成本计算是一个自底向上的过程，首先计算扫描算子的代价，然后根据扫面算子的代价计算连接算子的代价，以及Non-SPJ算子的代价。

顺序扫描

顺序扫描的成本由 cost_seqscan() 函数估算。

其中 seq_page_cost、 cpu_tuple_cost 和 cpu_operator_cost在 postgresql.conf 文件中设置，默认值分别为1.0、0.01和0.0025，Ntuple和Npage分别是该表的所有元组和所有页的编号。

从运行成本估算可以看出，PostgreSQL 假设所有页面都将从存储中读取；也就是说，PostgreSQL 不考虑扫描的页面是否在共享缓冲区中。

索引扫描

启动成本

虽然 PostgreSQL 支持 一些索引方法，例如 BTree、 GiST、 GIN和 BRIN，但索引扫描的成本是使用常见的成本函数估算的：cost_index()。

索引扫描的启动成本是读取索引页以访问目标表中第一个元组的成本，它由以下等式定义：

Hindex是索引树的高度。

运行成本

索引扫描的运行成本是表和索引的 cpu 成本和 IO（输入/输出）成本之和：

前三个成本定义如下：

其中 cpu_index_tuple_cost和random_page_cost 在 postgresql.conf 文件中设置（默认分别为 0.005 和 4.0）； qual_op_cost粗略来说就是指数的评估成本，值为0.0025。选择性选择性是指定WHERE子句对索引的搜索范围的比例；它是一个从 0 到 1 的浮点数

选择率

查询谓词的选择率是通过直方图界值与高频值估计的，这些信息都储存在系统目录pg_staticstics中，并可通过pg_stats视图查询。

表中的每一列的高频值都在pg_stats视图的most_common_vals和most_common_freqs中成对存储。

• 高频值：该列上最常出现的取值列表
• 高频值频率：高频值相应出现频率的列表

排序

排序路径会在排序操作中被使用。排序操作包括order by、归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。如果能在工作内存中放下所有元组，那么排序操作会选用快速排序算法。否则就会创建临时文件，使用文件归并排序算法。

排序路径的启动代价就是对目标表的排序代价，因此代价就是O(Nsort) * Log₂(Nsort)，这里Nsort就是带排序的元组数。排序路径的运行代价就是读取已经排序好的元组的代价，因此代价就是O（Nsort）。

创建单表查询的计划树

PostgreSQL中的计划器会执行三个步骤：

1. 执行预处理
2. 在所有可能的访问路径中，找出代价最小的访问路径
3. 按照代价最小的路径，创建计划树

访问路径是估算代价时的处理单元。比如顺序扫描、索引扫描、排序，以及各种连接操作都有其对应的路径。访问路径只在计划器创建查询计划树的时候使用。最忌本的访问路径数据结构就是relation.h中定义的path结构体，相当于顺序扫描。所有其他的路径访问都基于该结构。

预处理

在创建计划树之前，计划器将线对PlannerInfo中的查询书进行一些预处理。预处理有很多步骤，本节值讨论和单表查询处理相关的主要步骤。

1. 简化目标列表，limit子句等

2. 布尔表达式的规范化

3. 压平与/或表达式

   SQL标准中的and/or是二元操作符，但他们在postgresql内部是多远操作符。而计划器总是会假设所有的嵌套and/or都应该被压平。

找出代价最小的访问路径

计划器对所有可能的访问路径进行代价估计，然后选择代价最小的那个。

1. 创建一个RelOptInfo数据结构，存储访问路径及其代价。

   RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo持有者baserestrictinfo变量如果存在相应缩影，还会持有indexlist变量。baserestrictinfo存储着查询的where子句，而indexlist储存着目标表上相关的索引。

2. 估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。这一处理过程的细节如下：

   a. 创建一条路径，估计该路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。

   b. 如果目标表上存在相关的索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应路径中。然后将索引访问路径添加到pathlist变量中。

   c. 如果可以进行位图扫描，则创建一条位图扫描访问路径。估计所有位图扫描的代价，并将代价写入路径中，然后将位图扫面路径添加到pathlist变量中。

3. 从RelOptInfo的pathlist中，找出代价最小的访问路径。

4. 如果有必要，估计limit、order by和aggregate操作的代价。

创建计划树

在最后一步中，计划器按照代价最小的路径生成一颗计划树。

计划树的根节点是定义在plannodes.h中的Plannedstmt结构，包含19个字段，其中有4个代表性字段：

• commandType存储操作的类型，注入select、update和insert。
• rtable储存范围表的列表(RangeTblEntry的列表).
• relationOids储存与查询相关表的oid。
• plantree存储这一棵由计划树，每个计划节点对应着一种特定操作，诸如顺序扫描、排序和索引扫描。

计划树包含各式各样的计划节点。PlanNode是所有计划节点的基类，其他计划节点都会包含PlanNode结构。比如顺序扫描节点SeqScanNode包含一个PlanNode和一个整型变量scanrelid。PlanNode包含14个字段，下面是7个代表性字段:

• startup_cost和total_cost是该节点对应操作的预估代价。

• rows是计划器预计扫描的行数。

• targetlist保存了该查询树中目标项的列表。

• qual储存了限定条件的列表。

• lefttree和righttree用于添加子节点。

执行器是如何工作的

在单表查询的例子中，执行器从计划树中取出计划节点，按照自底向上的顺序进行处理，并调用节点相应的处理函数。

每个计划节点都有相应的函数，用于执行节点对应的操作。这些函数在src/backend/executor目录中。

理解执行器如何工作的最好方式，就是阅读explain命令的输出。

image-20220523115944244.png

我们可以自底向上阅读explain的结果，来看一看执行器是如何工作的。

第六行：首先，执行器通过nodeSeqscan.c中定义的函数执行顺序扫描操作。

第四行：然后，执行器通过nodeSort.c中定义的函数，对顺序扫描的结果进行排序。

临时文件

执行器在处理查询时会使用工作内存和临时缓冲区，两者都在内存中分配。如果查询无法在内存中完成，就会用到临时文件。

使用带有Analyze选项的explain，待解释的命令会真正执行，并显示实际结果行数、实际执行时间和实际内存使用量。

image-20220523121116219.png

在第6行，explain命令显示执行器使用了10000KB的临时文件。临时文件会被临时创建在base/pg_tmp子目录中，并遵循如下命令规则：｛“pgsql_tmp”｝+ ｛创建本文件的postgres进程pid｝.{从0开始的序列号}

比如，临时文件pgsql_tmp8903.5是pid为8903的postgres进程创建的第6个临时文件。

连接

PostgreSQL中支持三种连接操作，分别是嵌套循环连接，归并连接和散列连接。在pg中，嵌套循环连接和归并连接有几种变体。

这三种连接方式都支持pg中所有的连接操作，注入inner join、 left/right outer join、 full outer join等。

循环嵌套连接

循环嵌套连接不需要任何启动代价，因此：start-up cost = 0

运行代价和内外表尺寸的乘积成比例，即run cost是O(Nouter * Ninner)， Nouter和Ninner分别是外表和内表的元组条数。run cost的定义如下：

Couter和Cinner分别是内表和外表顺序扫描的代价。

fig-3-16.png

循环嵌套连接的代价总会被估计，但实际中很少会使用这种连接操作，因为它有几种更高效的变体。

物化循环嵌套连接

在上面描述的循环嵌套连接中，每当读取一条外表中的元组时，都需要扫描内标中的所有元组。位每条外表元组对内标做全表扫描，这一过程代价高昂，pg支持一种物化嵌套循环连接，可以减少内标全表扫描的代价。

在运行嵌套循环连接之前，执行器会使用临时元组存储模块对内表进行一次扫描，将内表元组加载到工作或临时文件中。在处理内表元组时，临时元组存储比缓冲区管理器更为高效，特别是当所有的元组都能放入工作内存中。

fig-3-17.png

临时元组存储

qg内部提供了临时元组存储的模块，可用于各种操作，如五花膘、创建混合散列连接的批次等。该模块包含一系列函数，都在tuplestore.c中。这些函数用于从工作内存或临时文件读写元组。该工作内存还是临时文件取决于待存储元组的总数。

image-20220523145640021.png

上面显示了执行器要进行的操作，执行器对这些计划节点的处理过程如下：

第7行：执行器使用顺序扫描，物化内部表tbl_b。

第4行：执行器执行嵌套循环连接操作，外表是tbl_a，内表是物化的tbl_b。

索引嵌套循环连接

如果内表上有索引，且该索引能用于搜索满足连接条件的元组，那么计划器在外外表的每条元组搜索内标中的匹配元组时，会考虑使用索引进行直接搜索，以替代顺序扫描。这种变体叫做索引嵌套循环连接，如下图所示。虽然这种变体叫做“索引嵌套循环连接”，但是谁该算法基本上只需要在外表上循环一次，因此连接操作的执行非常高效。

fig-3-18.png

归并连接

与嵌套循环连接不同的是，归并连接只能用于自然连接与等值连接。

函数initial_cost_merge_join()和final_cost_merge_join()用于估计归并连接的代价。

归并连接的启动成本是内表与外表排序成本之和，因此其启动成本为：

这里Nouter和Ninner分别是外表和内标的元素条数，而运行代价是O(Nouter + Ninner)。

归并连接

下图是归并连接的示意图。

fig-3-20.png

如果所有元组都可以存储在内存中，那么排序操作就能在内存中进行，否则就是用临时文件。

image-20220523153645243.png

第9行：执行器对内表tbl_b进行排序，使用顺序扫描（第11行）。

第6行：执行器对外表tbl_a进行排序，使用顺序扫描(第8行)。

第4行：执行器执行归并连接操作，外表是排序好的tbl_a，内表是排好序的tbl_b。

物化归并连接

与嵌套循环连接类似，归并连接还支持物化归并连接，物化内表，使内表扫描更为高效。

fig-3-21.png

下面是物化归并连接的explain结果，很容易发现，与普通归并连接的差异是第9行:Materialize。

image-20220523161647572.png

其他变体

• 索引归并连接

Hash连接

与归并连接类似，hash连接只能用于自然连接与等值连接。

PostgreSQL中的散列连接的行为因表的大小而异。如果布标足够小（确切的说，内表大小不超过工作内存的25%），那么hash连接就是简单的两阶段内存hash连接，否则将会使用带倾斜批次的混合hash连接。

内存Hash连接

内存中的hash连接是在work_mem中处理的，在pg中，散列表区域被称作处理批次。一个批处理批次会有多个散列槽，内部称其为桶，桶的数量由nodeHash.c中定义的ExecChooseHashTableSize()函数所确定。桶的数量是2的整数次幂。

内存散列连接有两个阶段，分别是构建阶段和探测阶段。在构建阶段，内存表中的所有元组都会被插入到处理批次中；在探测阶段每条腕表元组都会与处理批次中的内表元组比较，如果满足连接条件，则将两条元组连接起来。

带倾斜的混合hash连接

当内表的元组无法全部存储在工作内表中的单个处理批次时，pg使用带倾斜批次的混合散列连接算法，该算法时混合散列连接诶的一种变体。

在第一个构建和探测阶段postgresql准备多个批次，宇通的数目类似，处理批次的数据由函数ExecChooseHashTableSize()决定，也就是2的整数次幂。工作内存中智慧分配一个处理批次，而其他批次都以临时文件的形式创建。属于这些批次的元组将通过临时元组存储功能被写入到相应的文件中。

连接访问路径与连接节点

连接访问路径

fig-3-30.png

连接节点

• NestedLoopNode
• MergeJoinNode
• HashJoinNode

创建多表查询和计划树

预处理

1. 对CTE进行计划与转换。如果存在with列表，计划器就会通过SS_process_ctes()函数对每个with查询进行处理。

2. 上拉子查询。如果from子句带有一个子查询，且该表没有用到group by，having、order by、limit和disinct、intersect或except，那么计划器就会使用pull_up_subqueries()函数将其转换为连接形式。

3. 将外连接转为内连接。如果可能的话，计划器会将outer join查询转化为inner join查询。

获取代价最小的路径

为了获取最佳计划树，计划器必须考虑各个索引与各种连接方法之间的所有可能组合。如果表的数量超过某个水平，该过程的代价就会因为组合爆炸而变得非常昂贵，以至于根本不可行。

如果表的数量小于12张，计划器可以使用动态规划来获取最佳计划。