PostgreSQL中的查询：1.查询执行阶段

PostgreSQL中的查询：1．查询执行阶段

开始关于PG内部执行机制的文章系列。这一篇侧重于查询计划和执行机制。

本系列包括：

1、查询执行阶段（本文）

2、统计数据

3、顺序扫描

4、索引扫描

5、嵌套循环连接

6、哈希连接

7、Merge join

本系列针对PG14编写。

简单查询协议

PG客户端－服务协议的基本目的是双重的：将SQL查询发送到服务，接收整个执行结果作为响应。服务接收到查询去执行要经过几个阶段。

解析

首先，需要解析查询文本，这样服务才能准确了解需要执行什么。

词法分析器和解析器。词法解析器负责识别查询字符串中的词位（如SQL关键字、字符串、数字文字等），而解析器确保生成的词位集在语法上是有效的。解析器和词法解析器使用标准工具Bison和Flex实现。解析的查询表示位抽象的语法树。例如：

在这里，将在后台内存中构建一棵树。下面以高度简化的形式表示该树。树中节点用查询的相应部分标记：

RTE是一个晦涩的缩写，表示“范围表条目”。PG源码中“range table”指***查询、连接结果－－也就是说SQL语句操作的任何记录集。

语法分析器。语法分析器确定数据库中是否存在查询中引用的表和其他对象，用户是否有访问这些对象的权限。语法分析需要的所有信息都在系统catalog中。

语法分析接收分析器传来的解析树并重新构建它，并用引用的特定数据库对象、数据类型信息等来补充它。如果开启debug＿right＿parse，则会在服务消息日志中显示完整的树信息，尽管这没什么实际意义。

转换

下一步，对查询进行重写。

系统内核将重写用于多种目的。其中之一是将解析树中的视图名替换为该视图查询相对应的子树。pg＿tables是上面例子的一个视图，重写后的解析树将采用以下形式：

解析树对应的查询（经所有操作仅在树上执行，而不是在查询文本上执行）：

解析树反映查询的语法结构，而不是执行操作的顺序。行级安全性在转换阶段实施。

系统核心使用重写的另一个例子是版本14中递归查询的SEARCH和CYCLE子句中实现。

PG支持自定义转换，用户可以使用重写规则系统来实现。规则系统作为PG主要功能之一。这些规则得到了项目基础的支持，并在早期开发过程中反复重新设计。这是一个强大的机制，但难以理解和调试。甚至有人提议将规则从PG中完全删除，但没有得到普遍支持。在大多数情况下，使用触发器而不是规则更安全、更方便。

如果debug＿print＿rewritten开启，则完整重写的解析树会显示在服务消息日志中。

计划

SQL是一种声明性语言：查询指定要检索什么，但不指定如何检索它。任何查询都可以通过多种方式执行。解析树中的每个操作都有多个执行选项。例如，您可以通过读取整个表并丢弃不需要的行来从表中检索特定记录，或者可以使用索引来查询与您查询匹配的行。数据集总是成对连接。连接顺序的变化会产生大量执行选项。然后有许多方法可以将2组行连接在一起。例如，您可以逐个遍历第一个集合中的行，并在另一个集合中查找匹配的行，或者您可以先对2个集合进行排序，然后将他们合并在一起。不同方法在某些情况下表现更好，在另一些情况下表现更差。

最佳计划的执行速度可能比非最佳计划快几个数量级，这就是为什么优化解析查询的执行计划器是系统最复杂的元素之一。

计划树。执行计划也可以表示为树，但其节点是对数据的物理操作而不是逻辑操作。

开启debug＿print＿plan，则整个执行计划树会显示在服务消息日志中。这是非常不切实际的，因为日志非常混乱。更方便的选择是使用EXPLAIN命令：

EXPLAIN

SELECT schemaname， tablename

FROM pg＿tables

WHERE tableowner ＝ ＇postgres＇

ORDER BY tablename；

                          QUERY PLAN?????????????????????????????????????????????????????????????????????

Sort  （cost＝21．03．．21．04 rows＝1 width＝128）

  Sort Key： c．relname

  ?＞ Nested Loop Left Join  （cost＝0．00．．21．02 rows＝1 width＝128）

     Join Filter： （n．oid ＝ c．relnamespace）

     ?＞ Seq Scan on pg＿class c  （cost＝0．00．．19．93 rows＝1 width＝72）

          Filter： （（relkind ＝ ANY （＇｛r，p｝＇：：＂char＂［］）） AND （pg＿g．．．

      ?＞ Seq Scan on pg＿namespace n  （cost＝0．00．．1．04 rows＝4 wid．．．

（7 rows）

该图显示了树的主要节点。相同的节点在EXPLAIN输出中使用箭头标记。Seq Scan节点表示读取表操作，而Nested Loop节点表示表连接操作。这里有2个优趣的点需要注意：

1） 其中一个初始化表从执行计划树中消失了，因为执行计划器指出查询处理中不需要它

2） 估算要处理的行数和每个节点处理的代价

计划查询。为找到最佳计划，PG使用基于成本的查询优化器。优化器会检查各种可用的执行计划并估算需要的资源量，例如IO周期和CPU周期。这个计算出的估算值转换成任意单位，被称为计划成本。选择结果成本最低的计划来执行。

问题是，可能的计划数量随着连接数量的增加而呈指数增长，即使对于相对简单的查询，也无法一一筛选所有计划。因此，使用动态规划和启发式限制搜索范围。这允许在合理的时间内精确第解决查询中更多表的问题，但不能保证所选的计划是真正最优的。因为计划其使用简化的数学模型并可能使用不精确的初始化数据。

Ordering joins：可以以特定方式构建查询，以显著缩小搜索范围（有可能错过找到最佳计划的机会）：

1） 公共表表达式通常与主查询分开优化。从12开始可以使用MATERIALIZE子句来强制执行此操作。

2） 来自非SQL函数的查询和主查询分开优化。（在某些情况下，SQL函数可以内联到主查询中）

3） join＿collapse＿limit参数与现式join子句以及from＿collapse＿limit参数与子查询一起可以定义某些连接顺序，具体取决于查询语法。

最后一个可能需要解释，下面的查询调用FROM子句中的几个表，没有显式连接：

SELECT ．．．FROM a， b， c， d， eWHERE ．．．

下面是此查询的解析树：

在这个查询中，规划器将考虑所有可能的连接顺序。在下一个示例中，一些连接由JOIN子句显式定义：

SELECT ．．．FROM a， b JOIN c ON ．．．， d， eWHERE ．．．

解析树反映了这一点：

规划器折叠连接树，有效地将其转换为上一个示例中的树。该算法递归地遍历树并用其组件的平面列表替换每个JOINEXPR节点。

但是只有在生成的屏幕列表包含不超过join＿collapse＿limit个元素（默认8个）时，才会发生这种“扁平化”。在上面示例中，如果将join＿collapse＿limit设置5或更少，则不会折叠JOINEXPR节点。对于规划器来说，这意味着两件事：表B必须连接到表C（反之亦然，join对中的join 顺序不受限制）；表A、D、E以及B到C的连接可以按任意顺序连接。

如果join＿collapse＿limit设置为1，则将保留任何显式JOIN顺序。注意，无论该参数如何，操作FULL OUTER JOIN都不会折叠。

参数from＿collapse＿limit（默认也是8）以类似的方式限制子查询的展平。子查询似乎与连接没有太多共同之处，但当它归结为解析树级别时，相似性显而易见。

例子：

SELECT ．．．FROM a， b JOIN c ON ．．．， d， eWHERE ．．．

下面是对应树：

这里唯一的区别是JOINEXPR节点被替换成FROMEXPR（因此参数名称为FROM）。

遗传搜索：每当生成的扁平树以太多相同级别的节点（表或连接结果）结束时，规划时间可能会飙升，因为每个节点都需要单独优化。如果geqo参数开启，当同级节点数量达到geqo＿threshold（默认12）时，PG将切换到遗传搜索。遗传搜索比动态规划的方法快得多。但并不能保证找到最佳计划。该算法有许多可调整的选项，这时另一篇文章主题。
 

选择最佳计划：最佳计划的定义因预期用途而异。当需要完整的输出时，计划必须优化与查询匹配的所有行的检索。另一方面，如果只想要前几个匹配的行，则最佳计划可能会完全不同。PG通过计算2个成本组件来解决这个问题。他们显示在“成本”一词之后的查询计划输出中：

Sort  （cost＝21．03．．21．04 rows＝1 width＝128）

第一个组成部分：启动成本，是为节点执行做准备的成本；第2个组成部分，总成本：代表总节点执行成本。

选择计划时，计划器首先要检查是否使用cursor（可以通过DECLARE命令设置cursor或者在PL／pgSQL中明确声明）。如果没有，计划器假设需要全部输出并选择总成本最低的计划。否则，如果使用cursor，则规划器会选择一个规划，以最佳方式检索匹配行总数中等于cursor＿tuple＿fraction（默认0．1）的行数。或者具体地说最低的计划：startup cost ＋ cursor＿tuple＿fraction＊（total cost－ startup cost）。

成本计算过程。要估计计划的成本，必须单独估计其每个节点。节点成本取决于节点类型（从表中读取的成本远低于对表排序的成本）和处理的数据量（通常，数据越多，成本越高）。虽然节点类型是立即知道的，但要评估数据量，我们首先需要估计节点的基数（输入行的数量）和选择性（剩余用于输出的行的比例）。为此，我们需要数据统计：表大小、跨列的数据分布。

因此优化依赖于准确的统计数据，这些数据由自动分析过程受继并保持最新。

如果每个计划节点的基数估计准确，计算出的总成本通常会与实际成本相匹配。场景的计划偏差通常是基数和选择性估计不准确的结果。这些错误是由不准确、过时或不可用的统计数据引起的，并在较小程度上是规划期所基于的固有模型不完善。

基数估计。基数估计是递归执行的。节点基数使用2个值计算：节点的字节的的基数，或输入行数；节点的选择性，或输出行于输入行的比例。基数是这2个值的成绩。选择性是一个介于0和1之间的数字。接近于零的选择性值称为高选择性，接近1的值称为低选择性。这是因为高选择性会消除较高比例的行，而较低的选择性值会降低阈值，因此丢弃的行数回更少。首先处理具有数据访问方法的叶节点。这就是表大小等统计信息的来源。应用于表的条件的选择性取决于条件类型。在最简单的形式中，选择性可以是一个常数值，但计划着回尝试使用所有可用信息来产生最准确的估计。最简单条件的选择性估计作为基础，使用不二运算构建的复杂条件可以使用以下简单公式进一步计算：

selx and y ＝ selx sely

selx or y ＝ 1－（1－selx ）（1－sely ）＝selx ＋ sely － selx sely

在这些公式中，x和y认为是独立的。如果他们相关，则使用这些公式，会使估计不太准确。对于连接的基数估计，计算2个值：笛卡尔积的基数（2个数据集的基数的乘积）和连接条件的选择性，这又取决于条件类型。其他节点类型的基数，例如排序或聚合节点也是类似计算的。

请注意，较低节点中的基数计算错误将向上传播，导致成本估算不准确，并最终导致次优计划。计划器只有表的统计数据，而不是连接结果的统计数据，这使情况变得更糟。

代价估算。代价估算过程也是递归的。子树的成本包括其子节点的成本加上父节点的成本。节点成本计算基于其执行操作的数学模型。已经计算的基数用于输入。该过程计算启动成本和总成本。有些操作不需要任何准备，可以立即开始执行。对于这些操作，启动成本是0．其他操作可能有先决标记。例如排序节点通常需要来自其子节点的所有数据才能开始操作。这些节点的启动成本不为0。即使下一个节点（或客户端）只需要单行输出，也必须计算此成本。

成本是计划者的最佳估计。任何计划错误都会影响成本与实际执行的相关程度。成本评估的注意目的是让计划者在相同条件下比较相同查询的不同执行计划。在任何其他情况下，按成本比较查询（更糟糕的是，不同的查询）是没有意义和错误的。例如，考虑由于统计数据不准确而被低估的成本。更新统计数据－－成本可能会发生变化，但估算会变得更加准确，计划最终会得到改进。

执行

按照计划执行优化后的查询。在后端内存中创建一个portal对象。Portal存储着执行查询需要的状态。这个状态以树的形式表示，其结构与计划树相同。树的节点作为装配线，相互请求和传递行记录：

从root节点开始执行。Root节点（例子中的SORT节点）向2个字节的请求数据。当它接收到所有请求的数据时会执行排序操作，然后将数据向上传递给客户端。

一些节点（例如NESTLOOP节点）连接来自不同来源的数据。该节点向2个字节的请求数据。在接收到与连接条件匹配的行后，节点立即将结果行传递给父节点（和排序不同，排序必须在处理他们之前接收所有行），然后该节点停止，知道其父节点请求另一行。因此，如果只需要部分结果（例如LIMIT设置），则操作不会完全执行。

2个SEQSCAN叶节点是表扫描。根据父节点的请求，叶节点从表中读取下一行并将其返回。这个节点和其他一些节点根本不存储行，而只是交付并立即忘记他们。其他节点例如排序，可能需要一次存储大量数据。为解决这个问题，在后端内存分配了一个work＿mem内存块，默认是保守的4MB限制；当内存用完时，多余的数据会被发送到磁盘上的临时文件中。

一个计划可能包含多个具有存储要求的节点，因此他可能分配了几块内存，每个块大小为work＿mem。查询进程可能占用的总内存大小没有限制。

扩展查询协议

使用简单的查询协议，任何命令即使它一次又一次重复也会经历上述所有阶段：解析、重写、规划、执行。但是没有理由一遍又一遍地解析同一个查询。如果他们尽在常量上有所不同，也没有理由重新解析查询：解析树将是相同的。简单查询协议的另一个烦恼是客户端接收完整的输出，而不管它可能有多长。

这2个问题都可以通过使用SQL命令来解决：为第一个问题准备一个查询并执行它，为第二个问题声明一个游标并获取所需行。但随后客户端将不得不处理命名新对象，而服务器将需要解析额外的命令。

扩展查询协议可以在协议命令级别对单独的执行阶段进行精确控制。

准备

在准备期间，查询会像往常一样被解析和重写，但解析树存储在后端内存中。PG没有用于解析查询的全局缓存。即使一个进程之前已经解析过查询，其他进程也必须再次解析它。然而，这中设计也有好处。在高负载下，全局内存缓冲很容易因为锁称为瓶颈。一个客户端发送多个小命令可能会影响整个实例的性能。在PG中，查询解析很便宜并与其他进程隔离。

可以使用附加参数准备查询。下面是一个使用SQL命令的例子（同样，这并不等同于协议命令级别的准备，但最终的效果是一样的）：

PREPARE plane（text） ASSELECT ＊ FROM aircrafts WHERE aircraft＿code ＝ ＄1；

本文的案例都使用demo数据库“Airlines”。此视图显示所有命名的预准备语句：

SELECT name， statement， parameter＿types

FROM pg＿prepared＿statements gx

?［ RECORD 1 ］???＋??????????????????????????????????????????????????

name           ｜ plane

statement    ｜ PREPARE plane（text） AS                           ＋

                   ｜ SELECT ＊ FROM aircrafts WHERE aircraft＿code ＝ ＄1；

parameter＿types ｜ ｛text｝

该视图没有列出任何未命名的语句（使用扩展协议或PL／pgSQL）。但它也没有列出来其他会话的准备好的语句：访问另一个会话的内存是不可能的。

参数绑定

在执行准备好的查询之前，会绑定当前参数值。

EXECUTE plane（＇733＇）；

aircraft＿code ｜     model     ｜ range

???????????????＋???????????????＋???????

733           ｜ Boeing 737?300 ｜  4200（1 row）

与文字表达式的串联相比，准备好的语句的一个优点是可以防止任何类型的SQL注入。因为参数值不会影响已经构建的解析树。在没有准备好的声明的情况下达到相同的安全级别，将需要对来自不受信任来源的所有值进行广泛转义。

规划和执行

执行准备好的语句时，首先会考虑提供的参数来计划其查询，然后发送选择的计划以执行。实际参数值对规划者很重要，因为不同参数集的最有规划也可能不同。例如，在查找高级航班预订时，使用索引扫描（例如Index Scan字样所示），因为计划者预计匹配的行不多：

CREATE INDEX ON bookings（total＿amount）；

EXPLAIN SELECT ＊ FROM bookings WHERE total＿amount ＞ 1000000；

                           QUERY PLAN?????????????????????????????????????????????????????????????????????

Bitmap Heap Scan on bookings  （cost＝86．38．．9227．74 rows＝4380 wid．．．

  Recheck Cond： （total＿amount ＞ ＇1000000＇：：numeric）

 ?＞ Bitmap Index Scan on bookings＿total＿amount＿idx  （cost＝0．00．．．．

      Index Cond： （total＿amount ＞ ＇1000000＇：：numeric）

（4 rows）

然而，下一个条件完全符合所有预订。索引扫描在这里没用，进行顺序扫描Seq Scan：

EXPLAIN SELECT ＊ FROM bookings WHERE total＿amount ＞ 100；

                           QUERY PLAN???????????????????????????????????????????????????????????????????

Seq Scan on bookings  （cost＝0．00．．39835．88 rows＝2111110 width＝21）

  Filter： （total＿amount ＞ ＇100＇：：numeric）

（2 rows）

在某些情况下，除了解析树外，规划器还会存储查询计划，以避免再出现时再次规划它。整个没有参数值的计划称为通用计划，而不是使用给定参数值生成的自定义计划。通用计划的一个明显用例是没有参数的语句。

对于前4此运行，带有参数的预处理语句总是根据实际参数值进行优化。然后计算平均计划成本。在第5次及以后，如果通用计划平均比自定义计划代价低，那么规划器从那时起存储和使用通用计划，并进行进一步优化。

plane准备好的语句已经执行过一次，在接下来的2次执行中，仍然使用自定义计划，如查询计划中的参数值所示：

EXECUTE plane（＇763＇）；

EXECUTE plane（＇773＇）；

EXPLAIN EXECUTE plane（＇319＇）；

                          QUERY PLAN??????????????????????????????????????????????????????????????????

Seq Scan on aircrafts＿data ml  （cost＝0．00．．1．39 rows＝1 width＝52）

 Filter： （（aircraft＿code）：：text ＝ ＇319＇：：text）

（2 rows）

执行4次后，规划器切换到通用规划。在这种情况下，通用计划与定制计划相同，成本相同，因此更可取。现在EXPLAIN命令显示参数编号，而不是实际值：

EXECUTE plane（＇320＇）；

EXPLAIN EXECUTE plane（＇321＇）；
                           QUERY PLAN??????????????????????????????????????????????????????????????????

Seq Scan on aircrafts＿data ml  （cost＝0．00．．1．39 rows＝1 width＝52）

 Filter： （（aircraft＿code）：：text ＝ ＇＄1＇：：text）

（2 rows）

不幸的是，只有前4个定制计划比通用计划更昂贵，而任何进一步的定制计划都会更便宜，但计划者会完全忽略他们。另一个可能的不完善来源是计划者比较成本估算，而不是要花费的实际资源成本。

这就是为什么在版本12及更高版本中，如果用户不喜欢自动结果，他们可以强制系统使用通用计划或自定义计划。这是通过参数plan＿cache＿mode来完成：

SET plan＿cache＿mode ＝ ＇force＿custom＿plan＇；

EXPLAIN EXECUTE plane（＇CN1＇）；
                          QUERY PLAN??????????????????????????????????????????????????????????????????

Seq Scan on aircrafts＿data ml  （cost＝0．00．．1．39 rows＝1 width＝52）

Filter： （（aircraft＿code）：：text ＝ ＇CN1＇：：text）

（2 rows）

14及更高版本中，pg＿prepared＿statements视图还显示计划选择统计信息：

SELECT name， generic＿plans， custom＿plans

FROM pg＿prepared＿statements；

name  ｜ generic＿plans ｜ custom＿plans

???????＋???????????????＋??????????????

plane ｜             1 ｜            6

（1 row）

输出检索

扩展查询协议允许客户端批量获取输出，一次多行，而不是一次全部获取。借助游标也可以实现相同目的，但成本更高，并且规划器将优化对第一个cursor＿tuple＿fraction行的检索：

每当查询返回大量行并且客户端都需要他们时，一次检索的行数对于整体数据传输速度至关重要。单批行越大，往返延迟损失的时间越少。然而，随着批量大小的增加，节省的效率会下降。例如，从批量大小1切换到批量大小10将显著增加时间节省。但从10切换到100几乎没有任何区别。

审核编辑 ：李倩