Query Execution Stages

Posted on In

1. Demo Database

前面章节中的示例都是基于只有几行数据的简单表。本章以及后面的章节要处理查询执行，在这方面对数据要求更高：我们需要行数多得多、彼此有关联的表。为了不在每个示例中都重新发明一个新的数据集，我选用了一个现成的演示数据库，它展示了俄罗斯的客运航空交通情况。这个数据库有多个版本；我们将使用 2017 年 8 月 15 日创建的较大版本。要安装这个版本，你需要从压缩包中解压出包含数据库副本的文件，然后在 psql 中运行这个文件。

在开发这个演示数据库时，我们尝试让它的模式（schema）足够简单，以便无需额外说明就能理解；同时，我们也希望它足够复杂，能够用来编写有意义的查询。数据库填充了贴近真实场景的数据，这使得示例更加全面，也更有趣味性。

这里我只会简要介绍主要的数据库对象；如果你想查看整个模式(schema)，可以参阅脚注中引用的完整描述。

主要的实体(entity)是 预订（booking），它对应于 bookings 表。一个预订可以包含多个乘客，每个乘客都有单独的电子机票（对应 tickets 表）。乘客本身不构成独立的实体；在我们的实验中，我们假设所有乘客都是唯一的

每张机票包含一个或多个航段（对应 ticket_flights 表）。一张机票之所以可能有多个航段，主要有两种情况：要么它是往返票，要么它包含联程航班。虽然数据库模式中没有相应的约束，但我们假设同一个预订（booking）中的所有机票都拥有相同的航段。

每个航班（flights 表）都从一个机场（airports 表）飞往另一个机场。具有相同航班号的航班拥有相同的出发地和目的地，但起飞日期不同。

routes 视图基于 flights 表构建；它展示的是与具体航班日期无关的航线信息。

在值机时，每位乘客都会被发放一张带有座位号的登机牌（boarding_passes 表）。乘客只能为机票中包含的航班办理值机。航班 + 座位 的组合必须唯一，因此不可能为同一个座位发放两张登机牌。

飞机上的座位数量（seats 表）以及这些座位在不同舱位之间的分布，取决于执行该航班的具体机型（aircrafts 表）。我们假设每一种机型只能有一种客舱布局。

有些表使用了代理主键（surrogate primary key），而另一些表使用了自然主键（natural key）（其中有些还是复合主键）。这样设计纯粹是为了演示，绝不是推荐的实践方式。

这个演示数据库可以看作是真实系统的一份转储：其中包含了某个过去时间点的数据快照。要查看这个时间，可以调用 bookings.now() 函数。在需要使用 now() 的真实查询场景中，你可以在演示查询里使用这个函数。

机场、城市和机型的名称存储在 airports_data 和 aircrafts_data 表中，并提供了两种语言：英文和俄文。为了构建本章的示例，我通常会查询实体关系图中显示的 airports 和 aircrafts 这两个视图；这些视图会根据 bookings.lang 参数的值来选择输出语言。不过在查询计划中，有些底层表的名称仍然可能会出现。

2. Simple Query Protoco

一种简单版本的客户端–服务器协议即可实现 SQL 查询的执行：客户端将查询文本发送给服务器，而服务器则返回完整的执行结果——无论结果包含多少行。发送到服务器的查询会经过几个阶段：解析（parse）→ 转换（transform）→ 计划（plan）→ 执行（execute）。

qes1

Parsing

首先，PostgreSQL 必须对查询文本进行解析（parse），以便理解需要执行的内容。

Lexical and syntactic analysis 词法分析器（lexer）会把查询文本拆分成一组词法单元（lexemes），例如关键字、字符串字面量、数字字面量等；而语法分析器（parser）会根据 SQL 的语言语法规则对这组词法单元进行验证。PostgreSQL 使用的是标准的解析工具，即 Flex 和 Bison。

解析后的查询会以抽象语法树（AST）的形式存储在后端进程的内存中。

例如，让我们来看下面这个查询：

1
2
3
4
SELECT schemaname, tablename
FROM pg_tables
WHERE tableowner = 'postgres'
ORDER BY tablename;

词法分析器从中识别出了 5 个关键字、5 个标识符、1 个字符串字面量，以及 3 个单字符词素（一个逗号、一个等号和一个分号）。语法分析器则使用这些词素来构建解析树，下面的插图展示了一个高度简化的解析树。树中每个节点旁的文字说明表示该节点对应查询中的哪一部分：

qes2

一个比较晦涩的缩写 RTE 代表 Range Table Entry（范围表项）。PostgreSQL 的源代码中使用 range table（范围表） 这个术语来指代表、子查询、连接结果——换句话说，指代 任何可以被 SQL 运算符处理的行集（set of rows）

语义分析（Semantic analysis） 的目的在于确认数据库中是否存在该查询按名称引用的表或其他对象，并检查用户是否拥有访问这些对象的权限。语义分析所需的全部信息都存储在 系统目录（system catalog） 中。

在获得解析树之后，语义分析器会对其进行进一步的重组，这包括：为解析树添加对具体数据库对象、数据类型以及其他信息的引用。

如果你启用了参数 debug_print_parse，就可以在服务器日志中看到完整的解析树，但这通常没有太大的实际意义。

Transformation

在下一阶段，查询会被转换（重写，rewrite）。

PostgreSQL 核心在多个场景下会使用查询转换。其中之一就是：
将解析树中 视图（view） 的名称替换为该视图底层查询（base query）对应的子树。

另一个使用转换的场景是行级安全（Row-Level Security, RLS） 的实现。
另外，递归查询中的 SEARCH 和 CYCLE 子句也会在此阶段被转换。

在上面的示例中，pg_tables 是一个视图；如果我们把它的定义直接展开写进查询文本，它将会是下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT schemaname, tablename
FROM (-- pg_tables
    SELECT n.nspname AS schemaname,
        c.relname AS tablename,
        pg_get_userbyid(c.relowner) AS tableowner,
        ...
    FROM pg_class c
        LEFT JOIN pg_namespace n ON n.oid = c.relnamespace
        LEFT JOIN pg_tablespace t ON t.oid = c.reltablespace
    WHERE c.relkind = ANY (ARRAY['r'::char, 'p'::char])
)
WHERE tableowner = 'postgres'
ORDER BY tablename；

不过，服务器并不会处理查询的文本表示；所有操作都在解析树（parse tree）上完成。下图展示的是一个简化后的重写树（如果启用 debug_print_rewritten 参数，你可以在服务器日志中看到其完整版本）。

解析树只反映了查询的语法结构，但并不包含任何关于操作执行顺序的信息。

此外，PostgreSQL 还支持自定义转换，用户可以通过 rewrite rule（重写规则）系统来实现自己的查询重写逻辑。

qes3

规则系统（rule system）的支持曾被宣称为 Postgres 开发的主要目标之一；在最初实现规则系统时，Postgres 还只是一个学术项目，但之后规则系统已经多次被重新设计。规则系统非常强大，但也相当难以理解和调试。甚至有人提议直接把规则系统从 PostgreSQL 中移除，但这一想法并未得到一致认可。在大多数情况下，使用 触发器（trigger） 会比使用规则更加安全且容易。

Planning

SQL 是一种声明式语言：查询只说明要取什么数据，而不说明如何取。

任何查询都可以有多种执行路径。解析树中的每个操作都可能有多种完成方式：
例如，结果既可以通过全表扫描（读取整张表并过滤掉不需要的数据）得到，也可以通过索引扫描来找到所需行。数据集在连接时总是两两结合（pairwise joins），这意味着连接顺序存在大量组合，从而产生数量巨大的候选执行方案。此外，还有多种连接算法（join algorithms）：例如，执行器可以扫描第一个数据集的每一行，并在第二个数据集中查找匹配行；或者，先对两个数据集进行排序，再执行合并连接（merge join）。对每一种算法，都能找到其优于其他算法的使用场景。

最优计划与非最优计划的执行时间可能相差几个数量级，因此用于对解析后的查询进行优化的 计划器（planner） 是系统中最复杂的组件之一

Plan tree 执行计划同样以树结构表示，但其节点处理的是物理数据操作，而不是逻辑操作。

如果你想查看完整的计划树，可以启用 debug_print_plan 参数，将计划树输出到服务器日志中。但在实际工作中，通常只需要查看 EXPLAIN 命令显示的文本形式的执行计划就足够了。

下图突出展示了执行计划树中的主要节点。正是这些节点会出现在下面 EXPLAIN 命令的输出中。

暂时我们先关注以下两点：

  • 这棵计划树中只包含了三个被查询表中的两个：规划器发现其中一个表对获取结果并非必需，于是将其从计划树中移除了。
  • 对于计划树中的每个节点，规划器都会给出估算的成本（cost）以及预计要处理的行数（rows）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
=> 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)

查询计划中的 Seq Scan 节点表示顺序扫描表数据，
而 Nested Loop 节点则表示连接（join）操作。

qes4

Plan search PostgreSQL 使用的是基于成本（cost-based）的优化器；它会遍历可能的执行计划，并估算执行这些计划所需的资源，例如 I/O 操作或 CPU 周期。这种估算会被归一化为一个数值，称为该计划的 cost（成本）。在所有被考虑的计划中，优化器最终会选择 成本最低的那个计划。

问题在于：潜在可用的执行计划数量会随着参与连接的表数呈指数级增长，因此即使针对相对简单的查询，也不可能把所有计划都枚举一遍。通常，规划器会使用动态规划（dynamic programming）算法并结合一些启发式规则（heuristics）来缩小搜索范围。这种方法使规划器能够在可接受的时间内，为包含大量表的查询找到数学上最优的执行计划。

准确的解决方案并不能保证所选计划确实是最佳计划，因为规划器使用简化的数学模型，可能缺乏可靠的输入数据

Managing the order of joins 查询可以通过某种结构方式来限制优化器的搜索范围（当然，这样做有可能错过最优执行计划）。

  • 公共表表达式（CTE） 和主查询可以被分别优化；如果你想强制这种行为，可以使用 MATERIALIZED 子句。

  • 在非 SQL 函数内部运行的子查询 总是会被单独优化。（SQL 函数有时可能会被 inline 到主查询中。）

  • 如果你设置了 join_collapse_limit 并在查询中使用显式的 JOIN 语法，那么部分连接顺序会被查询的语法结构所固定；类似地，from_collapse_limit 对子查询有相同的效果。

最后一点可能需要解释一下。让我们来看一个示例：在 FROM 子句中列出表，但没有写任何显式 JOIN 的查询。

1
2
3
SELECT ...
FROM a, b, c, d, e
WHERE ..

在这种情况下，规划器必须考虑所有可能的连接（join）组合。该查询会由解析树中的如下部分来表示（示意性展示）。

qes5

在下一个示例中，连接（join）的结构由 JOIN 子句 明确定义。

1
2
3
SELECT ...
FROM a, b JOIN c ON ..., d, e
WHERE ...

解析树会反映出这种结构。

qes6

规划器通常会将连接树（join tree）扁平化，使其看起来与第一个示例中的结构类似。该算法会递归遍历整棵树，并将每个 JOINEXPR 节点替换为其包含元素的扁平列表。

然而，只有当生成的扁平列表元素数量不超过 join_collapse_limit 时，这种合并操作才会执行。在这个特定的例子中，如果 join_collapse_limit 的值小于五，JOINEXPR 节点将不会被合并。

对于查询优化器而言，这意味着：

  • 表 B 必须与表 C 进行连接（或者反过来，C 必须与 B 连接；在这对表中的连接顺序没有限制）。
  • 表 A、D、E 以及 B 和 C 连接的结果可以按任意顺序进行连接。

如果 join_collapse_limit 参数设置为 1，则显式 JOIN 子句中定义的顺序将被保留。

关于 FULL OUTER JOIN 的操作数，它们永远不会被合并（collapsed），无论 join_collapse_limit 参数的值是多少。

from_collapse_limit 参数以类似的方式控制子查询的扁平化。虽然子查询看起来不像 JOIN 子句，但在解析树（parse tree）层面上，这种相似性就很明显了

一个例子：

1
2
3
4
5
6
7
SELECT ... 
FROM a,
(
	SELECT ... FROM b, c WHERE ...
) bc,
d, e 
WHERE ...

对应的JOIN树如下所示。这里唯一的区别是，这棵树包含的是 FROMEXPR 节点，而不是 JOINEXPR（因此参数名如此命名）。

qes7

遗传查询优化（Genetic query optimization） 在将查询树扁平化之后，某一层可能包含过多的元素——无论是表还是中间连接结果，这些元素都需要单独进行优化。由于查询计划的生成时间会随着需要连接的数据集数量呈指数增长，因此plan时间可能会超出所有合理的范围。

如果启用了 geqo 参数，并且某一层的元素数量超过 geqo_threshold 的阈值，查询规划器将使用遗传算法来优化查询。相比动态规划，遗传算法的速度要快得多，但它无法保证找到的查询计划一定是最优的。因此，一条经验法则是通过减少需要优化的元素数量来避免使用遗传算法。

遗传算法有若干可配置参数，但在此不作详细介绍。

选择最佳执行计划 查询计划是否可以被认为是最优的，取决于特定客户端如何使用查询结果。如果客户端需要一次性获取完整结果（例如，用于生成报表），那么计划应当优化所有行的检索效率。但如果优先考虑尽快返回前几行（例如，用于屏幕显示），那么最优计划可能完全不同。

为了做出这个选择，PostgreSQL 会计算成本的两个组成部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
=> 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)

第一个组成部分（启动成本）表示节点执行前的准备开销；第二个组成部分（总成本）则包括获取查询结果过程中产生的所有开销。

有时人们会说启动成本是获取结果集第一行的开销，但这种说法并不完全准确。

为了挑选出首选执行计划，优化器会检查查询是否使用了游标（无论是通过 SQL 中的 DECLARE 命令，还是在 PL/pgSQL 中显式声明（explicitly））。如果没有使用游标，则默认客户端需要一次性获取完整结果，优化器会选择总成本最小的计划。

如果查询是通过游标执行的，则所选计划必须优化仅获取所有行中 cursor_tuple_fraction 部分的效率。更准确地说，PostgreSQL 会选择使以下表达式值最小的计划：

1
startup cost + cursor_tuple_fraction (total cost − startup cost)

** 成本估算概述 ** 要估算一个计划的总成本，必须对计划中的所有节点进行成本估算。节点的成本取决于其类型（显而易见，读取堆表数据的成本与排序操作的成本不同）以及节点处理的数据量（数据量越大，通常成本越高）。虽然节点类型是已知的，但数据量只能根据输入集的预计基数（节点接收的行数）以及节点的选择性（输出中剩余行的比例）来预测。这些计算依赖于收集到的统计信息，例如表的大小以及表列中数据的分布情况。

如果对每个节点的基数估计准确，计算出的成本很可能能够较好地反映实际成本。规划中主要的缺陷通常源于基数和选择性的估计不准确，这可能由以下原因造成：

  1. 统计信息不准确或过时；
  2. 无法使用统计信息；
  3. （程度较轻）规划模型本身的不完善。

基数估计（Cardinality estimation） 要计算节点的基数，优化器必须递归地完成以下步骤：

  1. 估算每个子节点的基数，并评估该节点将从子节点接收到的输入行数；
  2. 估算节点的选择性(Selectivity)，即输出中剩余的输入行所占的比例。

节点的基数即这两个值的乘积。

选择性(Selectivity)用一个介于 0 到 1 之间的数表示。数值越小，选择性越高；反之，数值接近 1 表示选择性较低。乍一看可能不太直观，其含义是：高选择性条件会筛掉几乎所有行，而只排除少量行的条件则选择性低。

首先，优化器会估算定义数据访问方式的叶子节点的基数。这些计算依赖于收集到的统计信息，例如表的总大小。

过滤条件的选择性取决于条件的类型。在最简单的情况下，可以将其假设为一个常数值，尽管优化器会尽量利用所有可用信息来精确估算。通常，只需要掌握如何估算简单过滤条件即可；如果条件包含逻辑运算，其选择性则按照以下公式计算：

1
2
sel𝑥 𝑎𝑛𝒅 𝑦 = sel𝑥sel𝑦
sel𝑥 𝑜𝒓 𝑦  = 1−(1−sel𝑥)(1−sel𝑦) = sel𝑥+sel𝑦−sel𝑥sel𝑦

sel_X：满足条件 X 的行比例 sel_Y：满足条件 Y 的行比例 条件 X AND Y：满足两个条件的行，概率就是两者独立事件概率的乘积; (1 - sel_X)：不满足 X 的行比例, (1 - sel_Y)：不满足 Y 的行比例, (1 - sel_X)(1 - sel_Y)：同时不满足 X 和 Y 的行比例.所以 1 − (1 − sel_X)(1 − sel_Y) = 满足 X 或 Y 的行比例

不幸的是，上述公式假设谓词 X 和 Y 彼此独立。对于相关（correlated）的谓词，这类估算将不准确。

要估算 连接（join）的基数，优化器必须首先计算笛卡尔积的基数（即两个数据集基数的乘积），然后估算连接条件的选择性，这仍然取决于条件类型。

其他节点（如排序或聚合）的基数估算方式也类似。

需要注意的是：下层节点基数估算不准确，会影响后续所有计算，导致总成本估算不准确，从而选择了不理想的执行计划。更糟糕的是，优化器没有关于连接结果的统计信息，只能依赖表的统计信息。

成本估算 成本估算的过程同样是递归的。要计算一个子树的成本，需要先计算并累加其所有子节点的成本，然后再加上父节点自身的成本。

在估算节点成本时，PostgreSQL 会根据该节点执行的操作建立数学模型，并以已经估算好的节点基数作为输入。对于每个节点，都会计算 启动成本 和 总成本。

某些操作没有前置条件，因此可以立即执行，这类节点的启动成本为零。

而另一类操作则必须等待一些前置操作完成后才能执行。例如，排序节点通常需要等待其子节点返回所有数据后，才能进行自己的任务。这类节点的启动成本通常大于零：即使上层节点（或客户端）只需要输出中的一行，也必须支付这一成本。

优化器进行的所有计算都是估算值，可能与实际执行时间无关。它们的唯一目的，是在相同条件下对同一查询的不同执行计划进行比较。在其他情况下（尤其是不同查询之间），用成本来比较意义不大。例如，由于统计信息过时，成本可能被低估；在统计信息刷新后，计算出的成本可能上升，但由于估算更准确，服务器会选择更优的执行计划。

Execution

在查询优化阶段生成的执行计划现在必须被执行。

执行器（executor）会在后端内存中打开一个 portal，这是一个保存当前正在执行查询状态的对象。这个状态以一棵树的形式表示，结构与执行计划树相同。树中的各节点像流水线一样运作，彼此请求并传递行数据。

qes8

查询执行从根节点开始。以本例为例，根节点表示 排序（SORT）操作，它从子节点获取数据。在接收到所有行之后，根节点对数据进行排序，并将结果传递给客户端。

某些节点（如图示中的 NESTLOOP 节点）负责将来自不同来源的数据集进行连接。此类节点会从两个子节点拉取数据，并在收到满足连接条件的行对后立即向上层传递结果行（与排序不同，排序必须先获取所有行）。此时，节点的执行会暂停，直到其父节点请求下一行。如果查询只需要部分结果（例如包含 LIMIT 子句），该操作不会执行完整。

树中的两个 SEQSCAN 叶子节点负责表扫描。当父节点请求数据时，这些节点会从对应的表中获取下一行数据。

因此，一些节点不存储任何行，而是立即向上层传递数据；而其他节点（如 SORT）可能需要保留大量数据。为此，后端内存中会为其分配一个 work_mem 内存块；如果内存不足，多余的数据会溢写到磁盘上的临时文件。

一个执行计划可能包含多个需要数据存储的节点，因此 PostgreSQL 可能会分配多个 work_mem 大小的内存块。查询可使用的总 RAM 大小没有任何限制。

翻译来之

  1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals