# 页内剪枝与 HOT 更新 LLMS 索引： [llms.txt](/zh18/llms.txt) --- ## 5.1 页内剪枝 {#internal-ru-section-5-1} 在访问堆页面时，无论是更新还是普通读取，都可能执行快速的页内*剪枝*[^internal-ru-112-1]。这种情况会在以下三种情形之一出现： - 之前的 `UPDATE` 没有找到足够空间，无法把新的行版本放在同一个页面中。这一情况会记录在页面头部。 - 表页面的填充率超过 90%。 - 表页面的填充率超过存储参数 *fillfactor* 的值。 只有当页面的填充率低于存储参数 *fillfactor* 指定的百分比时，PostgreSQL 才会把新行插入（`INSERT`）该页面。其余空间会为更新（`UPDATE`）产生的新行版本预留。使用默认值时，表中不会预留空间。（*默认值：* `100`） 页内剪枝会从页面中移除在任何快照中都不再可见的行版本（也就是已经位于数据库视界之外的行版本）。它不会越过单个堆页面，但执行速度很快。被剪掉的行版本对应的项指针不会释放，因为索引可能仍然引用它们，而索引位于另一个页面。出于同样的原因，可见性映射和空闲空间映射也不会更新（因此释放的空间用于更新，而不是插入）。（*第 [106](/zh18/04-snapshots/#internal-ru-page-107) 页*） 页面可以在读取时被剪枝，这意味着 `SELECT` 语句也可能导致页面发生修改。这是除了延迟设置提示位之外的另一种情况。（*第 [86](/zh18/03-pages-and-tuples/#internal-ru-page-87) 页*） 下面通过一个例子看看页内剪枝如何工作。我们创建一个包含两列的表，并在每列上创建一个索引： ```text {label="psql"} => 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%。这意味着页面有足够空间容纳四个行版本，但只能插入三个。 现在插入一行，并多次更新它： ```text {label="psql"} => INSERT INTO hot VALUES (1, 'A'); => UPDATE hot SET s = 'B'; => UPDATE hot SET s = 'C'; => UPDATE hot SET s = 'D'; ``` 此时页面中有四个行版本： ```text {label="psql"} => 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](/zh18/03-pages-and-tuples/#internal-ru-page-76) 页*） ```text {label="psql"} => SELECT upper, pagesize FROM page_header(get_raw_page('hot',0)); upper | pagesize -------+---------- 64 | 8192 (1 row) ``` 下一次访问页面时会触发页内剪枝，移除所有过期行版本。随后，释放出的空间足以容纳新的行版本（0,5）： ```text {label="psql"} => 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](/zh18/25-b-tree/#internal-ru-page-530) 页*） ```text {label="psql"} => 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) ``` 在另一个索引中也能看到相同的情况： ```text {label="psql"} => 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 状态，也就是该元组已经不存在，应当忽略它。同时，服务器还会修改索引页面中的指针状态，避免以后重复访问表页面[^internal-ru-115-1]。 扩展用于查看索引页面的函数，增加“死”指针标志：（v. 13） ```text {label="psql"} => 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) ``` 目前索引页面上的所有指针都处于活动状态。但第一次通过索引访问表后，指针状态就会改变： ```text {label="psql" hl_lines="5"} => 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) ``` ```text {label="psql" hl_lines="4 5 6 7"} => 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 更新 {#internal-ru-section-5-2} 在索引中保存每个行版本的引用效率很低。 首先，每次修改行都必须更新表上创建的*所有*索引：一旦出现新的行版本，每个索引都必须包含指向它的引用，即使被修改的字段没有被索引。 其次，索引会积累指向历史行版本的引用，之后必须和这些行版本一起清理。（*第 [125](/zh18/06-vacuum-and-freezing/#internal-ru-page-126) 页*） 当然，在表上创建的索引越多，问题就越严重。 但是，如果更新只修改了不属于*任何*索引的列，就没有必要在索引中创建包含相同值的额外条目。 PostgreSQL 用一种称为 *HOT 更新* [^internal-ru-117-1]（Heap-Only Tuple update）的优化来避免多余的索引条目。这种更新可以在以下三种情况下进行： - 表上没有创建任何索引（这种情况下，任何更新都是 HOT 更新）； - 表上存在索引，但被更新的列没有被任何索引使用； - 被更新的列被某个索引使用，但其值没有发生变化。 如果某列以任何方式出现在 `CREATE INDEX` 命令中，就认为该列被索引使用：索引可以直接建立在该列上，也可以建立在包含该列的表达式上，或者该列作为非键列出现在 INCLUDE 索引中。唯一的例外是 BRIN 索引：其中没有指向表行的引用，因此不会妨碍 HOT 更新。（v. 16）（*第 [642](/zh18/29-brin/#internal-ru-page-643) 页*） 执行 HOT 更新时，索引页面中只有一个条目，它指向表行的第一个版本。同一行的其他版本如果仍位于这个表页面中，则通过各版本头部的 `ctid` 指针连接成一条链。 不被任何索引引用的行版本会标记 Heap-Only Tuple 位。如果某个行版本位于这条链中，则会标记 Heap Hot Updated 位。 如果索引扫描访问表页面时发现某个行版本带有 Heap Hot Updated 标志，就知道不能停在这里，而要沿着更新链继续向后遍历。当然，在把结果返回给客户端之前，服务器会检查这样读到的所有行版本的可见性。 下面删除一个索引并清空表，看看 HOT 更新如何工作。 ```text {label="psql"} => DROP INDEX hot_s; => TRUNCATE TABLE hot; ``` 为方便起见，我们重新定义 `heap_page` 函数，在输出中增加三个字段：`ctid` 以及与 HOT 更新有关的两个位： ```text {label="psql"} => 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; ``` 重复执行插入和更新操作： ```text {label="psql"} => INSERT INTO hot VALUES (1, 'A'); => UPDATE hot SET s = 'B'; ``` 页面中出现了一条 HOT 更新链： - Heap Hot Updated 位（`hhu`）表示需要沿着 `ctid` 链继续前进； - Heap Only Tuple 位（`hot`）表示没有索引引用这个行版本。 ```text {label="psql"} => 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) ``` 继续更新时，这条链会增长，但只能在页面范围内增长： ```text {label="psql"} => 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) ``` 此时索引中仍然只有一个引用，它指向这条链的头部： ```text {label="psql"} => SELECT * FROM index_page('hot_id',1); itemoffset | htid | dead ------------+-------+------ 1 | (0,1) | f (1 row) ``` HOT 更新链不会越过页面边界，因此遍历整条链不需要访问其他页面，也不会降低性能。 表的使用统计会跟踪更新类型。在这个例子中，7 次 `UPDATE` 操作中有 3 次是 HOT 更新： ```text {label="psql"} => 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 更新中的页内剪枝 {#internal-ru-section-5-3} HOT 更新中的页内剪枝是一个特殊但很重要的情况。 在前面的例子中，已经超过了 *fillfactor* 阈值，因此下一次更新应当触发页内剪枝。但这一次页面中包含一条 HOT 更新链。由于索引引用着链头，链头必须始终留在原位；其他指针则可以释放，因为可以确定没有外部引用。 为了不移动链头，PostgreSQL 使用双重寻址：索引所引用的指针（本例中为 (0,1)）会获得 redirect 状态，并指向当前作为链头的行版本： ```text {label="psql"} => 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)。 再进行几次更新： ```text {label="psql"} => UPDATE hot SET s = 'F'; ``` ```text {label="psql"} => UPDATE hot SET s = 'G'; ``` HOT 链增长了： ```text {label="psql"} => 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) ``` 下一次更新又会触发页内剪枝： ```text {label="psql"} => 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 链断裂 {#internal-ru-section-5-4} 如果页面没有足够的空闲空间容纳新的行版本，链就会断开。位于另一个页面中的行版本需要在索引中增加单独的引用。 为了观察这种情况，我们启动一个并发事务，并在其中创建一个阻止页内剪枝的数据快照： ```text {label="psql"} => BEGIN ISOLATION LEVEL REPEATABLE READ; => SELECT 1; ``` 现在在第一个会话中执行几次更新： ```text {label="psql"} => UPDATE hot SET s = 'I'; ``` ```text {label="psql"} => UPDATE hot SET s = 'J'; ``` ```text {label="psql"} => UPDATE hot SET s = 'K'; ``` 此时所有行版本都还能放在同一个页面中： ```text {label="psql"} => 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) ``` 下一次更新时，页面将没有足够空间，而页内剪枝也无法释放任何空间： ```text {label="psql"} => UPDATE hot SET s = 'L'; ``` ```text {label="psql"} => 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)： ```text {label="psql"} => 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 链的头部： ```text {label="psql"} => SELECT * FROM index_page('hot_id',1); itemoffset | htid | dead ------------+-------+------ 1 | (0,1) | f 2 | (1,1) | f (2 rows) ``` HOT 链断裂会单独记录在统计信息中：（v. 16） ```text {label="psql"} => 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 索引的页内剪枝 {#internal-ru-section-5-5} 前面说过，页内剪枝只处理一个表页面，不会触碰索引。不过，索引也有自己的剪枝机制[^internal-ru-124-1]，同样只清理一个页面，这里清理的是索引页面。 当向 B-树插入行即将导致索引页面分裂时，就会发生这种清理，因为原页面已经没有足够空间。问题在于，即使之后删除了一些索引条目，两个索引页面也不会重新合并成一个。这会导致索引膨胀；索引一旦膨胀，即便删除了大量数据，大小也可能无法缩小。但如果页内剪枝能够删除一部分条目，就可以推迟页面分裂。 页内剪枝可以从索引中删除两类条目。 首先，PostgreSQL 会清理此前标记为 dead 的条目[^internal-ru-124-2]。如前所述，当索引扫描发现某个索引条目指向一个在任何快照中都不再可见、或已经不存在的行版本时，就会设置这个标志。 如果没有找到已知为 dead 的条目，PostgreSQL 会检查那些指向同一个表行的不同版本的索引条目[^internal-ru-124-3]。由于多版本机制，更新操作可能产生大量行版本，其中许多很可能很快就会越过数据库视界。HOT 更新可以缓解这种影响，但并不总是适用：如果被更新的列属于某个索引，对应的引用就会传播到所有索引。在页面分裂之前，检查那些尚未标记为 dead、但已经可以清理的条目是有意义的。为此，必须检查相应行版本的可见性，而检查需要访问表页面。因此，只有那些“有希望”的索引条目才会被检查；这些条目是在多版本机制下作为现有条目的副本创建的。执行这种检查的代价低于允许一次多余的页面分裂。（v. 14） [^internal-ru-112-1]: [backend/access/heap/pruneheap.c](), 函数 heap\_page\_prune\_opt. [^internal-ru-115-1]: [backend/access/index/indexam.c](), 函数 index\_fetch\_heap. [^internal-ru-117-1]: [backend/access/heap/README.HOT](). [^internal-ru-124-1]: [postgrespro.ru/docs/postgresql/18/btree#BTREE-DELETION](). [^internal-ru-124-2]: [backend/access/nbtree/README](), Simple deletion 部分. [^internal-ru-124-3]: [backend/access/nbtree/README](), Bottom-Up deletion 部分; [include/access/tableam.h]().