PG 内核

• PG先写脏页还是先写WAL？
• 第一章 数据库的物理/逻辑结构
• 第二章 进程和内存架构
• 第三章 查询处理
• 第四章 外部数据包装器
• 第五章 并发控制
• 第六章 垃圾清理过程
• 第七章 堆内元组与仅索引扫描
• 第八章 缓冲区管理器
• 第九章 预写式日志
• 第十章 基础备份与时间点恢复
• 第十一章 流复制
• WAL与检查点概述

PG先写脏页还是先写WAL？

微信公众号原文

昨天在群里遇到一个有趣的关于 PostgreSQL 的问题：

”写脏数据页和写入WAL缓冲区的先后顺序是什么？“

我们都知道， WAL 就是 Write Ahead Log / 预写式日志 的缩写，那从逻辑上说，好像是先写 WAL 再写数据页才对。

但其实这个问题有趣在，写入其实是发生在两个地方的：内存与磁盘。而这对这两者的写入顺序是不一样的：在内存中，先写脏数据页，再写 WAL记录。在刷盘时，先刷 WAL 记录，再刷脏数据页。

我们可以用一个简单的例子来说明，当你执行一条 INSERT 时到底发生了什么？以及，数据库是如何确保这条插入的数据被正确持久化的。

INSERT的内存修改

当你执行 INSERT 语句时（不包括前后隐含的 BEGIN / COMMIT），修改首先在内存中发生：

1.首先排它锁定并钉住目标数据页面，准备修改。2.进入临界区，不允许打断，出错就 PANIC。3.修改内存中的数据页面。4.将修改的内存数据页面标记为脏页。5.生成一条包含修改内容的 WAL记录 ，写入内存中的 WAL 缓冲区。6.从临界区出来，以上3个操作都是内存中的高速操作7.解锁解钉数据页面。

完成这些任务之后，内存中的缓冲池数据页包含了 INSERT 后的结果，WAL缓冲区中则包含了 INSERT 的 XLogRecord 操作记录。这里我们可以看出，在内存中是先写数据页，再写 WAL 的。原因其实很简单，PostgreSQL默认使用物理复制，记录的是页面内的二进制数据变化，所以只有先把数据写入页面里，才会知道具体的页面变化到底是什么。

内存中的操作非常快，而且这里 3 和 6 中间使用了临界区（Critical Zone），确保数据页/WAL的修改整体是原子性的。不过，内存中的修改要落到磁盘上，才算真正持久化了。所以，还会涉及到 WAL 记录与 脏数据页刷盘的问题。

而这里，才是 Write-Ahead 真正约束的地方：脏数据页刷盘应当晚于WAL缓冲区刷盘。

下面是一个具体的例子，一条由单一 INSERT 语句构成的事务：

参考阅读《PostgreSQL指南：内幕探索》 9.5

testdb=# INSERT INTO tbl VALUES ('A');

执行上述语句时，内部函数exec_simple_query()会被调用，其伪代码如下所示：

exec_simple_query() @postgres.c

(1) ExtendCLOG()    @clog.c     /* 将当前事务的状态"IN_PROGRESS"写入CLOG */
(2) heap_insert()    @heapam.c    /* 插入元组，创建一条XLOG记录并调用函XLogInsert. */
(3)   XLogInsert()    @xlog.c     /* (9.5 以及后续的版本为 xloginsert.c) */
                                /* 将插入元组的XLOG记录写入WAL缓冲区，更新页面的 pd_lsn */

(4) finish_xact_command() @postgres.c    /* 执行提交 */   
      XLogInsert() @xlog.c              /* (9.5 以及后续的版本为 xloginsert.c) */
                                        /* 将该提交行为的XLOG记录写入WAL缓冲区 */
(5)   XLogWrite() @xlog.c                /* 将WAL缓冲区中所有的XLOG刷写入WAL段中 */

(6) TransactionIdCommitTree() @transam.c    
                            /* 在CLOG中将当前事务的状态由"IN_PROGRESS"修改为"COMMITTED" /*

1. 函数ExtendCLOG()将当前事务的状态IN_PROGRESS写入内存中的CLOG。
2. 函数heap_insert()向共享缓冲池的目标页面中插入堆元组，创建当前页面的XLOG记录，并执行函数XLogInsert()。
3. 函数XLogInsert()会将heap_insert()创建的XLOG记录写入WAL缓冲区LSN_1处，并将被修改页面的pd_lsn从LSN_0更新为LSN_1。
4. 函数finish_xact_command()会在该事务被提交时被调用，用于创建该提交动作的XLOG记录，而这里的XLogInsert()函数会将该记录写入WAL缓冲区LSN_2处。
5. 函数XLogWrite()会冲刷WAL缓冲区，并将所有内容写入WAL段文件中。如果wal_sync_method参数被配置为open_sync或open_datasync，记录会被同步写入（译者注：而不是提交才会刷新WAL缓冲区），因为函数会使用带有O_SYNC或O_DSYNC标记的open()系统调用。如果该参数被配置为fsync，fsync_writethrough，fdatasync，相应的系统调用就是fsync()，带有F_FULLSYNC选项的fcntl()，以及fdatasync()。无论哪一种情况，所有的XLOG记录都会被确保写入存储之中。
6. 函数TransactionIdCommitTree()将提交日志clog中当前事务的状态从IN_PROGRESS更改为COMMITTED。

如何强制WAL先于脏页刷盘？

那么，先刷WAL，再刷磁盘这条规则具体是怎么确保的呢？

每一个内存中的数据页上都保存了一个状态：最后一次对本数据页进行修改的 WAL 记录 LSN：pd_lsn，因此如果要把内存中的脏页刷入磁盘中，首先需要确保最后一次对这个页面进行修改的 WAL 已经被刷入磁盘中了。

所以我们可以在在 backend/storage/buffer/bufmgr.c#FlushBuffer （L3350）中看到，刷脏页的过程中会调用 XLogFlush 函数来确保这一点，XLogFlush 函数会检查当前的 WAL 刷盘位置是不是已经大于页面的 LSN，如果不是，则会推动 WAL 刷盘。

recptr = BufferGetLSN(buf);
XLogFlush(recptr);

谁会刷脏页呢？主要是BGWriter与Checkpointer，但普通的后端进程也可以刷脏页。一个脏页具体是被哪个进程刷盘比较随机，大家都有机会出力，但通常来说刷脏页的主力是，后台刷盘进程 BGWriter。不管是哪个进程刷脏页，都会确保最后修改数据页的WAL已经落盘，从而满足 Write Ahead 的约束条件。

脏页会在什么时间被刷盘呢？首先，数据页不能被锁定，其次，数据页不能被钉住。也就是说在上面 INSERT 的例子中，只有完成步骤 7 解锁解钉数据页 后，数据页才有可能被刷盘。而这一行为是异步的，具体时间是不确定的：PostgreSQL 能提供的保证是：在下次 Checkpoint（存盘点/检查点）之前，这个脏页肯定会被刷盘。（bufmgr.c）

/*
 * FlushBuffer
 *		Physically write out a shared buffer.
 *
 * NOTE: this actually just passes the buffer contents to the kernel; the
 * real write to disk won't happen until the kernel feels like it.  This
 * is okay from our point of view since we can redo the changes from WAL.
 * However, we will need to force the changes to disk via fsync before
 * we can checkpoint WAL.
 *
 * The caller must hold a pin on the buffer and have share-locked the
 * buffer contents.  (Note: a share-lock does not prevent updates of
 * hint bits in the buffer, so the page could change while the write
 * is in progress, but we assume that that will not invalidate the data
 * written.)
 *
 * If the caller has an smgr reference for the buffer's relation, pass it
 * as the second parameter.  If not, pass NULL.
 */
static void
FlushBuffer(BufferDesc *buf, SMgrRelation reln, IOObject io_object,
			IOContext io_context)
{
	XLogRecPtr	recptr;
	ErrorContextCallback errcallback;
	instr_time	io_start;
	Block		bufBlock;
	char	   *bufToWrite;
	uint32		buf_state;

    /* ... */
	recptr = BufferGetLSN(buf);

	/* To check if block content changes while flushing. - vadim 01/17/97 */
	buf_state &= ~BM_JUST_DIRTIED;
	UnlockBufHdr(buf, buf_state);

	/*
	 * Force XLOG flush up to buffer's LSN.  This implements the basic WAL
	 * rule that log updates must hit disk before any of the data-file changes
	 * they describe do.
	 *
	 * However, this rule does not apply to unlogged relations, which will be
	 * lost after a crash anyway.  Most unlogged relation pages do not bear
	 * LSNs since we never emit WAL records for them, and therefore flushing
	 * up through the buffer LSN would be useless, but harmless.  However,
	 * GiST indexes use LSNs internally to track page-splits, and therefore
	 * unlogged GiST pages bear "fake" LSNs generated by
	 * GetFakeLSNForUnloggedRel.  It is unlikely but possible that the fake
	 * LSN counter could advance past the WAL insertion point; and if it did
	 * happen, attempting to flush WAL through that location would fail, with
	 * disastrous system-wide consequences.  To make sure that can't happen,
	 * skip the flush if the buffer isn't permanent.
	 */
	if (buf_state & BM_PERMANENT)
		XLogFlush(recptr);
    /* ... */
}

WAL是如何刷盘的？

我们已经知道了，刷脏数据页这件事通常是异步进行的，且肯定晚于对应的 WAL 记录刷盘。那么新的问题就是，WAL 是由谁在什么时间点来刷盘的呢：从内存中的 WAL 缓冲区刷入磁盘中？

要回答这个问题，首先要理解 WAL 的模型。WAL 在逻辑上是一个长度无限的文件，任何一个改变数据库系统状态的操作，都会生成相应的 XLogRecord，即 WAL记录。每一条 WAL 记录都会使用其起始位置的文件偏移量作为自己的唯一标识符，即 LSN（逻辑日志位点）。

各种各样修改系统状态的行为都会产生 WAL记录：例如 BEGIN 有一条 WAL记录，INSERT 有一条 WAL记录，COMMIT 也有一条WAL记录，而WAL记录会首先被写入内存中的 WAL缓冲区（最大16MB）。

PostgreSQL 支持多个客户端并发修改，所以同一时刻会有各种进程往内存中的 WAL缓冲区（最大16MB）写东西。所以不同进程、不同事务产生的 XLogRecord 会在同一个逻辑文件中相互交织。每次写入都是原子性的，一条记录一条记录的写。

内存里的WAL缓冲区中的内容，会被各种进程写入/刷入持久化磁盘上的WAL文件里。当前写入内存WAL缓冲区的逻辑日志位置点称作 INSERT LSN。写入操作系统缓冲区的日志位点叫 WRITE LSN，已经使用 FSYNC 之类的 API 确保已经成功持久化的日志位点叫 FLUSH LSN。这里面的关系是 INSERT_LSN >= WRITE_LSN >= FLUSH_LSN。原理很简单：内存中的东西最新，写入可能稍微滞后些，刷盘则可能比写入更滞后一些。

刷盘的主力是 WAL Writer 进程，但其实各种进程都可以刷写。刷盘靠 XLogFlush 函数 （backend/access/transam/xlog.c#XLogFlush），这里的逻辑很简单，就是指定一个位置点，把这个位置点及之前的 WAL 从缓冲区全刷至磁盘。具体的实现逻辑是死循环抢自旋锁，如果目标 LSN 已经被别的进程刷盘了就退出循环，否则就亲自上阵把 WAL 日志刷盘到指定位点。（xlog.c）

/*
 * Ensure that all XLOG data through the given position is flushed to disk.
 *
 * NOTE: this differs from XLogWrite mainly in that the WALWriteLock is not
 * already held, and we try to avoid acquiring it if possible.
 */
void
XLogFlush(XLogRecPtr record)
{
	XLogRecPtr	WriteRqstPtr;
	XLogwrtRqst WriteRqst;
	TimeLineID	insertTLI = XLogCtl->InsertTimeLineID;

	/*
	 * During REDO, we are reading not writing WAL.  Therefore, instead of
	 * trying to flush the WAL, we should update minRecoveryPoint instead. We
	 * test XLogInsertAllowed(), not InRecovery, because we need checkpointer
	 * to act this way too, and because when it tries to write the
	 * end-of-recovery checkpoint, it should indeed flush.
	 */
	if (!XLogInsertAllowed())
	{
		UpdateMinRecoveryPoint(record, false);
		return;
	}

	/* Quick exit if already known flushed */
	if (record <= LogwrtResult.Flush)
		return;

	START_CRIT_SECTION();

	/*
	 * Since fsync is usually a horribly expensive operation, we try to
	 * piggyback as much data as we can on each fsync: if we see any more data
	 * entered into the xlog buffer, we'll write and fsync that too, so that
	 * the final value of LogwrtResult.Flush is as large as possible. This
	 * gives us some chance of avoiding another fsync immediately after.
	 */

	/* initialize to given target; may increase below */
	WriteRqstPtr = record;

	/*
	 * Now wait until we get the write lock, or someone else does the flush
	 * for us.
	 */
	for (;;)
	{
		/* ... */
	}

	END_CRIT_SECTION();

	/* wake up walsenders now that we've released heavily contended locks */
	WalSndWakeupProcessRequests(true, !RecoveryInProgress());

	/*
	 * If we still haven't flushed to the request point then we have a
	 * problem; most likely, the requested flush point is past end of XLOG.
	 * This has been seen to occur when a disk page has a corrupted LSN.
	 *
	 * Formerly we treated this as a PANIC condition, but that hurts the
	 * system's robustness rather than helping it: we do not want to take down
	 * the whole system due to corruption on one data page.  In particular, if
	 * the bad page is encountered again during recovery then we would be
	 * unable to restart the database at all!  (This scenario actually
	 * happened in the field several times with 7.1 releases.)	As of 8.4, bad
	 * LSNs encountered during recovery are UpdateMinRecoveryPoint's problem;
	 * the only time we can reach here during recovery is while flushing the
	 * end-of-recovery checkpoint record, and we don't expect that to have a
	 * bad LSN.
	 *
	 * Note that for calls from xact.c, the ERROR will be promoted to PANIC
	 * since xact.c calls this routine inside a critical section.  However,
	 * calls from bufmgr.c are not within critical sections and so we will not
	 * force a restart for a bad LSN on a data page.
	 */
	if (LogwrtResult.Flush < record)
		elog(ERROR,
			 "xlog flush request %X/%X is not satisfied --- flushed only to %X/%X",
			 LSN_FORMAT_ARGS(record),
			 LSN_FORMAT_ARGS(LogwrtResult.Flush));
}

关于内核原理

关于 PostgreSQL 的内核原理，我认为有几个学习材料非常值得参考。

第一本是《PG Internal》，鈴木啓修写的，基于 PostgreSQL 9.6 与 11 的代码，讲解PG内核原理。我之前翻译了中文版《PostgreSQL指南：内部探索》。第二本是 《PostgreSQL 14 Internal》，是俄罗斯 Postgres Pro 公司 Egor Rogov 写的，基于 PostgreSQL 14 进行架构讲解。

当然我认为最有学习价值的还是 PostgreSQL 源代码，特别是源代码中的 README，比如本文中的这个问题，就在事务管理器源码 README 中详细介绍了。PostgreSQL 的源代码是自我解释的，你只需要懂英文大致就能理解这里面的逻辑。

The general schema for executing a WAL-logged action is

1. Pin and exclusive-lock the shared buffer(s) containing the data page(s)
to be modified.

2. START_CRIT_SECTION()  (Any error during the next three steps must cause a
PANIC because the shared buffers will contain unlogged changes, which we
have to ensure don't get to disk.  Obviously, you should check conditions
such as whether there's enough free space on the page before you start the
critical section.)

3. Apply the required changes to the shared buffer(s).

4. Mark the shared buffer(s) as dirty with MarkBufferDirty().  (This must
happen before the WAL record is inserted; see notes in SyncOneBuffer().)
Note that marking a buffer dirty with MarkBufferDirty() should only
happen iff you write a WAL record; see Writing Hints below.

5. If the relation requires WAL-logging, build a WAL record using
XLogBeginInsert and XLogRegister* functions, and insert it.  (See
"Constructing a WAL record" below).  Then update the page's LSN using the
returned XLOG location.  For instance,

		XLogBeginInsert();
		XLogRegisterBuffer(...)
		XLogRegisterData(...)
		recptr = XLogInsert(rmgr_id, info);

		PageSetLSN(dp, recptr);

6. END_CRIT_SECTION()

7. Unlock and unpin the buffer(s).

Complex changes (such as a multilevel index insertion) normally need to be
described by a series of atomic-action WAL records.  The intermediate states
must be self-consistent, so that if the replay is interrupted between any
two actions, the system is fully functional.  In btree indexes, for example,
a page split requires a new page to be allocated, and an insertion of a new
key in the parent btree level, but for locking reasons this has to be
reflected by two separate WAL records.  Replaying the first record, to
allocate the new page and move tuples to it, sets a flag on the page to
indicate that the key has not been inserted to the parent yet.  Replaying the
second record clears the flag.  This intermediate state is never seen by
other backends during normal operation, because the lock on the child page
is held across the two actions, but will be seen if the operation is
interrupted before writing the second WAL record.  The search algorithm works
with the intermediate state as normal, but if an insertion encounters a page
with the incomplete-split flag set, it will finish the interrupted split by
inserting the key to the parent, before proceeding.

第一章 数据库的物理/逻辑结构

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

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

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

1.1 数据库集簇的逻辑结构

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

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

图1.1 数据库集簇的逻辑结构

在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中的表空间对应一个包含基础目录之外数据的目录。

图1.2 数据库集簇示例

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

1.2.1 数据库集簇的布局

官方文档中描述了数据库集簇的布局。 表1.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展示了表空间的内部布局，以及表空间与主数据区域的关系。

图 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 堆表文件的内部布局

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

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

图 1.4. 堆表文件的页面布局

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

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

此外，大小超过约2KB（8KB的四分之一）的堆元组会使用一种称为 TOAST（The Oversized-Attribute Storage Technique，超大属性存储技术） 的方法来存储与管理。详情请参阅PostgreSQL文档。

1.4 读写元组的方式

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

1.4.1 写入堆元组

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

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

图1.5 堆元组的写入

1.4.2 读取堆元组

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

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

图 1.6 顺序扫描和索引扫描

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章中详细介绍。

第二章 进程和内存架构

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

2.1 进程架构

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

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

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

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

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

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

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

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

图2.1 PostgreSQL的进程架构示例

本图展示了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的内部机制。 因此在本章中仅做简要介绍。 细节将在后续章节中描述。

表2.1 后台进程

这里展示了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 PostgreSQL的内存架构

2.2.1 本地内存区域

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

表2.2 本地内存区域

2.2.2 共享内存区域

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

表2.3 共享内存区域

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

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

诸如此类。

第三章 查询处理

查询处理是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）

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

图3.1 查询处理

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

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;

图3.2. 语法解析树的例子

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;

图3.3 查询树一例

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

• 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展示了结果相应的计划树。

图3.5 一个简单的计划树以及其与EXPLAIN命令的关系

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

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

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

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

图3.6 执行器，缓冲管理器，临时文件之间的关系

除此之外，当访问元组的时候，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，而运行代价由以下公式定义： $$ \begin{align} \verb|run_cost| &= \verb|cpu_run_cost| + \verb|disk_run_cost | \ &= (\verb|cpu_tuple_cost| + \verb|cpu_operator_cost|) × N_{\verb|tuple|} + \verb|seq_page_cost| × N_{\verb|page|}, \end{align} $$ 其中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)

$$ \begin{equation}\tag{1} N_{\verb|tuple|}=10000 \end{equation} $$

$$ \begin{equation}\tag{2} N_{\verb|page|}=45 \end{equation} $$

因此： $$ \begin{align} \verb|run_cost| &= (0.01 + 0.0025) × 10000 + 1.0 × 45 = 170.0. \end{align} $$

最终： $$ \verb|total_cost| = 0.0 + 170.0 = 170.0 $$

作为验证，下面是该查询的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)

$$ \begin{equation}\tag{3} N_{\verb|index|,\verb|tuple|} = 10000 \end{equation} $$

$$ \begin{equation}\tag{4} N_{\verb|index|,\verb|page|} = 30 \end{equation} $$

3.2.2.1 启动代价

索引扫描的启动代价就是读取索引页以访问目标表的第一条元组的代价，由下面的公式定义： $$ \begin{equation} \verb| start-up_cost| = {\mathrm{ceil}(\log_2 (N_{\verb|index|,\verb|tuple|})) + (H_{\verb|index|} + 1) × 50} × \verb|cpu_operator_cost| \end{equation} $$ 其中$H_{\verb|index|}$是索引树的高度。

在本例中，套用公式(3)，$N_{\verb|index,tuple|}$是10000；$H_{\verb|index|}$是1；$\verb|cpu_operator_cost|$是0.0025（默认值）。因此 $$ \begin{equation}\tag{5} \verb|start-up_cost| = {\mathrm{ceil}(\log_2(10000)) + (1 + 1) × 50} × 0.0025 = 0.285 \end{equation} $$

3.2.2.2 运行代价

索引扫描的运行代价是表和索引的CPU代价与IO代价之和。 $$ \begin{align} \verb|run_cost| &= (\verb|index_cpu_cost| + \verb|table_cpu_cost|) + (\verb|index_io_cost| + \verb|table_io_cost|). \end{align} $$

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

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

$$ \begin{align} \verb|index_cpu_cost| &= \verb|Selectivity| × N_{\verb|index|,\verb|tuple|} × (\verb|cpu_index_tuple_cost| + \verb|qual_op_cost|) \ \verb|table_cpu_cost| &= \verb|Selectivity| × N_{\verb|tuple|}× \verb|cpu_tuple_cost| \ \verb|index_io_cost| &= \mathrm{ceil}(\verb|Selectivity| × N_{\verb|index|,\verb|page|}) ×\verb|random_page_cost| \end{align} $$

以上公式中的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|})$就是需要读取的索引元组数量，诸如此类。

选择率（Selectivity）

查询谓词的选择率是通过**直方图界值（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)，有 $$ \begin{equation}\tag{7} \verb|index_cpu_cost| = 0.024× 10000 × (0.005+0.0025)=1.8 \end{equation} $$ $$ \begin{equation}\tag{8} \verb|table_cpu_cost| = 0.024 × 10000 × 0.01 = 2.4 \end{equation} $$

$$ \begin{equation}\tag{9} \verb|index_io_cost| = \mathrm{ceil}(0.024 × 30) × 4.0 = 4.0 \end{equation} $$

$\verb|table_io_cost|$ 由下面的公式定义： $$ \begin{equation} \verb|table_io_cost| = \verb|max_io_cost| + \verb|indexCorerelation|^2 × (\verb|min_io_cost|-\verb|max_io_cost|) \end{equation} $$

$\verb|max_io_cost_io_cost|$ 是最差情况下的I/O代价，即，随机扫描所有数据页的代价；这个代价由以下公式定义： $$ \begin{equation} \verb|max_io_cost| = N_{\verb|page|} × \verb|random_page_cost| \end{equation} $$

在本例中，由(2)，$N_{\verb|page|}=45$，得 $$ \begin{equation}\tag{10} \verb|max_io_cost| = 45 × 4.0 = 180.0 \end{equation} $$

$\verb|min_io_cost|$是最优情况下的I/O代价，即，顺序扫描选定的数据页；这个代价由以下公式定义： $$ \begin{equation} \verb|min_io_cost| = 1 × \verb|random_page_cost| + (\mathrm{ceil}(\verb|Selectivity| × N_{\verb|page|})-1) × \verb|seq_page_cost| \end{equation} $$ 在本例中， $$ \begin{equation} \tag{11} \verb|min_io_cost| \ = 1 × 4.0 + (\mathrm{ceil}(0.024 × 45)-1) × 1.0 \end{equation} $$

下文详细介绍$\verb|indexCorrelation|$，在本例中， $$ \begin{equation} \tag{12} \verb|indexCorrelation| = 1.0 \end{equation} $$

由(10)，(11)和(12)，得 $$ \begin{equation} \tag{13} \verb|table_io_cost| = 180.0+1.0^2 × (5.0-180.0)=5.0 \end{equation} $$

综上，由(7)，(8)，(9)和(13)得 $$ \begin{equation}\tag{14} \verb|run_cost| = (1.8+2.4)+(4.0+5.0)=13.2 \end{equation} $$

索引相关性（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)可得 $$ \begin{equation}\tag{15} \verb|total_cost| = 0.285 + 13.2 = 13.485 \end{equation} $$

作为确认，上述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;

在本例中，启动代价由以下公式定义： $$ \begin{equation} \verb|start-up_cost| = \verb|C|+ \verb|comparison_cost| × N_{\verb|sort|} × \log_2(N_{\verb|sort|}) \end{equation} $$

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

$$ \begin{equation} \verb|start-up_cost| = 13.485+(2×0.0025)×240.0×\log_2(240.0)=22.973 \end{equation} $$

运行代价是在内存中读取排好序的元组的代价，即： $$ \begin{equation} \verb|run_cost| = \verb|cpu_operator_cost| × N_{\verb|sort|} = 0.0025 × 240 = 0.6 \end{equation} $$ 综上： $$ \begin{equation} \verb|total_cost|=22.973+0.6=23.573 \end{equation} $$ 作为确认，以上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.3 创建单表查询的计划树

计划器非常复杂，故本节仅描述最简单的情况，即单表查询的计划树创建过程。更复杂的查询，换而言之即多表查询，其计划树创建过程将在第3.6节中阐述。

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

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

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

计划器为了处理上述步骤，会在内部创建一个PlannerInfo数据结构。在该数据结构中包含着查询树，查询所涉及关系信息，访问路径等等。

typedef struct PathKey {
    NodeTag type;
    EquivalenceClass *pk_eclass; /* 值是否有序 */
    Oid pk_opfamily;             /* 用于定义顺序的B树操作符族 */
    int pk_strategy;             /* 排序方向(ASC or DESC) */
    bool pk_nulls_first;         /* NULL是否排序在常规值之前？ */
} PathKey;

typedef struct Path {
    NodeTag type;
    NodeTag pathtype;          /* 标识 scan/join 方法的标签 */
    RelOptInfo *parent;        /* 路径所基于的关系 */
    PathTarget *pathtarget;    /* Vars/Exprs的列表, 代价, 宽度 */
    ParamPathInfo *param_info; /* 参数化信息, 如果没有则为NULL */
    bool parallel_aware;       /* 涉及到并行相关的逻辑？ */
    bool parallel_safe;        /* 是否能作为并行执行计划的一部分? */
    int parallel_workers;      /* 期待的并行工作进程数量； 0表示没有并行 */

    /* 估计路径的尺寸或代价 (更多详情参考costsize.c) */
    double rows;       /* 预估结果元组数目 */
    Cost startup_cost; /* 获取任何元组前需要花费的代价 */
    Cost total_cost;   /* 总代价 (假设获取所有元组所需代价) */
    List *pathkeys;    /* 路径输出的排序顺序 */
    /* pathkeys 是PathKey节点的列表，PathKey定义见上面 */
} Path;

typedef struct PlannerInfo {
    NodeTag type;
    Query *parse;                    /* 被计划的查询 */
    PlannerGlobal *glob;             /* 当前计划器运行时的全局信息 */
    Index query_level;               /* 最外层查询为1 */
    struct PlannerInfo *parent_root; /* 最外层查询为NULL */

    /* plan_params包含着当前计划中的查询层次需要对低层查询暴露的表达式。
     * outer_params包含着PARAM_EXEC参数中的paramId列表，这些参数是外
     * 部查询层次对当前查询层次所暴露的。*/
    List *plan_params; /* PlannerParamItems的列表, 见下 */
    Bitmapset *outer_params;

    /* simple_rel_array 持有着指向“基础关系”与“其他关系”的指针 (详情参考
     * RelOptInfo的注释)。它由rangetable index所索引（因此第0项总是废值）。
     * 当RTE并不与基础关系相对应，譬如连接的RTE，或未引用的视图RTE，或该
     * RelOptInfo还没有产生时，里面的项目可能为NULL。*/
    struct RelOptInfo **simple_rel_array; /* 所有单个关系的RelOptInfos */
    int simple_rel_array_size;            /* 数组分配的大小 */

    /* simple_rte_array 与simple_rel_array 长度相同，且持有指向关联范围表项的指针。
     * 这使得我们能避免执行rt_fetch(), 当需要展开很大的继承集时会很慢。 */
    RangeTblEntry **simple_rte_array; /* rangetable的数组 */

    /* all_baserels是所有查询所涉及基本关系的关系ID列表（但不含“其他关系”的ID）
     * 也就是说，最终连接时，所需构建的关系标识符。该字段是由make_one_rel计算的。
     * 计算发生于计算Paths之前。*/
    Relids all_baserels;

    /* nullable_baserels 是在进行外连接的jointree中那些可空的基础关系的ID集合。
     * 这些关系可能在WHERE子句，SELECT目标列表或其他地方产生空值。该字段由函数
     * deconstruct_jointree负责计算。*/
    Relids nullable_baserels;

    /* join_rel_list是一个列表，在计划过程中连接关系的RelOptInfos都放在这里。
     * 对于比较小的问题，我们只是简单的扫过这个列表来完成查找。但当连接很多关系时，
     * 我们会使用散列表来加速查询。散列表当且仅当join_rel_hash不为空时存在且
     * 有效。注意即使用散列表查找时，我们依然会维护列表，这会简化GEQO的相关问题。*/
    List *join_rel_list;        /* 连接关系的RelOptInfos */
    struct HTAB *join_rel_hash; /* 连接关系的散列表，可选 */

    /* 当使用动态规划进行连接搜索时，join_rel_level[k]是第k层的连接关系RelOptInfos列表。
     * 新的连接关系RelOptInfos会自动添加到join_rel_level[join_cur_level]中，
     * 而join_cur_level为当前层级。如果没用到动态规划，join_rel_level则为空。*/
    List **join_rel_level;    /* 连接关系RelOptInfo的列表 */
    int join_cur_level;       /* 待追加列表的序号 */
    List *init_plans;         /* 查询的初始SubPlans */
    List *cte_plan_ids;       /* 子计划的ID列表，每个CTE对应一个 */
    List *multiexpr_params;   /* MULTIEXPR子查询输出用到的双层嵌套参数列表 */
    List *eq_classes;         /* 活跃的EquivalenceClasses列表 */
    List *canon_pathkeys;     /* "标准" PathKeys 的列表 */
    List *left_join_clauses;  /* RestrictInfos列表，用于左连接子句 */
    List *right_join_clauses; /* RestrictInfos列表，用于右连接子句 */
    List *full_join_clauses;  /* RestrictInfos列表，用于完全连接子句 */
    List *join_info_list;     /* SpecialJoinInfos 的列表 */
    List *append_rel_list;    /* AppendRelInfos 的列表 */
    List *rowMarks;           /* PlanRowMarks 的列表 */
    List *placeholder_list;   /* PlaceHolderInfos 的列表 */
    List *fkey_list;          /* ForeignKeyOptInfos 的列表 */
    List *query_pathkeys;     /* query_planner()期望的pathkeys */
    List *group_pathkeys;     /* groupClause的pathkeys, 如果有的话 */
    List *window_pathkeys;    /* 底部窗口的pathkeys, 如果有的话 */
    List *distinct_pathkeys;  /* distinctClause的pathkeys, 如果有的话 */
    List *sort_pathkeys;      /* sortClause的pathkeys, 如果有的话 */
    List *initial_rels;       /* 我们现在正在尝试连接的RelOptInfos */

    /* 使用fetch_upper_rel()来获取任意特定的上层关系 */
    List *upper_rels[UPPERREL_FINAL + 1]; /* upper-rel RelOptInfos */

    /* grouping_planner针对上层处理过程选择的目标列表 */
    struct PathTarget *upper_targets[UPPERREL_FINAL + 1];

    /* grouping_planner会将最终处理过后的targetlist回传至此。在最终计划最顶层的目标列表中会用到 */
    List *processed_tlist;

    /* create_plan()期间填充的字段，定义于setrefs.c */
    AttrNumber *grouping_map;    /* 针对GroupingFunc的修补 */
    List *minmax_aggs;           /* MinMaxAggInfos列表 */
    MemoryContext planner_cxt;   /* 持有PlannerInfo的上下文 */
    double total_table_pages;    /* 查询涉及到所有表的页面总数 */
    double tuple_fraction;       /* 传递给查询计划器的tuple_fraction */
    double limit_tuples;         /* 传递给查询计划器的limit_tuples */
    bool hasInheritedTarget;     /* 若parse->resultRelation为继承的子关系则为真 */
    bool hasJoinRTEs;            /* 如果任意RTEs为RTE_JOIN类别则为真 */
    bool hasLateralRTEs;         /* 如果任意RTEs被标记为LATERAL则为真 */
    bool hasDeletedRTEs;         /* 如果任意RTEs从连接树中被删除则为真 */
    bool hasHavingQual;          /* 如果havingQual非空则为真 */
    bool hasPseudoConstantQuals; /* 如果任意RestrictInfo包含
    								pseudoconstant = true则为真 */
    bool hasRecursion;           /* 如果计划中包含递归WITH项则为真 */

    /* 当hasRecursion为真时，会使用以下字段： */
    int wt_param_id;                 /* 工作表上PARAM_EXEC的ID */
    struct Path *non_recursive_path; /* 非递归项的路径 */

    /* 这些字段是createplan.c的工作变量 */
    Relids curOuterRels;  /* 当前节点外部的关系 */
    List *curOuterParams; /* 尚未赋值的NestLoopParams */

    /* 可选的join_search_hook私有数据, 例如, GEQO */
    void *join_search_private;
} PlannerInfo;

本节会通过一个具体的例子，来描述如何基于查询树创建计划树。

3.3.1 预处理

在创建计划树之前，计划器对先PlannerInfo中的查询树进行一些预处理。

预处理有很多步骤，本节只讨论和单表查询处理相关的主要步骤。其他预处理操作将在3.6节中描述。

1. 简化目标列表（target list），LIMIT子句等；

   例如，表达式2+2会被重写为4，这是由clauses.c中eval_const_expressions()函数负责的。

2. 布尔表达式的规范化

   例如，NOT(NOT a)会被重写为a

3. 压平与/或表达式

   SQL标准中的AND/OR是二元操作符；但在PostgreSQL内部它们是多元操作符。而计划器总是会假设所有的嵌套AND/OR都应当被压平。

   这里有一个具体的例子。考虑这样一个布尔表达式(id = 1) OR (id = 2) OR (id = 3)，图3.9(a) 展示了使用二元表达式时的查询树，预处理会将这些二元算子简化压平为一个三元算子，如图3.9(b)所示。

   图3.9. 压平布尔表达式的例子

   

3.3.2 找出代价最小的访问路径

计划器对所有可能的访问路径进行代价估计，然后选择代价最小的那个。具体来说，计划器会执行以下几个步骤：

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

   RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo结构体的simple_rel_array字段中，如图3.10所示。在初始状态时RelOptInfo持有着baserestrictinfo变量，如果存在相应索引，还会持有indexlist变量。baserestrictinfo存储着查询的WHERE子句，而indexlist存储着目标表上相关的索引。

   typedef enum RelOptKind
   {
   	RELOPT_BASEREL,
   	RELOPT_JOINREL,
   	RELOPT_OTHER_MEMBER_REL,
   	RELOPT_UPPER_REL,
   	RELOPT_DEADREL
   } RelOptKind;
   
   typedef struct RelOptInfo
   {
   	NodeTag		type;
   	RelOptKind	reloptkind;
   
   	/* 本RelOptInfo包含的所有关系 */
   	Relids		relids;			/* 基本关系的ID集合 (范围表索引) */
   
   	/* 由计划器生成的预估尺寸 */
   	double		rows;			/* 预估结果元组数目 */
   
   	/* 计划器标记位，每个关系一份 */
   	bool		consider_startup;	    /* 保留启动代价最低的路径？ */
   	bool		consider_param_startup; /* 同上, 针对参数化路径？ */
   	bool		consider_parallel;	    /* 考虑并行路径？ */
   
   	/* 扫描当前关系的默认结果目标列表 */
   	struct PathTarget *reltarget;		/* Vars/Exprs, 代价, 宽度的列表 */
   
   	/* 物化相关信息 */
   	List	   *pathlist;			    /* Path 结构体列表 */
   	List	   *ppilist;			    /* pathlist中使用的ParamPathInfos */
   	List	   *partial_pathlist;		/* 部分路径 */
   	struct Path *cheapest_startup_path;
   	struct Path *cheapest_total_path;
   	struct Path *cheapest_unique_path;
   	List	    *cheapest_parameterized_paths;
   
   	/* 基础关系与连接关系都需要的 参数化信息 */
   	/* (参见 lateral_vars 与 lateral_referencers) */
   	Relids		direct_lateral_relids;	/* 直接以LATERAL方式引用的关系 */
   	Relids		lateral_relids; 	    
   
   	/* 关于基础关系的信息 (连接关系不会设置这些字段！) */
   	Index		relid;
   	Oid		    reltablespace;	    /* 表空间 */
   	RTEKind		rtekind;		    /* RELATION, SUBQUERY, 或 FUNCTION */
   	AttrNumber	min_attr;		    /* 关系属性的最小值 (通常<0) */
   	AttrNumber	max_attr;		    /* 关系属性的最大值 */
   	Relids	   	*attr_needed;		/* 被索引的数组 [min_attr .. max_attr] */
   	int32	   	*attr_widths;	   	/* 被索引的数组 [min_attr .. max_attr] */
   	List	   	*lateral_vars;	   	/* 关系所引用的LATERAL Vars 与 PHVs */
   	Relids		lateral_referencers;/* 侧面引用本表的关系 */
   	List	   	*indexlist;		    /* IndexOptInfo列表 */
   	BlockNumber pages;			    /* 来自pg_class的页面数估计值 */
   	double		tuples;
   	double		allvisfrac;
   	PlannerInfo *subroot;		    /* 如有子查询 */
   	List	   	*subplan_params; 	/* 如有子查询 */
   	int		    rel_parallel_workers;	/* 期望的并行工作进程数量 */
   
   	/* 有关外部表与外部表连接的相关信息 */
   	Oid			serverid;		/* 外部表与外部表连接相应的服务器ID */
   	Oid			userid;			/* 用于检查访问权限的用户标识 */
   	bool		useridiscurrent;/* 当前用户是否能合法进行JOIN */
   	struct FdwRoutine *fdwroutine;
   	void	   	*fdw_private;
   
   	/* 被各种扫描与连接所使用 */
   	List	   	*baserestrictinfo;	/* RestrictInfo结构体列表 (如果存在基础关系) */
   	QualCost	baserestrictcost;	/* 求值上述限制条件的代价 */
   	List	   	*joininfo;		    /* RestrictInfo 结构体列表，涉及到本表的连接会用到 */
   	bool		has_eclass_joins;	/* T 意味着joininfo不完整 */
   } RelOptInfo;
   

2. 估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。

   这一处理过程的细节如下：

   1. 创建一条路径，估计该路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。
   2. 如果目标表上存在相关的索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应路径中。然后将索引访问路径添加到pathlist变量中。
   3. 如果可以进行位图扫描，则创建一条位图扫描访问路径。估计所有的位图扫描的代价，并将代价写入到路径中。然后将位图扫描路径添加到pathlist变量中。

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

4. 如有必要，估计LIMIT，ORDER BY和AGGREGATE操作的代价。

为了更加清晰的理解计划器的执行过程，下面给出了两个具体的例子。

3.3.2.1 例1

首先来研究一个不带索引的简单单表查询；该查询同时包含WHERE和ORDER BY子句。

testdb=# \d tbl_1
     Table "public.tbl_1"
 Column |  Type   | Modifiers 
--------+---------+-----------
 id     | integer | 
 data   | integer | 

testdb=# SELECT * FROM tbl_1 WHERE id < 300 ORDER BY data;

图3.10和图3.11展示了本例中计划器的处理过程。

图3.10 如何得到例1中代价最小的路径

1. 创建一个RelOptInfo结构，将其保存在PlannerInfo结构的simple_rel_array字段中。

2. 在RelOptInfo结构的baserestrictinfo字段中，添加一条WHERE子句。

   WHERE子句id<300会经由initsplan.c中定义的distribute_restrictinfo_to_rels()函数，添加至列表变量baserestrictinfo中。另外由于目标表上没有相关索引，RelOptInfo的indexlist字段为空。

3. 为了满足排序要求，planner.c中的standard_qp_callback()函数会在PlannerInfo的sor_pathkeys字段中添加一个pathkey。

   Pathkey是表示路径排序顺序的数据结构。本例因为查询包含一条ORDER BY子句，且该子句中的列为data，故data会被包装为pathkey，放入列表变量sort_pathkeys中。

4. 创建一个Path结构，并使用cost_seqscan函数估计顺序扫描的代价，并将代价写入Path中。然后使用pathnode.c中定义的add_path()函数，将该路径添加至RelOptInfo中。

   如之前所提到过的，Path中同时包含启动代价和总代价，都是由cost_seqscan函数所估计的。

在本例中，因为目标表上没有索引，计划器只估计了顺序扫描的代价，因此最小代价是自动确定的。

图3.11 如何得到例1中代价最小的路径（接图3.10）

5. 创建一个新的RelOptInfo结构，用于处理ORDER BY子句。

   注意新的RelOptInfo没有baserestrictinfo字段，该信息已经被WHERE子句所持有。

6. 创建一个排序路径，并添加到新的RelOptInfo中；然后让SortPath的subpath字段指向顺序扫描的路径。

   typedef struct SortPath
   {
       Path	path;
       Path	*subpath;		/* 代表输入来源的子路径 */
   } SortPath;
   

   SortPath结构包含两个Path结构：path与subpath；path中存储了排序算子本身的相关信息，而subpath则指向之前得到的代价最小的路径。

   注意顺序扫描路径中parent字段，该字段指向之前的RelOptInfo结构体（也就是在baserestrictinfo中存储着WHERE子句的那个RelOptInfo）。因此在下一步创建计划树的过程中，尽管新的RelOptInfo结构并未包含baserestrictinfo，但计划器可以创建一个包含Filter的顺序扫描节点，将WHERE子句作为过滤条件。

这里已经获得了代价最小的访问路径，然后就可以基于此生成一颗计划树。3.3.3节描述了相关的细节。

3.3.2.2 例2

下面我们将研究另一个单表查询的例子，这一次表上有两个索引，而查询带有一个WHERE子句。

testdb=# \d tbl_2
     Table "public.tbl_2"
 Column |  Type   | Modifiers 
--------+---------+-----------
 id     | integer | not null
 data   | integer | 
Indexes:
    "tbl_2_pkey" PRIMARY KEY, btree (id)
    "tbl_2_data_idx" btree (data)

testdb=# SELECT * FROM tbl_2 WHERE id < 240;

图3.12到3.14展示了本例中计划器的处理过程。

1. 创建一个RelOptInfo结构体

2. 在baserestrictinfo中添加一个WHERE子句；并将目标表上的索引（们）添加到indexlist中。

   在本例中，WHERE子句'id <240'会被添加至baserestrictinfo中，而两个索引：tbl_2_pkey和tbl_2_data_idx会被添加至RelOptInfo的列表变量indexlist中。

3. 创建一条路径，估计其顺序扫描代价，并添加到RelOptInfo的pathlist中。

图3.12 如何得到例2中代价最小的路径

typedef struct IndexPath
{
	Path			path;
	IndexOptInfo 	*indexinfo;
	List	   		*indexclauses;
	List	   		*indexquals;
	List	   		*indexqualcols;
	List	   		*indexorderbys;
	List	   		*indexorderbycols;
	ScanDirection 	indexscandir;
	Cost			indextotalcost;
	Selectivity 	indexselectivity;
} IndexPath;

/*
 * IndexOptInfo
 *      用于计划/优化的信息，每个索引对应一个。
 *
 *		indexkeys[], indexcollations[], opfamily[], 以及 opcintype[]
 *		每个字段都有 ncolumns 个项.
 *
 *		sortopfamily[], reverse_sort[], 以及 nulls_first[] 类似，也都有
 *		ncolumns 个项, 当且仅当该索引是有序的，否则这些指针都为空。
 *
 *		indexkeys[] 数组中的零值表示该索引列是一个表达式，而每个这种列在indexprs
 *      中都会有一个对应的元素。
 *
 *      对于有序索引，reverse_sort[] 以及 nulls_first[] 描述了正向索引扫描时
 *      索引的排序顺序。当进行反向索引扫描时，就会产生相反的顺序。
 *
 *		indexprs 与 indpred 会通过prepqual.c 中的 eval_const_expressions() 
 *      用于简单地与WHERE子句匹配，indpred使用简单的合取范式。
 *
 *		indextlist 是 TargetEntry的列表，标识着索引建在哪些列上。对于简单的列，
 *      它会提供基本关系中与之对应的Var，对于表达式列，它还会指向indexprs对应元素。
 *      相对应的Var。
 *
 *		当IndexOptInfo创建时，这里大多数字段都会被填充 (plancat.c)，但indrestrictinfo 
 *      与predOK会在稍后通过check_index_predicates()设置。
 */
typedef struct IndexOptInfo
{
	NodeTag		type;
	Oid		    indexoid;		/* 索引关系的OID */
	Oid		    reltablespace;	/* 索引所属的表空间 (不是表) */
	RelOptInfo 	*rel;			/* 索引对应的表，反向链接 */

	/* 索引尺寸的统计 (来自pg_class和其他地方) */
	BlockNumber pages;			/* 索引中的磁盘页面数 */
	double		tuples;			/* 索引中的元组数量 */
	int		    tree_height;	/* 索引树的高度，未知则为 -1  */

	/* 索引描述符信息 */
	int		    ncolumns;		/* 索引中列的数量 */
	int		    *indexkeys;		/* 索引中列的序号，或者0 */
	Oid		    *indexcollations;	/* 索引列上排序规则的OID */
	Oid		    *opfamily;		/* 列上运算符族的OID */
	Oid		    *opcintype;		/* 运算符族输入数据类型的OID */
	Oid		    *sortopfamily;	/* 如果这些列有序，B树算子族的OID */
	bool	   	*reverse_sort;	/* 排序顺序是反向降序的吗？ */
	bool	   	*nulls_first;	/* 排序顺序中，空值是排在最前面的吗？ */
	bool	   	*canreturn;		/* 在仅索引扫描中，哪些索引列可以被返回？ */
	Oid		    relam;			/* 访问方法的OID (在 pg_am 中) */

	List	   	*indexprs;		/* 非平凡的索引列，即表达式 */
	List	   	*indpred;		/* 如果是部分索引，则为谓词，否则为空 */

	List	   	*indextlist;	/* 表示索引列的目标列表 */

	List	   	*indrestrictinfo;	/* 父关系的baserestrictinfo列表 */

	bool		predOK;			    /* 如果查询与索引谓词匹配则为真 */
	bool		unique;			    /* 唯一索引则为真 */
	bool		immediate;		    /* 唯一约束是否是立即强制实施的？ */
	bool		hypothetical;		/* 如果索引并非真实存在则为真。 */

	/* 剩下这些字段是从索引访问方法的API结构里复制过来的 */
	bool		amcanorderbyop;     /* 访问方法是否支持按算子结果排序？ */
	bool		amoptionalkey;		/* 查询是否可以忽略第一列中的键？ */
	bool		amsearcharray;		/* 访问方法是否能处理ScalarArrayOpExpr限定条件? */
	bool		amsearchnulls;		/* 访问方法是否能搜索空项或非空项？ */
	bool		amhasgettuple;		/* 访问方法是否有amgettuple接口？ */
	bool		amhasgetbitmap; 	/* 访问方法是否有amgetbitmap接口？ */
	/* 相比include amapi.h，我们直接在这里用这种方式声明 amcostestimate  */
	void		(*amcostestimate) ();	/* 访问方法的代价估计器 */
} IndexOptInfo;

4. 创建一个IndexPath，估计索引扫描的代价，并通过add_path()函数将IndexPath添加到RelOptInfo的pathlist中。

   在本例中有两个索引：tbl_2_pkey与tbl_2_data_index，这些索引会按先后顺序依次处理。

   一条针对tbl_2_pkey的IndexPath会先被创建出来，并进行启动代价与总代价的评估。在本例中，tbl_2_pkey是id列上的索引，而WHERE子句也包含该id列；因此WHERE子句会被存储在IndexPath的indexclauses字段中。

5. 创建另一个IndexPath，估计另一种索引扫描的代价，并将该IndexPath添加到RelOptInfo的pathlist中。

   接下来，与tbl_2_data_idx相应的IndexPath会被创建出来，并进行代价估计。本例中tbl_2_data_idx并没有相关的WHERE子句；因此其indexclauses为空。

注意add_path()函数并不总是真的会将路径添加到路径列表中。这一操作相当复杂，故这里就省去了具体描述。详细细节可以参考add_path()函数的注释。

图3.13 如何得到例2中代价最小的路径（接图3.12）

6. 创建一个新的RelOptInfo结构

7. 将代价最小的路径，添加到新RelOptInfo的pathlist中。

   本例中代价最小的路径是使用tbl_2_pkey的索引路径；故将该路径添加到新的RelOptInfo中。

图3.14 如何得到例2中代价最小的路径（接图3.13）

3.3.3 创建计划树

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

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

• **commandType**存储操作的类型，诸如SELECT，UPDATE和INSERT。
• **rtable**存储范围表的列表（RangeTblEntry的列表）。
• **relationOids**存储与查询相关表的oid。
• **plantree**存储着一颗由计划节点组成的计划树，每个计划节点对应着一种特定操作，诸如顺序扫描，排序和索引扫描。

/* ----------------
 *		PlannedStmt 节点
 * 计划器的输出是一颗计划树，PlannedStmt是计划树的根节点。
 * PlannedStmt存储着执行器所需的“一次性”信息。
 * ----------------*/
typedef struct PlannedStmt
{
	NodeTag		type;
	CmdType		commandType;		/* 增|删|改|查 */
	uint32		queryId;			/* 查询标识符 (复制自Query) */
	bool		hasReturning;		/* 增|删|改是否带有RETURNING? */
	bool		hasModifyingCTE;	/* WITH子句中是否出现了增|删|改？ */
	bool		canSetTag;			/* 我是否设置了命令结果标记？ */
	bool		transientPlan;		/* 当TransactionXmin变化时重新进行计划? */
	bool		dependsOnRole;		/* 执行计划是否特定于当前的角色？ */
	bool		parallelModeNeeded;	/* 需要并行模式才能执行？ */
	struct Plan *planTree;			/* 计划节点树 */
	List	   	*rtable;			/* RangeTblEntry节点的列表 */
	
    /* 目标关系上用于增|删|改的范围表索引 */
	List	   	*resultRelations;   /* RT索引的整数列表, 或NIL */
	Node	   	*utilityStmt;		/* 如为DECLARE CURSOR则非空 */
	List	   	*subplans;			/* SubPlan表达式的计划树 expressions */
	Bitmapset  	*rewindPlanIDs;		/* 需要REWIND的子计划的索引序号 */
	List	   	*rowMarks;			/* PlanRowMark列表 */
	List	   	*relationOids;		/* 计划所依赖的关系OID列表 */
	List	   	*invalItems;		/* 其他依赖，诸如PlanInvalItems */
	int			nParamExec;			/* 使用的PARAM_EXEC参数数量 */
} PlannedStmt;