PostgreSQL 技术内幕

《PostgreSQL 技术内幕》由 Hironobu Suzuki 原著，中文版经正规出版引进。本站以冯若航、刘阳明和张文升完成的 2018 年中文译稿为主体，并持续补译英文原著新增内容。

全书从数据库集簇、进程和查询处理出发，依次进入并发控制、VACUUM、缓冲区、WAL、备份、时间点恢复、物理流复制与逻辑复制。

阅读本书

• 阅读完整目录定位十二章与技术附录。
• 从作者序或第一章开始顺序阅读。
• 打开整书打印视图阅读或另存为 PDF。
• 查阅许可与授权了解版权与使用条款。

版本说明

这份中文译稿主体反映 PostgreSQL 9.x 至 11 前后的实现；本站另补译了英文原著后来加入、涉及 PostgreSQL 10 至 19 的章节。第 12 章在英文原著中仍标为 Beta/WIP，PostgreSQL 19相关内容也属于发布前描述。涉及当前 PostgreSQL 行为时，请同时查阅持续更新的英文原著、PostgreSQL 官方文档与源码。

作者序

中国的PostgreSQL用户们，你们好！

本书详细解释了PostgreSQL的内部工作细节，目标读者为DBA与系统开发人员。理解数据库内部机制很有挑战，愿本书能在您精通PostgreSQL的道路上有所助益。

本书能出中文版，我真的感到非常高兴，我这样认为是有原因的。

这是我的书中第一本被翻译成外语的作品。当自己的书出版时，心情愉悦自不必说，而自己的一部作品能翻译成外语出版，更是一件非常令人激动的事情。

其次，我收到了来自世界各地的电子邮件，请求将这本书翻译成各种外语。实际上，至少有一半的邮件来自中国。许多邮件跟我说“这本书对中国PostgreSQL用户很有必要”，因此，我很高兴终于能对他们的要求作出回应。

而最重要的原因与我的家族史有关。先父于多年前去世，他在中国的哈尔滨住过好几年。此后他回到日本，而我出生了。他患心脏病已经很长时间了，因此脾气很差。我对他的印象很差，除了一件事。当我还是孩子的时候，父亲每晚睡觉前都会给我和妹妹讲他在中国的经历。在讲这些时，他总是显得非常高兴，经常说中国人民帮助了他。

他的故事给我留下了深刻的印象，当然也影响了我的人生。因为这些故事，我从小就对这个世界和未知的事物有强烈的好奇心，而我的好奇心也引领我走向软件工程的道路。而现在，我已经在中国出版了我的第一本书。简而言之，这是一个关于日本家庭与中国之间让爱接力传递的故事。

我很高兴终于能把这份情还给中国人民了。当然，这本书是一份很小的礼物。然而，我愿充满感激之情地将它献给您。

2017年，我有幸访问中国，亲眼目睹了中国令人惊叹的发展。对我而言，这是一次非常难忘的经历。我希望能再去中国，如果有机会，我也想在中国工作。

无论如何，让我们享受PostgreSQL吧！

2018年11月

致谢

本书的出版离不开出版社工作人员与译者们巨大的努力与付出，对此我深表感激。

作者

Hironobu Suzuki 日语：鈴木 啓修

我毕业于信息工程研究生院 （信息工程硕士），曾在多家公司担任软件开发人员和技术经理/技术主管。我在数据库和系统集成领域出版了七本书（3本PostgreSQL书和3本MySQL书）。

作为日本PostgreSQL用户组的主任（2010-2016），我连续六年组织了日本规模最大的 （非商业）PostgreSQL技术研讨会，并担任日本2013年PostgreSQL大会的委员会主席，以及2008年和2009年的委员会成员。

当我年轻时，曾在厄瓜多尔住了两年，有时我会回到那里去。

目前我住在爱尔兰，都柏林。

译者序

各位读者你们好，相信能选择这本书的读者，大多已经对PostgreSQL有所了解了。本书从PostgreSQL的整体架构展开，依次介绍了各个功能模块的来龙去脉，对于DBA与数据库系统开发人员了解数据库内部原理，阅读学习PostgreSQL源码是不可多得的一本好书。

数据库是信息系统的核心组件，关系型数据库则是数据库皇冠上的明珠，而PostgreSQL的官方口号是“世界上最先进的开源关系型数据库”。PostgreSQL在各行各业、各种场景下都有着广泛应用。但会用只是“知其然”，知道背后的原理，才能“知其所以然”。对数据库原理及其具体实现的理解，能让架构师以最小的复杂度代价实现所需的功能，能让程序员以最少的复杂度代价写出更可靠高效的代码，也能让DBA在遇到疑难杂症时获得精准的直觉与深刻的洞察。

数据库是一个博大精深的领域，存储、I/O、计算无所不包。PostgreSQL可以视作关系型数据库实现的典范，用不到100万行C代码实现如此丰富的软件系统，可谓凝练无比。它的每一个功能模块都值得用一本甚至几本书的篇幅去介绍。本书限于篇幅，虽无法一一深入所有细节，但它为读者进一步理解PostgreSQL提供了一幅全局概念地图。读者完全可以顺着各章线索，以点带面，深入挖掘源码背后的设计思路。

我偶然发现了这本书，读完之后感觉受益匪浅。这么好的书没有中文翻译，实在是遗憾，遂萌生了翻译的念头。某不才，愿为PostgreSQL在中国的发展贡献一份力量。译者水平有限，翻译如有疏漏，还望读者海涵。

译者

冯若航，刘阳明，张文升

探探 PostgreSQL DBA Team

1 数据库集簇、数据库与数据表

第一章和第二章简单介绍了一些 PostgreSQL 的基础知识，有助于读者理解后续章节的内容。本章包括以下几个主题：

• 数据库集簇（database cluster） 的逻辑结构
• 数据库集簇的物理结构
• 堆表（heap table） 文件的内部布局
• 从表中读写数据的方式

如果你已经熟悉这些内容，可以跳过本章。

1.1 数据库集簇的逻辑结构

数据库集簇（database cluster）是一组数据库（database） 的集合，由一个PostgreSQL服务器管理。第一次听到这个定义也许会令人疑惑，PostgreSQL中的术语“数据库集簇”，并非 意味着“一组数据库服务器”。 一个PostgreSQL服务器只会在单机上运行并管理单个数据库集簇。

图1.1展示了一个数据库集簇的逻辑结构。 数据库（database） 是 数据库对象（database objects） 的集合。 在关系型数据库理论中，数据库对象是用于存储或引用数据的数据结构。 （堆）表是一个典型的例子，还有更多种对象，例如索引，序列，视图，函数等。 在PostgreSQL中数据库本身也是数据库对象，并在逻辑上彼此分离。 所有其他的数据库对象（例如表，索引等）归属于各自相应的数据库。

在 PostgreSQL 内部，所有的数据库对象都通过相应的 对象标识符（Object Identifiers, OID） 进行管理，这些标识符是无符号的4字节整型。数据库对象与相应OID之间的关系存储在相应的系统目录中，依具体的对象类型而异。 例如数据库和堆表对象的OID分别存储在pg_database和pg_class中，因此当你希望找出OID时，可以执行以下查询：

sampledb=# SELECT datname, oid FROM pg_database WHERE datname = 'sampledb';
 datname  |  oid  
----------+-------
 sampledb | 16384
(1 row)

sampledb=# SELECT relname, oid FROM pg_class WHERE relname = 'sampletbl';
  relname  |  oid  
-----------+-------
 sampletbl | 18740 
(1 row)

1.2 数据库集簇的物理结构

数据库集簇在本质上就是一个文件目录，名曰 基础目录（base directory），包含着一系列子目录与文件。 执行 initdb 命令会在指定目录下创建基础目录从而初始化一个新的数据库集簇。 通常会将基础目录的路径配置到环境变量PGDATA中，但这并不是必须的。

图1.2 展示了一个PostgreSQL数据库集簇的例子。 base子目录中的每一个子目录都对应一个数据库，数据库中每个表和索引都会在相应子目录下存储为（至少）一个文件；还有几个包含特定数据的子目录，以及配置文件。 虽然PostgreSQL支持表空间（Tablespace），但该术语的含义与其他RDBMS不同。 PostgreSQL中的表空间对应一个包含基础目录之外数据的目录。

后续小节将描述数据库集簇的布局，数据库的布局，表和索引对应的文件布局，以及PostgreSQL中表空间的布局。

1.2.1 数据库集簇的布局

官方文档 中描述了数据库集簇的布局。 表1.1中列出了主要的文件与子目录：

1.2.2 数据库布局

一个数据库与base子目录下的一个子目录对应；且该子目录的名称与相应数据库的OID相同。 例如当数据库sampledb的OID为16384时，它对应的子目录名称即为16384。

$ cd $PGDATA
$ ls -ld base/16384
drwx------  213 postgres postgres  7242  8 26 16:33 16384

1.2.3 表与索引相关文件的布局

每个小于1GB的表或索引都在相应的数据库目录中存储为单个文件。在数据库内部，表和索引作为数据库对象是通过OID来管理的，而这些数据文件则由变量relfilenode管理。 表和索引的relfilenode值通常与其OID一致，但也有例外，下面将详细展开。

让我们看一看表sampletbl的oid和relfilenode：

sampledb=# SELECT relname, oid, relfilenode FROM pg_class WHERE relname = 'sampletbl';
  relname  |  oid  | relfilenode
-----------+-------+-------------
 sampletbl | 18740 |       18740 
(1 row)

从上面的结果可以看出oid和relfilenode值相等。还可以看到表sampletbl的数据文件路径是base/16384/18740。

$ cd $PGDATA
$ ls -la base/16384/18740
-rw------- 1 postgres postgres 8192 Apr 21 10:21 base/16384/18740

表和索引的relfilenode值会被一些命令（例如TRUNCATE，REINDEX，CLUSTER）所改变。 例如对表 sampletbl执行TRUNCATE，PostgreSQL会为表分配一个新的relfilenode（18812），删除旧的数据文件（18740），并创建一个新的数据文件（18812）。

sampledb=# TRUNCATE sampletbl;
TRUNCATE TABLE

sampledb=# SELECT relname, oid, relfilenode FROM pg_class WHERE relname = 'sampletbl';
  relname  |  oid  | relfilenode
-----------+-------+-------------
 sampletbl | 18740 |       18812 
(1 row)

在9.0或更高版本中，内建函数pg_relation_filepath能够根据OID或名称返回关系对应的文件路径，非常实用。

sampledb=# SELECT pg_relation_filepath('sampletbl');
pg_relation_filepath 
----------------------
base/16384/18812
(1 row)

当表和索引的文件大小超过1GB时，PostgreSQL会创建并使用一个名为relfilenode.1的新文件。如果新文件也填满了，则会创建下一个名为relfilenode.2的新文件，依此类推。

译者注：数据库系统中的 表（Table） 与关系代数中的 关系（Relation） 关系紧密但又不尽相同。在PostgreSQL中，表，索引，TOAST表都归类为关系。

$ cd $PGDATA
$ ls -la -h base/16384/19427*
-rw------- 1 postgres postgres 1.0G  Apr  21 11:16 data/base/16384/19427
-rw------- 1 postgres postgres  45M  Apr  21 11:20 data/base/16384/19427.1
...

在构建PostgreSQL时，可以使用配置选项--with-segsize更改表和索引的最大文件大小。

仔细观察数据库子目录就会发现，每个表都有两个与之相关联的文件，后缀分别为_fsm和_vm。这些实际上是空闲空间映射（free space map）和可见性映射（visibility map） 文件，分别存储了表文件每个页面上的空闲空间信息与可见性信息（更多细节见第5.3.4节和第6.2节）。索引没有可见性映射文件，只有空闲空间映射文件。

一个具体的示例如下所示：

$ cd $PGDATA
$ ls -la base/16384/18751*
-rw------- 1 postgres postgres  8192 Apr 21 10:21 base/16384/18751
-rw------- 1 postgres postgres 24576 Apr 21 10:18 base/16384/18751_fsm
-rw------- 1 postgres postgres  8192 Apr 21 10:18 base/16384/18751_vm

在数据库系统内部，这些文件（主体数据文件，空闲空间映射文件，可见性映射文件等）也被称为相应关系的分支（fork）；空闲空间映射是表/索引数据文件的第一个分支（分支编号为1），可见性映射表是数据文件的第二个分支（分支编号为2），数据文件的分支编号为0。

译者注：每个 关系（relation） 可能会有四种分支，分支编号分别为0，1，2，3，0号分支main为关系数据文件本体，1号分支fsm保存了main分支中空闲空间的信息，2号分支vm保存了main分支中可见性的信息，3号分支init是很少见的特殊分支，通常用于不被日志记录（unlogged）的表与索引。

每个分支都会被存储为磁盘上的一到多个文件：PostgreSQL会将过大的分支文件切分为若干个段，以免文件的尺寸超过某些特定文件系统允许的大小，也便于一些归档工具进行并发复制，默认的段大小为1GB。

1.2.4 表空间

PostgreSQL中的 表空间（Tablespace） 是基础目录之外的附加数据区域。 在8.0版本中引入了该功能。

图1.3展示了表空间的内部布局，以及表空间与主数据区域的关系。

执行CREATE TABLESPACE语句会在指定的目录下创建表空间。而在该目录下还会创建版本特定的子目录（例如PG_9.4_201409291）。版本特定的命名方式为：

PG_主版本号_目录版本号

举个例子，如果在/home/postgres/tblspc中创建一个表空间new_tblspc，其oid为16386，则会在表空间下创建一个名如PG_9.4_201409291的子目录。

$ ls -l /home/postgres/tblspc/
total 4
drwx------ 2 postgres postgres 4096 Apr 21 10:08 PG_9.4_201409291

表空间目录通过pg_tblspc子目录中的符号链接寻址，链接名称与表空间的OID值相同。

$ ls -l $PGDATA/pg_tblspc/
total 0
lrwxrwxrwx 1 postgres postgres 21 Apr 21 10:08 16386 -> /home/postgres/tblspc

如果在该表空间下创建新的数据库（OID为16387），则会在版本特定的子目录下创建相应目录。

$ ls -l /home/postgres/tblspc/PG_9.4_201409291/
total 4
drwx------ 2 postgres postgres 4096 Apr 21 10:10 16387

如果在该表空间内创建一个新表，但新表所属的数据库却创建在基础目录下，那么PG会首先在版本特定的子目录下创建名称与现有数据库OID相同的新目录，然后将新表文件放置在刚创建的目录下。

sampledb=# CREATE TABLE newtbl (.....) TABLESPACE new_tblspc;

sampledb=# SELECT pg_relation_filepath('newtbl');
             pg_relation_filepath             
----------------------------------------------
 pg_tblspc/16386/PG_9.4_201409291/16384/18894

1.3 堆表文件的内部布局

1.3.1 堆表页面的内部布局

在数据文件（堆表，索引，也包括空闲空间映射和可见性映射）内部，它被划分为固定长度的页（pages），或曰 区块（blocks），大小默认为8192字节（8KB）。 每个文件中的页从0开始按顺序编号，这些数字称为区块号（block numbers）。 如果文件已填满，PostgreSQL通过在文件末尾追加一个新的空页来增长文件。

页面内部的布局取决于数据文件的类型。本节会描述表的页面布局，因为理解接下来的几章需要这些知识。

表的页面包含了三种类型的数据：

1. 堆元组（heap tuples） —— 堆元组就是数据记录本身。它们从页面底部开始依序堆叠。第5.2节与第9章会描述元组的内部结构，这一知识对于理解PostgreSQL并发控制与WAL机制是必须的。

2. 行指针（line pointer） —— 每个行指针占4个字节，保存着指向堆元组的指针。它们也被称为项目指针（item pointer）。行指针简单地组织为一个数组，扮演了元组索引的角色。每个索引项从1开始依次编号，称为偏移号（offset number）。当向页面中添加新元组时，一个相应的新行指针也会被放入数组中，并指向新添加的元组。

3. 首部数据（header data） —— 页面的起始位置分配了由结构PageHeaderData定义的首部数据。它的大小为24个字节，包含关于页面的元数据。该结构的主要成员变量为：

   • pd_lsn —— 本页面最近一次变更所写入XLOG记录对应的LSN。它是一个8字节无符号整数，与WAL机制相关，第9章将详细展开。
   • pd_checksum —— 本页面的校验和值。（注意只有在9.3或更高版本才有此变量，早期版中该字段用于存储页面的时间线标识）
   • pd_lower，pd_upper —— pd_lower指向行指针的末尾，pd_upper指向最新堆元组的起始位置。
   • pd_special —— 在索引页中会用到该字段。在堆表页中它指向页尾。（在索引页中它指向特殊空间的起始位置，特殊空间是仅由索引使用的特殊数据区域，包含特定的数据，具体内容依索引的类型而定，如B树，GiST，GiN等。

   /* @src/include/storage/bufpage.h */
   
   /*
    * 磁盘页面布局
    *
    * 对任何页面都适用的通用空间管理信息
    *
    *		pd_lsn		- 本页面最近变更对应xlog记录的标识。
    *		pd_checksum - 页面校验和
    *		pd_flags	- 标记位
    *		pd_lower	- 空闲空间开始位置
    *		pd_upper	- 空闲空间结束位置
    *		pd_special	- 特殊空间开始位置
    *		pd_pagesize_version - 页面的大小，以及页面布局的版本号
    *		pd_prune_xid - 本页面中可以修剪的最老的元组中的XID.
    *
    * 缓冲管理器使用LSN来强制实施WAL的基本规则："WAL需先于数据写入"。直到xlog刷盘位置超过
    * 本页面的LSN之前，不允许将缓冲区的脏页刷入磁盘。
    *
    * pd_checksum 存储着页面的校验和，如果本页面配置了校验。0是一个合法的校验和值。如果页面
    * 没有使用校验和，我们就不会设置这个字段的值；通常这意味着该字段值为0，但如果数据库是从早于
    * 9.3版本从 pg_upgrade升级而来，也可能会出现非零的值。因为那时候这块地方用于存储页面最后
    * 更新时的时间线标识。 注意，并没有标识告诉你页面的标识符到底是有效还是无效的，也没有与之关
    * 联的标记为。这是特意设计成这样的，从而避免了需要依赖页面的具体内容来决定是否校验页面本身。
    *
    * pd_prune_xid是一个提示字段，用于帮助确认剪枝是否有用。目前对于索引页没用。
    *
    * 页面版本编号与页面尺寸被打包成了单个uint16字段，这是有历史原因的：在PostgreSQL7.3之前
    * 并没有页面版本编号这个概念，这样做能让我们假装7.3之前的版本的页面版本编号为0。我们约束页面
    * 的尺寸必须为256的倍数，留下低8位用于页面版本编号。
    *
    * 最小的可行页面大小可能是64字节，能放下页的首部，空闲空间，以及一个最小的元组。当然在实践中
    * 肯定要大得多(默认为8192字节)，所以页面大小必需是256的倍数并不是一个重要限制。而在另一端，
    * 我们最大只能支持32KB的页面，因为 lp_off/lp_len字段都是15bit。
    */
   typedef struct PageHeaderData
   {
   	PageXLogRecPtr 	pd_lsn;			/* 最近应用至本页面XLog记录的LSN */
   	uint16			pd_checksum;	/* 校验和 */
   	uint16		  	pd_flags;		/* 标记位，详情见下 */
   	LocationIndex 	pd_lower;		/* 空闲空间起始位置 */
   	LocationIndex 	pd_upper;		/* 空闲空间终止位置 */
   	LocationIndex 	pd_special;		/* 特殊用途空间的开始位置 */
   	uint16		  	pd_pagesize_version;
   	TransactionId 	pd_prune_xid; 	/* 最老的可修剪XID, 如果没有设置为0 */
   	ItemIdData		pd_linp[FLEXIBLE_ARRAY_MEMBER]; /* 行指针的数组 */
   } PageHeaderData;
   
   
   /* 缓冲区页中的项目指针(item pointer)，也被称为行指针(line pointer)。
    *
    * 在某些情况下，项目指针处于 “使用中”的状态，但在本页中没有任何相关联的存储区域。
    * 按照惯例，lp_len == 0 表示该行指针没有关联存储。独立于其lp_flags的状态. 
    */
   typedef struct ItemIdData
   {
   	unsigned	lp_off:15,		/* 元组偏移量 (相对页面起始处) */
   				lp_flags:2,		/* 行指针的状态，见下 */
   				lp_len:15;		/* 元组的长度，以字节计 */
   } ItemIdData;
   
   /* lp_flags有下列可能的状态，LP_UNUSED的行指针可以立即重用，而其他状态的不行。 */
   #define LP_UNUSED		0		/* unused (lp_len必需始终为0) */
   #define LP_NORMAL		1		/* used (lp_len必需始终>0) */
   #define LP_REDIRECT		2		/* HOT 重定向 (lp_len必需为0) */
   #define LP_DEAD			3		/* 死元组，有没有对应的存储尚未可知 */

行指针的末尾与最新元组起始位置之间的空余空间称为空闲空间（free space）或空洞（hole）。

为了识别表中的元组，数据库内部会使用元组标识符（tuple identifier, TID）。TID由一对值组成：元组所属页面的区块号，及指向元组的行指针的偏移号。TID的一种典型用途是索引，更多细节参见第1.4.2节。

结构体PageHeaderData定义于src/include/storage/bufpage.h中。

1.3.2 TOAST（超大属性存储技术）

大小超过约2 KB的堆元组——更准确地说，超过默认TOAST_TUPLE_THRESHOLD所规定的2032字节——会使用一种称为TOAST（The Oversized-Attribute Storage Technique，超大属性存储技术）的机制来管理。

如果一个数据项经过压缩后仍超过2 KB，PostgreSQL会为该表创建专用的TOAST表及相应的TOAST索引。实际数据存放在TOAST表中，原表中只保留一个指向TOAST条目的指针。

1.3.2.1 实际示例

下面创建一张名为tbl_toast的表来演示这一机制：

testdb=# CREATE TABLE tbl_toast (id SERIAL PRIMARY KEY, data text);
testdb=# ALTER TABLE tbl_toast ALTER COLUMN data SET STORAGE EXTERNAL;

第一行插入一个能直接放入普通页面的小字符串abc，第二行和第三行则分别插入约10 KB的数据：

testdb=# INSERT INTO tbl_toast (data) VALUES ('abc');
testdb=# INSERT INTO tbl_toast (data) SELECT repeat('abcdefghij', 1000) FROM generate_series(1, 2);

本例中，tbl_toast的OID为16406：

testdb=# SELECT relname, oid, relfilenode FROM pg_class WHERE relname = 'tbl_toast';
  relname  |  oid  | relfilenode
-----------+-------+-------------
 tbl_toast | 16406 |       16406
(1 row)

相应的TOAST表及其索引分别命名为pg_toast_16406与pg_toast_16406_index：

testdb=# SELECT relname, relpages FROM pg_class
    WHERE relname LIKE '%toast%16406%'
          AND relnamespace = (SELECT oid FROM pg_namespace WHERE nspname = 'pg_toast');
       relname        | relpages
----------------------+----------
 pg_toast_16406       |        0
 pg_toast_16406_index |        1
(2 rows)

可以用下面的查询取得这些关系的OID与物理文件路径。本例中的路径分别为base/16384/16411和base/16384/16412：

testdb=# \x
Expanded display is on.
testdb=# SELECT c.relname AS main_table, t.relname AS toast_table, t.oid AS toast_table_oid,
        pg_relation_filepath(t.oid) AS physical_path,
        i.relname AS toast_index, i.oid AS toast_index_oid,
        pg_relation_filepath(i.oid) AS index_path
    FROM pg_class c JOIN pg_class t ON c.reltoastrelid = t.oid
        JOIN pg_index idx ON idx.indrelid = t.oid
        JOIN pg_class i ON i.oid = idx.indexrelid WHERE c.relname = 'tbl_toast';
-[ RECORD 1 ]---+---------------------
main_table      | tbl_toast
toast_table     | pg_toast_16406
toast_table_oid | 16411
physical_path   | base/16384/16411
toast_index     | pg_toast_16406_index
toast_index_oid | 16412
index_path      | base/16384/16412

关于元组压缩： 为了直接观察TOAST机制，本例通过ALTER TABLE调整存储参数，禁用了数据压缩。通常情况下，PostgreSQL会尝试压缩超过2 KB的数据，默认压缩算法为pglz（PostgreSQL Lempel-Ziv）。

1.3.2.2 结构分析

图1.3-1展示了主表tbl_toast与TOAST表pg_toast_16406之间的关系。该图对应新版英文原著的图1.5；为避免与中文旧译本已有的图1.5冲突，这里采用补充编号。

由于tbl_toast第二行和第三行中的data项均为10 KB，它们不会以内联原始数据的形式保存，而是使用varatt_external结构存储为TOAST指针：

typedef struct varatt_external
{
    int32   va_rawsize;     /* 包含首部的原始数据大小 */
    uint32  va_extinfo;     /* 外部存储大小（不含首部）及压缩方法 */
    Oid     va_valueid;     /* TOAST表中该值的唯一标识 */
    Oid     va_toastrelid;  /* 存放该值的TOAST表RelID */
} varatt_external;

这四个字段的含义如下：

• va_rawsize： 包含首部在内的原始数据大小。
• va_extinfo： 外部存储的实际大小（不含首部）及所用压缩方法。
• va_valueid： 该值在TOAST表中的唯一标识，内部称为chunk_id。
• va_toastrelid： 存放该数据的TOAST表OID。

va_valueid（即chunk_id）与va_toastrelid的组合构成了指向外部数据的实际指针。本例中，第二个和第三个元组的va_valueid分别为16415与16416，va_toastrelid则为16411，也就是TOAST表的OID。

1.3.2.3 TOAST表的内容

TOAST表包含三列：chunk_id、chunk_seq与chunk_data。

• chunk_id： 原表中被TOAST化数据项的标识。
• chunk_seq： 数据项被拆成多个片段后，各片段的顺序号。
• chunk_data： 实际的二进制数据片段。

pg_toast_16406中的内容如下：

testdb=# SELECT chunk_id, chunk_seq, chunk_data FROM pg_toast.pg_toast_16406;
 chunk_id | chunk_seq |        chunk_data
----------+-----------+-------------------------
    16415 |         0 | \x616263646566.....6566
    16415 |         1 | \x6768696a6162.....6162
    16415 |         2 | \x636465666768.....6768
    16415 |         3 | \x696a61626364.....6364
    16415 |         4 | \x65666768696a.....696a
    16415 |         5 | \x6162...696a
    16416 |         0 | \x616263646566.....6566
    16416 |         1 | \x6768696a6162.....6162
    16416 |         2 | \x636465666768.....6768
    16416 |         3 | \x696a61626364.....6364
    16416 |         4 | \x65666768696a.....696a
    16416 |         5 | \x6162...696a
(12 rows)

TOAST索引以chunk_id与chunk_seq作为复合键。读取TOAST化数据时，系统会扫描TOAST索引，按正确顺序取得对应的chunk_data片段，再重组成原始数据项。

1.4 读写元组的方式

本章的最后将描述读取与写入堆元组的方式。

1.4.1 写入堆元组

让我们假设有一个表，仅由一个页面组成，且该页面只包含一个堆元组。 此页面的pd_lower指向第一个行指针，而该行指针和pd_upper都指向第一个堆元组。 如图1.5(a)所示。

当第二个元组被插入时，它会被放在第一个元组之后。第二个行指针被插入到第一个行指针的后面，并指向第二个元组。 pd_lower更改为指向第二个行指针，pd_upper更改为指向第二个堆元组，如图1.5(b)。 页面内的首部数据（例如pd_lsn、pd_checksum和pd_flags）也会被改写为适当的值，细节在第5.3节和第9章中描述。

1.4.2 读取堆元组

这里简述两种典型的访问方式：顺序扫描与B树索引扫描：

• 顺序扫描 —— 通过扫描每一页中的行指针，依序读取所有页面中的所有元组，如图1.6(a)。
• B树索引扫描 —— 索引文件包含着索引元组，索引元组由一个键值对组成，键为被索引的列值，值为目标堆元组的TID。进行索引查询时，首先使用键进行查找，如果找到了对应的索引元组，PostgreSQL就会根据相应值中的TID来读取对应的堆元组 （使用B树索引找到索引元组的方法请参考相关资料，这一部分属于数据库系统的通用知识，限于篇幅这里不再详细展开）。例如在图1.6(b)中，所获索引元组中TID的值为（区块号 = 7，偏移号 = 2）， 这意味着目标堆元组是表中第7页的第2个元组，因而PostgreSQL可以直接读取所需的堆元组，而避免对页面做不必要的扫描。

PostgreSQL还支持TID扫描，位图扫描（Bitmap-Scan）和仅索引扫描（Index-Only-Scan）。

TID扫描是一种通过使用所需元组的TID直接访问元组的方法。 例如要在表中找到第0个页面中的第1个元组，可以执行以下查询：

sampledb=# SELECT ctid, data FROM sampletbl WHERE ctid = '(0,1)';
 ctid  |   data    
-------+-----------
 (0,1) | AAAAAAAAA
(1 row)

sampledb=# EXPLAIN SELECT ctid, data FROM sampletbl WHERE ctid = '(0,1)';
                        QUERY PLAN
----------------------------------------------------------
 Tid Scan on sampletbl  (cost=0.00..1.11 rows=1 width=38)
   TID Cond: (ctid = '(0,1)'::tid)

仅索引扫描将在第7章中详细介绍。

2 进程和内存架构

本章总结了PostgreSQL中进程与内存的架构，有助于读者理解后续章节。 如果读者已经熟悉这些内容，可以直接跳过本章。

2.1 进程架构

PostgreSQL是一个客户端/服务器风格的关系型数据库管理系统，采用多进程架构，运行在单台主机上。

我们通常所谓的 “PostgreSQL服务器（PostgreSQL Server）” 实际上是一系列协同工作的进程集合，包含着下列进程：

• Postgres服务器进程（Postgres Server Process） 是所有数据库集簇管理进程的父进程。

• 每个 后端进程（Backend Process） 负责处理客户端发出的查询和语句。

• 各种 后台进程（Background Process） 负责执行各种数据库管理任务（例如清理过程与检查点过程）。

• 各种 复制相关（Replication Associated Process） 的进程负责流复制，流复制的细节会在第11章中介绍。

• 后台工作进程（Background Worker Process） 在 9.3 版被引入，它能执行任意由用户实现的处理逻辑。这里不详述，请参阅官方文档。

以下几小节将详细描述前三种进程。

本图展示了PostgreSQL服务器包含的进程：postgres服务器进程，两个后端进程，七个后台进程，以及两个客户端进程。 也画出了数据库集簇，共享内存，以及两个客户端。

2.1.1 Postgres服务器进程

如上所述，Postgres服务器进程（postgres server process） 是 PostgreSQL 服务器中所有进程的父进程，在早期版本中它被称为 “postmaster”。

带start参数执行pg_ctl实用程序会启动一个postgres服务器进程。它会在内存中分配共享内存区域，启动各种后台进程，如有必要还会启动复制相关进程与后台工作进程，并等待来自客户端的连接请求。 每当接收到来自客户端的连接请求时，它都会启动一个后端进程 （然后由启动的后端进程处理该客户端发出的所有查询）。

一个postgres服务器进程只会监听一个网络端口，默认端口为5432。如果要在同一台主机上运行多个PostgreSQL服务器，则应为每个服务器配置不同的监听端口，如5432，5433等。

2.1.2 后端进程

每个后端进程（也称为 “postgres”）由postgres服务器进程启动，并处理连接另一侧的客户端发出的所有查询。它通过单条TCP连接与客户端通信，并在客户端断开连接时终止。

因为一条连接只允许操作一个数据库，因此必须在连接到PostgreSQL服务器时显式指定要连接的数据库。

PostgreSQL允许多个客户端同时连接；配置参数max_connections用于控制最大客户端连接数（默认为100）。

因为PostgreSQL没有原生的连接池功能，因此如果许多客户端频繁地重复与PostgreSQL服务器建立、断开连接（譬如Web应用），则会导致建立连接与创建后端进程的开销变大。这种情况对数据库服务器的性能有负面影响，通常可以使用池化中间件（PgBouncer或Pgpool-II）来避免该问题。

2.1.3 后台进程

表2.1是后台进程的列表。比起postgres服务器和后端进程，后台进程的种类要多很多。想要简单地解释每种后台进程的具体功能是不现实的，因为这些功能有赖PostgreSQL的内部机制与特定的独立特性。依赖于各个特定的特性以及PostgreSQL的内部机制。 因此在本章中仅做简要介绍。 细节将在后续章节中描述。

这里展示了PostgreSQL服务器包含的实际进程。 在以下示例中有一个postgres服务器进程（pid为9687），两个后端进程（pid为9697和9717），以及表2.1中列出的几个后台进程正在运行，亦见图2.1。

postgres> pstree -p 9687
-+= 00001 root /sbin/launchd
 \-+- 09687 postgres /usr/local/pgsql/bin/postgres -D /usr/local/pgsql/data
   |--= 09688 postgres postgres: logger process     
   |--= 09690 postgres postgres: checkpointer process     
   |--= 09691 postgres postgres: writer process     
   |--= 09692 postgres postgres: wal writer process     
   |--= 09693 postgres postgres: autovacuum launcher process     
   |--= 09694 postgres postgres: archiver process     
   |--= 09695 postgres postgres: stats collector process     
   |--= 09697 postgres postgres: postgres sampledb 192.168.1.100(54924) idle  
   \--= 09717 postgres postgres: postgres sampledb 192.168.1.100(54964) idle in transaction  

2.2 内存架构

PostgreSQL的内存架构可以分为两部分：

• 本地内存区域 —— 由每个后端进程分配，供自己使用。
• 共享内存区域 —— 供PostgreSQL服务器的所有进程使用。

下面一小节简要介绍了这两部分架构。

2.2.1 本地内存区域

每个后端进程都会分配一块本地内存区域用于查询处理。该区域会分为几个子区域 —— 子区域的大小有的固定，有的可变。 表2.2列出了主要的子区域。 详细信息将在后续章节中介绍。

2.2.2 共享内存区域

PostgreSQL服务器启动时会分配共享内存区域。该区域分为几个固定大小的子区域。 表2.3列出了主要的子区域。 详细信息将在后续章节中介绍。

除了上面这些，PostgreSQL还分配了这几个区域：

• 用于访问控制机制的子区域（例如信号量，轻量级锁，共享和排他锁等）。
• 各种后台进程使用的子区域，例如checkpointer和autovacuum。
• 用于事务处理的子区域，例如保存点（save-point） 与 两阶段提交（2PC）。

诸如此类。

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节介绍了三种连接算法：嵌套循环连接（Nested Loop Join）、归并连接（Merge Join）、散列连接（Hash Join）。3.6节将介绍为多表查询创建计划树的过程。

PostgreSQL支持三种技术上很有趣，而且也很实用的功能：外部数据包装（Foreign Data Wrapper, FDW），并行查询，以及版本11即将支持的JIT编译。前两者将在第4章中描述，JIT编译超出本书范围，详见官方文档。

3.1 概览

尽管PostgreSQL在9.6版本后有了基于多个后台工作进程的并行查询，但大体上来讲，还是每个连接对应一个后端进程。后端进程由五个子系统组成，如下所示：

1. 解析器（Parser）

   解析器根据SQL语句生成一棵语法解析树（parse tree）。

2. 分析器（Analyzer）

   分析器对语法解析树进行语义分析，生成一棵查询树（query tree）。

3. 重写器（Rewriter）

   重写器按照规则系统中存在的规则，对查询树进行改写。

4. 计划器（Planner）

   计划器基于查询树，生成一棵执行效率最高的计划树（plan tree）。

5. 执行器（Executor）

   执行器按照计划树中的顺序访问表和索引，执行相应查询。

本节将概述这些子系统。计划器和执行器很复杂，后面的章节会对这些函数的细节进行描述。

PostgreSQL的查询处理在官方文档中有详细的描述

3.1.1 解析器（Parser）

解析器基于SQL语句的文本，生成一棵后续子系统可以理解的语法解析树。下面是一个具体的例子。

考虑以下查询：

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

语法解析树的根节点是一个定义在parsenodes.h中的SelectStmt数据结构。图3.2(a)展示了一个查询，而图3.2(b)则是该查询对应的语法解析树。

typedef struct SelectStmt
{
        NodeTag         type;

        /* 这些字段只会在SelectStmts“叶节点”中使用 */
        List       *distinctClause;     /* NULL, DISTINCT ON表达式列表, 或
                                       对所有的(SELECT DISTINCT)为lcons(NIL,NIL) */
        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;

SELECT查询中的元素和语法解析树中的元素有着对应关系。比如，(1)是目标列表中的一个元素，与目标表的'id'列相对应，(4)是一个WHERE子句，诸如此类。

当解析器生成语法分析树时只会检查语法，只有当查询中出现语法错误时才会返回错误。解析器并不会检查输入查询的语义，举个例子，如果查询中包含一个不存在的表名，解析器并不会报错，语义检查由分析器负责。

3.1.2 分析器（Analyzer）

分析器对解析器产出的语法解析树（parse tree）进行语义分析，并产出一棵查询树（query tree）。

查询树的根节点是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;		/* 如果有，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;

简要介绍一下上图中的查询树：

• targetlist 是查询结果中 列（Column） 的列表。在本例中该列表包含两列：id 和data。如果在输入的查询树中使用了*（星号），那么分析器会将其显式替换为所有具体的列。
• 范围表rtable是该查询所用到关系的列表。本例中该变量包含了表tbl_a的信息，如该表的表名与oid。
• 连接树jointree存储着FROM和WHERE子句的相关信息。
• 排序子句sortClause是SortGroupClause结构体的列表。

官方文档描述了查询树的细节。

3.1.3 重写器（Rewriter）

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;

当执行一个包含该视图的查询，解析器会创建一棵如图3.4(a)所示的语法解析树。

sampledb=# SELECT * FROM employees_list;

在该阶段，重写器会基于pg_rules中存储的视图规则将rangetable节点重写为一棵查询子树，与子查询相对应。

图3.4 重写阶段一例

因为PostgreSQL使用这种机制实现视图，直到9.2版本，视图都是不能更新的。虽然9.3版本后可以对视图进行更新，但对视图的更新仍然存在很多限制，具体细节请参考官方文档。

3.1.4 计划器与执行器

计划器从重写器获取一棵查询树（query tree），基于查询树生成一棵能被执行器高效执行的（查询）计划树（plan tree）。

在PostgreSQL中，计划器是完全基于代价估计（cost-based）的；它不支持基于规则的优化与提示（hint）。计划器是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展示了结果相应的计划树。

计划树由许多称为 计划节点（plan node） 的元素组成，这些节点挂在PlannedStmt结构对应的计划树上。这些元素定义在plannodes.h中，第3.3.3节与第3.5.4.2会解释相关细节。

每个计划节点都包含着执行器进行处理所必需的信息，在单表查询的场景中，执行器会按照从终端节点往根节点的顺序依次处理这些节点。

比如图3.5中的计划树就是一个列表，包含一个排序节点和一个顺序扫描节点；因而执行器会首先对表tbl_a执行顺序扫描，并对获取的结果进行排序。

执行器会通过第8章将介绍的缓冲区管理器来访问数据库集簇的表和索引。当处理一个查询时，执行器会使用预先分配的内存空间，比如temp_buffers和work_mem，必要时还会创建临时文件。

除此之外，当访问元组的时候，PostgreSQL还会使用并发控制机制来维护运行中事务的一致性和隔离性。第五章介绍了并发控制机制。

3.2 单表查询的代价估计

PostgreSQL的查询优化是基于 代价（Cost） 的。代价是一个无量纲的值，它并不是一种绝对的性能指标，但可以作为比较各种操作代价时的相对性能指标。

costsize.c中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。

在PostgreSQL中有三种代价：启动（start-up） ， 运行（run）和总和（total）。总代价是启动代价和运行代价的和；因此只有启动代价和运行代价是单独估计的。

1. 启动代价（start-up）：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价就是读取目标表的索引页，取到第一个元组的代价
2. 运行代价（run）： 获取全部元组的代价
3. 总代价（total）：前两者之和

EXPLAIN命令显示了每个操作的启动代价和总代价，下面是一个简单的例子：

testdb=# EXPLAIN SELECT * FROM tbl;
                       QUERY PLAN                        
---------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..145.00 rows=10000 width=8)
(1 row)

在第4行显示了顺序扫描的相关信息。代价部分包含了两个值：0.00和145.00。在本例中，启动代价和总代价分别为0.00和145.00。

在本节中，我们将详细介绍顺序扫描，索引扫描和排序操作的代价是如何估算的。

在接下来的内容中，我们使用下面这个表及其索引作为例子。

testdb=# CREATE TABLE tbl (id int PRIMARY KEY, data int);
testdb=# CREATE INDEX tbl_data_idx ON tbl (data);
testdb=# INSERT INTO tbl SELECT generate_series(1,10000),generate_series(1,10000);
testdb=# ANALYZE;
testdb=# \d tbl
      Table "public.tbl"
 Column |  Type   | Modifiers 
--------+---------+-----------
 id     | integer | not null
 data   | integer | 
Indexes:
    "tbl_pkey" PRIMARY KEY, btree (id)
    "tbl_data_idx" btree (data)

3.2.1 顺序扫描

顺序扫描的代价是通过函数cost_seqscan()估计的。本节将研究顺序扫描代价是如何估计的，以下面的查询为例：

testdb=# SELECT * FROM tbl WHERE id < 8000;

在顺序扫描中，启动代价等于0，而运行代价由以下公式定义：

其中seq_page_cost，cpu_tuple_cost和cpu_operator_cost是在postgresql.conf 中配置的参数，默认值分别为1.0，0.01和0.0025。$N_{\verb|tuple|}$ 和$N_{\verb|page|}$ 分别是表中的元组总数与页面总数，这两个值可以使用以下查询获取。

testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl';
 relpages | reltuples 
----------+-----------
       45 |     10000
(1 row)

因此：

最终：

作为验证，下面是该查询的EXPLAIN结果：

testdb=# EXPLAIN SELECT * FROM tbl WHERE id < 8000;
                       QUERY PLAN                       
--------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..170.00 rows=8000 width=8)
   Filter: (id < 8000)
(2 rows)

在第4行中可以看到，启动代价和总代价分别是0.00和170.0，且预计全表扫描返回行数为8000条（元组）。

在第5行显示了一个顺序扫描的过滤器Filter:(id < 8000)。更精确地说，它是一个表级过滤谓词（table level filter predicate）。注意这种类型的过滤器只会在读取所有元组的时候使用，它并不会减少需要扫描的表页面数量。

从优化运行代价的角度来看，PostgreSQL假设所有的物理页都是从存储介质中获取的；即，PostgreSQL不会考虑扫 描的页面是否来自共享缓冲区。

3.2.2 索引扫描

尽管PostgreSQL支持很多索引方法，比如B树，GiST，GIN和BRIN，不过索引扫描的代价估计都使用一个共用的代价函数：cost_index()。

本节将研究索引扫描的代价是如何估计的，以下列查询为例。

testdb=# SELECT id, data FROM tbl WHERE data < 240;

在估计该查询的代价之前，下面的查询能获取$N_{\verb|index|,\verb|page|}$和$N_{\verb|index|,\verb|tuple|}$的值：

testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl_data_idx';
 relpages | reltuples 
----------+-----------
       30 |     10000
(1 row)

3.2.2.1 启动代价

索引扫描的启动代价就是读取索引页以访问目标表的第一条元组的代价，由下面的公式定义：

其中$H_{\verb|index|}$是索引树的高度。

在本例中，套用公式(3)，$N_{\verb|index,tuple|}$是10000；$H_{\verb|index|}$是1；$\verb|cpu_operator_cost|$是0.0025（默认值）。因此

3.2.2.2 运行代价

索引扫描的运行代价是表和索引的CPU代价与IO代价之和。

如果使用仅索引扫描，则不会估计table_cpu_cost与table_io_cost，仅索引扫描将在第七章中介绍。

前三个代价（即index_cpu_cost，table_cpu_cost和index_io_cost）如下所示：

以上公式中的cpu_index_tuple_cost和random_page_cost在postgresql.conf中配置（默认值分别为0.005和4.0）。$\verb|qual_op_cost|$粗略来说就是索引求值的代价，默认值是0.0025，这里不再展开。选择率（Selectivity） 是一个0到1之间的浮点数，代表查询指定的WHERE子句在索引中搜索范围的比例。举个例子，$(\verb|Selectivity| × N_{\verb|tuple|})$就是需要读取的表元组数量，$(\verb|Selectivity| × N_{\verb|index|,\verb|tuple|})$就是需要读取的索引元组数量，诸如此类。

选择率

查询谓词的选择率是通过 直方图界值（histogram_bounds） 与 高频值（Most Common Value, MCV） 估计的，这些信息都存储在系统目录pg_statistics中，并可通过pg_stats视图查询。这里通过一个具体的例子来简要介绍选择率的计算方法，细节可以参考官方文档。

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

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

下面是一个简单的例子。表countries有两列：一列country存储国家名，一列continent存储该国所属大洲。

testdb=# \d countries
   Table "public.countries"
  Column   | Type | Modifiers 
-----------+------+-----------
 country   | text | 
 continent | text | 
Indexes:
    "continent_idx" btree (continent)

testdb=# SELECT continent, count(*) AS "number of countries", 
testdb-#     (count(*)/(SELECT count(*) FROM countries)::real) AS "number of countries / all countries"
testdb-#       FROM countries GROUP BY continent ORDER BY "number of countries" DESC;
   continent   | number of countries | number of countries / all countries 
---------------+---------------------+-------------------------------------
 Africa        |                  53 |                   0.274611398963731
 Europe        |                  47 |                   0.243523316062176
 Asia          |                  44 |                   0.227979274611399
 North America |                  23 |                   0.119170984455959
 Oceania       |                  14 |                  0.0725388601036269
 South America |                  12 |                  0.0621761658031088
(6 rows)

考虑下面的查询，该查询带有WHERE条件continent = 'Asia'。

testdb=# SELECT * FROM countries WHERE continent = 'Asia';

这时候，计划器使用continent列上的高频值来估计索引扫描的代价，列上的most_common_vals与 most_common_freqs如下所示：

testdb=# \x
Expanded display is on.
testdb=# SELECT most_common_vals, most_common_freqs FROM pg_stats 
testdb-#                  WHERE tablename = 'countries' AND attname='continent';
-[ RECORD 1 ]-----+-----------------------------------------------------------
most_common_vals  | {Africa,Europe,Asia,"North America",Oceania,"South America"}
most_common_freqs | {0.274611,0.243523,0.227979,0.119171,0.0725389,0.0621762}

与most_common_vals中Asia值对应的most_common_freqs为0.227979。因此0.227979会在估算中被用作选择率。

如果高频值不可用，就会使用目标列上的直方图界值来估计代价。

• 直方图值（histogram_bounds） 是一系列值，这些值将列上的取值划分为数量大致相同的若干个组。

下面是一个具体的例子。这是表tbl中data列上的直方图界值；

testdb=# SELECT histogram_bounds FROM pg_stats WHERE tablename = 'tbl' AND attname = 'data';
        			     	      histogram_bounds
------------------------------------------------------------------------------
 {1,100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700,1800,1900,2000,2100,
2200,2300,2400,2500,2600,2700,2800,2900,3000,3100,3200,3300,3400,3500,3600,3700,3800,3900,4000,4100,
4200,4300,4400,4500,4600,4700,4800,4900,5000,5100,5200,5300,5400,5500,5600,5700,5800,5900,6000,6100,
6200,6300,6400,6500,6600,6700,6800,6900,7000,7100,7200,7300,7400,7500,7600,7700,7800,7900,8000,8100,
8200,8300,8400,8500,8600,8700,8800,8900,9000,9100,9200,9300,9400,9500,9600,9700,9800,9900,10000}
(1 row)

默认情况下，直方图界值会将列上的取值划分入100个桶。图3.7展示了这些桶及其对应的直方图界值。桶从0开始编号，每个桶保存了（大致）相同数量的元组。直方图界值就是相应桶的边界。比如，直方图界值的第0个值是1，意即这是bucket_0中的最小值。第1个值是100，意即bucket_1中的最小值是100，等等。

图3.7 桶和直方图界值

然后本节例子中选择率计算如下所示。假设查询带有WHERE子句data < 240，而值240落在第二个桶中。在本例中可以通过线性插值推算出相应的选择率。因此查询中data列的选择率可以套用下面的公式计算：

$$> \verb|Selectivity| = \frac{2+(240-hb[2])/(hb[3]-hb[2])}{100}=\frac{2+(240-200)/(300-200)}{100}=\frac{2+40/100}{100}=0.024 \ (6) >$$

因此，根据公式(1)，(3)，(4)和(6)，有

$\verb|table_io_cost|$ 由下面的公式定义：

$\verb|max_io_cost_io_cost|$ 是最差情况下的I/O代价，即，随机扫描所有数据页的代价；这个代价由以下公式定义：

在本例中，由(2)，$N_{\verb|page|}=45$，得

$\verb|min_io_cost|$是最优情况下的I/O代价，即，顺序扫描选定的数据页；这个代价由以下公式定义：

在本例中，

下文详细介绍$\verb|indexCorrelation|$，在本例中，

由(10)，(11)和(12)，得

综上，由(7)，(8)，(9)和(13)得

索引相关性（index correlation）

索引相关性是列值在物理上的顺序和逻辑上的顺序的统计相关性（引自官方文档）。索引相关性的取值范围从$-1$到$+1$。下面的例子有助于理解索引扫描和索引相关性的关系。

表tbl_corr有5个列：两个列为文本类型，三个列为整数类型。这三个整数列保存着从1到12的数字。在物理上表tbl_corr包含三个页，每页有4条元组。每个数字列有一个名如index_col_asc的索引。

testdb=# \d tbl_corr
    Table "public.tbl_corr"
  Column  |  Type   | Modifiers 
----------+---------+-----------
 col      | text    | 
 col_asc  | integer | 
 col_desc | integer | 
 col_rand | integer | 
 data     | text    |
Indexes:
    "tbl_corr_asc_idx" btree (col_asc)
    "tbl_corr_desc_idx" btree (col_desc)
    "tbl_corr_rand_idx" btree (col_rand)

testdb=# SELECT col,col_asc,col_desc,col_rand 
testdb-#                         FROM tbl_corr;
   col    | col_asc | col_desc | col_rand 
----------+---------+----------+----------
 Tuple_1  |       1 |       12 |        3
 Tuple_2  |       2 |       11 |        8
 Tuple_3  |       3 |       10 |        5
 Tuple_4  |       4 |        9 |        9
 Tuple_5  |       5 |        8 |        7
 Tuple_6  |       6 |        7 |        2
 Tuple_7  |       7 |        6 |       10
 Tuple_8  |       8 |        5 |       11
 Tuple_9  |       9 |        4 |        4
 Tuple_10 |      10 |        3 |        1
 Tuple_11 |      11 |        2 |       12
 Tuple_12 |      12 |        1 |        6
(12 rows)

这些列的索引相关性如下：

testdb=# SELECT tablename,attname, correlation FROM pg_stats WHERE tablename = 'tbl_corr';
 tablename | attname  | correlation 
-----------+----------+-------------
 tbl_corr  | col_asc  |           1
 tbl_corr  | col_desc |          -1
 tbl_corr  | col_rand |    0.125874
(3 rows)

当执行下列查询时，由于所有的目标元组都在第一页中，PostgreSQL只会读取第一页，如图3.8(a)所示。

testdb=# SELECT * FROM tbl_corr WHERE col_asc BETWEEN 2 AND 4;

而执行下列查询时则不然，PostgreSQL需要读所有的页，如图3.8(b)所示。

testdb=# SELECT * FROM tbl_corr WHERE col_rand BETWEEN 2 AND 4;

如此可知，索引相关性是一种统计上的相关性。在索引扫描代价估计中，索引相关性体现了索引顺序和物理元组顺序扭曲程度给随机访问性能造成的影响大小。

图3.8 索引相关性

3.2.2.3 整体代价

由(3)和(14)可得

作为确认，上述SELECT查询的EXPLAIN结果如下所示：

testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240;
                                QUERY PLAN                                 
---------------------------------------------------------------------------
 Index Scan using tbl_data_idx on tbl  (cost=0.29..13.49 rows=240 width=8)
   Index Cond: (data < 240)
(2 rows)

在第4行可以看到启动代价和总代价分别是0.29和13.49，预估有240条元组被扫描。

在第5行显示了一个索引条件Index Cond:(data < 240)。更准确地说，这个条件叫做访问谓词（access predicate），它表达了索引扫描的开始条件与结束条件。

根据这篇文章，PostgreSQL中的EXPLAIN命令不会区分访问谓词（access predicate）和索引过滤谓词（index filter predicate）。因此当分析EXPLAIN的输出时，即使看到了“IndexCond”，也应当注意一下预估返回行数。

seq_page_cost和random_page_cost

seq_page_cost和random_page_cost的默认值分别为1.0和4.0。这意味着PostgreSQL假设随机扫描比顺序扫描慢4倍；显然，PostgreSQL的默认值是基于HDD（普通硬盘）设置的。

另一方面，近年来SSD得到了广泛的应用，random_page_cost的默认值就显得太大了。使用SSD时如果仍然采用random_page_cost的默认值，则计划器有可能会选择低效的计划。因此当使用SSD时最好将random_page_cost的值设为1.0。

这篇文章报告了使用random_page_cost默认值导致的问题。

3.2.3 排序

排序路径（sort path） 会在排序操作中被使用。排序操作包括ORDER BY，归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。

如果能在工作内存中放下所有元组，那么排序操作会选用快速排序算法。否则的话则会创建临时文件，使用文件归并排序算法。

排序路径的启动代价就是对目标表的排序代价，因此代价就是$O(N_{\verb|sort|}× \log_2(N_{\verb|sort|})$，这里$N_{\verb|sort|}$就是待排序的元组数。排序路径的运行代价就是读取已经排好序的元组的代价，因而代价就是$O(N_{sort})$。

本节将研究以下查询排序代价的估计过程。假设该查询只使用工作内存，不使用临时文件。

testdb=# SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;

在本例中，启动代价由以下公式定义：

这里$C$就是上一次扫描的总代价，即上次索引扫描的总代价；由(15)可得C等于13.485；$N_{\verb|sort|}=240$；$\verb|comparison_cost|$ 定义为$2 × \verb|cpu_operator_cost|$。因此有

运行代价是在内存中读取排好序的元组的代价，即：

综上：

作为确认，以上SELECT查询的EXPLAIN命令结果如下：

testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;
                                   QUERY PLAN                                    
---------------------------------------------------------------------------------
 Sort  (cost=22.97..23.57 rows=240 width=8)
   Sort Key: id
   ->  Index Scan using tbl_data_idx on tbl  (cost=0.29..13.49 rows=240 width=8)
         Index Cond: (data < 240)
(4 rows)

在第4行可以看到启动代价和运行代价分别为22.97和23.57。

3.2.4 基数估计

前面的讨论都假设选择率可以被精确计算。然而在现实中，选择率估计从数据库系统诞生之初便一直是最棘手、最持久的问题之一。

3.2.4.1 选择率与基数

PostgreSQL内部主要使用选择率（Selectivity），而数据库领域通常更多讨论基数（Cardinality）。基数是一个整数，两者之间的关系为：

其中$N_{\text{tuple}}$是表中的元组（行）总数。下文将主要使用“基数”这个术语。

3.2.4.2 基数估计为何困难

下面用一个具体例子说明基数估计的难点。假设数据库中记录着100名村民，residents表包含年龄类别age（未满18岁、青年、中年、老年）和驾照状态license（无驾照、普通驾照、金色驾照）。这里的“金色驾照”是日本的一种称谓，授予连续五年无事故、无违章的驾驶者。

数据库设置

表结构如下：

testdb=# CREATE TYPE license AS ENUM ('none', 'standard', 'gold');
CREATE TYPE
testdb=# CREATE TYPE age AS ENUM ('under18', 'young', 'middle', 'elder');
CREATE TYPE

testdb=# CREATE TABLE residents (id int, name text, license license, age age);
CREATE TABLE

testdb=# \d residents
 Column  |  Type   | Collation | Nullable | Default
---------+---------+-----------+----------+---------
 id      | integer |           |          |
 name    | text    |           |          |
 license | license |           |          |
 age     | age     |           |          |

载入100行测试数据后执行ANALYZE：

testdb=# COPY residents FROM '/usr/local/pgsql/residents.csv' (FORMAT csv);
COPY 100
testdb=# ANALYZE;
ANALYZE

测试数据的年龄分布如下：

驾照状态分布如下：

可以从pg_stats中取得这些最常见值（MCV）及其频率：

testdb=# SELECT most_common_vals, most_common_freqs
           FROM pg_stats WHERE tablename = 'residents' AND attname = 'age';
      most_common_vals       |  most_common_freqs
-----------------------------+---------------------
 {middle,young,under18,elder} | {0.35,0.25,0.2,0.2}
(1 row)

testdb=# SELECT most_common_vals, most_common_freqs
           FROM pg_stats WHERE tablename = 'residents' AND attname = 'license';
 most_common_vals   | most_common_freqs
--------------------+-------------------
 {standard,none,gold} | {0.55,0.4,0.05}
(1 row)

未考虑相关性时的估计错误

下面查询未满18岁且没有驾照的居民，并用EXPLAIN ANALYZE比较计划器的估计值与实际结果：

testdb=# EXPLAIN (ANALYZE TRUE, TIMING FALSE, BUFFERS FALSE)
testdb-#     SELECT * FROM residents WHERE age = 'under18' AND license = 'none';
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Seq Scan on residents  (cost=0.00..2.50 rows=8 width=18) (actual rows=20.00 loops=1)
   Filter: ((age = 'under18'::age) AND (license = 'none'::license))
   Rows Removed by Filter: 80
 Planning Time: 0.183 ms
 Execution Time: 0.048 ms
(8 rows)

估计基数为$8$，实际行数却是$20$。现实约束决定了未满18岁的人不能取得驾照，因此所有20名未成年人都必然属于none类别。

根本原因：错误地假设列相互独立

PostgreSQL计划器在默认假设两列相互独立的情况下，把under18的比例$0.2$与none的比例$0.4$相乘，得到：

大多数关系数据库的计划器在没有额外信息时都会假设各列相互独立，从而忽略数据之间可能存在的相关性。列之间的相关性越强，这种估计通常就越不准确。因此，基数估计至今仍是数据库研究中的活跃领域。

3.2.4.3 部分解决方案：扩展统计信息

PostgreSQL 10引入了多列扩展统计信息；PostgreSQL 12又加入了这里所使用的多列MCV统计。通过CREATE STATISTICS可以把age与license之间的相关性记录在一个统计对象中：

testdb=# CREATE STATISTICS stat_residents (mcv) ON license, age FROM residents;
CREATE STATISTICS
testdb=# ANALYZE;
ANALYZE

生成扩展统计信息后，未满18岁人群的估计结果与现实更加接近：

1. age = 'under18' AND license = 'none'

   testdb=# EXPLAIN (ANALYZE TRUE, TIMING FALSE, BUFFERS FALSE)
   testdb-#     SELECT * FROM residents WHERE age = 'under18' AND license = 'none';
                                         QUERY PLAN
   ---------------------------------------------------------------------------------------
    Seq Scan on residents  (cost=0.00..2.50 rows=20 width=18) (actual rows=20.00 loops=1)
      Filter: ((age = 'under18'::age) AND (license = 'none'::license))
      Rows Removed by Filter: 80
   (8 rows)

2. age = 'under18' AND license = 'standard'

   testdb=# EXPLAIN (ANALYZE TRUE, TIMING FALSE, BUFFERS FALSE)
   testdb-#     SELECT * FROM residents WHERE age = 'under18' AND license = 'standard';
                                        QUERY PLAN
   -------------------------------------------------------------------------------------
    Seq Scan on residents  (cost=0.00..2.50 rows=1 width=18) (actual rows=0.00 loops=1)
      Filter: ((age = 'under18'::age) AND (license = 'standard'::license))
      Rows Removed by Filter: 100
   (6 rows)

3. age = 'under18' AND license = 'gold'

   testdb=# EXPLAIN (ANALYZE TRUE, TIMING FALSE, BUFFERS FALSE)
   testdb-#     SELECT * FROM residents WHERE age = 'under18' AND license = 'gold';
                                        QUERY PLAN
   -------------------------------------------------------------------------------------
    Seq Scan on residents  (cost=0.00..2.50 rows=1 width=18) (actual rows=0.00 loops=1)
      Filter: ((age = 'under18'::age) AND (license = 'gold'::license))
      Rows Removed by Filter: 100
   (6 rows)