5 页内剪枝与 HOT 更新

PostgreSQL 18 · 基于俄文 PG18 原版的简体中文译本

简体中文 · PG14 English · PG14简体中文 · PG18Русский · PG18

5.1 页内剪枝

在访问堆页面时，无论是更新还是普通读取，都可能执行快速的页内剪枝¹。这种情况会在以下三种情形之一出现：

之前的 UPDATE 没有找到足够空间，无法把新的行版本放在同一个页面中。这一情况会记录在页面头部。
表页面的填充率超过 90%。
表页面的填充率超过存储参数 fillfactor 的值。

只有当页面的填充率低于存储参数 fillfactor 指定的百分比时，PostgreSQL 才会把新行插入（INSERT）该页面。其余空间会为更新（UPDATE）产生的新行版本预留。使用默认值时，表中不会预留空间。（默认值： 100）

页内剪枝会从页面中移除在任何快照中都不再可见的行版本（也就是已经位于数据库视界之外的行版本）。它不会越过单个堆页面，但执行速度很快。被剪掉的行版本对应的项指针不会释放，因为索引可能仍然引用它们，而索引位于另一个页面。出于同样的原因，可见性映射和空闲空间映射也不会更新（因此释放的空间用于更新，而不是插入）。（第 106 页）

页面可以在读取时被剪枝，这意味着 SELECT 语句也可能导致页面发生修改。这是除了延迟设置提示位之外的另一种情况。（第 86 页）

下面通过一个例子看看页内剪枝如何工作。我们创建一个包含两列的表，并在每列上创建一个索引：

=> CREATE TABLE hot(id integer, s char(2000)) WITH (fillfactor = 75);
=> CREATE INDEX hot_id ON hot(id);
=> CREATE INDEX hot_s ON hot(s);

如果 s 列只存储拉丁字母，那么每个行版本的大小固定为 2004 字节，另加 24 字节的头部。存储参数 fillfactor 设置为 75%。这意味着页面有足够空间容纳四个行版本，但只能插入三个。

现在插入一行，并多次更新它：

=> INSERT INTO hot VALUES (1, 'A');
=> UPDATE hot SET s = 'B';
=> UPDATE hot SET s = 'C';
=> UPDATE hot SET s = 'D';

此时页面中有四个行版本：

=> SELECT * FROM heap_page('hot',0);
 ctid  | state  | xmin  | xmax
-------+--------+-------+-------
 (0,1) | normal | 820 c | 821 c
 (0,2) | normal | 821 c | 822 c
 (0,3) | normal | 822 c | 823
 (0,4) | normal | 823   | 0 a
(4 rows)

正如预期，我们刚刚超过了 fillfactor。从 pagesize 和 upper 的差值可以看出这一点：该差值超过页面大小的 75%，也就是 6144 字节。（第 75 页）

=> SELECT upper, pagesize FROM page_header(get_raw_page('hot',0));
 upper | pagesize
-------+----------
    64 |     8192
(1 row)

下一次访问页面时会触发页内剪枝，移除所有过期行版本。随后，释放出的空间足以容纳新的行版本（0,5）：

=> UPDATE hot SET s = 'E';
=> SELECT * FROM heap_page('hot',0);
 ctid  | state  | xmin  | xmax
-------+--------+-------+------
 (0,1) | dead   |       |
 (0,2) | dead   |       |
 (0,3) | dead   |       |
 (0,4) | normal | 823 c | 824
 (0,5) | normal | 824   | 0 a
(5 rows)

剪枝后留下的行版本会在物理上向页面地址较高的一侧移动，使所有空闲空间汇聚成一个连续片段。项指针也会相应修改。因此，页面中不会出现空闲空间碎片。

被剪枝行版本对应的项指针暂时不能释放，因为索引页面仍然引用它们；PostgreSQL 会把这些指针的状态从 normal 改为 dead（“死”）。下面查看 hot_s 索引的第一页（第 0 页用于存储元数据）：（第 529 页）

=> SELECT * FROM index_page('hot_s',1);
 itemoffset | htid
------------+-------
          1 | (0,1)
          2 | (0,2)
          3 | (0,3)
          4 | (0,4)
          5 | (0,5)
(5 rows)

在另一个索引中也能看到相同的情况：

=> SELECT * FROM index_page('hot_id',1);
 itemoffset | htid
------------+-------
          1 | (0,1)
          2 | (0,2)
          3 | (0,3)
          4 | (0,4)
          5 | (0,5)
(5 rows)

进行索引访问时，服务器可能得到 (0,1)、(0,2) 或 (0,3) 作为元组标识符。随后它会尝试从表页面读取对应的元组，却发现项指针处于 dead 状态，也就是该元组已经不存在，应当忽略它。同时，服务器还会修改索引页面中的指针状态，避免以后重复访问表页面²。

扩展用于查看索引页面的函数，增加“死”指针标志：（v. 13）

=> DROP FUNCTION index_page(text, integer);
=> CREATE FUNCTION index_page(relname text, pageno integer)
RETURNS TABLE(itemoffset smallint, htid tid, dead boolean)
AS $$
SELECT itemoffset,
       htid,
       dead -- начиная с v.13
FROM bt_page_items(relname,pageno);
$$ LANGUAGE sql;
=> SELECT * FROM index_page('hot_id',1);
 itemoffset | htid  | dead
------------+-------+------
          1 | (0,1) | f
          2 | (0,2) | f
          3 | (0,3) | f
          4 | (0,4) | f
          5 | (0,5) | f
(5 rows)

目前索引页面上的所有指针都处于活动状态。但第一次通过索引访问表后，指针状态就会改变：

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT * FROM hot WHERE id = 1;
                        QUERY PLAN
-----------------------------------------------------------
 Index Scan using hot_id on hot (actual rows=1.00 loops=1)
   Index Cond: (id = 1)
   Index Searches: 1
(3 rows)

=> SELECT * FROM index_page('hot_id',1);
 itemoffset | htid  | dead
------------+-------+------
          1 | (0,1) | t
          2 | (0,2) | t
          3 | (0,3) | t
          4 | (0,4) | t
          5 | (0,5) | f
(5 rows)

虽然第四个指针所引用的表行还没有被剪枝，状态仍为 normal，但它已经位于数据库视界之外。因此，索引中的第四个指针也被标记为 dead。

5.2 HOT 更新

在索引中保存每个行版本的引用效率很低。

首先，每次修改行都必须更新表上创建的所有索引：一旦出现新的行版本，每个索引都必须包含指向它的引用，即使被修改的字段没有被索引。

其次，索引会积累指向历史行版本的引用，之后必须和这些行版本一起清理。（第 125 页）

当然，在表上创建的索引越多，问题就越严重。

但是，如果更新只修改了不属于任何索引的列，就没有必要在索引中创建包含相同值的额外条目。

PostgreSQL 用一种称为 HOT 更新 ³（Heap-Only Tuple update）的优化来避免多余的索引条目。这种更新可以在以下三种情况下进行：

表上没有创建任何索引（这种情况下，任何更新都是 HOT 更新）；
表上存在索引，但被更新的列没有被任何索引使用；
被更新的列被某个索引使用，但其值没有发生变化。

如果某列以任何方式出现在 CREATE INDEX 命令中，就认为该列被索引使用：索引可以直接建立在该列上，也可以建立在包含该列的表达式上，或者该列作为非键列出现在 INCLUDE 索引中。唯一的例外是 BRIN 索引：其中没有指向表行的引用，因此不会妨碍 HOT 更新。（v. 16）（第 642 页）

执行 HOT 更新时，索引页面中只有一个条目，它指向表行的第一个版本。同一行的其他版本如果仍位于这个表页面中，则通过各版本头部的 ctid 指针连接成一条链。

不被任何索引引用的行版本会标记 Heap-Only Tuple 位。如果某个行版本位于这条链中，则会标记 Heap Hot Updated 位。

如果索引扫描访问表页面时发现某个行版本带有 Heap Hot Updated 标志，就知道不能停在这里，而要沿着更新链继续向后遍历。当然，在把结果返回给客户端之前，服务器会检查这样读到的所有行版本的可见性。

下面删除一个索引并清空表，看看 HOT 更新如何工作。

=> DROP INDEX hot_s;
=> TRUNCATE TABLE hot;

为方便起见，我们重新定义 heap_page 函数，在输出中增加三个字段：ctid 以及与 HOT 更新有关的两个位：

=> DROP FUNCTION heap_page(text,integer);
=> CREATE FUNCTION heap_page(
  relname text,
  pageno integer
)
RETURNS TABLE(
  ctid tid,
  state text,
  xmin text,
  xmax text,
  hhu text,
  hot text,
  t_ctid tid
)
AS $$
SELECT (pageno,lp)::text::tid AS ctid,
       CASE lp_flags
         WHEN 0 THEN 'unused'
         WHEN 1 THEN 'normal'
         WHEN 2 THEN 'redirect to '||lp_off
         WHEN 3 THEN 'dead'
       END AS state,
       t_xmin || CASE
         -- f пригодится позже
         WHEN (t_infomask & 256+512) = 256+512 THEN ' f'
         WHEN (t_infomask & 256) > 0 THEN ' c'
         WHEN (t_infomask & 512) > 0 THEN ' a'
         ELSE ''
       END AS xmin,
       t_xmax || CASE
         WHEN (t_infomask & 1024) > 0 THEN ' c'
         WHEN (t_infomask & 2048) > 0 THEN ' a'
         ELSE ''
       END AS xmax,
       CASE WHEN (t_infomask2 & 16384) > 0 THEN 't' END AS hhu,
       CASE WHEN (t_infomask2 & 32768) > 0 THEN 't' END AS hot,
       t_ctid
FROM heap_page_items(get_raw_page(relname,pageno))
ORDER BY lp;
$$ LANGUAGE sql;

重复执行插入和更新操作：

=> INSERT INTO hot VALUES (1, 'A');
=> UPDATE hot SET s = 'B';

页面中出现了一条 HOT 更新链：

Heap Hot Updated 位（hhu）表示需要沿着 ctid 链继续前进；
Heap Only Tuple 位（hot）表示没有索引引用这个行版本。

=> SELECT * FROM heap_page('hot',0);
 ctid  | state  | xmin  | xmax | hhu | hot | t_ctid
-------+--------+-------+------+-----+-----+--------
 (0,1) | normal | 831 c | 832  | t   |     | (0,2)
 (0,2) | normal | 832   | 0 a  |     | t   | (0,2)
(2 rows)

继续更新时，这条链会增长，但只能在页面范围内增长：

=> UPDATE hot SET s = 'C';
=> UPDATE hot SET s = 'D';
=> SELECT * FROM heap_page('hot',0);
 ctid  | state  | xmin  | xmax  | hhu | hot | t_ctid
-------+--------+-------+-------+-----+-----+--------
 (0,1) | normal | 831 c | 832 c | t   |     | (0,2)
 (0,2) | normal | 832 c | 833 c | t   | t   | (0,3)
 (0,3) | normal | 833 c | 834   | t   | t   | (0,4)
 (0,4) | normal | 834   | 0 a   |     | t   | (0,4)
(4 rows)

此时索引中仍然只有一个引用，它指向这条链的头部：

=> SELECT * FROM index_page('hot_id',1);
 itemoffset | htid  | dead
------------+-------+------
          1 | (0,1) | f
(1 row)

HOT 更新链不会越过页面边界，因此遍历整条链不需要访问其他页面，也不会降低性能。

表的使用统计会跟踪更新类型。在这个例子中，7 次 UPDATE 操作中有 3 次是 HOT 更新：

=> SELECT n_tup_upd, n_tup_hot_upd
FROM pg_stat_all_tables
WHERE relid = 'hot'::regclass;
 n_tup_upd | n_tup_hot_upd
-----------+---------------
         7 |             3
(1 row)

5.3 HOT 更新中的页内剪枝

HOT 更新中的页内剪枝是一个特殊但很重要的情况。

在前面的例子中，已经超过了 fillfactor 阈值，因此下一次更新应当触发页内剪枝。但这一次页面中包含一条 HOT 更新链。由于索引引用着链头，链头必须始终留在原位；其他指针则可以释放，因为可以确定没有外部引用。

为了不移动链头，PostgreSQL 使用双重寻址：索引所引用的指针（本例中为 (0,1)）会获得 redirect 状态，并指向当前作为链头的行版本：

=> UPDATE hot SET s = 'E';
=> SELECT * FROM heap_page('hot',0);
 ctid  |     state     | xmin  | xmax | hhu | hot | t_ctid
-------+---------------+-------+------+-----+-----+--------
 (0,1) | redirect to 4 |       |      |     |     |
 (0,2) | normal        | 835   | 0 a  |     | t   | (0,2)
 (0,3) | unused        |       |      |     |     |
 (0,4) | normal        | 834 c | 835  | t   | t   | (0,2)
(4 rows)

这里，(0,1)、(0,2) 和 (0,3) 这些行版本已经被剪掉；链头指针 1 保留下来用于重定向，而指针 2 和 3 因为可以确定没有索引引用，已经被释放（状态变为 unused）。新的行版本写入释放出的空间，位置为 (0,2)。

再进行几次更新：

=> UPDATE hot SET s = 'F';

=> UPDATE hot SET s = 'G';

HOT 链增长了：

=> SELECT * FROM heap_page('hot',0);
 ctid  |     state     | xmin  | xmax  | hhu | hot | t_ctid
-------+---------------+-------+-------+-----+-----+--------
 (0,1) | redirect to 4 |       |       |     |     |
 (0,2) | normal        | 835 c | 836 c | t   | t   | (0,3)
 (0,3) | normal        | 836 c | 837   | t   | t   | (0,5)
 (0,4) | normal        | 834 c | 835 c | t   | t   | (0,2)
 (0,5) | normal        | 837   | 0 a   |     | t   | (0,5)
(5 rows)

下一次更新又会触发页内剪枝：

=> UPDATE hot SET s = 'H';
=> SELECT * FROM heap_page('hot',0);
 ctid  |     state     | xmin  | xmax | hhu | hot | t_ctid
-------+---------------+-------+------+-----+-----+--------
 (0,1) | redirect to 5 |       |      |     |     |
 (0,2) | normal        | 838   | 0 a  |     | t   | (0,2)
 (0,3) | unused        |       |      |     |     |
 (0,4) | unused        |       |      |     |     |
 (0,5) | normal        | 837 c | 838  | t   | t   | (0,2)
(5 rows)

部分行版本被剪掉，指向链头的指针也相应移动。如果继续更新，在这个精心安排的例子中，所有行版本都能一直在同一个页面内循环使用。

5.4 HOT 链断裂

如果页面没有足够的空闲空间容纳新的行版本，链就会断开。位于另一个页面中的行版本需要在索引中增加单独的引用。

为了观察这种情况，我们启动一个并发事务，并在其中创建一个阻止页内剪枝的数据快照：

=> BEGIN ISOLATION LEVEL REPEATABLE READ;
=> SELECT 1;

现在在第一个会话中执行几次更新：

=> UPDATE hot SET s = 'I';

=> UPDATE hot SET s = 'J';

=> UPDATE hot SET s = 'K';

此时所有行版本都还能放在同一个页面中：

=> SELECT * FROM heap_page('hot',0);
 ctid  |     state     | xmin  | xmax  | hhu | hot | t_ctid
-------+---------------+-------+-------+-----+-----+--------
 (0,1) | redirect to 2 |       |       |     |     |
 (0,2) | normal        | 838 c | 839 c | t   | t   | (0,3)
 (0,3) | normal        | 839 c | 840 c | t   | t   | (0,4)
 (0,4) | normal        | 840 c | 841   | t   | t   | (0,5)
 (0,5) | normal        | 841   | 0 a   |     | t   | (0,5)
(5 rows)

下一次更新时，页面将没有足够空间，而页内剪枝也无法释放任何空间：

=> UPDATE hot SET s = 'L';

    => COMMIT; -- снимок больше не нужен
=> SELECT * FROM heap_page('hot',0);
 ctid  |     state     | xmin  | xmax  | hhu | hot | t_ctid
-------+---------------+-------+-------+-----+-----+--------
 (0,1) | redirect to 2 |       |       |     |     |
 (0,2) | normal        | 838 c | 839 c | t   | t   | (0,3)
 (0,3) | normal        | 839 c | 840 c | t   | t   | (0,4)
 (0,4) | normal        | 840 c | 841 c | t   | t   | (0,5)
 (0,5) | normal        | 841 c | 842   |     | t   | (1,1)
(5 rows)

在版本 (0,5) 中可以看到指向页面 1 的引用 (1,1)：

=> SELECT * FROM heap_page('hot',1);
 ctid  | state  | xmin | xmax | hhu | hot | t_ctid
-------+--------+------+------+-----+-----+--------
 (1,1) | normal | 842  | 0 a  |     |     | (1,1)
(1 row)

不过，这个引用不会被使用，因为版本 (0,5) 没有设置 Heap Hot Updated 位。至于版本 (1,1)，现在可以从包含两个条目的索引访问它。两个条目分别指向各自 HOT 链的头部：

=> SELECT * FROM index_page('hot_id',1);
 itemoffset | htid  | dead
------------+-------+------
          1 | (0,1) | f
          2 | (1,1) | f
(2 rows)

HOT 链断裂会单独记录在统计信息中：（v. 16）

=> SELECT n_tup_upd, n_tup_hot_upd, n_tup_newpage_upd
FROM pg_stat_all_tables
WHERE relid = 'hot'::regclass;
 n_tup_upd | n_tup_hot_upd | n_tup_newpage_upd
-----------+---------------+-------------------
        15 |            10 |                 1
(1 row)

这里，15 次 UPDATE 操作中有 11 次是 HOT 更新：其中 10 次在页面内完成，另 1 次因为空间不足导致链断裂。

如果经常更新不属于索引的列，可以考虑降低 fillfactor，为页面中的更新预留足够空间。当然还要记住，fillfactor 越低，页面中留下的空闲空间越多，表的物理大小也会相应增加。

5.5 索引的页内剪枝

前面说过，页内剪枝只处理一个表页面，不会触碰索引。不过，索引也有自己的剪枝机制⁴，同样只清理一个页面，这里清理的是索引页面。

当向 B-树插入行即将导致索引页面分裂时，就会发生这种清理，因为原页面已经没有足够空间。问题在于，即使之后删除了一些索引条目，两个索引页面也不会重新合并成一个。这会导致索引膨胀；索引一旦膨胀，即便删除了大量数据，大小也可能无法缩小。但如果页内剪枝能够删除一部分条目，就可以推迟页面分裂。

页内剪枝可以从索引中删除两类条目。

首先，PostgreSQL 会清理此前标记为 dead 的条目⁵。如前所述，当索引扫描发现某个索引条目指向一个在任何快照中都不再可见、或已经不存在的行版本时，就会设置这个标志。

如果没有找到已知为 dead 的条目，PostgreSQL 会检查那些指向同一个表行的不同版本的索引条目⁶。由于多版本机制，更新操作可能产生大量行版本，其中许多很可能很快就会越过数据库视界。HOT 更新可以缓解这种影响，但并不总是适用：如果被更新的列属于某个索引，对应的引用就会传播到所有索引。在页面分裂之前，检查那些尚未标记为 dead、但已经可以清理的条目是有意义的。为此，必须检查相应行版本的可见性，而检查需要访问表页面。因此，只有那些“有希望”的索引条目才会被检查；这些条目是在多版本机制下作为现有条目的副本创建的。执行这种检查的代价低于允许一次多余的页面分裂。（v. 14）

backend/access/heap/pruneheap.c, 函数 heap_page_prune_opt. ↩︎
backend/access/index/indexam.c, 函数 index_fetch_heap. ↩︎
backend/access/heap/README.HOT. ↩︎
postgrespro.ru/docs/postgresql/18/btree#BTREE-DELETION. ↩︎
backend/access/nbtree/README, Simple deletion 部分. ↩︎
backend/access/nbtree/README, Bottom-Up deletion 部分; include/access/tableam.h. ↩︎