This is the multi-page printable view of this section. Click here to print.
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" /*
- 函数
ExtendCLOG()
将当前事务的状态IN_PROGRESS
写入内存中的CLOG。 - 函数
heap_insert()
向共享缓冲池的目标页面中插入堆元组,创建当前页面的XLOG记录,并执行函数XLogInsert()
。 - 函数
XLogInsert()
会将heap_insert()
创建的XLOG记录写入WAL缓冲区LSN_1
处,并将被修改页面的pd_lsn
从LSN_0
更新为LSN_1
。 - 函数
finish_xact_command()
会在该事务被提交时被调用,用于创建该提交动作的XLOG记录,而这里的XLogInsert()
函数会将该记录写入WAL缓冲区LSN_2
处。 - 函数
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记录都会被确保写入存储之中。 - 函数
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 基本目录下的数据库文件和子目录的布局(参考官方文档)
文件 | 描述 |
---|---|
PG_VERSION |
包含PostgreSQL主版本号 |
pg_hba.conf |
控制PosgreSQL客户端认证 |
pg_ident.conf |
控制PostgreSQL用户名映射 |
postgresql.conf |
配置参数 |
postgresql.auto.conf |
存储使用ALTER SYSTEM 修改的配置参数(9.4或更新版本) |
postmaster.opts |
记录服务器上次启动的命令行选项 |
子目录 | 描述 |
---|---|
base/ |
每个数据库对应的子目录存储于此 |
global/ |
数据库集簇范畴的表(例如pg_database ),以及pg_control 文件。 |
pg_commit_ts/ |
事务提交的时间戳数据(9.5及更新版本)。 |
pg_clog/ (9.6-) |
事务提交状态数据(9.6及更老版本),在版本10中被重命名为pg_xact 。CLOG将在5.4节中描述 |
pg_dynshmem/ |
动态共享内存子系统中使用的文件(9.4或更新版本)。 |
pg_logical/ |
逻辑解码的状态数据(9.4或更新版本)。 |
pg_multixact/ |
多事务状态数据 |
pg_notify/ |
LISTEN /NOTIFY 状态数据 |
pg_repslot/ |
复制槽数据(9.4或更新版本)。 |
pg_serial/ |
已提交的可串行化事务相关信息(9.1或更新版本) |
pg_snapshots/ |
导出快照(9.2或更新版本)。 PostgreSQL函数pg_export_snapshot 在此子目录中创建快照信息文件。 |
pg_stat/ |
统计子系统的永久文件 |
pg_stat_tmp/ |
统计子系统的临时文件 |
pg_subtrans/ |
子事务状态数据 |
pg_tblspc/ |
指向表空间的符号链接 |
pg_twophase/ |
两阶段事务(prepared transactions)的状态文件 |
pg_wal/ (10+) |
WAL( Write Ahead Logging)段文件(10或更新版本),从pg_xlog 重命名而来。 |
pg_xact/ (10+) |
事务提交状态数据,(10或更新版本),从pg_clog 重命名而来。CLOG将在5.4节中描述。 |
pg_xlog/ (9.6-) | WAL(Write Ahead Logging) 段文件(9.6及更老版本),它在版本10中被重命名为pg_wal 。 |
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. 堆表文件的页面布局
表的页面包含了三种类型的数据:
-
堆元组(heap tuples) —— 堆元组就是数据记录本身。它们从页面底部开始依序堆叠。第5.2节与第9章会描述元组的内部结构,这一知识对于理解PostgreSQL并发控制与WAL机制是必须的。
-
行指针(line pointer) —— 每个行指针占4个字节,保存着指向堆元组的指针。它们也被称为项目指针(item pointer)。行指针简单地组织为一个数组,扮演了元组索引的角色。每个索引项从1开始依次编号,称为偏移号(offset number)。当向页面中添加新元组时,一个相应的新行指针也会被放入数组中,并指向新添加的元组。
-
首部数据(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 后台进程
进程 | 概述 | 参考 |
---|---|---|
background writer | 本进程负责将共享缓冲池中的脏页逐渐刷入持久化存储中(例如,HDD,SSD)(在9.1及更旧版本中,它还负责处理检查点(checkpoint)) | 8.6 |
checkpointer | 在9.2及更新版本中,该进程负责处理检查点。 | 8.6, 9.7 |
autovacuum launcher | 周期性地启动自动清理工作进程(更准确地说,它向Postgres服务器请求创建自动清理工作进程) | 6.5 |
WAL writer | 本进程周期性地将WAL缓冲区中的WAL数据刷入持久存储中。 | 9.9 |
statistics collector | 本进程负责收集统计信息,用于诸如pg_stat_activity ,pg_stat_database 等系统视图。 |
|
logging collector (logger) | 本进程负责将错误消息写入日志文件。 | |
archiver | 本进程负责将日志归档。 | 9.10 |
这里展示了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 本地内存区域
子区域 | 描述 | 参考 |
---|---|---|
work_mem |
执行器在执行ORDER BY 和DISTINCT 时使用该区域对元组做排序,以及存储归并连接和散列连接中的连接表。 |
第3章 |
maintenance_work_mem |
某些类型的维护操作使用该区域(例如VACUUM ,REINDEX )。 |
6.1 |
temp_buffers |
执行器使用此区域存储临时表。 |
2.2.2 共享内存区域
PostgreSQL服务器启动时会分配共享内存区域。该区域分为几个固定大小的子区域。 表2.3列出了主要的子区域。 详细信息将在后续章节中介绍。
表2.3 共享内存区域
子区域 | 描述 | 参考 |
---|---|---|
shared buffer pool |
PostgreSQL将表和索引中的页面从持久存储加载至此,并直接操作它们。 | 第8章 |
WAL buffer |
为确保服务故障不会导致任何数据丢失,PostgreSQL实现了WAL机制。 WAL数据(也称为XLOG记录)是PostgreSQL中的事务日志;WAL缓冲区是WAL数据在写入持久存储之前的缓冲区。 | 第9章 |
commit log |
提交日志(Commit Log, CLOG) 为并发控制(CC)机制保存了所需的所有事务状态(例如进行中,已提交,已中止等)。 | 5.4 |
除了上面这些,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版本后有了基于多个后台工作进程的并行查询,但大体上来讲,还是每个连接对应一个后端进程。后端进程由五个子系统组成,如下所示:
-
解析器(Parser)
解析器根据SQL语句生成一颗语法解析树(parse tree) 。
-
分析器(Analyzer)
分析器对语法解析树进行语义分析,生成一颗查询树(query tree)。
-
重写器(Rewriter)
重写器按照规则系统中存在的规则,对查询树进行改写。
-
计划器(Planner)
计划器基于查询树,生成一颗执行效率最高的计划树(plan tree)。
-
执行器(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)。总代价是启动代价和运行代价的和;因此只有启动代价和运行代价是单独估计的。
- 启动代价(start-up):在读取到第一条元组前花费的代价,比如索引扫描节点的启动代价就是读取目标表的索引页,取到第一个元组的代价
- 运行代价(run): 获取全部元组的代价
- 总代价(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} $$
前三个代价(即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中的计划器会执行三个处理步骤:
- 执行预处理
- 在所有可能的访问路径中,找出代价最小的访问路径
- 按照代价最小的路径,创建计划树
访问路径(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节中描述。
-
简化目标列表(target list),
LIMIT
子句等;例如,表达式
2+2
会被重写为4
,这是由clauses.c
中eval_const_expressions()
函数负责的。 -
布尔表达式的规范化
例如,
NOT(NOT a)
会被重写为a
-
压平与/或表达式
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 找出代价最小的访问路径
计划器对所有可能的访问路径进行代价估计,然后选择代价最小的那个。具体来说,计划器会执行以下几个步骤:
-
创建一个
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;
-
估计所有可能访问路径的代价,并将访问路径添加至
RelOptInfo
结构中。这一处理过程的细节如下:
- 创建一条路径,估计该路径中顺序扫描的代价,并将其写入路径中。将该路径添加到
RelOptInfo
结构的pathlist
变量中。 - 如果目标表上存在相关的索引,则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价,并将代价写入相应路径中。然后将索引访问路径添加到
pathlist
变量中。 - 如果可以进行位图扫描,则创建一条位图扫描访问路径。估计所有的位图扫描的代价,并将代价写入到路径中。然后将位图扫描路径添加到
pathlist
变量中。
- 创建一条路径,估计该路径中顺序扫描的代价,并将其写入路径中。将该路径添加到
-
从
RelOptInfo
的pathlist
中,找出代价最小的访问路径。 -
如有必要,估计
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中代价最小的路径
-
创建一个
RelOptInfo
结构,将其保存在PlannerInfo
结构的simple_rel_array
字段中。 -
在
RelOptInfo
结构的baserestrictinfo
字段中,添加一条WHERE
子句。WHERE
子句id<300
会经由initsplan.c
中定义的distribute_restrictinfo_to_rels()
函数,添加至列表变量baserestrictinfo
中。另外由于目标表上没有相关索引,RelOptInfo
的indexlist
字段为空。 -
为了满足排序要求,
planner.c
中的standard_qp_callback()
函数会在PlannerInfo
的sor_pathkeys
字段中添加一个pathkey
。Pathkey
是表示路径排序顺序的数据结构。本例因为查询包含一条ORDER BY
子句,且该子句中的列为data
,故data
会被包装为pathkey
,放入列表变量sort_pathkeys
中。 -
创建一个
Path
结构,并使用cost_seqscan
函数估计顺序扫描的代价,并将代价写入Path
中。然后使用pathnode.c
中定义的add_path()
函数,将该路径添加至RelOptInfo
中。如之前所提到过的,
Path
中同时包含启动代价和总代价,都是由cost_seqscan
函数所估计的。
在本例中,因为目标表上没有索引,计划器只估计了顺序扫描的代价,因此最小代价是自动确定的。
图3.11 如何得到例1中代价最小的路径(接图3.10)
-
创建一个新的
RelOptInfo
结构,用于处理ORDER BY
子句。注意新的
RelOptInfo
没有baserestrictinfo
字段,该信息已经被WHERE
子句所持有。 -
创建一个排序路径,并添加到新的
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展示了本例中计划器的处理过程。
-
创建一个
RelOptInfo
结构体 -
在
baserestrictinfo
中添加一个WHERE
子句;并将目标表上的索引(们)添加到indexlist
中。在本例中,
WHERE
子句'id <240'
会被添加至baserestrictinfo
中,而两个索引:tbl_2_pkey
和tbl_2_data_idx
会被添加至RelOptInfo
的列表变量indexlist
中。 -
创建一条路径,估计其顺序扫描代价,并添加到
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;
-
创建一个
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
字段中。 -
创建另一个
IndexPath
,估计另一种索引扫描的代价,并将该IndexPath
添加到RelOptInfo
的pathlist
中。接下来,与
tbl_2_data_idx
相应的IndexPath
会被创建出来,并进行代价估计。本例中tbl_2_data_idx
并没有相关的WHERE
子句;因此其indexclauses
为空。
注意
add_path()
函数并不总是真的会将路径添加到路径列表中。这一操作相当复杂,故这里就省去了具体描述。详细细节可以参考add_path()
函数的注释。
图3.13 如何得到例2中代价最小的路径(接图3.12)
-
创建一个新的
RelOptInfo
结构 -
将代价最小的路径,添加到新
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;
如上所述,计划树包含各式各样的计划节点。PlanNode
是所有计划节点的基类,其他计划节点都会包含PlanNode
结构。比如顺序扫描节点SeqScanNode
,包含一个PlanNode
和一个整型变量scanrelid
。PlanNode
包含14个字段。下面是7个代表性字段:
startup_cost
和total_cost
是该节点对应操作的预估代价。rows
是计划器预计扫描的行数。targetlist
保存了该查询树中目标项的列表。qual
储存了限定条件的列表。lefttree
和righttree
用于添加子节点。
/* ----------------
* 计划节点(Plan Node)
*
* 所有的计划节点都"派生"自Plan结构,将其作为自己的第一个字段。这样确保了当其强制转换为Plan
* 结构时所有东西都能正常工作。(当作为通用参数传入执行器时,节点指针会很频繁地转换为Plan*)
*
* 我们从来不会真的去实例化任何Plan节点,它只是所有Plan类型节点的公共抽象父类。
* ----------------
*/
typedef struct Plan
{
NodeTag type;
/* 计划的预估执行开销 ( 详情见 costsize.c ) */
Cost startup_cost; /* 获取第一条元组前的代价 */
Cost total_cost; /* 获取所有元组的代价 */
/* 计划器对该计划步骤返回结果大小的估计 */
double plan_rows; /* 计划预期产出的行数 */
int plan_width; /* 以字节计的行宽 */
/* 并行查询所需的信息 */
bool parallel_aware; /* 是否涉及到并行逻辑? */
/* 所有计划类型的公有结构化数据 */
int plan_node_id; /* 在整个计划树范围内唯一的标识 */
List *targetlist; /* 该节点需要计算的目标列表 */
List *qual; /* 隐式合取化处理的 限制条件 列表 */
struct Plan *lefttree; /* 输入的查询树 */
struct Plan *righttree;
List *initPlan; /* Init Plan 节点 (无关子查询表达式) */
/* “参数变化驱动”的重扫描 相关的管理信息
* extParam包含着所有外部PARAM_EXEC参数的参数ID列表,这些参数会影响当前计划节点
* 及其子节点。这里不包括该节点initPlans时setParam的相关参数,但会包括其extParams
*
* allParam包含了所有extParam的参数ID列表,以及影响当前节点的参数ID。(即,
* 在initPlans中setParams的参数)。注意这里包含了*所有*会影响本节点的PARAM_EXEC参数
*/
Bitmapset *extParam;
Bitmapset *allParam;
} Plan;
/* ------------
* 扫描节点(Scan nodes)
* ----------- */
typedef unsigned int Index;
typedef struct Scan
{
Plan plan;
Index scanrelid; /* relid 是访问范围表的索引 */
} Scan;
/* ----------------
* 顺序扫描节点
* ---------------- */
typedef Scan SeqScan;
下面是两颗计划树,分别与前一小节中的两个例子对应。
3.3.3.1 例1
第一个例子是3.3.2.1节例1对应的计划树。图3.11所示的代价最小的路径,是由一个排序路径和一个顺序扫描路径组合而成。根路径是排序路径,而其子路径为顺序扫描路径。尽管这里忽略了大量细节,但是从代价最小的路径中生成计划树的过程是显而易见的。在本例中,一个 SortNode
被添加到PlannedStmt
结构中,而SortNode
的左子树上则挂载了一个SeqScanNode
,如图3.15(a)所示。
在SortNode
中,左子树lefttree
指向SeqScanNode
。
在SeqScanNode
中,qual
保存了WHERE
子句:'id<300'
。
typedef struct Sort
{
Plan plan;
int numCols; /* 排序键 列的数目 */
AttrNumber *sortColIdx; /* 它们在目标列表中的位置序号 */
Oid *sortOperators; /* 排序所赖运算符的OID */
Oid *collations; /* collation的OID */
bool *nullsFirst; /* NULLS FIRST/LAST 方向 */
} Sort;
图3.15. 计划树的例子
3.3.3.2 例2
第二个例子是3.3.2.2节例2对应的计划树。其代价最小的路径为索引扫描路径,如图3.14所示。因此计划树由单个IndexScanNode
独立组成,如图3.15(b)所示。
在本例中,WHERE
子句id < 240
是一个访问谓词,它储存在IndexScanNode
的indexqual
字段中。
/* 索引扫描节点 */
typedef struct Scan
{
Plan plan;
Index scanrelid; /* relid 是范围表上的索引ID */
} Scan;
typedef struct IndexScan
{
Scan scan;
Oid indexid; /* 待扫描的索引OID */
List *indexqual; /* 索引限定条件的列表 (通常是OpExprs) */
List *indexqualorig; /* 同上,但使用原始形式 */
List *indexorderby; /* 索引的ORDER BY表达式 */
List *indexorderbyorig; /* 同上,但使用原始形式 */
List *indexorderbyops; /* ORDER BY表达式用到的排序运算符的OID */
ScanDirection indexorderdir; /* 正序扫描还是逆序扫描,或者根本不在乎 */
} IndexScan;
3.4 执行器如何工作
在单表查询的例子中,执行器从计划树中取出计划节点,按照自底向上的顺序进行处理,并调用节点相应的处理函数。
每个计划节点都有相应的函数,用于执行节点对应的操作。这些函数在src/backend/executor
目录中。例如,执行顺序扫描的的函数(SeqScan
)定义于nodeSeqscan.c
中;执行索引扫描的函数(IndexScanNode
)定义在nodeIndexScan.c
中;SortNode
节点对应的排序函数定义在nodeSort.c
中,诸如此类。
当然,理解执行器如何工作的最好方式,就是阅读EXPLAIN
命令的输出。因为PostgreSQL的EXPLAIN
命令几乎就是照着计划树输出的。下面以3.3.3节的例1为例。
testdb=# EXPLAIN SELECT * FROM tbl_1 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_1 (cost=0.00..170.00 rows=300 width=8)
Filter: (id < 300)
(4 rows)
我们可以自底向上阅读EXPLAIN
的结果,来看一看执行器是如何工作的。
第6行:首先,执行器通过nodeSeqscan.c
中定义的函数执行顺序扫描操作。
第4行:然后,执行器通过nodeSort.c
中定义的函数,对顺序扫描的结果进行排序。
临时文件
执行器在处理查询时会使用工作内存(
work_mem
)和临时缓冲区(temp_buffers
),两者都于内存中分配。如果查询无法在内存中完成,就会用到临时文件。使用带有
Analyze
选项的EXPLAIN
,待解释的命令会真正执行,并显示实际结果行数,实际执行时间和实际内存用量。下面是一个具体的例子:testdb=# EXPLAIN ANALYZE SELECT id, data FROM tbl_25m ORDER BY id; QUERY PLAN ---------------------------------------------------------------------- Sort (cost=3944070.01..3945895.01 rows=730000 width=4104) (actual time=885.648..1033.746 rows=730000 loops=1) Sort Key: id Sort Method: external sort Disk: 10000kB -> Seq Scan on tbl_25m (cost=0.00..10531.00 rows=730000 width=4104) (actual time=0.024..102.548 rows=730000 loops=1) Planning time: 1.548 ms Execution time: 1109.571 ms (6 rows)
在第6行,
EXPLAIN
命令显示出执行器使用了10000KB的临时文件。临时文件会被临时创建于
base/pg_tmp
子目录中,并遵循如下命名规则{"pgsql_tmp"} + {创建本文件的Postgres进程PID} . {从0开始的序列号}
比如,临时文件
pgsql_tmp8903.5
是pid
为8903
的postgres
进程创建的第6个临时文件
3.5 连接
PostgreSQL 中支持三种**连接(JOIN)**操作:嵌套循环连接(Nested Loop Join),归并连接(Merge Join) ,散列连接(Hash Join)。在PostgreSQL中,嵌套循环连接与归并连接有几种变体。
在下文中,我们会假设读者已经对这三种操作的基本行为有了解。如果读者对这些概念不熟悉,可以参阅[1, 2]。PostgreSQL支持一种针对数据倾斜的混合散列连接(hybrid hash join),关于这方面的资料不多,因此这里会详细描述该操作。
需要注意的是,这三种**连接方法(join method)**都支持PostgreSQL中所有的连接操作,诸如INNER JOIN
,LEFT/RIGHT OUTER JOIN
,FULL OUTER JOIN
等;但是为了简单起见,这里只关注NATURAL INNER JOIN
。
3.5.1 嵌套循环连接(Nested Loop Join)
嵌套循环连接是最为基础的连接操作,任何**连接条件(join condition)**都可以使用这种连接方式。PostgreSQL支持嵌套循环连接及其五种变体。
3.5.1.1 嵌套循环连接
嵌套循环连接无需任何启动代价,因此: $$ \verb|start-up_cost| = 0 $$ 运行代价与内外表尺寸的乘积成比例;即$\verb|runcost|$是$O(N_{\verb|outer|}× N_{\verb|inner|})$,这里$N_{\verb|outer|}$和$N_{\verb|inner|}$分别是外表和内表的元组条数。更准确的说,$\verb|run_cost|$的定义如下: $$ \begin{equation} \verb|run_cost|=(\verb|cpu_operator_cost|+ \verb|cpu_tuple_cost|)× N_{\verb|outer|}× N_{\verb|inner|} + C_{\verb|inner|}× N_{\verb|outer|}+C_{\verb|outer|} \end{equation} $$ 这里$C_{\verb|outer|}$和$C_{\verb|inner|}$分别是内表和外表顺序扫描的代价;
图3.16 嵌套循环连接
嵌套循环连接的代价总是会被估计,但实际中很少会使用这种连接操作,因为它有几种更高效的变体,下面将会讲到。
3.5.1.2 物化嵌套循环连接
在上面描述的嵌套循环连接中,每当读取一条外表中的元组时,都需要扫描内表中的所有元组。为每条外表元组对内表做全表扫描,这一过程代价高昂,PostgreSQL支持一种物化嵌套循环连接(materialized nested loop join) ,可以减少内表全表扫描的代价。
在运行嵌套循环连接之前,执行器会使用**临时元组存储(temporary tuple storage)**模块对内表进行一次扫描,将内表元组加载到工作内存或临时文件中。在处理内表元组时,临时元组存储比缓冲区管理器更为高效,特别是当所有的元组都能放入工作内存中时。
图 3.17说明了物化嵌套循环连接的处理过程。扫描物化元组在内部被称为重扫描(rescan)。
图3.17 物化嵌套循环连接
临时元组存储
PostgreSQL内部提供了临时元组存储的模块,可用于各种操作:物化表,创建混合散列连接的批次,等等。该模块包含一系列函数,都在
tuplestore.c
中。这些函数用于从工作内存或临时文件读写元组。使用工作内存还是临时文件取决于待存储元组的总数。
下面给出一个具体的例子,并研究一下执行器是如何处理物化嵌套循环连接的计划树并估计其代价的。
testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id;
QUERY PLAN
-----------------------------------------------------------------------
Nested Loop (cost=0.00..750230.50 rows=5000 width=16)
Join Filter: (a.id = b.id)
-> Seq Scan on tbl_a a (cost=0.00..145.00 rows=10000 width=8)
-> Materialize (cost=0.00..98.00 rows=5000 width=8)
-> Seq Scan on tbl_b b (cost=0.00..73.00 rows=5000 width=8)
(5 rows)
上面显示了执行器要进行的操作,执行器对这些计划节点的处理过程如下:
第7行:执行器使用顺序扫描,物化内部表tbl_b
。
第4行:执行器执行嵌套循环连接操作,外表是tbl_a
,内表是物化的tbl_b
。
下面来估算“物化”操作(第7行)与“嵌套循环”(第4行)的代价。假设物化的内部表元组都在工作内存中。
物化(Materialize):
物化操作没有启动代价;因此, $$ \begin{equation} \verb|start-up_cost| = 0 \end{equation} $$ 其运行代价定义如下: $$ \verb|run_cost| = 2 × \verb|cpu_operator_cost| × N_{\verb|inner|}; $$ 因此: $$ \verb|run_cost|=2× 0.0025× 5000=25.0 $$ 此外, $$ \verb|total_cost| = (\verb|start-up_cost|+ \verb|total_cost_of_seq_scan|)+ \verb|run_cost| $$ 因此, $$ \verb|total_cost| = (0.0+73.0)+25.0=98.0 $$ (物化)嵌套循环:
嵌套循环没有启动代价,因此: $$ \verb|start-up_cost|=0 $$ 在估计运行代价之前,先来看一下重扫描的代价,重扫描的代价定义如下: $$ \verb|rescan_cost| = \verb|cpu_operator_cost| × N_{\verb|inner|} $$ 这本例中: $$ \verb|rescan_cost| = (0.0025)× 5000=12.5 $$ 运行代价由以下公式定义: $$ \verb|run_cost| =(\verb|cpu_operator_cost| + \verb|cpu_tuple_cost|)× N_{\verb|inner|}× N_{\verb|outer|} \
- \verb|recan_cost|× (N_{\verb|outer|}-1) + C^{\verb|total|}{\verb|outer|,\verb|seqscan|} + C^{\verb|total|}{\verb|materialize|}, $$ 这里 $C^{\verb|total|}{\verb|outer|,\verb|seqscan|}$代表外部表的全部扫描代价,$C^{\verb|total|}{\verb|materialize|}$代表物化代价;因此 $$ \verb|run_cost| = ( 0.0025 + 0.01 ) × 5000 × 10000 + 12.5 ×(10000−1)+145.0+98.0=750230.5 $$
3.5.1.3 索引嵌套循环连接
如果内表上有索引,且该索引能用于搜索满足连接条件的元组。那么计划器在为外表的每条元组搜索内表中的匹配元组时,会考虑使用索引进行直接搜索,以替代顺序扫描。这种变体叫做索引嵌套循环连接(indexed nested loop join),如图3.18所示。尽管这种变体叫做索引"嵌套循环连接",但该算法基本上只需要在在外表上循环一次,因此连接操作执行起来相当高效。
图3.18 索引嵌套循环连接
下面是索引嵌套循环连接的一个具体例子。
testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=0.29..1935.50 rows=5000 width=16)
-> Seq Scan on tbl_b b (cost=0.00..73.00 rows=5000 width=8)
-> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..0.36 rows=1 width=8)
Index Cond: (id = b.id)
(4 rows)
第6行展示了访问内表中元组的代价。即在内表中查找满足第七行连接条件(id = b.id)
的元组的代价。
在第7行的索引条件(id = b.id)
中,b.id
是连接条件中的外表属性的值。每当顺序扫描外表取回一条元组时,就会依第6行所示的索引搜索路径,查找内表中需要与之连接的元组。换而言之,外表元组的值作为参数传入内表的索引扫描中,索引扫描路径会查找满足连接条件的内表元组。这种索引路径被称为参数化(索引)路径(parameterized (index) path),细节见PostgreSQ源码:backend/optimizer/README
。
该嵌套循环连接的启动代价,等于第6行中索引扫描的代价,因此: $$ \verb|start-up_cost| = 0.285 $$ 索引嵌套循环扫描的总代价由下列公式所定义: $$ \verb|total_cost|= (\verb|cpu_tuple_cost| + C^{\verb|total|}{\verb|inner,parameterized|} )× N{\verb|outer|}+C^{\verb|run|}{\verb|outer,seqscan|} $$ 这里$C^{\verb|total|}{\verb|inner,parameterized|}$是参数化内表索引扫描的整体代价,
在本例中: $$ \verb|total_cost|=(0.01+0.3625)× 5000 + 73.0 = 1935.5 $$ 而运行代价为: $$ \verb|run_cost| = 1935.5-0.285=1935.215 $$ 如上所示,索引嵌套扫描的整体代价是$O(N_{\verb|outer|})$。
3.5.1.4 其他变体
如果在外表上存在一个与连接条件相关的索引,那么在外表上也可以以索引扫描替代顺序扫描。特别是,当WHERE
子句中的访问谓词可以使用该索引时,能缩小外表上的搜索范围,嵌套循环连接的代价可能会急剧减少。
当使用外表索引扫描时,PostgreSQL支持三种嵌套循环连接的变体,如图3.19所示。
图3.19 嵌套循环连接的三种变体,使用外表索引扫描
这些连接的EXPLAIN
结果如下:
-
使用外表索引扫描的嵌套循环连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_mergejoin TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id = 500; QUERY PLAN ------------------------------------------------------------------------------- Nested Loop (cost=0.29..93.81 rows=1 width=16) -> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..8.30 rows=1 width=8) Index Cond: (id = 500) -> Seq Scan on tbl_b b (cost=0.00..85.50 rows=1 width=8) Filter: (id = 500) (5 rows)
-
使用外表索引扫描的物化嵌套循环连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_mergejoin TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id < 40 AND b.id < 10; QUERY PLAN ------------------------------------------------------------------------------- Nested Loop (cost=0.29..99.76 rows=1 width=16) Join Filter: (c.id = b.id) -> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..8.97 rows=39 width=8) Index Cond: (id < 40) -> Materialize (cost=0.00..85.55 rows=9 width=8) -> Seq Scan on tbl_b b (cost=0.00..85.50 rows=9 width=8) Filter: (id < 10) (7 rows)
-
使用外表索引扫描的索引嵌套循环连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_mergejoin TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_d AS d WHERE a.id = d.id AND a.id < 40; QUERY PLAN ------------------------------------------------------------------------------- Nested Loop (cost=0.57..173.06 rows=20 width=16) -> Index Scan using tbl_a_pkey on tbl_a a (cost=0.29..8.97 rows=39 width=8) Index Cond: (id < 40) -> Index Scan using tbl_d_pkey on tbl_d d (cost=0.28..4.20 rows=1 width=8) Index Cond: (id = a.id) (5 rows)
3.5.2 归并连接(Merge Join)
与嵌套循环连接不同的是,**归并连接(Merge Join)**只能用于自然连接与等值连接。
函数initial_cost_mergejoin()
和final_cost_mergejoin()
用于估计归并连接的代价。
因为精确估计归并连接的代价非常复杂,因此这里略过不提,只会说明归并连接算法的工作流程。归并连接的启动成本是内表与外表排序成本之和,因此其启动成本为: $$ O(N_{\verb|outer|} \log_2(N_{\verb|outer|}) + N_{\verb|inner|} \log_2(N_{\verb|inner|})) $$ 这里$N_{\verb|outer|}$和$N_{\verb|inner|}$是分别是外表和内表的元组条数,而运行代价是$O(N_{\verb|outer|}+N_{\verb|inner|})$。
与嵌套循环连接类似,归并连接在PostgreSQL中有4种变体。
3.5.2.1 归并连接
图3.20是归并连接的概念示意图。
图3.20 归并连接
如果所有元组都可以存储在内存中,那么排序操作就能在内存中进行,否则会使用临时文件。
下面是一个具体的例子,一个归并连接的EXPLAIN
输出如下所示。
# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND b.id < 1000;
QUERY PLAN
-------------------------------------------------------------------------
Merge Join (cost=944.71..984.71 rows=1000 width=16)
Merge Cond: (a.id = b.id)
-> Sort (cost=809.39..834.39 rows=10000 width=8)
Sort Key: a.id
-> Seq Scan on tbl_a a (cost=0.00..145.00 rows=10000 width=8)
-> Sort (cost=135.33..137.83 rows=1000 width=8)
Sort Key: b.id
-> Seq Scan on tbl_b b (cost=0.00..85.50 rows=1000 width=8)
Filter: (id < 1000)
(9 rows)
- 第9行:执行器对内表
tbl_b
进行排序,使用顺序扫描(第11行)。 - 第6行:执行器对外表
tbl_a
进行排序,使用顺序扫描(第8行)。 - 第4行:执行器执行归并连接操作,外表是排好序的
tbl_a
,内表是排好序的tbl_b
。
3.5.2.2 物化归并连接
与嵌套循环连接类似,归并连接还支持物化归并连接(Materialized Merge Join),物化内表,使内表扫描更为高效。
图3.21 物化归并连接
这里是物化归并连接的EXPLAIN
结果,很容易发现,与普通归并连接的差异是第9行:Materialize
。
testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id;
QUERY PLAN
---------------------------------------------------------------------------------
Merge Join (cost=10466.08..10578.58 rows=5000 width=2064)
Merge Cond: (a.id = b.id)
-> Sort (cost=6708.39..6733.39 rows=10000 width=1032)
Sort Key: a.id
-> Seq Scan on tbl_a a (cost=0.00..1529.00 rows=10000 width=1032)
-> Materialize (cost=3757.69..3782.69 rows=5000 width=1032)
-> Sort (cost=3757.69..3770.19 rows=5000 width=1032)
Sort Key: b.id
-> Seq Scan on tbl_b b (cost=0.00..1193.00 rows=5000 width=1032)
(9 rows)
- 第10行:执行器对内表
tbl_b
进行排序,使用顺序扫描(第12行)。 - 第9行:执行器对
tbl_b
排好序的结果进行物化。 - 第6行:执行器对外表
tbl_a
进行排序,使用顺序扫描(第8行)。 - 第4行:执行器执行归并连接操作,外表是排好序的
tbl_a
,内表是物化的排好序的tbl_b
。
3.5.2.3 其他变体
与嵌套循环连接类似,当外表上可以进行索引扫描时,归并连接也存在相应的变体。
图3.22 归并连接的三种变体,使用外表索引扫描
这些连接的EXPLAIN
结果如下。
-
使用外表索引扫描的归并连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_nestloop TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND b.id < 1000; QUERY PLAN ------------------------------------------------------------------------------ Merge Join (cost=135.61..322.11 rows=1000 width=16) Merge Cond: (c.id = b.id) -> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..318.29 rows=10000 width=8) -> Sort (cost=135.33..137.83 rows=1000 width=8) Sort Key: b.id -> Seq Scan on tbl_b b (cost=0.00..85.50 rows=1000 width=8) Filter: (id < 1000) (7 rows)
-
使用外表索引扫描的物化归并连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_nestloop TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND b.id < 4500; QUERY PLAN ------------------------------------------------------------------------------- Merge Join (cost=421.84..672.09 rows=4500 width=16) Merge Cond: (c.id = b.id) -> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..318.29 rows=10000 width=8) -> Materialize (cost=421.55..444.05 rows=4500 width=8) -> Sort (cost=421.55..432.80 rows=4500 width=8) Sort Key: b.id -> Seq Scan on tbl_b b (cost=0.00..85.50 rows=4500 width=8) Filter: (id < 4500) (8 rows)
-
使用外表索引扫描的索引归并连接
testdb=# SET enable_hashjoin TO off; SET testdb=# SET enable_nestloop TO off; SET testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_d AS d WHERE c.id = d.id AND d.id < 1000; QUERY PLAN ------------------------------------------------------------------------------- Merge Join (cost=0.57..226.07 rows=1000 width=16) Merge Cond: (c.id = d.id) -> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..318.29 rows=10000 width=8) -> Index Scan using tbl_d_pkey on tbl_d d (cost=0.28..41.78 rows=1000 width=8) Index Cond: (id < 1000) (5 rows)
3.5.3 散列连接(Hash Join)
与归并连接类似,**散列连接(Hash Join)**只能用于自然连接与等值连接。
PostgreSQL中的散列连接的行为因表的大小而异。 如果目标表足够小(确切地讲,内表大小不超过工作内存的25%),那么散列连接就是简单的两阶段内存散列连接(two-phase in-memory hash join) ; 否则,将会使用带倾斜批次的混合散列连接(hybrid hash join)。
本小节将介绍PostgreSQL中这两种散列连接的执行过程。
这里省略了代价估算的部分,因为它很复杂。粗略来说,假设向散列表插入与搜索时没有遇到冲突,那么启动和运行成本复杂度都是$O(N_{\verb|outer|} + N_{\verb|inner|})$。
3.5.3.1 内存散列连接
下面将描述内存中的散列连接。
内存中的散列连接是在work_mem
中处理的,在PostgreSQL中,散列表区域被称作处理批次(batch)。 一个处理批次会有多个散列槽(hash slots),内部称其为桶(buckets),桶的数量由nodeHash.c
中定义的ExecChooseHashTableSize()
函数所确定。 桶的数量总是2的整数次幂。
内存散列连接有两个阶段:**构建(build)阶段和探测(probe)**阶段。 在构建阶段,内表中的所有元组都会被插入到batch中;在探测阶段,每条外表元组都会与处理批次中的内表元组比较,如果满足连接条件,则将两条元组连接起来。
为了理解该操作的过程,下面是一个具体的例子。 假设该查询中的连接操作使用散列连接。
SELECT * FROM tbl_outer AS outer, tbl_inner AS inner WHERE inner.attr1 = outer.attr2;
散列连接的过程如图3.23和3.24所示。
图3.23 内存散列连接的构建阶段
-
在工作内存上创建一个处理批次。
在本例中,处理批次有八个桶;即桶的数量是2的3次方。
-
将内表的第一个元组插入批次的相应的桶中。
具体过程如下:
-
找出元组中涉及连接条件的属性,计算其散列键。
在本例中,因为
WHERE
子句是inner.attr1 = outer.attr2
,因此内置的散列函数会对第一条元组的属性attr1
取散列值,用作散列键。 -
将第一条元组插入散列键相应的桶中。
假设第一条元组的散列键以二进制记法表示为
0x000 ... 001
,即其末三**位(bit)**为001
。 在这种情况下,该元组会被插入到键为001
的桶中。
在本文中,构建处理批次的插入操作会用运算符 ⊕ 表示。
-
-
插入内表中的其余元组。
图3.24. 内存散列连接的探测阶段
-
依外表的第一条元组进行探测。
详情如下:
-
找出第一条外表元组中涉及连接条件的属性,计算其散列键。
在这个例子中,假设第一条元组的属性
attr2
的散列键是0x000 ... 100
,即其末三**位(bit)**为100
。 最后三位是100
。 -
将外表中第一条元组与批次中的内表元组进行比较。如果满足连接条件,则连接内外表元组。
因为第一个元组的散列键的末三位为
100
,执行器找出键为100
的桶中的所有内表元组,并对内外表元组两侧相应的属性进行比较。这些属性由连接条件(在WHERE
子句中)所指明。如果满足连接条件,执行器会连接外表中的第一条元组与内表中的相应元组。如果不满足则执行器不做任何事情。
在本例中,键为
100
的桶中有Tuple_C
。如果Tuple_C
的attr1
等于第一条元组(Tuple_W
)的attr2
,则Tuple_C
和Tuple_W
将被连接,并保存至内存或临时文件中。
在本文中,处理批次的探测操作用运算符 ⊗ 表示。
-
-
依次对外表中的其他元组执行探测。
3.5.3.2 带倾斜的混合散列连接
当内表的元组无法全部存储在工作内存中的单个处理批次时,PostgreSQL使用带倾斜批次的混合散列连接算法,该算法是混合散列连接的一种变体。
首先,这里会描述混合散列连接的基本概念。在第一个构建和探测阶段,PostgreSQL准备多个批次。与桶的数目类似,处理批次的数目由函数ExecChooseHashTableSize()
决定,也总是2的整数次幂。工作内存中只会分配一个处理批次,而其他批次作都以临时文件的形式创建。属于这些批次的元组将通过临时元组存储功能,被写入到相应的文件中。
图3.25说明了如何将元组存储在四个($ 2 ^ 2 $)处理批次中。在本例中元组散列键的最后五个比特位决定了元组所属的批次与桶,因为处理批次的数量为$2^2$,而桶的数量为$2^3$,因此需要5个比特位来表示,其中前两位决定了元组所属的批次,而后三位决定了元组在该批次中所属的桶。例如:Batch_0
存储着散列键介于$\textcolor{red}{00}000$与$\textcolor{red}{00}111$的元组;而Batch_1
存储着散列键介于$\textcolor{red}{01}000$与$\textcolor{red}{01}111$的元组,依此类推。
图3.25 混合散列连接中的多个处理批次
在混合散列连接中,构建与探测阶段的执行次数与处理批次的数目相同,因为内外表元组都被存至相同数量的处理批次中。在第一轮构建与探测阶段中,除了处理第一个处理批次,还会创建所有的处理批次。另一方面,第二轮及后续的处理批次都需要读写临时文件,这属于代价巨大的操作。因此PostgreSQL还准备了一个名为skew的特殊处理批次,即倾斜批次,以便在第一轮中高效处理尽可能多的元组。
这个特殊的倾斜批次中的内表元组在连接条件内表一侧属性上的取值,会选用外表连接属性上的高频值(MCV)。因此在第一轮处理中能与外表中尽可能多的元组相连接。这种解释不太好理解,因此下面给出了一个具体的例子。
假设有两个表:客户表customers
与购买历史表purchase_history
。customers
由两个属性组成:name
和address
; purchase_history
由两个属性组成:customer_name
和buying_item
。customers
有10,000行,而purchase_history
表有1,000,000行。前10%的客户进行了70%的购买。
理解了这些假设,让我们考虑当执行以下查询时,带倾斜的混合散列连接的第一轮是如何执行的。
SELECT * FROM customers AS c, purchase_history AS h
WHERE c.name = h.customer_name;
如果customers
是内表,而purchase_history
是外表,则PostgreSQL将使用purchase_history
表的高频值值,将前10%的customers
元组存储于倾斜批次中。 请注意这里引用的是外表上的高频值,而插入倾斜批次的是内表元组。 在第一轮的探测阶段,外表(purchase_history
)中70%的元组将与倾斜批次中存储的元组相连接。 因此,外表分布越是不均匀,第一轮中越是可以处理尽可能多的元组。
接下来会介绍带倾斜批次的混合散列连接的工作原理,如图3.26至3.29所示。
图3.26 混合散列连接的构建阶段的第一轮
-
在工作内存中创建一个处理批次,以及一个倾斜批次。
-
创建处理批次相应的临时文件,用于存储排好序的内表元组。
在本例中,内表被分割为四个批次,因此创建了三个批次文件。
-
为内表的第一条元组执行构建操作。
细节如下:
-
如果第一条元组应当插入倾斜批次中,则将其插入倾斜批次;否则继续下一步。
在该例中,如果第一条元组属于前10%的客户,则将其插入到倾斜批次中。
-
计算第一条元组的散列键,然后将其插入相应的处理批次。
-
-
对内表其余元组依次执行构建操作。
图3.27 混合散列连接,探测阶段第一轮
-
创建临时处理批次文件,用于外表排序。
-
为外表的第一条元组执行探测操作,如果外表第一条元组上相应字段取值为MCV,则在倾斜批次上进行探测,否则进行第七步。
在本例中,如果第一条元组是前10%客户的购买数据,则它会与倾斜批次中的内表元组进行比较。
-
为外表的第一条元组执行探测操作。
操作的内容取决于该元组散列键的取值。如果该元组属于
Batch_0
则直接完成探测操作;否则将其插入相应的外表处理批次中。 -
为外表的其余元组执行探测操作。
注意在本例中,外表中70%的元组已经在第一轮中的倾斜批次中处理了。
图3.28 构建阶段与探测阶段,第二轮
-
移除倾斜批次与
Batch_0
,为下一轮处理批次腾地方。 -
为批次文件
batch_1_in
中的内表元组执行构建操作。 -
为批次文件
batch_1_out
中的外表元组依次执行探测操作。
图3.29 构建阶段与探测阶段,第三轮及后续
-
为批次文件
batch_2_in
与batch_2_out
执行构建操作与探测操作。 -
为批次文件
batch_3_in
与batch_3_out
执行构建操作与探测操作。
3.5.4 连接访问路径与连接节点
3.5.4.1 连接访问路径
嵌套循环连接的访问路径由JoinPath
结构表示,其他连接访问路径,诸如MergePath
与HashPath
都基于其实现。
下图列出了所有的连接访问路径,细节略过不提。
图3.30 Join访问路径
typedef JoinPath NestPath;
typedef enum JoinType
{
/* 根据SQL JOIN语法确定的标准连接种类,解析器只允许输出这几种取值。
* (例如JoinExpr节点) */
JOIN_INNER, /* 仅包含匹配的元组对 */
JOIN_LEFT, /* 匹配元组对 + 未匹配的左表元组 */
JOIN_FULL, /* 匹配元组对 + 未匹配的左右表元组 */
JOIN_RIGHT, /* 匹配元组对 + 未匹配的右表元组 */
/* 关系理论中的半连接(semijoin)与否定半连接(anti-semijoin)并没有用SQL JOIN
* 语法来表示,而是用另一种风格标准来表示(举个例子,EXISTS)。计划器会认出这些情景
* 并将其转换为连接。因此计划器与执行器必须支持这几种取值。注意:对于JOIN_SEMI的
* 输出而言,连接到哪一条右表元组是不确定的。而对于JOIN_ANTI的输出而言,会保证使用
* 空值进行行扩展。*/
JOIN_SEMI, /* 左表元组的一份拷贝,如果该元组有相应匹配 */
JOIN_ANTI, /* 右表元组的一份拷贝,如果该元组有相应匹配 */
/* 这几种代码用于计划器内部,执行器并不支持。(其实大多数时候计划器也不会用) */
JOIN_UNIQUE_OUTER, /* 左表路径必须是UNIQUE的 */
JOIN_UNIQUE_INNER /* 右表路径必须是UNIQUE的 */
} JoinType;
typedef struct JoinPath
{
Path path;
JoinType jointype;
Path *outerjoinpath; /* 连接外表一侧的路径 */
Path *innerjoinpath; /* 连接内表一侧的路径 */
List *joinrestrictinfo; /* 连接所适用的限制信息 */
/* 参考RelOptInfo与ParamPathInfo才能理解为什么JoinPath需要有joinrestrictinfo
* 且不能合并到RelOptInfo中。 */
} JoinPath;
typedef struct MergePath
{
JoinPath jpath;
List *path_mergeclauses; /* 归并所需的连接子句 */
List *outersortkeys; /* 用于外表显式排序的键,如果存在 */
List *innersortkeys; /* 用于内表显式排序的键,如果存在 */
bool materialize_inner; /* 为内表执行物化过程? */
} MergePath;
3.5.4.2 连接节点
本小节列出了三种连接节点:NestedLoopNode
,MergeJoinNode
和HashJoinNode
,它们都基于JoinNode
实现,细节略过不提。
/* ----------------
* 连接节点
*
* jointype: 连接左右子树元组的规则
* joinqual: 来自 JOIN/ON 或 JOIN/USING 的连接限定条件
* (plan.qual 包含了来自WHERE子句的条件)
*
* 当jointype为INNER时,joinqual 与 plan.qual 在语义上可以互换。对于OUTER而言这两者
* 则无法互换;只有joinqual会被用于匹配判定,以及是否需要生成空值扩展的元组。
* (但 plan.qual 仍然会在实际返回一条元组前生效。)
* 对于外连接而言,只有joinquals能被用于归并连接或散列连接的连接条件。
* ----------------
*/
typedef struct Join
{
Plan plan;
JoinType jointype;
List *joinqual; /* 连接条件 (除 plan.qual 外) */
} Join;
/* ----------------
* 嵌套循环连接节点
*
* nestParams的列表标识出了执行器所需的参数,这些参数从外表子计划中的当前行获取,
* 并传入内表子计划中用于执行。当前我们限制这些值为简单的Vars,但也许某一天这一限制
* 会放松。(注意在创建执行计划期间,paramval实际上可能是一个PlaceHolderVar表达式;
* 但当其进入执行器时,它必须转换为varno为OUTER_VAR的Var。)
* ----------------*/
typedef struct NestLoop
{
Join join;
List *nestParams; /* NestLoopParam 节点的列表*/
} NestLoop;
typedef struct NestLoopParam
{
NodeTag type;
int paramno; /* 需要配置的PARAM_EXEC参数数量 */
Var *paramval; /* 需要赋值给Param的外表变量 */
} NestLoopParam;
/* ----------------
* 归并连接节点
*
* 待归并列上期待的顺序是通过一个btree运算符族的OID,一个排序规则的OID,一个方向字段
* (BTLessStrategyNumber 或 * BTGreaterStrategyNumber),以及一个 NULL FIRST
* 标记位描述的。注意归并语句的两侧可能是不同的数据类型,但它们会按照共同的运算符族与排序
* 规则,以同样的方式排序。每个归并子句中的算子必须为相应运算符族中的等值运算。
* ---------------- */
typedef struct MergeJoin
{
Join join;
List *mergeclauses; /* mergeclauses 是一颗表达式树 */
/* 这些字段都是数组,但与mergeclauses列表有着同样的长度: */
Oid *mergeFamilies; /* B树运算符族的OID列表,每条子句一个 */
Oid *mergeCollations; /* 排序规则的OID列表,每条子句一个 */
int *mergeStrategies; /* 顺序(ASC 或 DESC)的列表,每条子句一个 */
bool *mergeNullsFirst; /* 空值顺序,每条子句一个 */
} MergeJoin;
/* ----------------
* 散列连接节点
* ---------------- */
typedef struct HashJoin
{
Join join;
List *hashclauses;
} HashJoin;
3.6 创建多表查询计划树
本节将说明多表查询计划树的创建过程。
3.6.1 预处理
预处理由planner.c
中定义的subquery_planner()
函数执行。第3.3.1节已经描述了单表查询的预处理。本节将描述多表查询的预处理;尽管这块内容很多,但这里只会挑其中一部分来讲。
-
对CTE进行计划与转换
如果存在
WITH
列表,计划器就会通过SS_process_ctes()
函数对每个WITH
查询进行处理。 -
上拉子查询
如果
FROM
子句带有一个子查询,且该子查询没用用到GROUP BY
,HAVING
,ORDER BY
,LIMIT
和DISTINCT
,INTERSECT
或EXCEPT
,那么计划器会使用pull_up_subqueries()
函数将其转换为连接形式。例如下面一个FROM
子句含子查询的查询就可以被转换为自然连接查询。自不必说,这种转换是在查询树上进行的。# SELECT * FROM tbl_a AS a, (SELECT * FROM tbl_b) as b WHERE a.id = b.id; ↓ # SELECT * FROM tbl_a AS a, tbl_b as b WHERE a.id = b.id;
-
将外连接转为内连接
如果可能的话,计划器会将
OUTER JOIN
查询转换为INNER JOIN
查询。
3.6.2 获取代价最小的路径
为了获取最佳计划树,计划器必须考虑各个索引与各种连接方法之间的所有可能组合。 如果表的数量超过某个水平,该过程的代价就会因为组合爆炸而变得非常昂贵,以至于根本不可行。
幸运的是,如果表的数量小于12张,计划器可以使用动态规划来获取最佳计划; 否则计划器会使用遗传算法。详情如下:
基因查询优化器
当执行一个多表连接查询时,大量时间耗费在了优化查询计划上。 为了应对这种情况,PostgreSQL实现了一个有趣的功能:基因查询优化器。 这种近似算法能在合理时间内确定一个合理的计划。 因此在查询优化阶段,如果参与连接的表数量超过参数
geqo_threshold
指定的阈值(默认值为12),PostgreSQL将使用遗传算法来生成查询计划。
使用动态规划确定最佳计划树的过程,其步骤如下:
-
第一层
获得每张表上代价最小的路径,代价最小的路径存储在表相应的
RelOptInfo
结构中。 -
第二层
从所有表中选择两个表,为每种组合找出代价最低的路径。
举个例子,如果总共有两张表,表
A
与表B
,则表A
和B
表连接的各种路径中,代价最小的那条即为最终想要的答案。在下文中,两个表的RelOptInfo
记做${A,B}$。如果有三个表,则需要获取${A,B}, {A,C},{B,C}$三种组合里各自代价最小的路径。
-
第三层及其后
继续进行同样的处理,直到层级等于表数量。
通过这种方式,在每个层级都能解决最小代价问题的一部分,且其结果能被更高层级的计算复用,从而使代价最小的计划树能够被高效地计算出来。
图3.31 如何使用动态规划获取代价最小的访问路径
接下来会针对下面的查询,解释计划器是如何获取代价最小的计划的。
testdb=# \d tbl_a
Table "public.tbl_a"
Column | Type | Modifiers
--------+---------+-----------
id | integer | not null
data | integer |
Indexes:
"tbl_a_pkey" PRIMARY KEY, btree (id)
testdb=# \d tbl_b
Table "public.tbl_b"
Column | Type | Modifiers
--------+---------+-----------
id | integer |
data | integer |
testdb=# SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND b.data < 400;
3.6.2.1 第一层的处理
在第一层中,计划器会为查询中涉及的关系创建相应的RelOptInfo
结构,并估计每个关系上的最小代价。 在这一步中,RelOptInfo
结构会被添加至该查询对应PlannerInfo
的simple_rel_arrey
数组字段中。
图3.32 第一层处理后的PlannerInfo
与RelOptInfo
表tbl_a
的RelOptInfo
有三条访问路径,它们被添加至RelOptInfo
的路径列表中。这三条路径分别被三个指针所链接,即三个指向代价最小路径的指针:启动代价最小的路径,总代价最小的路径,参数化代价最小的路径。 启动代价最小的路径与总代价最小的路径涵义显而易见,因此,这里只会说一下参数化索引扫描代价最小的路径(cheapest parameterized index scan path)。
如3.5.1.3节所述,计划器会考虑为索引嵌套循环连接使用参数化路径(parameterized path)(极少数情况下也会用于带外表索引扫描的索引化归并连接)。参数化索引扫描代价最小的路径,就是所有参数化路径中代价最小的那个。
表tbl_b
的RelOptInfo
仅有顺序扫描访问路径,因为tbl_b
上没有相关索引。
3.6.2.2 第二层的处理
在第二层中,计划器会在PlannerInfo
的join_rel_list
字段中创建一个RelOptInfo
结构。 然后估计所有可能连接路径的代价,并且选择代价最小的那条访问路径。 RelOptInfo
会将最佳访问路径作为总代价最小的路径, 如图3.33所示。
图3.33 第二层处理后的PlannerInfo
和RelOptInfo
表3.1展示了本例中连接访问路径的所有组合。本例中查询的连接类型为等值连接(equi-join),因而对全部三种连接算法进行评估。 为方便起见,这里引入了一些有关访问路径的符号:
SeqScanPath(table)
表示表table
上的顺序扫描路径。Materialized -> SeqScanPath(table)
表示表table
上的物化顺序扫描路径。IndexScanPath(table,attribute)
表示按表table
中属性attribute
上的索引扫描路径。ParameterizedIndexScanPath(table,attribute1,attribute2)
表示表table
中属性attribute1
上的参数化索引路径,并使用外表上的属性attribute2
参数化。
表 3.1 此示例中的所有连接访问路径组合
嵌套循环连接
外表路径 | 内表路径 | 备注 |
---|---|---|
SeqScanPath(tbl_a) |
SeqScanPath(tbl_b) |
|
SeqScanPath(tbl_a) |
Materialized -> SeqScanPath(tbl_b) |
物化嵌套循环链接 |
IndexScanPath(tbl_a,id) |
SeqScanPath(tbl_b) |
嵌套循环连接,走外表索引 |
IndexScanPath(tbl_a,id) |
Materialized -> SeqScanPath(tbl_b) |
物化嵌套循环连接,走外表索引 |
SeqScanPath(tbl_b) |
SeqScanPath(tbl_a) |
|
SeqScanPath(tbl_b) |
Materialized -> SeqScanPath(tbl_a) |
物化嵌套循环连接 |
SeqScanPath(tbl_b) |
ParametalizedIndexScanPath(tbl_a, id, tbl_b.id) |
索引嵌套循环连接 |
归并连接
外表路径 | 内表路径 | 备注 |
---|---|---|
SeqScanPath(tbl_a) |
SeqScanPath(tbl_b) |
|
IndexScanPath(tbl_a,id) |
SeqScanPath(tbl_b) |
用外表索引做归并连接 |
SeqScanPath(tbl_b) |
SeqScanPath(tbl_a) |
哈希连接
外表路径 | 内表路径 | 备注 |
---|---|---|
SeqScanPath(tbl_a) |
SeqScanPath(tbl_b) |
|
SeqScanPath(tbl_b) |
SeqScanPath(tbl_a) |
例如在嵌套循环连接的部分总共评估了七条连接路径。 第一条表示在外表tbl_a
和内表tbl_b
上都使用顺序扫描路径;第二条表示在外表tbl_a
上使用路径顺序扫描路径,而在内表tbl_b
上使用物化顺序扫描路径,诸如此类。
计划器最终从估计的连接访问路径中选择代价最小的那条,并且将其添加至RelOptInfo{tbl_a,tbl_b}
的路径列表中,如图3.33所示。
在本例中,如下面EXPLAIN
的结果所示,计划器选择了在内表tbl_b
和外表tbl_c
上进行散列连接。
testdb=# EXPLAIN SELECT * FROM tbl_b AS b, tbl_c AS c WHERE c.id = b.id AND b.data < 400;
QUERY PLAN
----------------------------------------------------------------------
Hash Join (cost=90.50..277.00 rows=400 width=16)
Hash Cond: (c.id = b.id)
-> Seq Scan on tbl_c c (cost=0.00..145.00 rows=10000 width=8)
-> Hash (cost=85.50..85.50 rows=400 width=8)
-> Seq Scan on tbl_b b (cost=0.00..85.50 rows=400 width=8)
Filter: (data < 400)
(6 rows)
3.6.3 获取三表查询代价最小的路径
涉及三个表的查询,其代价最小的路径的获取过程如下所示:
testdb=# \d tbl_a
Table "public.tbl_a"
Column | Type | Modifiers
--------+---------+-----------
id | integer |
data | integer |
testdb=# \d tbl_b
Table "public.tbl_b"
Column | Type | Modifiers
--------+---------+-----------
id | integer |
data | integer |
testdb=# \d tbl_c
Table "public.tbl_c"
Column | Type | Modifiers
--------+---------+-----------
id | integer | not null
data | integer |
Indexes:
"tbl_c_pkey" PRIMARY KEY, btree (id)
testdb=# SELECT * FROM tbl_a AS a, tbl_b AS b, tbl_c AS c
testdb-# WHERE a.id = b.id AND b.id = c.id AND a.data < 40;
-
第一层:
计划器估计所有表上各自开销最小的路径,并将该信息存储在表相应的
RelOptInfos
结构{tbl_a}
,{tbl_b}
,{tbl_c}
中。 -
第二层:
计划器从三个表中选出两个,列出所有组合,分别评估每种组合里代价最小的路径。然后,规划器将信息存储在组合相应的
RelOptInfos
结构中:{tbl_a,tbl_b}
,{tbl_b,tbl_c}
和{tbl_a,tbl_c}
中。 -
第三层:
计划器根据所有已获取的
RelOptInfos
,选择代价最小的路径。更确切地说,计划器会考虑三种RelOptInfos
组合:{tbl_a,{tbl_b,tbl_c}}
,{tbl_b,{tbl_a,tbl_c}}
和{tbl_c,{tbl_a,tbl_b}}
,而{tbl_a,tbl_b,tbl_c}
如下所示:
$$ \begin{equation} {\verb|tbl_a|,\verb|tbl_b|,\verb|tbl_c|} = \ \mathrm{min}({\verb|tbl_a|,{\verb|tbl_b|,\verb|tbl_c|}}, {\verb|tbl_b|,{\verb|tbl_a|,\verb|tbl_c|}}, {\verb|tbl_c|,{\verb|tbl_a|,\verb|tbl_b|}}). \end{equation} $$
计划器会估算这里面所有可能连接路径的代价。
在处理{tbl_c,{tbl_a,tbl_b}}
对应的RelOptInfo
时,计划器会估计tbl_c
和{tbl_a,tbl_b}
连接代价最小的路径。本例中{tbl_a,tbl_b}
已经选定为内表为tbl_a
且外表为tbl_b
的散列连接。如先前小节所述,在估计时三种连接算法及其变体都会被评估,即嵌套循环连接及其变体,归并连接及其变体,散列连接及其变体。
计划器以同样的方式处理{tbl_a,{tbl_b,tbl_c}}
与{tbl_b,{tbl_a,tbl_c}}
对应的RelOptInfo
,并最终从所有估好的路径中选择代价最小的访问路径。
该查询的EXPLAIN
命令结果如下所示:
最外层的连接是索引嵌套循环连接(第5行),第13行显示了内表上的参数化索引扫描,外表则是一个散列连接的结果该散列连接的内表是tbl_a
,外表是tbl_b
(第7-12行)。 因此,执行程序首先执行tbl_a
和tbl_b
上的散列连接,再执行索引嵌套循环连接。
参考文献
- [1] Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, “Database System Concepts”, McGraw-Hill Education, ISBN-13: 978-0073523323
- [2] Thomas M. Connolly, and Carolyn E. Begg, “Database Systems”, Pearson, ISBN-13: 978-0321523068
第四章 外部数据包装器
本章将介绍一种相当实用,而且很有趣的特性:外部数据包装器(Foreign Data Wrapper FDW)。
4.1 外部数据包装器(FDW)
2003年,SQL标准中添加了一个访问远程数据的规范,称为SQL外部数据管理(SQL/MED)。PostgreSQL在9.1版本开发出了FDW,实现了一部分SQL/MED中的特性。
在SQL/MED中,远程服务器上的表被称为外部表(Foreign Table)。 PostgreSQL的外部数据包装器(FDW) 使用与本地表类似的方式,通过SQL/MED来管理外部表。
图4.1 FDW的基本概念
安装完必要的扩展并配置妥当后,就可以访问远程服务器上的外部表了。 例如假设有两个远程服务器分别名为postgresql
和mysql
,它们上面分别有两张表:foreign_pg_tbl
和foreign_my_tbl
。 在本例中,可以在本地服务器上执行SELECT
查询以访问外部表,如下所示。
localdb=# -- foreign_pg_tbl 在远程postgresql服务器上
localdb-# SELECT count(*) FROM foreign_pg_tbl;
count
-------
20000
localdb=# -- foreign_my_tbl 在远程mysql服务器上
localdb-# SELECT count(*) FROM foreign_my_tbl;
count
-------
10000
此外还可以在本地连接来自不同服务器中的外部表。
localdb=# SELECT count(*) FROM foreign_pg_tbl AS p, foreign_my_tbl AS m WHERE p.id = m.id;
count
-------
10000
Postgres wiki中列出了很多现有的FDW扩展。但只有postgres_fdw
与file_fdw
是由官方PostgreSQL全球开发组维护的。postgres_fdw
可用于访问远程PostgreSQL服务器。
以下部分将详细介绍PostgreSQL的FDW。 4.1.1节为概述,4.1.2节介绍了postgres_fdw
扩展的工作方式。
Citus
Citus是由citusdata.com开发的开源PostgreSQL扩展,它能创建用于并行化查询的分布式PostgreSQL服务器集群。citus算是PostgreSQL生态中机制上最为复杂,且商业上最为成功的扩展之一,它也是一种FDW。
4.1.1 概述
使用FDW特性需要先安装相应的扩展,并执行一些设置命令,例如CREATE FOREIGN TABLE
,CREATE SERVER
和CREATE USER MAPPING
(细节请参阅官方文档)。
在配置妥当之后,查询处理期间,执行器将会调用扩展中定义的相应函数来访问外部表。
图4.2 FDW是如何执行的
- 分析器为输入的SQL创建一颗查询树。
- 计划器(或执行器)连接到远程服务器。
- 如果启用了
use_remote_estimate
选项(默认关闭),则计划器将执行EXPLAIN
命令以估计每条计划路径的代价。 - 计划器按照计划树创建出纯文本SQL语句,在内部称该过程为逆解析(deparesing)。
- 执行器将纯文本SQL语句发送到远程服务器并接收结果。
如有必要,执行器会进一步处理接收到的结果。 例如执行多表查询时,执行器会将收到的数据与其他表进行连接。
以下各节介绍了每一步中的具体细节。
4.1.1.1 创建一颗查询树
分析器会根据输入的SQL创建一颗查询树,并使用外部表的定义。当执行命令CREATE FOREIGN TABLE
和IMPORT FOREIGN SCHEMA
时,外部表的定义会被存储至系统目录pg_catalog.pg_class
和pg_catalog.pg_foreign_table
中。
4.1.1.2 连接至远程服务器
计划器(或执行器)会使用特定的库连接至远程数据库服务器。 例如要连接至远程PostgreSQL服务器时,postgres_fdw
会使用libpq
。 而连接到mysql服务器时,由EnterpriseDB开发的mysql_fdw
使用libmysqlclient
。
当执行CREATE USER MAPPING
和CREATE SERVER
命令时,诸如用户名,服务器IP地址和端口号等连接参数会被存储至系统目录pg_catalog.pg_user_mapping
和pg_catalog.pg_foreign_server
中。
4.1.1.3 使用EXPLAIN命令创建计划树(可选)
PostgreSQL的FDW机制支持一种特性:获取外部表上的统计信息,用于估计查询代价。一些FDW扩展使用了该特性,例如postgres_fdw
,mysql_fdw
,tds_fdw
和jdbc2_fdw
。
如果使用ALTER SERVER
命令将use_remote_estimate
选项设置为on
,则计划器会向远程服务器发起查询,执行EXPLAIN
命令获取执行计划的代价。否则在默认情况下,会使用默认内置常量值作为代价。
localdb=# ALTER SERVER remote_server_name OPTIONS (use_remote_estimate 'on');
尽管一些扩展也会执行EXPLAIN
命令,但目前只有postgres_fdw
才能忠于EXPLAIN
命令的真正意图,因为PostgreSQL的EXPLAIN
命令会同时返回启动代价和总代价。而其他DBMS的FDW扩展一般无法使用EXPLAIN
命令的结果进行规划。 例如MySQL的EXPLAIN
命令仅仅返回估计的行数, 但如第3章所述,PostgreSQL的计划器需要更多的信息来估算代价。
4.1.1.4 逆解析
在生成执行计划树的过程中,计划器会为执行计划树上外部表的扫描路径创建相应的纯文本SQL语句。 例如图4.3展示了下列SELECT
语句对应的计划树。
localdb=# SELECT * FROM tbl_a AS a WHERE a.id < 10;
图4.3展示了一个存储着纯文本形式SELECT
语句的ForeignScan
节点,PlannedStmt
是执行计划树对应的数据结构,包含指向ForeignScan
节点的链接。 这里,postgres_fdw
从查询树中重新创建出SELECT
纯文本语句,该过程在PostgreSQL中被称为逆解析(deparsing)。
图4.3 扫描外部表的计划树样例
使用mysql_fdw
时,则会从查询树中重新创建MySQL相应的SELECT
语句。 使用redis_fdw
或rw_redis_fdw
会创建一条Redis中的SELECT
命令。
4.1.1.5 发送SQL命令并接收结果
在进行逆解析之后,执行器将逆解析得到的SQL语句发送到远程服务器并接收结果。
扩展的开发者决定了将SQL语句发送至远程服务器的具体方法。 例如mysql_fdw
在发送多条SQL语句时不使用事务。 在mysql_fdw
中执行SELECT
查询的典型SQL语句序列如下所示(图4.4)。
- (5-1)将
SQL_MODE
设置为'ANSI_QUOTES'
。 - (5-2)将
SELECT
语句发送到远程服务器。 - (5-3)从远程服务器接收结果。这里
mysql_fdw
会将结果转换为PostgreSQL可读的格式。所有FDW扩展都实现了将结果转换为PostgreSQL可读数据的功能。
图4.4 mysql_fdw
执行一个典型SELECT查询时的SQL语句序列
下面是远程服务器的日志,列出了实际接收到的语句。
mysql> SELECT command_type,argument FROM mysql.general_log;
+--------------+-----------------------------------------------------------+
| command_type | argument |
+--------------+-----------------------------------------------------------+
... snip ...
| Query | SET sql_mode='ANSI_QUOTES' |
| Prepare | SELECT `id`, `data` FROM `localdb`.`tbl_a` WHERE ((`id` < 10)) |
| Close stmt | |
+--------------+-----------------------------------------------------------+
postgres_fdw
中的SQL命令顺序要更为复杂。在postgres_fdw
中执行一个典型的SELECT
查询,实际的语句序列如图4.5所示。
-
(5-1)启动远程事务。远程事务的默认隔离级别是
REPEATABLE READ
;但如果本地事务的隔离级别设置为SERIALIZABLE
,则远程事务的隔离级别也会设置为SERIALIZABLE
。 -
(5-2)-(5-4)声明一个游标,SQL语句基本上以游标的方式来执行。
-
(5-5)执行
FETCH
命令获取结果。默认情况下FETCH
命令一次获取100行。 -
(5-6)从远程服务器接收结果。
-
(5-7)关闭游标。
-
(5-8)提交远程事务。
图4.5 postgres_fdw
执行一个典型SELECT查询时的SQL语句序列
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR SELECT id, data FROM public.tbl_a WHERE ((id < 10))
LOG: bind : DECLARE c1 CURSOR FOR SELECT id, data FROM public.tbl_a WHERE ((id < 10))
LOG: execute : DECLARE c1 CURSOR FOR SELECT id, data FROM public.tbl_a WHERE ((id < 10))
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
postgres_fdw
中远程事务的默认隔离级别远程事务的默认隔离级别为
REPEATABLE READ
,官方文档给出了原因和说明:当本地事务使用
SERIALIZABLE
隔离级别时,远程事务也会使用SERIALIZABLE
隔离级别,否则使用REPEATABLE READ
隔离级别。 这样做可以确保在远程服务器上执行多次扫表时,每次的结果之间都能保持一致。因此,即使其他活动在远程服务器上进行了并发更新,单个事务中的连续查询也将看到远程服务器上的一致性快照。
4.1.2 postgres_fdw
的工作原理
postgres_fdw
扩展是一个由PostgreSQL全球开发组官方维护的特殊模块,其源码包含在PostgreSQL源码树中。
postgres_fdw
正处于不断改善的过程中。 表4.1列出了官方文档中与postgres_fdw
有关的发行说明。
表4.1 与postgres_fdw有关的发布说明(摘自官方文档)
版本 | 描述 |
---|---|
9.3 | postgres_fdw 模块正式发布 |
9.6 | 在远程服务器上执行排序 在远程服务器上执行连接 如果可行,在远程服务器上执行 UPDATE 与DELETE 允许在服务器与表的选项中设置批量拉取结果集的大小 |
10 | 如果可行, 将聚合函数下推至远程服务器 |
前一节描述了postgres_fdw 如何处理单表查询,接下来的小节将介绍postgres_fdw 如何处理多表查询,排序操作与聚合函数。 |
本小节重点介绍SELECT
语句;但postgres_fdw
还可以处理其他DML(INSERT
,UPDATE
和DELETE
)语句。
PostgreSQL的FDW不会检测死锁
postgres_fdw
与FDW功能并不支持分布式锁管理器与分布式死锁检测功能, 因此很容易产生死锁。 例如某客户端A更新了一个本地表tbl_local
与一个外部表tbl_remote
,而另一个客户端B以相反的顺序更新tbl_remote
和tbl_local
,则这两个事务陷入死锁。但PostgreSQL无法检测到这种情况, 因而无法提交这些事务。localdb=# -- Client A localdb=# BEGIN; BEGIN localdb=# UPDATE tbl_local SET data = 0 WHERE id = 1; UPDATE 1 localdb=# UPDATE tbl_remote SET data = 0 WHERE id = 1; UPDATE 1
localdb=# -- Client B localdb=# BEGIN; BEGIN localdb=# UPDATE tbl_remote SET data = 0 WHERE id = 1; UPDATE 1 localdb=# UPDATE tbl_local SET data = 0 WHERE id = 1; UPDATE 1
4.1.2.1 多表查询
当执行多表查询时,postgres_fdw
使用单表SELECT
语句依次拉取每个外部表,并在本地服务器上执行连接操作。
在9.5或更早版本中,即使所有外部表都存储在同一个远程服务器中,postgres_fdw
也会单独拉取每个表再连接。
在9.6或更高版本中,postgres_fdw
已经有所改进,当外部表位于同一服务器上且use_remote_estimate
选项打开时,可以在远程服务器上执行远程连接操作。
执行细节如下所述。
9.5及更早版本:
我们研究一下PostgreSQL如何处理以下查询:两个外部表的连接:tbl_a
和tbl_b
。
localdb=# SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND a.id < 200;
EXPLAIN
的执行结果如下
localdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND a.id < 200;
QUERY PLAN
------------------------------------------------------------------------------
Merge Join (cost=532.31..700.34 rows=10918 width=16)
Merge Cond: (a.id = b.id)
-> Sort (cost=200.59..202.72 rows=853 width=8)
Sort Key: a.id
-> Foreign Scan on tbl_a a (cost=100.00..159.06 rows=853 width=8)
-> Sort (cost=331.72..338.12 rows=2560 width=8)
Sort Key: b.id
-> Foreign Scan on tbl_b b (cost=100.00..186.80 rows=2560 width=8)
(8 rows)
结果显示,执行器选择了归并连接,并按以下步骤处理:
-
第8行:执行器使用外部表扫描拉取表
tbl_a
。 -
第6行:执行器在本地服务器上对拉取的
tbl_a
行进行排序。 -
第11行:执行器使用外表扫描拉取表
tbl_b
。 -
第9行:执行器在本地服务器上对拉取的
tbl_b
行进行排序。 -
第4行:执行器在本地服务器上执行归并连接操作。
下面描述执行器如何拉取行集(图4.6)。
-
(5-1)启动远程事务。
-
(5-2)声明游标
c1
,其SELECT
语句如下所示:SELECT id,data FROM public.tbl_a WHERE(id <200)
-
(5-3)执行
FETCH
命令以拉取游标c1
的结果。 -
(5-4)声明游标
c2
,其SELECT
语句如下所示:SELECT id,data FROM public.tbl_b
注意原来双表查询中的WHERE子句是
tbl_a.id = tbl_b.id AND tbl_a.id <200
;因而从逻辑上讲这条SELECT
语句也可以添加上一条WHERE子句tbl_b.id <200
。但postgres_fdw
没有办法执行这样的推理,因此执行器必须执行不包含任何WHERE子句的SELECT
语句,获取外部表tbl_b
中的所有行。这种处理方式效率很差,因为必须通过网络从远程服务器读取不必要的行。此外,执行归并连接还需要先对接受到的行进行排序。
-
(5-5)执行
FETCH
命令,拉取游标c2
的结果。 -
(5-6)关闭游标
c1
。 -
(5-7)关闭游标
c2
。 -
(5-8)提交事务。
图4.6 在9.5及更早版本中执行多表查询时的SQL语句序列
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: bind : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: execute : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: statement: FETCH 100 FROM c1
LOG: statement: FETCH 100 FROM c1
LOG: parse : DECLARE c2 CURSOR FOR
SELECT id, data FROM public.tbl_b
LOG: bind : DECLARE c2 CURSOR FOR
SELECT id, data FROM public.tbl_b
LOG: execute : DECLARE c2 CURSOR FOR
SELECT id, data FROM public.tbl_b
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
... snip
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
LOG: statement: FETCH 100 FROM c2
LOG: statement: CLOSE c2
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
在接收到行之后,执行器对接收到的tbl_a
和tbl_b
行进行排序,然后对已排序的行执行合并连接操作。
9.6或更高版本:
如果启用了use_remote_estimate
选项(默认为关闭),则postgres_fdw
会发送几条EXPLAIN
命令,用于获取与外部表相关的所有计划的代价。
当发送EXPLAIN
命令时,postgres_fdw
将为每个单表查询执行EXPLAIN
,也为执行远程连接操作时的SELECT
语句执行EXPLAIN
。在本例中,以下七个EXPLAIN
命令会被发送至远程服务器,用于估算每个SELECT
语句的开销,从而选择开销最小的执行计划。
(1) EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((id < 200))
(2) EXPLAIN SELECT id, data FROM public.tbl_b
(3) EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
(4) EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((((SELECT null::integer)::integer) = id)) AND ((id < 200))
(5) EXPLAIN SELECT id, data FROM public.tbl_b ORDER BY id ASC NULLS LAST
(6) EXPLAIN SELECT id, data FROM public.tbl_b WHERE ((((SELECT null::integer)::integer) = id))
(7) EXPLAIN SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
让我们在本地服务器上执行EXPLAIN
命令,并观察计划器选择了哪一个计划。
localdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_b AS b WHERE a.id = b.id AND a.id < 200;
QUERY PLAN
-----------------------------------------------------------
Foreign Scan (cost=134.35..244.45 rows=80 width=16)
Relations: (public.tbl_a a) INNER JOIN (public.tbl_b b)
(2 rows)
结果显示,计划器选择了在远程服务器上进行INNER JOIN
处理的执行计划,也是最有效率的执行计划。
下面讲述postgres_fdw
是如何执行这一过程的,如图4.7所示。
图4.7 执行远程连接操作时的SQL语句序列,9.6及更高版本
-
(3-1)启动远程事务。
-
(3-2)执行
EXPLAIN
命令,估计每条计划路径的代价。在本例中执行了七条EXPLAIN
命令。然后计划器根据EXPLAIN
命令的结果,选取具有最低开销的SELECT
查询。 -
(5-1)声明游标
c1
,其SELECT
语句如下所示:SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
-
(5-2)从远程服务器接收结果。
-
(5-3)关闭游标
c1
。 -
(5-4)提交事务。
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_b
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_a WHERE ((((SELECT null::integer)::integer) = id)) AND ((id < 200))
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_b ORDER BY id ASC NULLS LAST
LOG: statement: EXPLAIN SELECT id, data FROM public.tbl_b WHERE ((((SELECT null::integer)::integer) = id))
LOG: statement: EXPLAIN SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
LOG: parse: DECLARE c1 CURSOR FOR
SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
LOG: bind: DECLARE c1 CURSOR FOR
SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
LOG: execute: DECLARE c1 CURSOR FOR
SELECT r1.id, r1.data, r2.id, r2.data FROM (public.tbl_a r1 INNER JOIN public.tbl_b r2 ON (((r1.id = r2.id)) AND ((r1.id < 200))))
LOG: statement: FETCH 100 FROM c1
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
注意如果禁用use_remote_estimate
选项(默认情况),则远程连接查询很少会被选择,因为这种情况下其代价会使用一个很大的预置值进行估计。
4.1.2.2 排序操作
在9.5或更早版本中,排序操作(如ORDER BY
)都是在本地服务器上处理的。即,本地服务器在排序操作之前从远程服务器拉取所有的目标行。让我们通过EXPLAIN
来看一个包含ORDER BY
子句的简单查询是如何被处理的。
localdb=# EXPLAIN SELECT * FROM tbl_a AS a WHERE a.id < 200 ORDER BY a.id;
QUERY PLAN
-----------------------------------------------------------------------
Sort (cost=200.59..202.72 rows=853 width=8)
Sort Key: id
-> Foreign Scan on tbl_a a (cost=100.00..159.06 rows=853 width=8)
(3 rows)
第6行:执行器将以下查询发送到远程服务器,然后获取查询结果。
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
第4行:执行器在本地服务器上对拉取的tbl_a
中的行进行排序。
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: bind : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: execute : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
LOG: statement: FETCH 100 FROM c1
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
在9.6或更高版本中,如果可行,postgres_fdw
能在远程服务器上直接执行带ORDER BY
子句的SELECT
语句。
localdb=# EXPLAIN SELECT * FROM tbl_a AS a WHERE a.id < 200 ORDER BY a.id;
QUERY PLAN
-----------------------------------------------------------------
Foreign Scan on tbl_a a (cost=100.00..167.46 rows=853 width=8)
(1 row)
第4行:执行器将以下带ORDER BY
子句的查询发送至远程服务器,然后拉取已排序的查询结果。
SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
LOG: bind : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
LOG: execute : DECLARE c1 CURSOR FOR
SELECT id, data FROM public.tbl_a WHERE ((id < 200)) ORDER BY id ASC NULLS LAST
LOG: statement: FETCH 100 FROM c1
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
4.1.2.3 聚合函数
在9.6及更早版本中,类似于前一小节中提到的排序操作,AVG()
和COUNT()
这样的聚合函数会在本地服务器上进行处理,如下所示。
localdb=# EXPLAIN SELECT AVG(data) FROM tbl_a AS a WHERE a.id < 200;
QUERY PLAN
-----------------------------------------------------------------------
Aggregate (cost=168.50..168.51 rows=1 width=4)
-> Foreign Scan on tbl_a a (cost=100.00..166.06 rows=975 width=4)
(2 rows)
第5行:执行器将以下查询发送到远程服务器,然后拉取查询结果。
SELECT id, data FROM public.tbl_a WHERE ((id < 200))
第4行:执行器在本地服务器上对拉取的tbl_a
行集求均值。
这一过程开销很大,因为发送大量的行会产生大量网络流量,而且需要很长时间。
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR
SELECT data FROM public.tbl_a WHERE ((id < 200))
LOG: bind : DECLARE c1 CURSOR FOR
SELECT data FROM public.tbl_a WHERE ((id < 200))
LOG: execute : DECLARE c1 CURSOR FOR
SELECT data FROM public.tbl_a WHERE ((id < 200))
LOG: statement: FETCH 100 FROM c1
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
在10或更高版本中,如果可行的话,postgres_fdw
将在远程服务器上执行带聚合函数的SELECT
语句。
localdb=# EXPLAIN SELECT AVG(data) FROM tbl_a AS a WHERE a.id < 200;
QUERY PLAN
-----------------------------------------------------
Foreign Scan (cost=102.44..149.03 rows=1 width=32)
Relations: Aggregate on (public.tbl_a a)
(2 rows)
第4行:执行器将以下包含AVG()
函数的查询发送至远程服务器,然后获取查询结果。
SELECT avg(data) FROM public.tbl_a WHERE ((id < 200))
这种处理方式显然更为高效,因为远程服务器会负责计算均值,仅发送单行结果。
这里是远程服务器的实际日志。
LOG: statement: START TRANSACTION ISOLATION LEVEL REPEATABLE READ
LOG: parse : DECLARE c1 CURSOR FOR
SELECT avg(data) FROM public.tbl_a WHERE ((id < 200))
LOG: bind : DECLARE c1 CURSOR FOR
SELECT avg(data) FROM public.tbl_a WHERE ((id < 200))
LOG: execute : DECLARE c1 CURSOR FOR
SELECT avg(data) FROM public.tbl_a WHERE ((id < 200))
LOG: statement: FETCH 100 FROM c1
LOG: statement: CLOSE c1
LOG: statement: COMMIT TRANSACTION
下推
与上面的例子类似,下推(push-down) 指的是本地服务器允许一些操作在远程服务器上执行,例如聚合函数。
第五章 并发控制
当多个事务同时在数据库中运行时,并发控制是一种用于维持一致性与隔离性的技术,一致性与隔离性是ACID的两个属性。
从宽泛的意义上来讲,有三种并发控制技术:多版本并发控制(Multi-version Concurrency Control, MVCC),严格两阶段锁定(Strict Two-Phase Locking, S2PL)和乐观并发控制(Optimistic Concurrency Control, OCC),每种技术都有多种变体。在MVCC中,每个写操作都会创建一个新版本的数据项,并保留其旧版本。当事务读取数据对象时,系统会选择其中的一个版本,通过这种方式来确保各个事务间相互隔离。 MVCC的主要优势在于“读不会阻塞写,而写也不会阻塞读”,相反的例子是,基于S2PL的系统在写操作发生时会阻塞相应对象上的读操作,因为写入者获取了对象上的排他锁。 PostgreSQL和一些RDBMS使用一种MVCC的变体,名曰 快照隔离(Snapshot Isolation,SI)。
一些RDBMS(例如Oracle)使用回滚段来实现快照隔离SI。当写入新数据对象时,旧版本对象先被写入回滚段,随后用新对象覆写至数据区域。 PostgreSQL使用更简单的方法:新数据对象被直接插入到相关表页中。读取对象时,PostgreSQL根据可见性检查规则(visibility check rules),为每个事务选择合适的对象版本作为响应。
SI中不会出现在ANSI SQL-92标准中定义的三种异常:脏读,不可重复读和幻读。但SI无法实现真正的可串行化,因为在SI中可能会出现串行化异常:例如 写偏差(write skew) 和 只读事务偏差(Read-only Transaction Skew) 。需要注意的是:ANSI SQL-92标准中可串行化的定义与现代理论中的定义并不相同。为了解决这个问题,PostgreSQL从9.1版本之后添加了可串行化快照隔离(SSI,Serializable Snapshot Isolation),SSI可以检测串行化异常,并解决这种异常导致的冲突。因此,9.1版本之后的PostgreSQL提供了真正的SERIALIZABLE
隔离等级(此外SQL Server也使用SSI,而Oracle仍然使用SI)。
本章包括以下四个部分:
-
第1部分:第5.1~5.3节。
这一部分介绍了理解后续部分所需的基本信息。
第5.1和5.2节分别描述了事务标识和元组结构。第5.3节展示了如何插入,删除和更新元组。
-
第2部分:第5.4~5.6节。
这一部分说明了实现并发控制机制所需的关键功能。
第5.4,5.5和5.6节描述了提交日志(clog),分别介绍了事务状态,事务快照和可见性检查规则。
-
第3部分:第5.7~5.9节。
这一部分使用具体的例子来介绍PostgreSQL中的并发控制。
这一部分说明了如何防止ANSI SQL标准中定义的三种异常。第5.7节描述了可见性检查,第5.8节介绍了如何防止丢失更新,第5.9节简要描述了SSI。
-
第4部分:第5.10节。
这一部分描述了并发控制机制持久运行所需的几个维护过程。维护过程主要通过 清理过程(vacuum processing) 进行,清理过程将在第6章详细阐述。
并发控制包含着很多主题,本章重点介绍PostgreSQL独有的内容。故这里省略了锁模式与死锁处理的内容(相关信息请参阅官方文档)。
PostgreSQL中的事务隔离等级
PostgreSQL实现的事务隔离等级如下表所示:
隔离等级 | 脏读 | 不可重复读 | 幻读 | 串行化异常 |
---|---|---|---|---|
读已提交 | 不可能 | 可能 | 可能 | 可能 |
可重复读[1] | 不可能 | 不可能 | PG中不可能,见5.7.2小节 但ANSI SQL中可能 |
可能 |
可串行化 | 不可能 | 不可能 | 不可能 | 不可能 |
[1]:在9.0及更早版本中,该级别被当做SERIALIZABLE
,因为它不会出现ANSI SQL-92标准中定义的三种异常。 但9.1版中SSI的实现引入了真正的SERIALIZABLE
级别,该级别已被改称为REPEATABLE READ
。
PostgreSQL对DML(
SELECT, UPDATE, INSERT, DELETE
等命令)使用SSI,对DDL(CREATE TABLE
等命令)使用2PL。
5.1 事务标识
每当事务开始时,事务管理器就会为其分配一个称为 事务标识(transaction id, txid) 的唯一标识符。 PostgreSQL的txid
是一个32位无符号整数,总取值约42亿。在事务启动后执行内置的txid_current()
函数,即可获取当前事务的txid
,如下所示。
testdb=# BEGIN;
BEGIN
testdb=# SELECT txid_current();
txid_current
--------------
100
(1 row)
PostgreSQL保留以下三个特殊txid
:
- 0 表示 无效(Invalid) 的
txid
。 - 1 表示 初始启动(Bootstrap) 的
txid
,仅用于数据库集群的初始化过程。 - 2 表示 冻结(Frozen) 的
txid
,详情参考第5.10.1节。
txid
可以相互比较大小。例如对于txid=100
的事务,大于100的txid
属于“未来”,且对于txid=100
的事务而言都是 不可见(invisible) 的;小于100的txid
属于“过去”,且对该事务可见,如图5.1(a)所示。
图5.1 PostgreSQL中的事务标识
因为txid
在逻辑上是无限的,而实际系统中的txid
空间不足(4字节取值空间约42亿),因此PostgreSQL将txid
空间视为一个环。对于某个特定的txid
,其前约21亿个txid
属于过去,而其后约21亿个txid
属于未来。如图5.1(b)所示。
所谓的txid
回卷问题将在5.10.1节中介绍。
请注意,
txid
并非是在BEGIN
命令执行时分配的。在PostgreSQL中,当执行BEGIN
命令后的第一条命令时,事务管理器才会分配txid
,并真正启动其事务。
5.2 元组结构
可以将表页中的堆元组分为两类:普通数据元组与TOAST元组。本节只会介绍普通元组。
堆元组由三个部分组成,即HeapTupleHeaderData
结构,空值位图,以及用户数据,如图5.2所示。
图5.2 元组结构
HeapTupleHeaderData
结构在src/include/access/htup_details.h
中定义。
typedef struct HeapTupleFields
{
TransactionId t_xmin; /* 插入事务的ID */
TransactionId t_xmax; /*删除或锁定事务的ID*/
union
{
CommandId t_cid; /* 插入或删除的命令ID */
TransactionId t_xvac; /* 老式VACUUM FULL的事务ID */
} t_field3;
} HeapTupleFields;
typedef struct DatumTupleFields
{
int32 datum_len_; /* 变长头部长度*/
int32 datum_typmod; /* -1或者是记录类型的标识 */
Oid datum_typeid; /* 复杂类型的OID或记录ID */
} DatumTupleFields;
typedef struct HeapTupleHeaderData
{
union
{
HeapTupleFields t_heap;
DatumTupleFields t_datum;
} t_choice;
ItemPointerData t_ctid; /* 当前元组,或更新元组的TID */
/* 下面的字段必需与结构MinimalTupleData相匹配! */
uint16 t_infomask2; /* 属性与标记位 */
uint16 t_infomask; /* 很多标记位 */
uint8 t_hoff; /* 首部+位图+填充的长度 */
/* ^ - 23 bytes - ^ */
bits8 t_bits[1]; /* NULL值的位图 —— 变长的 */
/* 本结构后面还有更多数据 */
} HeapTupleHeaderData;
typedef HeapTupleHeaderData *HeapTupleHeader;
虽然HeapTupleHeaderData
结构包含七个字段,但后续部分中只需要了解四个字段即可。
t_xmin
保存插入此元组的事务的txid
。t_xmax
保存删除或更新此元组的事务的txid
。如果尚未删除或更新此元组,则t_xmax
设置为0,即无效。t_cid
保存命令标识(command id, cid),cid
意思是在当前事务中,执行当前命令之前执行了多少SQL命令,从零开始计数。例如,假设我们在单个事务中执行了三条INSERT
命令BEGIN;INSERT;INSERT;INSERT;COMMIT;
。如果第一条命令插入此元组,则该元组的t_cid
会被设置为0。如果第二条命令插入此元组,则其t_cid
会被设置为1,依此类推。t_ctid
保存着指向自身或新元组的元组标识符(tid
)。如第1.3节中所述,tid
用于标识表中的元组。在更新该元组时,其t_ctid
会指向新版本的元组;否则t_ctid
会指向自己。
5.3 元组的增删改
本节会介绍元组的增删改过程,并简要描述用于插入与更新元组的自由空间映射(Free Space Map, FSM)。
这里主要关注元组,页首部与行指针不会在这里画出来,元组的具体表示如图5.3所示。
图5.3 元组的表示
5.3.1 插入
在插入操作中,新元组将直接插入到目标表的页面中,如图5.4所示。
图5.4 插入元组
假设元组是由txid=99
的事务插入页面中的,在这种情况下,被插入元组的首部字段会依以下步骤设置。
Tuple_1
:
t_xmin
设置为99,因为此元组由txid=99
的事务所插入。t_xmax
设置为0,因为此元组尚未被删除或更新。t_cid
设置为0,因为此元组是由txid=99
的事务所执行的第一条命令所插入的。t_ctid
设置为(0,1)
,指向自身,因为这是该元组的最新版本。
pageinspect
PostgreSQL自带了一个第三方贡献的扩展模块
pageinspect
,可用于检查数据库页面的具体内容。testdb=# CREATE EXTENSION pageinspect; CREATE EXTENSION testdb=# CREATE TABLE tbl (data text); CREATE TABLE testdb=# INSERT INTO tbl VALUES(A); INSERT 0 1 testdb=# SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page(tbl, 0)); tuple | t_xmin | t_xmax | t_cid | t_ctid -------+--------+--------+-------+-------- 1 | 99 | 0 | 0 | (0,1) (1 row)
5.3.2 删除
在删除操作中,目标元组只是在逻辑上被标记为删除。目标元组的t_xmax
字段将被设置为执行DELETE
命令事务的txid
。如图5.5所示。
图5.5 删除元组
假设Tuple_1
被txid=111
的事务删除。在这种情况下,Tuple_1
的首部字段会依以下步骤设置。
Tuple_1
:
t_xmax
被设为111。
如果txid=111
的事务已经提交,那么Tuple_1
就不是必需的了。通常不需要的元组在PostgreSQL中被称为死元组(dead tuple)。
死元组最终将从页面中被移除。清除死元组的过程被称为清理(VACUUM)过程,第6章将介绍清理过程。
5.3.3 更新
在更新操作中,PostgreSQL在逻辑上实际执行的是删除最新的元组,并插入一条新的元组(图5.6)。
图5.6 两次更新同一行
假设由txid=99
的事务插入的行,被txid=100
的事务更新两次。
当执行第一条UPDATE
命令时,Tuple_1
的t_xmax
被设为txid 100
,在逻辑上被删除;然后Tuple_2
被插入;接下来重写Tuple_1
的t_ctid
以指向Tuple_2
。Tuple_1
和Tuple_2
的头部字段设置如下。
Tuple_1
:
t_xmax
被设置为100。t_ctid
从(0,1)
被改写为(0,2)
。
Tuple_2
:
t_xmin
被设置为100。t_xmax
被设置为0。t_cid
被设置为0。t_ctid
被设置为(0,2)
。
当执行第二条UPDATE
命令时,和第一条UPDATE
命令类似,Tuple_2
被逻辑删除,Tuple_3
被插入。Tuple_2
和Tuple_3
的首部字段设置如下。
Tuple_2
:
t_xmax
被设置为100。t_ctid
从(0,2)
被改写为(0,3)
。
Tuple_3
:
t_xmin
被设置为100。t_xmax
被设置为0。t_cid
被设置为1。t_ctid
被设置为(0,3)
。
与删除操作类似,如果txid=100
的事务已经提交,那么Tuple_1
和Tuple_2
就成为了死元组,而如果txid=100
的事务中止,Tuple_2
和Tuple_3
就成了死元组。
5.3.4 空闲空间映射
插入堆或索引元组时,PostgreSQL使用表与索引相应的FSM来选择可供插入的页面。
如1.2.3节所述,表和索引都有各自的FSM。每个FSM存储着相应表或索引文件中每个页面可用空间容量的信息。
所有FSM都以后缀fsm
存储,在需要时它们会被加载到共享内存中。
pg_freespacemap
扩展
pg_freespacemap
能提供特定表或索引上的空闲空间信息。以下查询列出了特定表中每个页面的空闲率。testdb=# CREATE EXTENSION pg_freespacemap; CREATE EXTENSION testdb=# SELECT *, round(100 * avail/8192 ,2) as "freespace ratio" FROM pg_freespace(accounts); blkno | avail | freespace ratio -------+-------+----------------- 0 | 7904 | 96.00 1 | 7520 | 91.00 2 | 7136 | 87.00 3 | 7136 | 87.00 4 | 7136 | 87.00 5 | 7136 | 87.00 ....
5.4 提交日志(clog)
PostgreSQL在提交日志(Commit Log, clog)中保存事务的状态。提交日志(通常称为clog)分配于共享内存中,并用于事务处理过程的全过程。
本节将介绍PostgreSQL中事务的状态,clog的工作方式与维护过程。
5.4.1 事务状态
PostgreSQL定义了四种事务状态,即:IN_PROGRESS
,COMMITTED
,ABORTED
和SUB_COMMITTED
。
前三种状态涵义显而易见。例如当事务正在进行时,其状态为IN_PROGRESS
,依此类推。
SUB_COMMITTED
状态用于子事务,本文省略了与子事务相关的描述。
5.4.2 提交日志如何工作
提交日志(下称clog)在逻辑上是一个数组,由共享内存中一系列8KB页面组成。数组的序号索引对应着相应事务的标识,而其内容则是相应事务的状态。clog的工作方式如图5.7所示。
图5.7 clog如何工作
T1:
txid 200
提交;txid 200
的状态从IN_PROGRESS
变为COMMITTED
。 T2:txid 201
中止;txid 201
的状态从IN_PROGRESS
变为ABORTED
。
txid
不断前进,当clog空间耗尽无法存储新的事务状态时,就会追加分配一个新的页面。
当需要获取事务的状态时,PostgreSQL将调用相应内部函数读取clog,并返回所请求事务的状态。(参见第5.7.1节中的提示位(Hint Bits))
5.4.3 提交日志的维护
当PostgreSQL关机或执行存档过程时,clog数据会写入至pg_clog
子目录下的文件中(注意在10版本中,pg_clog
被重命名为pg_xact
)。这些文件被命名为0000
,0001
等等。文件的最大尺寸为256 KB。例如当clog使用八个页面时,从第一页到第八页的总大小为64 KB,这些数据会写入到文件0000
(64 KB)中;而当clog使用37个页面时(296 KB),数据则会写入到0000
和0001
两个文件中,其大小分别为256 KB和40 KB。
当PostgreSQL启动时会加载存储在pg_clog
(pg_xact
)中的文件,用其数据初始化clog。
clog的大小会不断增长,因为只要clog一填满就会追加新的页面。但并非所有数据都是必需的。第6章中描述的清理过程会定期删除这些不需要的旧数据(clog页面和文件),有关删除clog数据的详情请参见第6.4节。
5.5 事务快照
**事务快照(transaction snapshot)**是一个数据集,存储着某个特定事务在某个特定时间点所看到的事务状态信息:哪些事务处于活跃状态。这里活跃状态意味着事务正在进行中,或还没有开始。
事务快照在PostgreSQL内部的文本表示格式定义为100:100:
。举个例子,这里100:100:
意味着txid < 100
的事务处于非活跃状态,而txid ≥ 100
的事务处于活跃状态。下文都将使用这种便利形式来表示。如果读者还不熟悉这种形式,请参阅下文。
内置函数
txid_current_snapshot
及其文本表示函数
txid_current_snapshot
显示当前事务的快照。testdb=# SELECT txid_current_snapshot(); txid_current_snapshot ----------------------- 100:104:100,102 (1 row)
txid_current_snapshot
的文本表示是xmin:xmax:xip_list
,各部分描述如下。
xmin
最早仍然活跃的事务的
txid
。所有比它更早的事务txid < xmin
要么已经提交并可见,要么已经回滚并生成死元组。
xmax
第一个尚未分配的
txid
。所有txid ≥ xmax
的事务在获取快照时尚未启动,因而其结果对当前事务不可见。
xip_list
获取快照时活跃事务的
txid
列表。该列表仅包括xmin
与xmax
之间的txid
。例如,在快照
100:104:100,102
中,xmin
是100
,xmax
是104
,而xip_list
为100,102
。以下显示了两个具体的示例:
图5.8 事务快照的表示样例
第一个例子是
100:100:
,如图图5.8(a)所示,此快照表示:
- 因为
xmin
为100,因此txid < 100
的事务是非活跃的- 因为
xmax
为100,因此txid ≥ 100
的事务是活跃的第二个例子是
100:104:100,102
,如图5.8(b)所示,此快照表示:
txid < 100
的事务不活跃。txid ≥ 104
的事务是活跃的。txid
等于100和102的事务是活跃的,因为它们在xip_list
中,而txid
等于101和103的事务不活跃。
事务快照是由事务管理器提供的。在READ COMMITTED
隔离级别,事务在执行每条SQL时都会获取快照;其他情况下(REPEATABLE READ
或SERIALIZABLE
隔离级别),事务只会在执行第一条SQL命令时获取一次快照。获取的事务快照用于元组的可见性检查,如第5.7节所述。
使用获取的快照进行可见性检查时,所有活跃的事务都必须被当成IN PROGRESS
的事务等同对待,无论它们实际上是否已经提交或中止。这条规则非常重要,因为它正是READ COMMITTED
和REPEATABLE READ/SERIALIZABLE
隔离级别中表现差异的根本来源,我们将在接下来几节中频繁回到这条规则上来。
在本节的剩余部分中,我们会通过一个具体的场景来描述事务与事务管理器,如图5.9所示。
图5.9 事务管理器与事务
事务管理器始终保存着当前运行的事务的有关信息。假设三个事务一个接一个地开始,并且Transaction_A
和Transaction_B
的隔离级别是READ COMMITTED
,Transaction_C
的隔离级别是REPEATABLE READ
。
-
T1:
Transaction_A
启动并执行第一条SELECT
命令。执行第一个命令时,Transaction_A
请求此刻的txid
和快照。在这种情况下,事务管理器分配txid=200
,并返回事务快照200:200:
。 -
T2:
Transaction_B
启动并执行第一条SELECT
命令。事务管理器分配txid=201
,并返回事务快照200:200:
,因为Transaction_A(txid=200)
正在进行中。因此无法从Transaction_B
中看到Transaction_A
。 -
T3:
Transaction_C
启动并执行第一条SELECT
命令。事务管理器分配txid=202
,并返回事务快照200:200:
,因此不能从Transaction_C
中看到Transaction_A
和Transaction_B
。 -
T4:
Transaction_A
已提交。事务管理器删除有关此事务的信息。 -
T5:
Transaction_B
和Transaction_C
执行它们各自的SELECT
命令。Transaction_B
需要一个新的事务快照,因为它使用了READ COMMITTED
隔离等级。在这种情况下,Transaction_B
获取新快照201:201:
,因为Transaction_A(txid=200)
已提交。因此Transaction_A
的变更对Transaction_B
可见了。Transaction_C
不需要新的事务快照,因为它处于REPEATABLE READ
隔离等级,并继续使用已获取的快照,即200:200:
。因此,Transaction_A
的变更仍然对Transaction_C
不可见。
5.6 可见性检查规则
可见性检查规则是一组规则,用于确定一条元组是否对一个事务可见,可见性检查规则会用到元组的t_xmin
和t_xmax
,提交日志clog,以及已获取的事务快照。这些规则太复杂,无法详细解释,故本书只列出了理解后续内容所需的最小规则子集。在下文中省略了与子事务相关的规则,并忽略了关于t_ctid
的讨论,比如我们不会考虑在同一个事务中对一条元组多次重复更新的情况。
所选规则有十条,可以分类为三种情况。
5.6.1 t_xmin
的状态为ABORTED
t_xmin
状态为ABORTED
的元组始终不可见(规则1),因为插入此元组的事务已中止。
/* 创建元组的事务已经中止 */
Rule 1: IF t_xmin status is ABORTED THEN
RETURN Invisible
END IF
该规则明确表示为以下数学表达式。
- 规则1:
If Status(t_xmin) = ABORTED ⇒ Invisible
5.6.2 t_xmin
的状态为IN_PROGRESS
t_xmin
状态为IN_PROGRESS
的元组基本上是不可见的(规则3和4),但在一个条件下除外。
/* 创建元组的事务正在进行中 */
IF t_xmin status is IN_PROGRESS THEN
/* 当前事务自己创建了本元组 */
IF t_xmin = current_txid THEN
/* 该元组没有被标记删除,则应当看见本事务自己创建的元组 */
Rule 2: IF t_xmax = INVALID THEN
RETURN Visible /* 例外,被自己创建的未删元组可见 */
Rule 3: ELSE
/* 这条元组被当前事务自己创建后又删除掉了,故不可见 */
RETURN Invisible
END IF
Rule 4: ELSE /* t_xmin ≠ current_txid */
/* 其他运行中的事务创建了本元组 */
RETURN Invisible
END IF
END IF
如果该元组被另一个进行中的事务插入(t_xmin
对应事务状态为IN_PROGRESS
),则该元组显然是不可见的(规则4)。
如果t_xmin
等于当前事务的txid
(即,是当前事务插入了该元组),且t_xmax ≠ 0
,则该元组是不可见的,因为它已被当前事务更新或删除(规则3)。
例外是,当前事务插入此元组且t_xmax
无效(t_xmax = 0
)的情况。 在这种情况下,此元组对当前事务中可见(规则2)。
- 规则2:
If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax = INVAILD ⇒ Visible
- 规则3:
If Status(t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax ≠ INVAILD ⇒ Invisible
- 规则4:
If Status(t_xmin) = IN_PROGRESS ∧ t_xmin ≠ current_txid ⇒ Invisible
5.6.3 t_xmin
的状态为COMMITTED
t_xmin
状态为COMMITTED
的元组是可见的(规则 6,8和9),但在三个条件下除外。
/* 创建元组的事务已经提交 */
IF t_xmin status is COMMITTED THEN
/* 创建元组的事务在获取的事务快照中处于活跃状态,创建无效,不可见 */
Rule 5: IF t_xmin is active in the obtained transaction snapshot THEN
RETURN Invisible
/* 元组被删除,但删除元组的事务中止了,删除无效,可见 */
/* 创建元组的事务已提交,且非活跃,元组也没有被标记为删除,则可见 */
Rule 6: ELSE IF t_xmax = INVALID OR status of t_xmax is ABORTED THEN
RETURN Visible
/* 元组被删除,但删除元组的事务正在进行中,分情况 */
ELSE IF t_xmax status is IN_PROGRESS THEN
/* 如果恰好是被本事务自己删除的,删除有效,不可见 */
Rule 7: IF t_xmax = current_txid THEN
RETURN Invisible
/* 如果是被其他事务删除的,删除无效,可见 */
Rule 8: ELSE /* t_xmax ≠ current_txid */
RETURN Visible
END IF
/* 元组被删除,且删除元组的事务已经提交 */
ELSE IF t_xmax status is COMMITTED THEN
/* 删除元组的事务在获取的事务快照中处于活跃状态,删除无效,不可见 */
Rule 9: IF t_xmax is active in the obtained transaction snapshot THEN
RETURN Visible
Rule 10: ELSE /* 删除有效,可见 */
RETURN Invisible
END IF
END IF
END IF
规则6是显而易见的,因为t_xmax
为INVALID
,或者t_xmax
对应事务已经中止,相应元组可见。三个例外条件及规则8与规则9的描述如下。
第一个例外情况是t_xmin
在获取的事务快照中处于活跃状态(规则5)。在这种情况下,这条元组是不可见的,因为t_xmin
应该被视为正在进行中(取快照时创建该元组的事务尚未提交,因此对于REPEATABLE READ
以及更高隔离等级而言,即使在判断时创建该元组的事务已经提交,但其结果仍然不可见)。
第二个例外情况是t_xmax
是当前的txid
(规则7)。这种情况与规则3类似,此元组是不可见的,因为它已经被此事务本身更新或删除。
相反,如果t_xmax
的状态是IN_PROGRESS
并且t_xmax
不是当前的txid
(规则8),则元组是可见的,因为它尚未被删除(因为删除该元组的事务尚未提交)。
第三个例外情况是t_xmax
的状态为COMMITTED
,且t_xmax
在获取的事务快照中是非活跃的(规则10)。在这种情况下该元组不可见,因为它已被另一个事务更新或删除。
相反,如果t_xmax
的状态为COMMITTED
,但t_xmax
在获取的事务快照中处于活跃状态(规则9),则元组可见,因为t_xmax
对应的事务应被视为正在进行中,删除尚未提交生效。
- 规则5:
If Status(t_xmin) = COMMITTED ∧ Snapshot(t_xmin) = active ⇒ Invisible
- 规则6:
If Status(t_xmin) = COMMITTED ∧ (t_xmax = INVALID ∨ Status(t_xmax) = ABORTED) ⇒ Visible
- 规则7:
If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax = current_txid ⇒ Invisible
- 规则8:
If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS ∧ t_xmax ≠ current_txid ⇒ Visible
- 规则9:
If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) = active ⇒ Visible
- 规则10:
If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) ≠ active ⇒ Invisible
5.7 可见性检查
本节描述了PostgreSQL执行可见性检查的流程。可见性检查(Visiblity Check),即如何为给定事务挑选堆元组的恰当版本。本节还介绍了PostgreSQL如何防止ANSI SQL-92标准中定义的异常:脏读,可重读和幻读。
5.7.1 可见性检查
图5.10中的场景描述了可见性检查的过程。
图5.10 可见性检查场景一例
在图5.10所示的场景中,SQL命令按以下时序执行。
- T1:启动事务
(txid=200)
- T2:启动事务
(txid=201)
- T3:执行
txid=200
和201的事务的SELECT
命令 - T4:执行
txid=200
的事务的UPDATE
命令 - T5:执行
txid=200
和201的事务的SELECT
命令 - T6:提交
txid=200
的事务 - T7:执行
txid=201
的事务的SELECT
命令
为了简化描述,假设这里只有两个事务,即txid=200
和201
的事务。txid=200
的事务的隔离级别是READ COMMITTED
,而txid=201
的事务的隔离级别是READ COMMITTED
或REPEATABLE READ
。
我们将研究SELECT
命令是如何为每条元组执行可见性检查的。
T3的SELECT
命令:
在T3时间点,表tbl
中只有一条元组Tuple_1
,按照规则6,这条元组是可见的,因此两个事务中的SELECT
命令都返回"Jekyll"
。
-
Rule 6(Tuple_1) ⇒ Status(t_xmin:199) = COMMITTED ∧ t_xmax = INVALID ⇒ Visible
创建元组
Tuple_1
的事务199已经提交,且该元组并未被标记删除,因此根据规则6,对当前事务可见。
testdb=# -- txid 200
testdb=# SELECT * FROM tbl;
name
--------
Jekyll
(1 row)
testdb=# -- txid 201
testdb=# SELECT * FROM tbl;
name
--------
Jekyll
(1 row)
T5的SELECT
命令
首先来看一下由txid=200
的事务所执行的SELECT
命令。根据规则7,Tuple_1
不可见,根据规则2,Tuple_2
可见;因此该SELECT
命令返回"Hyde"
。
-
Rule 7(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = IN_PROGRESS ∧ t_xmax:200 = current_txid:200 ⇒ Invisible
创建元组
Tuple_1
的事务199已经提交,且该元组被当前事务标记删除,根据规则7,Tuple_1
对当前事务不可见。 -
Rule 2(Tuple_2): Status(t_xmin:200) = IN_PROGRESS ∧ t_xmin:200 = current_txid:200 ∧ t_xmax = INVAILD ⇒ Visible
创建元组
Tuple_2
的事务200正在进行,而且就是当前事务自己,根据规则2,Tuple_2
对当前事务可见。
testdb=# -- txid 200
testdb=# SELECT * FROM tbl;
name
------
Hyde
(1 row)
另一方面,在由txid=201
的事务所执行的SELECT
命令中,Tuple_1
基于规则8确定可见,而Tuple_2
基于规则4不可见;因此该SELECT
命令返回"Jekyll"
。
-
Rule 8(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = IN_PROGRESS ∧ t_xmax:200 ≠ current_txid:201 ⇒ Visible
元组
Tuple_1
由已提交事务199创建,由活跃事务200标记删除,但删除效果对当前事务201不可见。因此根据规则8,Tuple_1
可见。 -
Rule 4(Tuple_2): Status(t_xmin:200) = IN_PROGRESS ∧ t_xmin:200 ≠ current_txid:201 ⇒ Invisible
元组
Tuple_2
由活跃事务200创建,且不是由当前事务自己创建的,故根据规则4,Tuple_2
不可见。
testdb=# -- txid 201
testdb=# SELECT * FROM tbl;
name
--------
Jekyll
(1 row)
如果更新的元组在本事务提交之前被其他事务看见,这种现象被称为脏读(Dirty Reads),也称为写读冲突(wr-conflicts)。 但如上所示,PostgreSQL中任何隔离级别都不会出现脏读。
T7的SELECT
命令
在下文中,描述了T7的SELECT
命令在两个隔离级别中的行为。
首先来研究txid=201
的事务处于READ COMMITTED
隔离级别时的情况。 在这种情况下,txid=200
的事务被视为已提交,因为在这个时间点获取的事务快照是201:201:
。因此Tuple_1
根据规则10不可见,Tuple_2
根据规则6可见,SELECT
命令返回"Hyde"
。
-
Rule 10(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = COMMITTED ∧ Snapshot(t_xmax:200) ≠ active ⇒ Invisible
元组
Tuple_1
由已提交事务199创建,由非活跃的已提交事务200标记删除,Tuple_1
按照规则10不可见。 -
Rule 6(Tuple_2): Status(t_xmin:200) = COMMITTED ∧ t_xmax = INVALID ⇒ Visible
元组
Tuple_2
由已提交事务200创建,且未被标记为删除,故Tuple_2
按照规则6可见。
testdb=# -- txid 201 (READ COMMITTED)
testdb=# SELECT * FROM tbl;
name
------
Hyde
(1 row)
这里需要注意,事务201中的SELECT
命令,在txid=200
的事务提交前后中时的执行结果是不一样的,这种现象通常被称作不可重复读(Non-Repeatable Read)。
相反的是,当txid=201
的事务处于REPEATABLE READ
级别时,即使在T7时刻txid=200
的事务实际上已经提交,它也必须被视作仍在进行,因而获取到的事务快照是200:200:
。 根据规则9,Tuple_1
是可见的,根据规则5,Tuple_2
不可见,所以最后SELECT
命令会返回"Jekyll"
。 请注意在REPEATABLE READ
(和SERIALIZABLE
)级别中不会发生不可重复读。
-
Rule9(Tuple_1): Status(t_xmin:199) = COMMITTED ∧ Status(t_xmax:200) = COMMITTED ∧ Snapshot(t_xmax:200) = active ⇒ Visible
元组
Tuple_1
由已提交事务199创建,由已提交事务200标记删除,但因为事务200位于当前事物的活跃事务快照中(也就是在当前事物201开始执行并获取事务级快照时,事物200还未提交),因此删除对当前事务尚未生效,根据规则9,Tuple_1
可见。Tuple_1
按照规则10不可见。 -
Rule5(Tuple_2): Status(t_xmin:200) = COMMITTED ∧ Snapshot(t_xmin:200) = active ⇒ Invisible
元组
Tuple_2
由已提交事务200创建,但该事务在本事务快照中属于活跃事务(即在本事务开始前还未提交),因此事务200的变更对本事务尚不可见,按照规则5,Tuple_2
不可见。
testdb=# -- txid 201 (REPEATABLE READ)
testdb=# SELECT * FROM tbl;
name
--------
Jekyll
(1 row)
提示位(Hint Bits)
PostgreSQL在内部提供了三个函数
TransactionIdIsInProgress
,TransactionIdDidCommit
和TransactionIdDidAbort
,用于获取事务的状态。这些函数被设计为尽可能减少对clog的频繁访问。 尽管如此,如果在检查每条元组时都执行这些函数,那这里很可能会成为一个性能瓶颈。为了解决这个问题,PostgreSQL使用了提示位(hint bits),如下所示。
#define HEAP_XMIN_COMMITTED 0x0100 /* 元组xmin对应事务已提交 */ #define HEAP_XMIN_INVALID 0x0200 /* 元组xmin对应事务无效/中止 */ #define HEAP_XMAX_COMMITTED 0x0400 /* 元组xmax对应事务已提交 */ #define HEAP_XMAX_INVALID 0x0800 /* 元组xmax对应事务无效/中止 */
在读取或写入元组时,PostgreSQL会择机将提示位设置到元组的
t_informask
字段中。 举个例子,假设PostgreSQL检查了元组的t_xmin
对应事务的状态,结果为COMMITTED
。 在这种情况下,PostgreSQL会在元组的t_infomask
中置位一个HEAP_XMIN_COMMITTED
标记,表示创建这条元组的事务已经提交了。 如果已经设置了提示位,则不再需要调用TransactionIdDidCommit
和TransactionIdDidAbort
来获取事务状态了。 因此PostgreSQL能高效地检查每个元组t_xmin
和t_xmax
对应事务的状态。
5.7.2 PostgreSQL可重复读等级中的幻读
ANSI SQL-92标准中定义的REPEATABLE READ
隔离等级允许出现幻读(Phantom Reads), 但PostgreSQL实现的REPEATABLE READ
隔离等级不允许发生幻读。 在原则上,快照隔离中不允许出现幻读。
假设两个事务Tx_A
和Tx_B
同时运行。 它们的隔离级别分别为READ COMMITTED
和REPEATABLE READ
,它们的txid
分别为100和101。两个事务一前一后接连开始,首先Tx_A
插入一条元组,并提交。 插入的元组的t_xmin
为100。接着,Tx_B
执行SELECT
命令;但根据规则5,Tx_A
插入的元组对Tx_B
是不可见的。因此不会发生幻读。
-
Rule5(new tuple): Status(t_xmin:100) = COMMITTED ∧ Snapshot(t_xmin:100) = active ⇒ Invisible
新元组由已提交的事务
Tx_A
创建,但Tx_A
在Tx_B
的事务快照中处于活跃状态,因此根据规则5,新元组对Tx_B
不可见。Tx_A: txid = 100
Tx_B: txid = 101
START TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION ISOLATION LEVEL REPEATABLE READ;
INSERT tbl(id, data)
COMMIT;
SELECT * FROM tbl WHERE id=1;
(0 rows)
5.8 防止丢失更新
丢失更新(Lost Update),又被称作写-写冲突(ww-conflict),是事务并发更新同一行时所发生的异常,REPEATABLE READ
和SERIALIZABLE
隔离等级必须阻止该异常的出现。 本节将会介绍PostgreSQL是如何防止丢失更新的,并举一些例子来说明。
5.8.1 并发UPDATE
命令的行为
执行UPDATE
命令时,内部实际上调用了ExecUpdate
函数。 ExecUpdate
的伪代码如下所示:
伪代码:
ExecUpdate
(1) FOR row in 本UPDATE命令待更新的所有行集 (2) WHILE true /* 第一部分 */ (3) IF 目标行 正在 被更新 THEN (4) 等待 更新目标行的事务 结束(提交或中止) (5) IF (更新目标行的事务已提交) AND (当前事务隔离级别是 可重复读或可串行化) THEN (6) 中止当前事务 /* 以先更新者为准 */ ELSE (7) 跳转步骤(2) END IF /* 第二部分 */ (8) ELSE IF 目标行 已经 被另一个并发事务所更新 THEN (9) IF (当前事务的隔离级别是 读已提交 ) THEN (10) 更新目标行 ELSE (11) 中止当前事务 /* 先更新者为准 */ END IF /* 第三部分 */ /* 目标行没有被修改过,或者被一个 已经结束 的事务所更新 */ ELSE (12) 更新目标行 END IF END WHILE END FOR
- 获取被本
UPDATE
命令更新的每一行,并对每一行依次执行下列操作。- 重复以下过程,直到目标行更新完成,或本事务中止。
- 如果目标行正在被更新则进入步骤(4),否则进入步骤(8)。
- 等待正在更新目标行的事务结束,因为PostgreSQL在SI中使用了**以先更新者为准(first-updater-win)**的方案。
- 如果更新目标行的事务已经提交,且当前事务的隔离等级为可重复读或可串行化则进入步骤(6),否则进入步骤(7)。
- 中止本事务,以防止丢失更新。(因为另一个事务已经对目标行进行了更新并提交)
- 跳转回步骤(2),并对目标行进行新一轮的更新尝试。
- 如果目标行已被另一个并发事务所更新则进入步骤(9),否则进入步骤(12)。
- 如果当前事务的隔离级别为读已提交则进入步骤(10),否则进入步骤(11)。
- 更新目标行,并回到步骤(1),处理下一条目标行。
- 中止当前事务,以防止丢失更新。
- 更新目标行,并回到步骤(1),因为目标行尚未被修改过,或者虽然已经被更新,但更新它的事务已经结束。已终止的事务更新,即存在写写冲突。
此函数依次为每个待更新的目标行执行更新操作。 它有一个外层循环来更新每一行,而内部while循环则包含了三个分支,分支条件如图5.11所示。
图5.11 ExecUpdate
内部的三个部分
-
目标行正在被更新,如图5.11[1]所示
“正在被更新”意味着该行正在被另一个事务同时更新,且另一个事务尚未结束。在这种情况下,当前事务必须等待更新目标行的事务结束,因为PostgreSQL的SI实现采用**以先更新者为准(first-updater-win)**的方案。例如,假设事务
Tx_A
和Tx_B
同时运行,且Tx_B
尝试更新某一行;但Tx_A
已更新了这一行,且仍在进行中。在这种情况下Tx_B
会等待Tx_A
结束。在更新目标行的事务提交后,当前事务的更新操作将完成等待继续进行。如果当前事务处于
READ COMMITTED
隔离等级,则会更新目标行;而若处于REPEATABLE READ
或SERIALIZABLE
隔离等级时,当前事务则会立即中止,以防止丢失更新。 -
目标行已经被另一个并发事务所更新,如图5.11[2]所示
当前事务尝试更新目标元组,但另一个并发事务已经更新了目标行并提交。在这种情况下,如果当前事务处于
READ COMMITTED
级别,则会更新目标行;否则会立即中止以防止丢失更新。 -
没有冲突,如图5.11[3]所示
当没有冲突时,当前事务可以直接更新目标行。
以先更新者为准 / 以先提交者为准
PostgreSQL基于SI的并发控制机制采用**以先更新者为准(first-updater-win)方案。 相反如下一节所述,PostgreSQL的SSI实现使用以先提交者为准(first-commiter-win)**方案。
5.8.2 例子
以下是三个例子。 第一个和第二个例子展示了目标行正在被更新时的行为,第三个例子展示了目标行已经被更新的行为。
例1
事务Tx_A
和Tx_B
更新同一张表中的同一行,它们的隔离等级均为READ COMMITTED
。
Tx_A |
Tx_B |
---|---|
START TRANSACTION ISOLATION LEVEL READ COMMITTED; |
|
START TRANSACTION |
START TRANSACTION ISOLATION LEVEL READ COMMITTED; |
START TRANSACTION |
|
UPDATE tbl SET name = 'Hyde'; |
|
UPDATE 1 |
|
UPDATE tbl SET name = 'Utterson'; |
|
↓ – 本事务进入阻塞状态,等待Tx_A 完成 |
|
COMMIT; |
↓ – Tx_A 提交,阻塞解除 |
UPDATE 1 |
Tx_B
的执行过程如下:
- 在执行
UPDATE
命令之后,Tx_B
应该等待Tx_A
结束,因为目标元组正在被Tx_A
更新(ExecUpdate
步骤4) - 在
Tx_A
提交后,Tx_B
尝试更新目标行(ExecUpdate
步骤7) - 在
ExecUpdate
内循环第二轮中,目标行被Tx_B
更新(ExecUpdate
步骤2,8,9,10)。
例2
Tx_A
和Tx_B
更新同一张表中的同一行,它们的隔离等级分别为读已提交和可重复读。
Tx_A |
Tx_B |
---|---|
START TRANSACTION ISOLATION LEVEL READ COMMITTED; |
|
START TRANSACTION |
START TRANSACTION ISOLATION LEVEL REPEATABLE READ; |
START TRANSACTION |
|
UPDATE tbl SET name = 'Hyde'; |
|
UPDATE 1 |
|
UPDATE tbl SET name = 'Utterson'; |
|
↓ – 本事务进入阻塞状态,等待Tx_A 完成 |
|
COMMIT; |
↓ – Tx_A 提交,阻塞解除 |
ERROR:couldn't serialize access due to concurrent update |
Tx_B
的执行过程如下:
Tx_B
在执行UPDATE
命令后阻塞,等待Tx_A
终止(ExecUpdate
步骤4)。- 当
Tx_A
提交后,Tx_B
会中止以解决冲突。因为目标行已经被更新,且当前事务Tx_B
的隔离级别为可重复读(ExecUpdate
步骤5,6)。
例3
Tx_B
(可重复读)尝试更新已经被Tx_A
更新的目标行,且Tx_A
已经提交。 在这种情况下,Tx_B
会中止(ExecUpdate
中的步骤2,8,9,11)。
Tx_A |
Tx_B |
---|---|
START TRANSACTION ISOLATION LEVEL READ COMMITTED; |
|
START TRANSACTION |
START TRANSACTION ISOLATION LEVEL REPEATABLE READ; |
START TRANSACTION |
|
UPDATE tbl SET name = 'Hyde'; |
|
UPDATE 1 |
|
COMMIT; |
|
UPDATE tbl SET name = 'Utterson'; |
|
ERROR:couldn't serialize access due to concurrent update |
5.9 可串行化快照隔离
从版本9.1开始,可串行化快照隔离(SSI)已经嵌入到快照隔离(SI)中,用以实现真正的可串行化隔离等级。SSI解释起来过于复杂,故本书仅解释其概要,详细信息请参阅文献[2]。
下文使用了以下技术术语而未加定义。 如果读者不熟悉这些术语,请参阅[1,3]。
- 前趋图(precedence graph),亦称作依赖图(dependency graph)或串行化图(serialization graph)
- 串行化异常(serialization anomalies)(例如,写偏差(Write-Skew))
5.9.1 SSI实现的基本策略
如果前趋图中存在由某些冲突构成的环,则会出现串行化异常。 这里使用一种最简单的异常来解释,即写偏差(Write-Skew)。
图5.12(1)展示了一种调度方式。 这里Transaction_A
读取了Tuple_B
,Transaction_B
读取了Tuple_A
。 然后Transaction_A
写Tuple_A
,Transaction_B
写Tuple_B
。 在这种情况下存在两个读-写冲突(rw-conflict),它们在该调度的前趋图中构成了一个环,如图5.12(2)所示。 故该调度存在串行化异常,即写偏差。
图5.12 存在写偏差的调度及其前趋图
从概念上讲,存在三种类型的冲突:写-读冲突(wr-conflicts)(脏读),写-写冲突(ww-conflicts)(丢失更新),以及读写冲突(rw-conflicts)。 但是这里无需考虑写-读冲突与写-写冲突,因为如前所述,PostgreSQL可以防止此类冲突。 因此PostgreSQL中的SSI实现只需要考虑读-写冲突。
PostgreSQL在SSI实现中采用以下策略:
- 使用SIREAD锁记录事务访问的所有对象(元组,页面,关系)。
- 当写入任何堆元组/索引元组时,使用SIREAD锁检测读-写冲突。
- 如果从读-写冲突中检测出串行化异常,则中止事务。
5.9.2 PostgreSQL的SSI实现
为了实现上述策略,PostgreSQL实现了很多数据结构与函数。 但这里我们只会使用两种数据结构:SIREAD锁与读-写冲突来描述SSI机制。它们都储存在共享内存中。
为简单起见,本文省略了一些重要的数据结构,例如
SERIALIZABLEXACT
。 因此对CheckTargetForConflictOut
,CheckTargetForConflictIn
和PreCommit_CheckForSerializationFailure
等函数的解释也极为简化。比如本文虽然指出哪些函数能检测到冲突;但并没有详细解释如何检测冲突。 如果读者想了解详细信息,请参阅源代码:predicate.c。
SIREAD锁
SIREAD锁,在内部又被称为谓词锁(predicate lock),是一个由对象与(虚拟)事务标识构成的二元组,存储着哪个事务访问了哪个对象的相关信息。注意这里省略了对虚拟事务标识的描述,使用txid
而非虚拟txid
能大幅简化说明。
在SERIALIZABLE
模式下只要执行DML命令,就会通过CheckTargetForConflictsOut
函数创建出SIREAD锁。举个例子,如果txid=100
的事务读取给定表的Tuple_1
,则会创建一个SIREAD锁{Tuple_1,{100}}
。如果是其他事务,例如txid=101
读取了Tuple_1
,则SIREAD锁会更新为{Tuple_1,{100,101}}
。请注意,读取索引页时也会创建SIREAD锁,因为在使用了第7.2节中将描述的**仅索引扫描(Index-Only Scan)**时,数据库只会读取索引页而不读取表页。
SIREAD锁有三个级别:元组,页面,以及关系。如果单个页面内所有元组的SIREAD锁都被创建,则它们会聚合为该页上的单个SIREAD锁,原有相关元组上的SIREAD锁都会被释放(删除),以减少内存空间占用。对读取的页面也是同理。
当为索引创建SIREAD锁时,一开始会创建页级别的SIREAD锁。当使用顺序扫描时,无论是否存在索引,是否存在WHERE
子句,一开始都会创建关系级别的SIREAD锁。请注意在某些情况下,这种实现可能会导致串行化异常的误报(假阳性(false-positive)),细节将在第5.9.4节中描述。
读-写冲突
读-写冲突是一个三元组,由SIREAD锁,以及两个分别读写该SIREAD锁的事务txid
构成。
当在可串行化模式下执行INSERT
,UPDATE
或DELETE
命令时,函数CheckTargetForConflictsIn
会被调用,并检查SIREAD锁来检测是否存在冲突,如果有就创建一个读-写冲突。
举个例子,假设txid = 100
的事务读取了Tuple_1
,然后txid=101
的事务更新了Tuple_1
。在这种情况下,txid=101
的事务中的UPDATE
命令会调用CheckTargetForConflictsIn
函数,并检测到在Tuple_1
上存在txid=100,101
之间的读-写冲突,并创建rw-conflict{r = 100, w = 101, {Tuple_1}}
。
CheckTargetForConflictOut
、CheckTargetForConflictIn
函数,以及在可串行化模式中执行COMMIT
命令会触发的PreCommit_CheckForSerializationFailure
函数,都会使用创建的读写冲突来检查串行化异常。如果它们检测到异常,则只有先提交的事务会真正提交,其他事务会中止(依据**以先提交者为准(first-committer-win)**策略)。
5.9.3 SSI的原理
本节将描述SSI如何解决写偏差异常,下面将使用一个简单的表tbl
为例。
testdb=# CREATE TABLE tbl (id INT primary key, flag bool DEFAULT false);
testdb=# INSERT INTO tbl (id) SELECT generate_series(1,2000);
testdb=# ANALYZE tbl;
事务Tx_A
和Tx_B
执行以下命令,如图5.13所示。
图5.13 写偏差场景一例
假设所有命令都使用索引扫描。 因此当执行命令时,它们会同时读取堆元组与索引页,每个索引页都包含指向相应堆元组的索引元组,如图5.14所示。
图5.14 例子中索引与表的关系
- T1:
Tx_A
执行SELECT
命令,该命令读取堆元组Tuple_2000
,以及包含主键的索引页Pkey_2
。 - T2:
Tx_B
执行SELECT
命令。 此命令读取堆元组Tuple_1
,以及包含主键的索引页Pkey_1
。 - T3:
Tx_A
执行UPDATE
命令,更新Tuple_1
。 - T4:
Tx_B
执行UPDATE
命令,更新Tuple_2000
。 - T5:
Tx_A
提交。 - T6:
Tx_B
提交,然而由于写偏差异常而被中止。
图5.15展示了PostgreSQL如何检测和解决上述场景中描述的写偏差异常。
图5.15 SIREA锁与读-写冲突,图5.13场景中的调度方式
-
T1: 执行
Tx_A
的SELECT
命令时,CheckTargetForConflictsOut
会创建SIREAD锁。在本例中该函数会创建两个SIREAD锁:L1
与L2
。L1
和L2
分别与Pkey_2
和Tuple_2000
相关联。 -
T2: 执行
Tx_B
的SELECT
命令时,CheckTargetForConflictsOut
会创建两个SIREAD锁:L3
和L4
。L3
和L4
分别与Pkey_1
和Tuple_1
相关联。 -
T3: 执行
Tx_A
的UPDATE
命令时,CheckTargetForConflictsOut
和CheckTargetForConflictsIN
会分别在ExecUpdate
执行前后被调用。在本例中,CheckTargetForConflictsOut
什么都不做。而CheckTargetForConflictsIn
则会创建读-写冲突C1
,这是Tx_B
和Tx_A
在Pkey_1
和Tuple_1
上的冲突,因为Pkey_1
和Tuple_1
都由Tx_B
读取并被Tx_A
写入。 -
T4: 执行
Tx_B
的UPDATE
命令时,CheckTargetForConflictsIn
会创建读-写冲突C2
,这是Tx_A
与Tx_B
在Pkey_2
和Tuple_2000
上的冲突。在这种情况下,
C1
和C2
在前趋图中构成一个环;因此Tx_A
和Tx_B
处于不可串行化状态。但事务Tx_A
和Tx_B
都尚未提交,因此CheckTargetForConflictsIn
不会中止Tx_B
。注意这是因为PostgreSQL的SSI实现采用先提交者为准方案。 -
T5: 当
Tx_A
尝试提交时,将调用PreCommit_CheckForSerializationFailure
。此函数可以检测串行化异常,并在允许的情况下执行提交操作。在这里因为Tx_B
仍在进行中,Tx_A
成功提交。 -
T6: 当
Tx_B
尝试提交时,PreCommit_CheckForSerializationFailure
检测到串行化异常,且Tx_A
已经提交;因此Tx_B
被中止。
此外,如果在Tx_A
提交之后(T5时刻),Tx_B
执行了UPDATE
命令,则Tx_B
会立即中止。因为Tx_B
的UPDATE
命令会调用CheckTargetForConflictsIn
,并检测到串行化异常,如图5.16(1)所示。
如果Tx_B
在T6时刻执行SELECT
命令而不是COMMIT
命令,则Tx_B
也会立即中止。因为Tx_B
的SELECT
命令调用的CheckTargetForConflictsOut
会检测到串行化异常,如图5.16(2)所示。
图5.16 其他写偏差场景
这里的Wiki解释了几种更为复杂的异常。
5.9.4 假阳性的串行化异常
在可串行化模式下,因为永远不会检测到**假阴性(false-negative,发生异常但未检测到)**串行化异常,PostgreSQL能始终完全保证并发事务的可串行性。 但相应的是在某些情况下,可能会检测到假阳性异常(没有发生异常但误报发生),用户在使用SERIALIZABLE
模式时应牢记这一点。 下文会描述PostgreSQL检测到假阳性异常的情况。
图5.17展示了发生假阳性串行化异常的情况。
图5.17 发生假阳性串行化异常的场景
当使用顺序扫描时,如SIREAD锁的解释中所述,PostgreSQL创建了一个关系级的SIREAD锁。 图5.18(1)展示了PostgreSQL使用顺序扫描时的SIREAD锁和读-写冲突。 在这种情况下,产生了与tbl
表上SIREAD锁相关联的读-写冲突:C1
和C2
,并且它们在前趋图中构成了一个环。 因此会检测到假阳性的写偏差异常(即,虽然实际上没有冲突,但Tx_A
与Tx_B
两者之一也将被中止)。
图 5.18 假阳性异常(1) - 使用顺序扫描
即使使用索引扫描,如果事务Tx_A
和Tx_B
都获取里相同的索引SIREAD锁,PostgreSQL也会误报假阳性异常。 图5.19展示了这种情况。 假设索引页Pkey_1
包含两条索引项,其中一条指向Tuple_1
,另一条指向Tuple_2
。 当Tx_A
和Tx_B
执行相应的SELECT
和UPDATE
命令时,Pkey_1
同时被Tx_A
和Tx_B
读取与写入。 这时候会产生Pkey_1
相关联的读-写冲突:C1
和C2
,并在前趋图中构成一个环,因而检测到假阳性写偏差异常(如果Tx_A
和Tx_B
获取不同索引页上的SIREAD锁则不会误报,并且两个事务都可以提交)。
图5.19 假阳性异常(2) - 使用相同索引页的索引扫描
5.10 所需的维护进程
PostgreSQL的并发控制机制需要以下维护过程。
- 删除死元组及指向死元组的索引元组
- 移除**提交日志(clog)**中非必需的部分
- 冻结旧的事务标识(txid)
- 更新FSM,VM,以及统计信息
第5.3.2和5.4.3节分别解释了为什么需要第一个和第二个过程。第三个过程与事务标识回卷问题有关,本小节将概述**事务标识回卷(txid wrap around)**问题。
在PostgreSQL中,清理过程(VACUUM
)负责这些过程。**清理过程(VACUUM)**在第6章中描述。
5.10.1 冻结处理
接下来将介绍**事务标识回卷(txid wrap around)**问题。
假设元组Tuple_1
是由txid = 100
事务创建的,即Tuple_1
的t_xmin = 100
。服务器运行了很长时间,但Tuple_1
一直未曾被修改。假设txid
已经前进到了$2^{31}+100$,这时候正好执行了一条SELECT
命令。此时,因为对当前事务而言txid = 100
的事务属于过去的事务,因而Tuple_1
对当前事务可见。然后再执行相同的SELECT
命令,此时txid
步进至$2^{31}+101$。但因对当前事务而言,txid = 100
的事务是属于未来的,因此Tuple_1
不再可见(图5.20)。这就是PostgreSQL中所谓的事务回卷问题。
图5.20 回卷问题
为了解决这个问题,PostgreSQL引入了一个**冻结事务标识(Frozen txid)**的概念,并实现了一个名为FREEZE
的过程。
在PostgreSQL中定义了一个冻结的txid
,它是一个特殊的保留值txid = 2
,在参与事务标识大小比较时,它总是比所有其他txid
都旧。换句话说,冻结的txid
始终处于非活跃状态,且其结果对其他事务始终可见。
清理过程(VACUUM
)会调用冻结过程(FREEZE
)。冻结过程将扫描所有表文件,如果元组的t_xmin
比当前txid - vacuum_freeze_min_age
(默认值为5000万)更老,则将该元组的t_xmin
重写为冻结事务标识。在第6章中会有更详细的解释。
举个例子,如图5.21(a)所示,当前txid
为5000万,此时通过VACUUM
命令调用冻结过程。在这种情况下,Tuple_1
和Tuple_2
的t_xmin
都被重写为2。
在版本9.4或更高版本中使用元组t_infomask
字段中的XMIN_FROZEN
标记位来标识冻结元组,而不是将元组的t_xmin
重写为冻结的txid
,如图5.21(b)所示。
图5.21 冻结过程
参考文献
- [1] Abraham Silberschatz, Henry F. Korth, and S. Sudarshan, “Database System Concepts”, McGraw-Hill Education, ISBN-13: 978-0073523323
- [2] Dan R. K. Ports, and Kevin Grittner, “Serializable Snapshot Isolation in PostgreSQL”, VDBL 2012
- [3] Thomas M. Connolly, and Carolyn E. Begg, “Database Systems”, Pearson, ISBN-13: 978-0321523068
第六章 垃圾清理过程
**清理(VACUUM)**是一种维护过程,有助于PostgreSQL的持久运行。它的两个主要任务是删除死元组,以及冻结事务标识,两者都在第5.10节中简要提到过。
为了移除死元组,清理过程有两种模式:并发清理(Concurrent Vacuum) 与完整清理(Full Vacuum) 。并发清理(通常简称为VACUUM
)会删除表文件每个页面中的死元组,而其他事务可以在其运行时继续读取该表。相反,完整清理不仅会移除整个文件中所有的死元组,还会对整个文件中所有的活元组进行碎片整理。而其他事务在完整清理运行时无法访问该表。
尽管清理过程对PostgreSQL至关重要,但与其他功能相比,它的改进相对其他功能而言要慢一些。例如在8.0版本之前,清理过程必须手动执行(通过psql
实用程序或使用cron
守护进程)。直到2005年实现了autovacuum
守护进程时,这一过程才实现了自动化。
由于清理过程涉及到全表扫描,因此该过程代价高昂。在版本8.4(2009)中引入了**可见性映射(Visibility Map, VM)**来提高移除死元组的效率。在版本9.6(2016)中增强了VM,从而改善了冻结过程的表现。
6.1节概述了并发清理的过程,而后续部分的内容如下所示:
- 可见性映射
- **冻结(Freeze)**过程
- 移除不必要的clog文件
- **自动清理(AutoVacuum)**守护进程
- 完整清理
6.1 并发清理概述
清理过程为指定的表,或数据库中的所有表执行以下任务。
- 移除死元组
- 移除每一页中的死元组,并对每一页内的活元组进行碎片整理。
- 移除指向死元组的索引元组。
- 冻结旧的事务标识(
txid
)- 如有必要,冻结旧元组的事务标识(txid)。
- 更新与冻结事务标识相关的系统视图(
pg_database
与pg_class
)。 - 如果可能,移除非必需的提交日志(clog)。
- 其他
- 更新已处理表的空闲空间映射(FSM)和可见性映射(VM)。
- 更新一些统计信息(
pg_stat_all_tables
等)。
这里假设读者已经熟悉以下术语:死元组,冻结事务标识,FSM,clog;如果读者不熟悉这些术语的含义,请参阅第5章。VM将在第6.2节中介绍。
以下伪代码描述了清理的过程。
伪码:并发清理
(1) FOR each table (2) 在目标表上获取 ShareUpdateExclusiveLock 锁 /* 第一部分 */ (3) 扫描所有页面,定位死元组;如有必要,冻结过老的元组。 (4) 如果存在,移除指向死元组的索引元组。 /* 第二部分 */ (5) FOR each page of the table (6) 移除死元组,重排本页内的活元组。 (7) 更新 FSM 与 VM END FOR /* 第三部分 */ (8) 如果可能,截断最后的页面。 (9) 更新系统数据字典与统计信息 释放ShareUpdateExclusiveLock锁 END FOR /* 后续处理 */ (10) 更新统计信息与系统数据字典 (11) 如果可能,移除没有必要的文件,以及clog中的文件。
- 从指定的表集中依次处理每一张表。
- 获取表上的
ShareUpdateExclusiveLock
锁, 此锁允许其他事务对该表进行读取。- 扫描表中所有的页面,以获取所有的死元组,并在必要时冻结旧元组。
- 删除指向相应死元组的索引元组(如果存在)。
- 对表的每个页面执行步骤(6)和(7)中的操作
- 移除死元组,并重新分配页面中的活元组。
- 更新目标表对应的FSM与VM。
- 如果最后一个页面没有任何元组,则截断最后一页。
- 更新与目标表清理过程相关的统计数据和系统视图。
- 更新与清理过程相关的统计数据和系统视图。
- 如果可能,移除clog中非必需的文件与页面。
该伪码分为两大块:一块是依次处理表的循环,一块是后处理逻辑。而循环块又能分为三个部分,每一个部分都有各自的任务。接下来会描述这三个部分,以及后处理的逻辑。
6.1.1 第一部分
这一部分执行冻结处理,并删除指向死元组的索引元组。
首先,PostgreSQL扫描目标表以构建死元组列表,如果可能的话,还会冻结旧元组。该列表存储在本地内存中的maintenance_work_mem
里(维护用的工作内存)。冻结处理将在第6.3节中介绍。
扫描完成后,PostgreSQL根据构建得到的死元组列表来删除索引元组。该过程在内部被称为“清除阶段(cleanup stage)”。不用说,该过程代价高昂。在10或更早版本中始终会执行清除阶段。在11或更高版本中,如果目标索引是B树,是否执行清除阶段由配置参数vacuum_cleanup_index_scale_factor
决定。详细信息请参考此参数的说明。
当maintenance_work_mem
已满,且未完成全部扫描时,PostgreSQL继续进行后续任务,即步骤4到7;完成后再重新返回步骤3并继续扫描。
6.1.2 第二部分
这一部分会移除死元组,并逐页更新FSM和VM。图6.1展示了一个例子:
图6.1 删除死元组
假设该表包含三个页面,这里先关注0号页面(即第一个页面)。该页面包含三条元组, 其中
Tuple_2
是一条死元组,如图6.1(1)所示。在这里PostgreSQL移除了Tuple_2
,并重排剩余元组来整理碎片空间,然后更新该页面的FSM和VM,如图6.1(2)所示。 PostgreSQL不断重复该过程直至最后一页。
请注意,非必需的行指针是不会被移除的,它们会在将来被重用。因为如果移除了行指针,就必须同时更新所有相关索引中的索引元组。
6.1.3 第三部分
第三部分会针对每个表,更新与清理过程相关的统计信息和系统视图。
此外,如果最后一页中没有元组,则该页会从表文件中被截断。
6.1.4 后续处理
当处理完成后,PostgreSQL会更新与清理过程相关的几个统计数据,以及相关的系统视图;如果可能的话,它还会移除部分非必需的clog(第6.4节)。
清理过程使用8.5节中将描述的环形缓冲区(ring buffer)。因此处理过的页面不会缓存在共享缓冲区中。
6.2 可见性映射
清理过程的代价高昂,因此PostgreSQL在8.4版中引入了VM,用于减小清理的开销。
VM的基本概念很简单。 每个表都拥有各自的可见性映射,用于保存表文件中每个页面的可见性。 页面的可见性确定了每个页面是否包含死元组。清理过程可以跳过没有死元组的页面。
图6.2展示了VM的使用方式。 假设该表包含三个页面,第0页和第2页包含死元组,而第1页不包含死元组。 表的可见性映射中保存着哪些页面包含死元组的信息。 在这种情况下,清理过程可以参考VM中的信息,跳过第一个页面。
图6.2 VM的使用方式
每个VM由一个或多个8 KB页面组成,文件以后缀_vm
存储。 例如,一个表文件的relfilenode
是18751,其FSM(18751_fsm
)和VM(18751_vm
)文件如下所示。
$ 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
6.2.1 可见性映射的改进
可见性映射在9.6版中进行了加强,以提高冻结处理的效率。新的VM除了显示页面可见性之外,还包含了页面中元组是否全部冻结的信息,参见第6.3.3节。
6.3 冻结过程
冻结过程有两种模式,依特定条件而择其一执行。为方便起见,将这两种模式分别称为惰性模式(lazy mode)和迫切模式(eager mode)。
**并发清理(Concurrent VACUUM)通常在内部被称为“惰性清理(lazy vacuum)”。但是,本文中定义的惰性模式是冻结过程(Freeze Processing)**执行的模式。
冻结过程通常以惰性模式运行;但当满足特定条件时,也会以迫切模式运行。在惰性模式下,冻结处理仅使用目标表对应的VM扫描包含死元组的页面。迫切模式相则反,它会扫描所有的页面,无论其是否包含死元组,它还会更新与冻结处理相关的系统视图,并在可能的情况下删除不必要的clog。
第6.3.1和6.3.2节分别描述了这两种模式;第6.3.3节描述了改进后的迫切模式冻结过程。
6.3.1 惰性模式
当开始冻结处理时,PostgreSQL计算freezeLimit_txid
,并冻结t_xmin
小于freezeLimit_txid
的元组。
freezeLimit_txid
定义如下:
$$
\begin{align}
\verb|freezeLimit_txid| = (\verb|OldestXmin| - \verb|vacuum_freeze_min_age|)
\end{align}
$$
而OldestXmin
是当前正在运行的事务中最早的事务标识(txid)。 举个例子,如果在执行VACUUM
命令时,还有其他三个事务正在运行,且其txid
分别为100,101,102
,那么这里OldestXmin
就是100。如果不存在其他事务,OldestXmin
就是执行此VACUUM
命令的事务标识。 这里vacuum_freeze_min_age
是一个配置参数(默认值为50,000,000
)。
图6.3给出了一个具体的例子。这里Table_1
由三个页面组成,每个页面包含三条元组。 执行VACUUM
命令时,当前txid
为50,002,500
且没有其他事务。在这种情况下,OldestXmin
就是50,002,500
;因此freezeLimit_txid
为2500
。冻结过程按照如下步骤执行。
图6.3 冻结元组——惰性模式
-
第0页:
三条元组被冻结,因为所有元组的
t_xmin
值都小于freezeLimit_txid
。此外,因为Tuple_1
是一条死元组,因而在该清理过程中被移除。 -
第1页:
通过引用可见性映射(从VM中发现该页面所有元组都可见),清理过程跳过了对该页面的清理。
-
第2页:
Tuple_7
和Tuple_8
被冻结,且Tuple_7
被移除。
在完成清理过程之前,与清理相关的统计数据会被更新,例如pg_stat_all_tables
视图中的n_live_tup
,n_dead_tup
,last_vacuum
,vacuum_count
等字段。
如上例所示,因为惰性模式可能会跳过页面,它可能无法冻结所有需要冻结的元组。
6.3.2 迫切模式
迫切模式弥补了惰性模式的缺陷。它会扫描所有页面,检查表中的所有元组,更新相关的系统视图,并在可能时删除非必需的clog文件与页面。
当满足以下条件时,会执行迫切模式。
$$
\begin{align}
\verb|pg_database.datfrozenxid| < (\verb|OldestXmin| - \verb|vacuum_freeze_table_age|)
\end{align}
$$
在上面的条件中,pg_database.datfrozenxid
是系统视图pg_database
中的列,并保存着每个数据库中最老的已冻结的事务标识。细节将在后面描述;因此这里我们假设所有pg_database.datfrozenxid
的值都是1821
(这是在9.5版本中安装新数据库集群之后的初始值)。 vacuum_freeze_table_age
是配置参数(默认为150,000,000
)。
图6.4给出了一个具体的例子。在表1中,Tuple_1
和Tuple_7
都已经被删除。Tuple_10
和Tuple_11
则已经插入第2页中。执行VACUUM
命令时的事务标识为150,002,000
,且没有其他事务。因此,OldestXmin=150,002,000
,freezeLimit_txid=100,002,000
。在这种情况下满足了上述条件:因为1821 < (150002000 - 150000000)
,因而冻结过程会以迫切模式执行,如下所示。
(注意,这里是版本9.5或更早版本的行为;最新版本的行为将在第6.3.3节中描述。)
图6.4 冻结旧元组——迫切模式(9.5或更早版本)
-
第0页:
即使所有元组都被冻结,也会检查
Tuple_2
和Tuple_3
。 -
第1页:
此页面中的三条元组都会被冻结,因为所有元组的
t_xmin
值都小于freezeLimit_txid
。注意在惰性模式下会跳过此页面。 -
第2页:
将
Tuple_10
冻结,而Tuple_11
没有冻结。
冻结一张表后,目标表的pg_class.relfrozenxid
将被更新。 pg_class
是一个系统视图,每个pg_class.relfrozenxid
列都保存着相应表的最近冻结的事务标识。本例中表1的pg_class.relfrozenxid
会被更新为当前的freezeLimit_txid
(即100,002,000
),这意味着表1中t_xmin
小于100,002,000
的所有元组都已被冻结。
在完成清理过程之前,必要时会更新pg_database.datfrozenxid
。每个pg_database.datfrozenxid
列都包含相应数据库中的最小pg_class.relfrozenxid
。例如,如果在迫切模式下仅仅对表1做冻结处理,则不会更新该数据库的pg_database.datfrozenxid
,因为其他关系的pg_class.relfrozenxid
(当前数据库可见的其他表和系统视图)还没有发生变化,如图6.5(1)所示。如果当前数据库中的所有关系都以迫切模式冻结,则数据库的pg_database.datfrozenxid
就会被更新,因为此数据库的所有关系的pg_class.relfrozenxid
都被更新为当前的freezeLimit txid
,如图6.5(2)所示。
图6.5 pg_database.datfrozenxid
与pg_class.relfrozenxid
之间的关系
如何显示
pg_class.relfrozenxid
与pg_database.datfrozenxid
如下所示,第一个查询显示
testdb
数据库中所有可见关系的relfrozenxid
,第二个查询显示testdb
数据库的pg_database.datfrozenxld
。testdb=# VACUUM table_1; VACUUM testdb=# SELECT n.nspname as "Schema", c.relname as "Name", c.relfrozenxid FROM pg_catalog.pg_class c LEFT JOIN pg_catalog.pg_namespace n ON n.oid = c.relnamespace WHERE c.relkind IN ('r','') AND n.nspname <> 'information_schema' AND n.nspname !~ '^pg_toast' AND pg_catalog.pg_table_is_visible(c.oid) ORDER BY c.relfrozenxid::text::bigint DESC; Schema | Name | relfrozenxid ------------+-------------------------+-------------- public | table_1 | 100002000 public | table_2 | 1846 pg_catalog | pg_database | 1827 pg_catalog | pg_user_mapping | 1821 pg_catalog | pg_largeobject | 1821 ... pg_catalog | pg_transform | 1821 (57 rows) testdb=# SELECT datname, datfrozenxid FROM pg_database WHERE datname = 'testdb'; datname | datfrozenxid ---------+-------------- testdb | 1821 (1 row)
FREEZE
选项带有
FREEZE
选项的VACUUM
命令会强制冻结指定表中的所有事务标识。虽然这是在迫切模式下执行的,但这里freezeLimit
会被设置为OldestXmin
(而不是OldestXmin - vacuum_freeze_min_age
)。 例如当txid=5000
的事务执行VACUUM FULL
命令,且没有其他正在运行的事务时,OldesXmin
会被设置为5000,而t_xmin
小于5000的元组将会被冻结。
6.3.3 改进迫切模式中的冻结过程
9.5或更早版本中的迫切模式效率不高,因为它始终会扫描所有页面。 比如在第6.3.2节的例子中,尽管第0页中所有元组都被冻结,但也会被扫描。
为了解决这一问题,9.6版本改进了可见性映射VM与冻结过程。如第6.2.1节所述,新VM包含着每个页面中所有元组是否都已被冻结的信息。在迫切模式下进行冻结处理时,可以跳过仅包含冻结元组的页面。
图6.6给出了一个例子。 根据VM中的信息,冻结此表时会跳过第0页。在更新完1号页面后,相关的VM信息会被更新,因为该页中所有的元组都已经被冻结了。
图6.6 冻结旧元组——迫切模式(9.6或更高版本)
6.4 移除不必要的提交日志文件
如5.4节中所述,**提交日志(clog)**存储着事务的状态。 当更新pg_database.datfrozenxid
时,PostgreSQL会尝试删除不必要的clog文件。 注意相应的clog页面也会被删除。
图6.7给出了一个例子。 如果clog文件0002
中包含最小的pg_database.datfrozenxid
,则可以删除旧文件(0000
和0001
),因为存储在这些文件中的所有事务在整个数据库集簇中已经被视为冻结了。
图6.7 删除不必要的clog文件和页面
pg_database.datfrozenxid
与clog文件下面展示了
pg_database.datfrozenxid
与clog文件的实际输出$ psql testdb -c "SELECT datname, datfrozenxid FROM pg_database" datname | datfrozenxid -----------+-------------- template1 | 7308883 template0 | 7556347 postgres | 7339732 testdb | 7506298 (4 rows) $ ls -la -h data/pg_clog/ # 10或更新的版本, "ls -la -h data/pg_xact/" total 316K drwx------ 2 postgres postgres 28 Dec 29 17:15 . drwx------ 20 postgres postgres 4.0K Dec 29 17:13 .. -rw------- 1 postgres postgres 256K Dec 29 17:15 0006 -rw------- 1 postgres postgres 56K Dec 29 17:15 0007
6.5 自动清理守护进程
**自动清理(AutoVacuum)**守护进程已经将清理过程自动化,因此PostgreSQL运维起来非常简单。
自动清理守护程序周期性地唤起几个autovacuum_worker
进程,默认情况下会每分钟唤醒一次(由参数autovacuum_naptime
定义),每次唤起三个工作进程(由autovacuum_max_works
定义)。
自动清理守护进程唤起的autovacuum
工作进程会依次对各个表执行并发清理,从而将对数据库活动的影响降至最低。
关于如何维护
AUTOVACUUM
参考文章:[PostgreSQL中的Autovacuum调参,Autovacuum内幕][https://www.percona.com/blog/2018/08/10/tuning-autovacuum-in-postgresql-and-autovacuum-internals/]
6.6 完整清理(FULL VACUUM
)
虽然并发清理对于运维至关重要,但光有它还不够。比如,即使删除了许多死元组,也无法压缩表大小的情况。
图6.8给出了一个极端的例子。假设一个表由三个页面组成,每个页面包含六条元组。执行以下DELETE
命令以删除元组,并执行VACUUM
命令以移除死元组:
图6.8 并发清理的缺陷示例
testdb=# DELETE FROM tbl WHERE id % 6 != 0;
testdb=# VACUUM tbl;
死元组虽然都被移除了,但表的尺寸没有减小。 这种情况既浪费了磁盘空间,又会对数据库性能产生负面影响。 例如在上面的例子中,当读取表中的三条元组时,必须从磁盘加载三个页面。
为了解决这种情况,PostgreSQL提供了完整清理模式。 图6.9概述了该模式。
图6.9 完整清理模式概述
-
创建新的表文件:见图6.9(1)
当对表执行
VACUUM FULL
命令时,PostgreSQL首先获取表上的AccessExclusiveLock
锁,并创建一个大小为8 KB的新的表文件。AccessExclusiveLock
锁不允许任何其他访问。 -
将活元组复制到新表:见图6.9(2)
PostgreSQL只将旧表文件中的活元组复制到新表中。
-
删除旧文件,重建索引,并更新统计信息,FSM和VM,见图6.9(3)
复制完所有活元组后,PostgreSQL将删除旧文件,重建所有相关的表索引,更新表的FSM和VM,并更新相关的统计信息和系统视图。
完整清理的伪代码如下所示:
伪代码:完整清理
(1) FOR each table (2) 获取表上的AccessExclusiveLock锁 (3) 创建一个新的表文件 (4) FOR 每个活元组 in 老表 (5) 将活元组拷贝到新表中 (6) 如果有必要,冻结该元组。 END FOR (7) 移除旧的表文件 (8) 重建所有索引 (9) 更新FSM与VM (10) 更新统计信息 释放AccessExclusiveLock锁 END FOR (11) 移除不必要的clog文件
使用VACUUM FULL
命令时,应当考虑两点。
- 当执行完整清理时,没有人可以访问(读/写)表。
- 最多会临时使用两倍于表的磁盘空间;因此在处理大表时,有必要检查剩余磁盘容量。
什么时候该使用
VACUUM FULL
?不幸的是,并没有关于什么时候该执行
VACUUM FULL
的最佳实践。但是扩展pg_freespacemap
可能会给出很好的建议。以下查询给出了表的平均空间空闲率。
testdb=# CREATE EXTENSION pg_freespacemap; CREATE EXTENSION testdb=# SELECT count(*) as "number of pages", pg_size_pretty(cast(avg(avail) as bigint)) as "Av. freespace size", round(100 * avg(avail)/8192 ,2) as "Av. freespace ratio" FROM pg_freespace('accounts'); number of pages | Av. freespace size | Av. freespace ratio -----------------+--------------------+--------------------- 1640 | 99 bytes | 1.21 (1 row)
从上面的结果可以看出,没有多少空闲空间。
如果删除几乎所有的元组,并执行
VACUUM
命令,则可以发现每个页面几乎都是空的。testdb=#