概觀#

雜湊索引（hash index）提供依特定索引鍵快速找到元組 ID（TID）的能力。粗略地說，它就是一張存放在磁碟上的雜湊表。

插入#

把值插入索引時，會計算索引鍵的雜湊函式。PostgreSQL 的雜湊函式回傳 32 位元或 64 位元整數，取這些值的最低幾個位元作為對應的桶編號。TID 與鍵的雜湊碼被加入選定的桶中。

索引的雜湊表動態擴充：最少兩個桶；隨著被索引元組增加，某個桶會被分裂成兩個。這項操作多用一個雜湊碼位元，因此元素只在分裂產生的兩個桶之間重新分配，雜湊表其他桶的組成保持不變。

搜尋#

索引搜尋計算索引鍵的雜湊函式與對應的桶編號。在該桶的所有內容中，搜尋只回傳與鍵的雜湊碼相符的 TID。

由於桶內元素依鍵的雜湊碼排序，二分搜尋能相當有效率地回傳匹配的 TID。

由於鍵不存放在雜湊表中，存取方法可能因雜湊碰撞回傳多餘的 TID。因此索引引擎必須重新檢查存取方法取得的所有結果。

基於同樣理由，唯索引掃描不被支援。

頁面佈局#

與一般雜湊表不同，雜湊索引存放在磁碟上，因此所有資料必須排進頁面，最好是讓索引操作（搜尋、插入、刪除）只需存取盡可能少的頁面。

雜湊索引使用四種頁面：

類型用途
metapage第零頁，提供索引的「目錄」
bucket page索引的主要頁面，每個桶一個
overflow page主桶頁面容納不下所有元素時使用的額外頁面
bitmap page含位元陣列的頁面，用來追蹤已釋出、可重複使用的溢位頁面

圖 24-1：雜湊索引初始的頁面配置——metapage、兩個桶頁面與一個 bitmap 頁面

=> CREATE EXTENSION pageinspect;
=> CREATE TABLE t(n integer);
=> ANALYZE t;
=> CREATE INDEX ON t USING hash(n);

=> SELECT page, hash_page_type(get_raw_page('t_n_idx', page))
FROM generate_series(0,3) page;
 page | hash_page_type
−−−−−−+−−−−−−−−−−−−−−−−
    0 | metapage
    1 | bucket
    2 | bucket
    3 | bitmap

此處先分析了表格，因此建立的索引具有可能的最小尺寸；否則桶數會依「表格含十個頁面」的假設來選定。

metapage 與 ffactor#

=> SELECT ntuples, ffactor, maxbucket
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 ntuples | ffactor | maxbucket
−−−−−−−−−+−−−−−−−−−+−−−−−−−−−−−
        0 |    307 |         1

ffactor 顯示每個桶的估計列數，依區塊大小與 fillfactor 儲存參數（預設 75）計算。

若資料分佈絕對均勻且無雜湊碰撞，你可以用更高的 fillfactor；但在真實資料庫中這會提高頁面溢位的風險。

溢位頁面#

插入 500 個相同值後，出現了溢位頁面：

=> INSERT INTO t(n) SELECT 0 FROM generate_series(1,500);
=> SELECT page, live_items, free_size, hasho_bucket
FROM (VALUES (1), (2), (4)) p(page),
  hash_page_stats(get_raw_page('t_n_idx', page));
 page | live_items | free_size | hasho_bucket
−−−−−−+−−−−−−−−−−−−+−−−−−−−−−−−+−−−−−−−−−−−−−−
    1 |          0 |      8148 |            0
    2 |        407 |         8 |            1
    4 |         93 |      6288 |            1

桶 0 是空的，所有值都進了桶 1：部分在主頁面，塞不下的在溢位頁面。

顯然，若桶的元素散佈在多個頁面上，效能就會受損。雜湊索引在資料分佈均勻時表現最佳。

桶的分裂#

當索引中的列數超過現有桶的估計 ffactor 值時，桶就會分裂。此處有兩個桶、ffactor 為 307，因此在第 615 列插入時發生：

=> SELECT ntuples, ffactor, maxbucket, ovflpoint
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 ntuples | ffactor | maxbucket | ovflpoint
−−−−−−−−−+−−−−−−−−−+−−−−−−−−−−−+−−−−−−−−−−−
     615 |     307 |         2 |         2

maxbucket 增為 2，現在有三個桶（編號 0 到 2）。

因此從作業系統的角度看，雜湊索引是跳躍式成長的，儘管從邏輯上看雜湊表是漸進成長。

圖 24-2：桶分裂後——只多了一個桶，頁面數卻加倍，多出的頁面預留給尚未出現的桶

為了在一定程度上平滑這種成長、避免一次配置太多頁面，從第十次擴增起，頁面改為分四個相等批次配置，而非一次全給（PostgreSQL 10 起）。

桶編號的定址#

=> SELECT maxbucket, highmask::bit(4), lowmask::bit(4)
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 maxbucket | highmask | lowmask
−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−
         2 | 0011     | 0001

桶編號由雜湊碼中對應 highmask 的位元決定。但若得到的桶編號不存在（超過 maxbucket），就改取 lowmask 的位元。

本例取最低兩個位元得到 0 到 3；但若得到 3，就只取最低一個位元——也就是用桶 1 取代桶 3。

spares 陣列與 bitmap 指標

每次大小加倍，新的桶頁面被配置為單一連續區塊，溢位頁面與 bitmap 頁面則依需要插進這些片段之間。

metapage 在 spares 陣列中保存插入各區塊的頁數，讓我們能用簡單算術依桶編號算出其主頁面編號：

=> SELECT spares[2], spares[3]
FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 spares | spares
−−−−−−−−+−−−−−−−−
      2 |      2

本例中第一次擴增後插入了兩個頁面（一個 bitmap、一個 overflow），第二次擴增後尚未有新增。

metapage 也存放指向 bitmap 頁面的指標陣列：

=> SELECT mapp[1] FROM hash_metapage_info(get_raw_page('t_n_idx', 0));
 mapp
−−−−−−
    3

metapage 中也存放一個指向 bitmap 頁面的指標陣列：

圖 24-3：metapage 以 mmap 指標陣列追蹤各 bitmap 頁面與已配置的頁面範圍

空間回收的限制#

索引頁面內的空間在「指向死元組的指標被移除」時釋出。這發生在頁面修剪（由「試圖把元素插入已完全填滿的頁面」觸發）或執行例行清理時。

  • 主頁面永久指派給它們的桶，即使完全不含元素
  • 被清空的溢位頁面在 bitmap 中被追蹤、可被重複使用（甚至可能被另一個桶使用）

縮減索引實體大小的唯一方式，是用 REINDEX 或 VACUUM FULL 重建它。

查詢計畫中看不出索引的類型——雜湊索引在計畫中同樣顯示為 Bitmap Index Scan 之類的節點。

運算子類別#

PostgreSQL 10 之前，雜湊索引不被記錄到 WAL——既無故障保護也無法複寫，因此不建議使用。

但即使在那時它們仍有自己的價值。原因是雜湊演算法被廣泛使用（特別是雜湊連接與分組），系統必須知道某資料型別可用哪個雜湊函式。

然而這個對應關係不是靜態的：它無法一勞永逸地定義，因為 PostgreSQL 允許隨時新增資料型別。因此它由**「雜湊索引 + 特定資料型別」的運算子類別維護，雜湊函式本身則是該類別的支援函式**。

=> SELECT opfname AS opfamily_name, amproc::regproc AS opfamily_procedure
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_amproc amproc ON amprocfamily = opf.oid
WHERE amname = 'hash' AND amprocnum = 1
ORDER BY opfamily_name, opfamily_procedure;
   opfamily_name    | opfamily_procedure
−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−
 aclitem_ops        | hash_aclitem
 array_ops          | hash_array
 bool_ops           | hashchar
 ...
(38 rows)

這些函式回傳 32 位元整數。雖然沒有文件說明，它們仍可用來計算對應型別之值的雜湊碼：

=> SELECT hashtext('one'), hashtext('two');
  hashtext | hashtext
−−−−−−−−−−−−+−−−−−−−−−−−−
 1793019229 | 1590507854

雜湊索引的運算子類別只提供「等於」運算子。

屬性#

存取方法屬性#

屬性值說明
can_order✗雜湊函式或多或少隨機地打散資料，無法用於列排序
can_unique✗不支援唯一約束
can_multi_col✗不支援多欄位索引
can_exclude✓支援排除約束
can_include✗不支援額外的 INCLUDE 欄位

儘管不支援唯一約束，雜湊索引能強制排除約束；而由於唯一支援的運算子是「等於」，這個排除就取得了唯一性的意涵：

=> ALTER TABLE aircrafts_data
  ADD CONSTRAINT unique_range EXCLUDE USING hash(range WITH =);
=> INSERT INTO aircrafts_data VALUES ('744','{"ru": "Boeing 747-400"}',11100);
ERROR: conflicting key value violates exclusion constraint "unique_range"

索引層級屬性#

屬性值說明
clusterable✗難以想像為何需要依雜湊函式值實體排序 heap 資料
index_scan✓支援一般索引掃描
bitmap_scan✓支援點陣圖掃描
backward_scan✓支援反向掃描

欄位層級屬性#

欄位層級屬性實質上由索引存取方法決定，且永遠取相同的值——全部為 false：

         name       | pg_index_column_has_property
−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
 asc                | f
 desc               | f
 nulls_first        | f
 nulls_last         | f
 orderable          | f
 distance_orderable | f
 returnable         | f
 search_array       | f
 search_nulls       | f

原因分別是：

  • 排序相關的全部不適用——雜湊函式不保留值的順序
  • returnable 為 false——雜湊索引不存放索引鍵，必須存取 heap，因此無法參與唯索引掃描
  • search_nulls 為 false——「等於」操作對 NULL 不適用
  • search_array 未實作
Backward 索引種類 B-tree Forward