頁面修剪#

在 heap 頁面被讀取或更新的過程中，PostgreSQL 可以順手做一次快速的頁面清理，稱為修剪（pruning）。它發生在以下情況：

• 先前的 UPDATE 操作在同一頁面中找不到足夠空間放置新元組（這個事件會記錄在頁首）
• heap 頁面所含的資料超過 fillfactor 儲存參數所允許的量

頁面修剪移除的是再也無法在任何快照中可見的元組（即位於資料庫水平線之外者）。它的特性：

• 從不跨越單一 heap 頁面，作為回報，執行得非常快
• 被修剪元組的指標仍留在原處，因為它們可能被索引參照——而索引已經是另一個頁面了
• 基於同樣理由，可見性映射與可用空間映射都不會被更新（因此回收的空間是留給更新用，而非插入用）

由於頁面可能在讀取時被修剪，任何 SELECT 敘述都可能造成頁面修改。這是除了延後設定資訊位元之外的另一種情況。

實驗：修剪如何運作#

建立雙欄位表格，兩欄各建一個索引，並把 fillfactor 設為 75%：

=> 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 欄位只含拉丁字母，每個 heap 元組固定為 2004 位元組加 24 位元組標頭。頁面空間足夠放四個元組，但因 fillfactor 為 75% 而只能插入三個。

插入一列並更新數次後，頁面含有四個元組，已超過 fillfactor 門檻：

=> SELECT * FROM heap_page('hot',0);
 ctid | state | xmin | xmax
−−−−−−−+−−−−−−−−+−−−−−−−+−−−−−−−
 (0,1) | normal | 801 c | 802 c
 (0,2) | normal | 802 c | 803 c
 (0,3) | normal | 803 c | 804
 (0,4) | normal | 804   | 0 a
(4 rows)

下一次頁面存取就會觸發修剪，移除所有過期元組，新元組隨即寫入釋出的空間：

=> 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 | 804 c | 805
 (0,5) | normal | 805   | 0 a
(5 rows)

• 剩餘的 heap 元組被實體移往高位址，使所有可用空間聚合成單一連續區塊；元組指標也相應修改，頁面中不會出現可用空間碎片化
• 被修剪元組的指標還不能移除（仍被索引參照），PostgreSQL 只把它們的狀態從 normal 改為 dead

索引端的連帶處理#

索引掃描可能回傳 (0,1)、(0,2)、(0,3) 這些元組識別碼。伺服器嘗試讀取對應的 heap 元組，卻發現指標處於 dead 狀態——這表示該元組已不存在、應予忽略。

順帶一提，伺服器同時也會修改索引頁面中的指標狀態，以避免重複存取 heap 頁面。

第一次索引掃描發生後，索引項目的 dead 旗標就被設起來：

=> 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)

第四個指標所參照的 heap 元組雖然尚未被修剪、仍為 normal 狀態，但它已經在資料庫水平線之外——因此該指標在索引中同樣被標記為 dead。

HOT 更新#

把所有 heap 元組的參照都保留在索引中是非常沒效率的：

• 每次列修改都會觸發表格上所有索引的更新——只要新的 heap 元組出現，每個索引都必須納入指向它的參照，即使被修改的欄位根本沒被索引
• 索引會累積指向歷史 heap 元組的參照，因此必須與這些元組一起被清理
• 表格上的索引越多，情況越糟

但若被更新的欄位不屬於任何索引，就沒有理由再建立一筆鍵值相同的索引項目。為避免這種冗餘，PostgreSQL 提供 HOT（Heap-Only Tuple）更新最佳化。

執行 HOT 更新時：

• 索引頁面中每一列只有一筆項目，指向最初的列版本
• 位於同一頁面的所有後續版本，透過元組標頭中的 ctid 指標串成一條鏈
• 未被任何索引參照的列版本，標記 Heap-Only Tuple 位元（hot）
• 被納入 HOT 鏈的版本，標記 Heap Hot Updated 位元（hhu）

索引掃描存取 heap 頁面時若發現某列版本標有 Heap Hot Updated，代表掃描應繼續，於是沿著 HOT 更新鏈往下走。當然，所有取得的列版本在回傳給客戶端之前都會經過可見性檢查。

實驗：HOT 鏈的成長#

刪掉 hot_s 索引並清空表格後，插入一列並更新：

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

=> SELECT * FROM heap_page('hot',0);
 ctid | state | xmin | xmax | hhu | hot | t_ctid
−−−−−−−+−−−−−−−−+−−−−−−−+−−−−−−+−−−−−+−−−−−+−−−−−−−−
 (0,1) | normal | 812 c | 813 | t    |     | (0,2)
 (0,2) | normal | 813   | 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 | 812 c | 813 c | t   |     | (0,2)
 (0,2) | normal | 813 c | 814 c | t   | t   | (0,3)
 (0,3) | normal | 814 c | 815   | t   | t   | (0,4)
 (0,4) | normal | 815   | 0 a   |     | t   | (0,4)
(4 rows)

而索引始終只有一筆參照，指向鏈的頭部：

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

由於 HOT 鏈只能在單一頁面內成長，走訪整條鏈永遠不需要存取其他頁面，因此不會拖累效能。

HOT 更新鏈的修剪#

頁面修剪有一個特殊但重要的情況：HOT 更新鏈的修剪。

鏈的頭部必須永遠留在原位（因為索引參照它），但其他指標可以被釋放（它們確定沒有外部參照）。

為避免移動頭部，PostgreSQL 使用雙重定址：被索引參照的那個指標會取得 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        | 816   | 0 a |      | t   | (0,2)
 (0,3) | unused        |       |      |     |     |
 (0,4) | normal        | 815 c | 816 | t    | t   | (0,2)
(4 rows)

• 元組 (0,1)、(0,2)、(0,3) 已被修剪
• 頭部指標 1 保留下來作重導向之用
• 指標 2、3 被釋放（取得 unused 狀態），因為它們保證沒有來自索引的參照
• 新元組寫入釋出的空間，成為 (0,2)

再更新數次後，下一次更新會再度觸發修剪，鏈頭指標也隨之調整（例如變成 redirect to 5）。

若未被索引的欄位經常被修改，把 fillfactor 調低是合理的做法，可在頁面中預留空間給更新使用。

但必須記得：fillfactor 越低，頁面中留下的可用空間越多，表格的實體大小也就越大。

HOT 鏈斷裂#

若頁面再也沒有空間容納新元組，鏈就會被切斷。PostgreSQL 必須新增一筆獨立的索引項目，用來參照位於另一頁面的元組。

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

=> SELECT * FROM heap_page('hot',0);
 ctid |      state     | xmin | xmax | hhu | hot | t_ctid
−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−+−−−−−−−+−−−−−+−−−−−+−−−−−−−−
 (0,1) | redirect to 2 |       |       |     |     |
 (0,2) | normal        | 819 c | 820 c | t   | t   | (0,3)
 (0,3) | normal        | 820 c | 821 c | t   | t   | (0,4)
 (0,4) | normal        | 821 c | 822   | t   | t   | (0,5)
 (0,5) | normal        | 822   | 0 a   |     | t   | (0,5)
(5 rows)

=> UPDATE hot SET s = 'L';

=> SELECT * FROM heap_page('hot',0);
 ctid |      state     | xmin | xmax | hhu | hot | t_ctid
−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−+−−−−−−−+−−−−−+−−−−−+−−−−−−−−
 (0,1) | redirect to 2 |       |       |     |     |
 ...
 (0,5) | normal        | 822 c | 823   |     | t   | (1,1)
(5 rows)

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

索引的頁面修剪#

前面說過頁面修剪局限於單一 heap 頁面、不影響索引。不過索引有自己的修剪機制，同樣只清理單一頁面——這次是索引頁面。

索引修剪發生在即將因空間不足而把 B-tree 頁面一分為二的時候。

問題在於：即使日後刪除了某些索引項目，兩個分裂後的索引頁面也不會再合併回一個。這會導致索引膨脹，而一旦膨脹，即使刪掉大部分資料索引也無法縮小。

但若修剪能移除部分元組，頁面分裂就可以被延後。

索引中有兩類元組可被修剪：

1. 已被標記為 dead 的元組。如前所述，PostgreSQL 在索引掃描時若偵測到某索引項目指向「已不在任何快照中可見、或根本不存在」的元組，就會設上這個標記。
2. 指向同一表格列不同版本的索引項目（PostgreSQL 14 起）。由於 MVCC，更新操作可能產生大量列版本，其中許多很快就會落到資料庫水平線之後。HOT 更新能緩解這個效應，但並非總是適用：若待更新的欄位屬於某索引，對應的參照就會被傳播到所有索引。

在頁面分裂之前，去找那些「尚未被標記為 dead、但其實已可修剪」的列是划算的。要做到這點，PostgreSQL 必須檢查 heap 元組的可見性——這需要存取表格，因此只對「有希望的」（promising）索引元組執行，也就是那些為 MVCC 目的而從既有項目複製出來的元組。

做這種檢查，比放任一次多餘的頁面分裂發生要便宜。