9.1第44章
Chapter 44. PostgreSQL 内部概要
作者: 本章源自Stefan Simkovics 在维也纳理工大学写的硕士论文《Enhancement of the ANSI SQL Implementation of PostgreSQL》， 该文是由 O.Univ.Prof.Dr. Georg Gottlob和Univ.Ass. Mag. Katrin Seyr 指导的。
本章将对PostgreSQL的服务器端的后台处理进程的内部机制做概要说明。 在阅读完毕下面的章节后，你可以对数据库内部是如何处理查询的有个概念。 本章并不打算对PostgreSQL内部处理作详细解析，因为这样的一份文档将会非常庞大；本章只是试图帮助读者了解从后端收到查询后到结果返回给客户端之间大概的流程。
44.1. 查询的处理过程
下面是一个简短的描述，描述一个查询从开始到得到结果要经过的处理过程。
- 首先必须先建立起从应用程序到 PostgreSQL 服务器的连接。应用程序向服务器发送查询，然后等待接收从服务器返回的结果。
- 文法分析器检查从应用程序（客户端）发送过来的查询， 核对语法并创建一棵查询树。
- 重写子系统接到文法分析阶段生成的查询树后，搜索在系统表里预定义好的的规则，并根据规则的内容对查询树进行变换。重写系统的一个应用就是实现视图。 当一个查询访问一个视图时（如一个虚拟表），重写子系统会把用户的查询里的视图转化为视图对应的实际的表。
- 规划器/优化器接到已重写的查询树后，生成一个计划树， 传给执行器。首先，规划器/优化器列出所有能取得相同查询结果的方法，例如，如果待扫描的关系上有一个索引，那么扫描的路径就有两个：一个可能是简单的顺序查找，而另一个可能就是使用索引查找。其次，规划器/优化器计算出不同方法的执行开销，选择开销最少的方法。 开销最小的方法然后会被展开成为一个可以供执行器使用的完整的查询规划。
- 执行器递归地走过规划树并且按照规划指定的方式检索数据行。 执行器在对关系进行扫描时使用存储系统， 进行排序 和连接， 计算 条件并且最终交回生成的数据行。
在随后的小节里，我们将对上面的每一个步骤进行更详细的讨论， 以便让我们对 PostgreSQL 的内部控制和数据结构有一个更准确的理解。
44.2. 连接是如何建立起来的
PostgreSQL 是用一个简单的"每用户一进程" 的client/server 模型实现的。 在这种模式里一个客户端进程只是与一个服务器进程联接。 因为我们不知道具体要建立多少个联接， 所以我们不得不利用一个主进程在每次联接请求时派生出一个新的服务器进程来。 这个主进程叫做 postmaster， 它监听着一个特定的 TCP/IP 端口等待进来的联接。 每当检测到一个联接请求时，postmaster 进程派生出一个新的叫 postgres的服务器进程。 服务器任务（postgres 进程）相互之间使用信号灯（signal）和共享内存进行通讯， 以确保在并行的数据访问过程中的数据完整性。
客户端进程可以是任何遵循 PostgreSQL 协议（在46章里描述）的程序。 许多客户端都是基于 C 语言库 libpq， 但是也存在几个对协议之独立的实现，比如 Java JDBC 驱动。
一旦建立起来联接， 客户端进程就可以向后端（服务器）进程发送查询了。 查询是通过纯文本传输的，也就是说在 前端（客户端）不做任何分析处理。 服务器分析查询，创建执行规划， 执行该规划并且通过已经建立起来的连接把检索出来的数据行返回给客户端。
44.3. 分析器阶段
分析器阶段含两个部分：
- 在 gram.y 和 scan.l 里定义的分析器是使用 Unix 工具 yacc 和 lex制作的。
- 转换处理对分析器返回的数据结构进行修改和增补。
44.3.1. 分析器
分析器必须检查（以纯 ASCII 文本方式到来的）查询字串的语法。 如果语法正确，则创建一个分析树并将之传回， 否则，返回一个错误。实现分析器和词法器我们使用了著名的 Unix 工具 lex 和 yacc。
词法器在文件 scan.l里定义，负责识别标识符，SQL 关键字等。 对于发现的每个关键字或者标识符都会生成一个记号并且传递给分析器。
分析器在文件 gram.y 里定义并且包含一套语法规则和触发规则时执行的动作。 动作代码（实际上是 C 代码）用于建立分析树。
文件 scan.l 用 lex 转换成 C 源文件 scan.c 而 gram.y 用 yacc 转换成 gram.c。 在完成这些转换后，一个通用的 C 编译器就可以用于创建分析器。 千万不要对生成的 C 源文件做修改，因为下一次调用 lex 或 yacc 时会把它们覆盖。
注意: 上面提到的转换和编译是使用跟随 PostgreSQL 发布的 makefiles 自动完成的。
对 yacc 或者 gram.y 里的语法规则的详细描述超出本文的范围。 有很多关于 lex 和 yacc的书籍和文档。你在开始研究 gram.y 里给出的语法之前，你应该对 yacc 很熟悉，否则你是看不懂那里面的内容，理解不了发生了什么事情的。
44.3.2. 转换处理
分析器截断只使用和 SQL 语法结构相关的固定规则创建一个分析树。 它不会查找任何系统表，因此就不可能理解请求查询里面的详细的语意。 在分析器技术之后，转换处理接受分析器传过来的分析树然后做进一步处理， 解析那些理解查询中引用了哪个表，哪个函数以及哪个操作符的语意。所生成的表示这个信息的数据结构叫做查询树。
把裸分析和语意分析分成两个过程的原因是系统表查找只能在一个事务中进行， 而我们不想在一接收到查询字串就发起一个事务。 裸分析阶段已经足够可以标识事务控制命令（BEGIN，ROLLBACK，等）， 并且这些东西不用任何进一步的分析就可以执行。一旦我们知道我们正在处理一个真正 的查询（比如SELECT 或者 UPDATE）， 我们就可以发起一个事务了（如果我们还没开始这么一个）。只有这个时候可以调用转换处理。
转换处理生成的查询树结构上在很大程度上类似于裸分析树，但是在细节上有很多区别。 比如，在分析树里的 FuncCall 节点代表那些看上去像函数调用的东西。 根据引用的名字是一个普通函数还是一个聚集函数， 这个可能被转换成一个 FuncExpr 或者一个 Aggref 节点。 同样，有关字段和表达式结果的具体数据类型也添加到查询树中。
44.4. PostgreSQL 规则系统
PostgreSQL 有一个强大的规则系统， 用以描述视图和不明确的视图更新。 最初的 PostgreSQL 规则系统由两个实现组成：
- 第一个能用的规则系统采用行级别的处理， 是在执行器的深层实现的。 每次访问一条独立的行时都要调用规则系统。 这个实现在1995年被删除了，那时 伯克力 Postgres 项目的最后一个官方版本正转换成 PostgreSQL95。
- 第二个规则系统的实现从技术角度来说叫查询重写。 重写系统是一个存在于分析器阶段和规划器/优化器之间的一个模块。 这个技术实现仍然存在。
查询重写在 Chapter 34 里有比较详细的讨论，所以我们无需再次介绍。 我们只需要说明重写器的输入和输出都是查询树，也就是说，在树的语意细节的表现或者层次方面没有变化。 我们可以把重写系统当作某种宏展开的机制。
44.5. 规划器/优化器
规划器/优化器的任务是创建一个优化了执行规划。 一个特定的 SQL 查询（因此也就是一个查询树）实际上可以以多种不同的方式执行， 每种都生成相同的结果集。如果可能，查询优化器将检查每个可能的执行规划，最终选择认为运行最快的执行计划。
注意: 有些情况下，检查一个查询所有可能的执行方式会花去很多时间和内存空间。 特别是在正在执行的查询涉及大量连接操作的时候。为了在合理的时间里判断一个合理的（而不是优化的）查询计划。 PostgreSQL 使用 基因查询优化。
规划器的搜索过程实际上是与叫做 paths 的数据结构一起结合运转的， 这个数据结构是一个很简单的规划的精简版本，它只包括规划器用来决策所必须的信息。 在找到最经济的路径之后，就制作一个完整的规划树传递给执行器。 它有足够的详细信息，代表着需要执行的计划，执行器可以读懂并运行之。 在本章剩余部分，我们将忽略路径和规划之间的区别。
44.5.1. 生成可能的规划
规划器/优化器通过为扫描查询里出现的每个关系（表）生成规划， 可能的规划是由每个关系上有哪些可用的索引决定的。 对一个关系总是可以进行一次顺序查找， 所以总是会创建只使用顺序查找的规划。 假设一个关系上定义着一个索引（例如 B-tree 索引）， 并且一条查询包含约束 relation.attribute OPR constant。如果 relation.attribute 碰巧匹配 B-tree 索引的关键字并且 OPR 又是列出在索引的操作符表中的操作符中的一个， 那么将会创建另一个使用 B-tree 索引扫描该关系的规划。 如果还有别的索引， 而且查询里面的约束又和那个索引的关键字匹配，则还会生成更多的规划。
在寻找完扫描一个关系的所有可能的规划后， 接着创建连接各个关系的规划。 规划器/优化器首先考虑在 WHERE 条件里存在连接子句的连接（比如，存在象 where rel1.attr1=rel2.attr2 这样的约束）。 没有连接子句的的连接对只有在没有别的选择的时候才考虑，也就是说， 一个关系没有和任何其它关系的连接子句可用。 规划器/优化器为它们认为可能的所有的连接关系对生成规划。 有三种可能的连接策略：
- 嵌套循环连接（nested loop join）：对左边的关系里面找到的每条元组都对右边关系进行一次扫描。 这个策略容易实现，但是可能会很耗费时间。 （但是，如果右边的关系可以用索引扫描，那么这个可能就是个好策略。 我们可以用来自左手边关系的当前行的数值为键字进行对右手边关系的索引扫描。）
- 融合排序连接（merge join）：在连接开始之前，每个关系都对连接字段进行排序。 然后对两个关系并行扫描，匹配的行就组合起来形成连接行。 这种联合更有吸引力，因为每个关系都只用扫描一次。 要求的排序步骤可以通过明确的排序步骤，或者是使用连接键字上的索引按照恰当的顺序扫描关系。
- 散列连接（hash join） ：首先扫描右边的关系，并用连接的字段作为散列键字装载进入一个散列表， 然后扫描左边的关系，并将找到的每行用作散列键字来以定位表里匹配的行。
如果查询里的关系多于两个，最后的结果必须通过一个连接步骤树建立， 每个步骤有两个输入。规划器检查不同的连接顺序可能，找出开销最小的。
完成的查询树由对基础关系的顺序或者索引扫描组成，并根据需要加上嵌套循环， 融合，或者散列连接节点，加上任何需要的辅助步骤，比如排序节点或者聚集函数计算节点等。 大多数这些规划节点类型都有额外的做选择（抛弃那些不符合指定布尔条件的行）和投影 （基于给出的字段数值，计算一个派生出的字段集，也就是，在需要时计算标量表达式）。 规划器的一个责任是从 WHERE 子句中附加选择条件以及为规划树最合适的节点计算所需要的输出表达式。
44.6. 执行器
执行器接受规划器/优化器传过来地查询规划然后递归地处理它， 抽取所需要地行集合。它实际上是一个需求－拉动地流水线机制。 每次调用一个规划节点地时候，它都必须给出更多的一个行，或者汇报它已经完成行的传递了。
为了提供一个扎实的例子，假设顶端节点是一个 MergeJoin 节点。 在做任何融合之前，首先得抓取两行（每个子规划一行）。因此执行器递归地调用自己来处理子规划（它从附着在 lefttree上的子规划开始）。 新的顶端节点（左子规划的顶端节点）假设是，一个 Sort 节点， 然后还是需要递归地获取一个输入行。Sort 节点的子节点可能是一个 SeqScan 节点，代表对一个表的实际读取动作。 这个节点的执行导致执行器从表中抓取一行然后把它返回给调用的节点。 Sort 将不断调用它的子节点以获取需要排序的所有行。 在用尽输入之后（由子节点返回一个 NULL 而不是一行表示），Sort 代码执行排序，然后就可以返回它的第一个输出行，也就是按照排序顺序输出的第一行。 它仍然保持剩下的行的排序状态，这样在随后有需求的时候，它就可以按照排序顺序返回这些行。
MergeJoin 节点也会类似地要求从它的右边子规划获取第一行。 然后它比较这两行看看它们是否能连接；如果能，那么它给它的调用者返回一个连接行。 在下一次调用的时候，或者是在它无法连接当前的两行的时候就是这次调用的时候， 它抓取其中一个表的下一行（抓取哪个表取决于比较结果如何），然后再检查看看两个表是否匹配。 最后，其中一个子规划耗尽资源，而 MergeJoin 返回 NULL，表明无法继续生成更多的连接行。
复杂的查询可能包含许多层的规划节点，但是一般的过程都是一样的： 每个节点在每次被调用的时候都计算并返回它的下一个输出行。 每个节点同样负责附加上任何规划器赋予它的选择或者投影表达式。
执行器机制是用于计算所有的四种基本 SQL 查询类型的： SELECT，INSERT，UPDATE， 和 DELETE。对于 SELECT 而言，顶层的执行器代码只是需要发送查询规划树返回的每一行给客户端。 对于 INSERT，返回的每一行都插入到 INSERT 声明的目标表中。 （一个简单的 INSERT ... VALUES 命令创建一个简单的规划树，包含一个 Result 节点，它只计算得出一个结果行。 但是 INSERT ... SELECT 可能需要执行器的全部能力。） 对于 UPDATE，规划器安排每个计算出来的行都包括所有更新的字段，加上原来的目标行的 TID （元组 ID，或者行 ID）； 执行器的顶层使用这些信息创建一个新的更新过的行，并且标记旧行被删除。对于 DELETE， 规划实际上返回的唯一的一个字段是 TID，然后执行器的顶层简单地使用这个 TID 访问每个目标行，并且把它们标记为已删除。
