MySQL 自適應哈希索引—構造
曾經優化慢查詢時，經常在日志中看到 truncate，當時一直疑惑 truncate 為什么會慢。
轉到數據庫方向之后，又碰到過幾次 truncate 執行時間過長，導致 MySQL 短暫卡住的問題。
經過源碼分析和同事測試驗證，發現這幾次的問題都跟自適應哈希索引有關，所以，深入研究下自適應哈希索引就很有必要了。
自適應哈希索引大概會有 3 篇文章。第 1 篇，我們來看看自適應哈希索引的構造過程。
本文基于 MySQL 8.0.32 源碼，存儲引擎為 InnoDB。
1、準備工作
創建測試表：
CREATE TABLE `t1` (
`id` int unsigned NOT NULL AUTO_INCREMENT,
`i1` int DEFAULT '0',
PRIMARY KEY (`id`) USING BTREE,
KEY `idx_i1` (`i1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb3插入測試數據：
INSERT INTO `t1`(`id`, `i1`)
VALUES (10, 101), (20, 201), (30, 301);示例 SQL：
SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 3012、AHI 有什么好處？
自適應哈希索引，英文全稱 Adaptive Hash Index，簡稱 AHI。
根據上下文需要，后續內容會混用自適應哈希索引和 AHI，不再單獨說明。
顧名思義，自適應哈希索引也是一種索引，使用哈希表作為存儲結構，自適應的意思是我們無法干涉它的創建、使用、更新、刪除，而是由 InnoDB 自行決定什么時候創建、怎么創建、什么時候更新和刪除。
我們知道 InnoDB 的主鍵索引、二級索引都是 B+ 樹結構。執行 SQL 語句時，以下幾種場景都需要定位到索引葉子結點中的某條記錄：
- insert 需要定位到插入目標位置的前一條記錄。
- 查詢優化階段，select、update、delete 預估掃描區間記錄數量時，需要定位到掃描區間的
第一條和最后一條記錄。 - 查詢執行階段，select、update、delete 需要定位到掃描區間的
第一條記錄。
得益于多叉結構，B+ 樹的層級一般都比較少，通常情況下，從根結點開始，最多經過 3 ~ 4 層就能定位到葉子結點中的記錄。
這個定位過程看起來挺快的，單次執行也確實比較快，但是對于頻繁執行的場景，還是有一點優化空間的。
為了追求極致性能，InnoDB 實現了 AHI，目的就是能夠根據搜索條件直接定位到索引葉子結點中的記錄。
圖片
上圖是一棵高為 4 的 B+ 樹示意圖，定位索引葉子結點記錄，需要從根結點開始，經過內結點、葉結點，最后定位到記錄，路徑為：① -> ② -> ③ -> ④
圖片
AHI 會使用多個 hash 桶來存儲哈希值到記錄地址的映射，上圖是一個 hash 桶的示意圖。
橙色塊表示記錄地址組成的鏈表，因為多條記錄可能被映射到 hash 桶中的同一個位置。
AHI 定位一條記錄時，根據 where 條件中的某些字段計算出哈希值，然后直接到 hash 桶中找到對應的記錄。
如果多條記錄被映射到 hash 桶中的同一個位置，那么找到的是個鏈表，需要遍歷這個鏈表以找到目標記錄。
3、原理介紹
AHI 能提升定位記錄的效率，但是，有得到必然有付出，天上掉餡餅的事在計算機世界里是不會發生的。
為了簡潔，這里我們把定位索引葉子結點中的記錄簡稱為定位記錄，后面內容也依此定義，不再單獨說明。
高效定位記錄，付出的代價是存儲哈希值到記錄地址的映射占用的內存空間、以及構造映射花費的時間。
因為有時間、空間成本，所以，InnoDB 希望構造 AHI 之后，能夠盡可能多的用上，做到收益大于成本。直白點說，就是需要滿足一定的條件，才能構造 AHI。
AHI 采用的是組團構造邏輯，也就是以數據頁為單位，滿足一定條件之后，就會為數據頁中的所有記錄構造 AHI，主要流程如下：
圖片
第 1 步，為數據頁所屬的索引計數（index->search_info->hash_analysis）。
SQL 執行過程中，每次定位某個索引葉子結點中的記錄，該索引的計數都會加 1。
如果索引計數達到 17，進入第 2 步，否則，執行流程到此結束。
因為第 2、3 步為構造信息計數、為數據頁計數也是需要時間成本的，所以，這里設置了第 1 道檻，只有索引被使用一定次數之后，才會執行第 2、3 步。
第 2 步，為構造信息計數（index->search_info->n_hash_potential）。
對于 select、insert、update、delete，定位記錄時，搜索條件和葉子結點中的記錄比較，會產生兩個邊界，左邊為下界，右邊為上界，基于下界和上界可以得到用于構造 AHI 的信息，我們稱之為構造信息。
圖片
以上是定位記錄時產生的下界、上界示意圖。定位記錄過程中，下界和上界會不斷向目標記錄靠近，最終，下界或上界的其中一個會指向目標記錄。
如果某次定位記錄時，基于下界或上界得到的構造信息，和索引對象中保存的構造信息一致，該構造信息計數加 1。否則，該索引計數清零，構造信息計數清零或重置為 1（具體見下一小節的介紹）。
第 3 步，為數據頁計數（block->n_hash_helps）。
定位到索引葉子結點記錄之后，就知道了該記錄所屬的數據頁，如果本次得到的構造信息和數據頁對象中保存的構造信息相同，數據頁計數加 1，否則數據頁計數重置為 1。
第 4 步，為數據頁構造 AHI。
如果滿足以下兩個條件，第 3 步的數據頁就具備了構造 AHI 的資格：
- 構造信息計數大于等于 100。
- 數據頁計數大于數據頁中記錄數量的十六分之一。
具備構造 AHI 的資格之后，對于以下三種情況之一，會為數據頁構造 AHI：
- 該數據頁之前沒有構造過 AHI。
- 該數據頁之前構造過 AHI，并且構造 AHI 之后，數據頁會從零開始重新計數，重新計數大于數據頁中記錄數量的兩倍。
- 該數據頁之前構造過 AHI，但是本次確定的構造信息和之前不一樣了。
注意：從各個條件判斷，到最終構造 AHI 的整個流程，并不是在執行一條 SQL 的過程中完成的，而是在執行多條 SQL 的過程中完成的。
到這里，構造 AHI 的主要流程就介紹完了，構造過程的具體細節，請繼續往下看。
4、構造過程
定位記錄會調用 btr_cur_search_to_nth_level()，這也是 AHI 的構造入口：
// storage/innobase/btr/btr0cur.cc
void btr_cur_search_to_nth_level(...) {
...
if (btr_search_enabled &&
!index->disable_ahi) {
// AHI 的構造入口
btr_search_info_update(cursor);
}
...
}btr_search_enabled = true（默認值），表示 InnoDB 啟用了 AHI。
!index->disable_ahi = true，即 index->disable_ahi = false，表示 index 對應的索引沒有禁用 AHI。
只有內部臨時表、沒有主鍵的表禁用了 AHI。
也就是說，對于正常的用戶表、系統表，!index->disable_ahi = true，會調用 btr_search_info_update()，進入 AHI 的構造流程。
（1）索引計數
構造 AHI 的第 1 步，就是調用 btr_search_info_update() 進行索引計數。
// storage/innobase/include/btr0sea.ic
static inline void btr_search_info_update(btr_cur_t *cursor) {
const auto index = cursor->index;
...
// 索引計數加 1
const auto hash_analysis_value = ++index->search_info->hash_analysis;
// BTR_SEARCH_HASH_ANALYSIS = 17（硬編碼）
if (hash_analysis_value < BTR_SEARCH_HASH_ANALYSIS) {
/* Do nothing */
return;
}
...
btr_search_info_update_slow(cursor);
}btr_search_info_update() 每次被調用都會增加索引計數（++index->search_info->hash_analysis）。
自增之后，如果索引計數小于 17，不需要進入 AHI 構造流程的下一步，直接返回。
如果索引計數大于等于 17，調用 btr_search_info_update_slow()，進入 AHI 構造流程的下一步。
看到這里，大家是否會有疑問：對于一條能使用索引的 select 語句，如果 where 條件只有一個掃描區間，執行過程中，btr_search_info_update() 最多會被調用幾次？
我們通過 1. 準備工作小節的示例 SQL 來揭曉答案，SQL 如下：
SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 301執行計劃如下：
圖片
通過執行計劃可知，示例 SQL 執行過程中，會使用索引 idx_i1。
查詢優化階段，MySQL 需要定位到掃描區間的第一條和最后一條記錄，用于計算掃描區間覆蓋的記錄數量：
- 定位掃描區間的第一條記錄，即滿足 id >= 101 的第一條記錄，第 1 次調用 btr_cur_search_to_nth_level()。
- 定位掃描掃描區間的最后一條記錄，即滿足 id < 301 的最后一條記錄，第 2 次調用 btr_cur_search_to_nth_level()。
查詢執行階段，從存儲引擎讀取第一條記錄之前，需要定位掃描區間的第一條記錄，即滿足 id >= 101 的第一條記錄，第 3 次調用 btr_cur_search_to_nth_level()。
定位掃描區間的第一條和最后一條記錄，都是定位索引葉子結點中的記錄。
到這里，我們就得到了前面那個問題的答案：3 次。
（2）構造信息計數
如果某個索引的計數達到了 17，就會進入 AHI 構造流程的第 2 步，根據本次定位記錄過程中得到的下界和上界，確定使用索引的前幾個字段構造 AHI，以及對于索引中前幾個字段值相同的一組記錄，構造 AHI 時選擇這組記錄的第一條還是最后一條。
3.原理介紹小節的第 2 步，我們已經把這些信息命名為構造信息。
基于定位記錄時得到的下界和上界確定構造信息、為構造信息計數的邏輯由 btr_search_info_update_hash() 完成。
// storage/innobase/btr/btr0sea.cc
void btr_search_info_update_slow(btr_cur_t *cursor) {
...
const auto block = btr_cur_get_block(cursor);
...
btr_search_info_update_hash(cursor);
...
}btr_search_info_update_hash() 的代碼有點長，我們分 2 段介紹。
介紹第 1 段代碼之前，我們先來看看表示構造信息的結構體定義（index->search_info->prefix_info）：
// storage/innobase/include/buf0buf.h
// 為了方便閱讀，以下結構體定義對源碼做了刪減
struct btr_search_prefix_info_t {
/** recommended prefix: number of bytes in an incomplete field */
uint32_t n_bytes;
/** recommended prefix length for hash search: number of full fields */
uint16_t n_fields;
/** true or false, depending on whether the leftmost record of several records
with the same prefix should be indexed in the hash index */
bool left_side;
}btr_search_prefix_info_t 包含 3 個屬性：
- n_fields、n_bytes：索引的前 n_fields 個字段，第 n_fields + 1 個字段的前 n_bytes 字節用于構造 AHI。
- left_side：如果索引中多條記錄的前 n_fields 個字段內容、第 n_fields + 1 個字段前 n_bytes 字節的內容相同，我們把這樣的一組記錄稱為前綴相同的記錄。對于前綴相同的記錄：left_side = true 時，選擇最左邊的記錄（第一條記錄）構造 AHI。left_side = false 時，選擇最右邊的記錄（最后一條記錄）構造 AHI。
接下來，我們開始介紹 btr_search_info_update_hash() 的第 1 段代碼邏輯。
// storage/innobase/btr/btr0sea.cc
/****** 第 1 段 ******/
static void btr_search_info_update_hash(btr_cur_t *cursor) {
dict_index_t *index = cursor->index;
int cmp;
...
// 索引中，通過幾個字段能唯一確定一條記錄？
// 對于主鍵索引，n_unique = 主鍵段字數量
// 對于二級索引，n_unique = 二級索引字段數量 + 主鍵字段數量
const uint16_t n_unique =
static_cast<uint16_t>(dict_index_get_n_unique_in_tree(index));
const auto info = index->search_info;
/****** if_1 ******/
// 構造信息計數不等于 0
// 說明之前已經確定過構造信息了
if (info->n_hash_potential != 0) {
// info->prefix_info 中
// 保存了之前確定的構造信息
const auto prefix_info = info->prefix_info.load();
...
/****** if_2 ******/
// prefix_info.n_fields
// 表示之前確定的構造信息的字段數量
// std::max(up_match, low_match)
// 表示下界或上界字段數量中較大的那個
if (prefix_info.n_fields == n_unique &&
std::max(cursor->up_match, cursor->low_match) == n_unique) {
// 兩個條件都滿足，說明：
// 如果本次通過下界、上界確定構造信息
// 會和之前確定的構造信息相同
// 那么，構造信息計數加 1
info->n_hash_potential++;
return;
}
...
const bool low_matches_prefix =
0 >= ut_pair_cmp(prefix_info.n_fields, prefix_info.n_bytes,
cursor->low_match, cursor->low_bytes);
const bool up_matches_prefix =
0 >= ut_pair_cmp(prefix_info.n_fields, prefix_info.n_bytes,
cursor->up_match, cursor->up_bytes);
/****** if_3 ******/
// 這里的構造信息指的是：
// 索引對象中保存的之前確定的構造信息
// prefix_info.left_side = true
// 如果構造信息【大于】下界，且【小于等于】上界
// 構造信息計數（n_hash_potential）加 1
// prefix_info.left_side = false
// 如果構造信息【小于等于】下界，且【大于】上界
// 構造信息計數（n_hash_potential）加 1
if (prefix_info.left_side ? (!low_matches_prefix && up_matches_prefix)
: (low_matches_prefix && !up_matches_prefix)) {
info->n_hash_potential++;
return;
}
}
...
}如果構造信息計數（info->n_hash_potential）不等于 0，if_1 條件成立，說明索引對象中已經保存了之前確定的構造信息。
但是，確定索引的 AHI 構造信息之后，還需要該索引的構造信息計數、某個數據頁的計數滿足條件，InnoDB 才會為該索引的該數據頁構造 AHI。
所以，索引對象中已經保存了之前確定的構造信息對應兩種情況：
- 已經用索引中保存的構造信息為某個（些）數據頁構造了 AHI。
- 只確定了構造信息，還沒有用它構造過 AHI。
構造信息計數被命名為 n_hash_potential（潛在的），就是因為存在第 2 種情況。
if_2、if_3 用于判斷：通過本次定位記錄時產生的下界或上界得到構造信息，是否和索引對象中保存的構造信息一致，如果一致，則增加構造信息計數。
if_2 包含兩個表達式，如果值都為 true，說明上面的判斷結果為 true，構造信息計數加 1（info->n_hash_potential++）。
如果 if_2 不成立，再判斷 if_3 是否成立。
前面介紹過，對于前綴相同的一組記錄，構造 AHI 時，由 left_side 決定選擇最左邊還是最右邊的記錄。
對于本次定位記錄得到的下界、上界，left_side 決定它們怎么和索引對象中保存的構造信息比較。
left_side = true 時，如果以下兩個條件同時滿足，構造信息計數（n_hash_potential）加 1：
- prefix_info.n_fields、n_bytes 大于下界（low_match、low_bytes）。
- prefix_info.n_fields、n_bytes 小于等于上界（up_match、up_bytes）。
left_side = false 時，如果以下兩個條件同時滿足，構造信息計數（n_hash_potential）加 1：
- prefix_info.n_fields、n_bytes 小于等于下界（low_match、low_bytes）。
- prefix_info.n_fields、n_bytes 大于上界（up_match、up_bytes）。
如果 if_3 成立，說明本次定位記錄得到的下界或上界的字段數量、字節數，和索引對象中保存的構造信息的字段數量（n_fields）、字節數（n_bytes）一致，構造信息計數加 1（info->n_hash_potential++）。
如果 if_3 不成立，說明構造信息變了，需要執行第 2 段代碼，確定新的構造信息，并且重置構造信息計數。
// storage/innobase/btr/btr0sea.cc
/****** 第 2 段 ******/
static void btr_search_info_update_hash(btr_cur_t *cursor) {
...
info->hash_analysis = 0;
cmp = ut_pair_cmp(cursor->up_match, cursor->up_bytes, cursor->low_match,
cursor->low_bytes);
/****** if_4 ******/
if (cmp == 0) {
// where 條件沒有定位到匹配的記錄
// 構造信息計數清零
info->n_hash_potential = 0;
// 雖然給構造信息賦值了，但是這個信息不會被使用
/* For extra safety, we set some sensible values here */
info->prefix_info = {0, 1, true};
/****** elseif_5 ******/
} else if (cmp > 0) {
// 上界（up_match、up_bytes）大于下界（low_match、low_bytes）
// left_side 都會設置為 true
// 構造信息計數重置為 1
info->n_hash_potential = 1;
ut_ad(cursor->up_match <= n_unique);
// 如果上界字段數量等于 n_unique
// 使用上界作為新的構造信息
if (cursor->up_match == n_unique) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ n_unique,
/* left_side */ true
};
// 下界字段數量（low_match）小于上界字段數量（up_match）
// 使用下界作為新的構造信息
} else if (cursor->low_match < cursor->up_match) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ static_cast<uint16_t>(cursor->low_match + 1),
/* left_side */ true
};
// 下界字段數量（low_match）等于上界字段數量（up_match）
// 下界字節數（low_bytes）小于上界字節數（up_bytes）
// 使用下界作為新的構造信息
} else {
info->prefix_info = {
/* n_bytes */ static_cast<uint32_t>(cursor->low_bytes + 1),
/* n_fields */ static_cast<uint16_t>(cursor->low_match),
/* left_side */ true
};
}
/****** else_1 ******/
} else {
// 上界（up_match、up_bytes）小于下界（low_match、low_bytes）
// left_side 都會設置為 false
// 構造信息計數重置為 1
info->n_hash_potential = 1;
ut_ad(cursor->low_match <= n_unique);
// 如果下界字段數量等于 n_unique
// 使用下界作為新的構造信息
if (cursor->low_match == n_unique) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ n_unique,
/* left_side */ false
};
// 下界字段數量（low_match）大于上界字段數量（up_match）
// 使用上界作為新的構造信息
} else if (cursor->low_match > cursor->up_match) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ static_cast<uint16_t>(cursor->up_match + 1),
/* left_side */ false
};
// 下界字段數量（low_match）等于上界字段數量（up_match）
// 下界字節數（low_bytes）大于上界字節數（up_bytes）
// 使用上界作為新的構造信息
} else {
info->prefix_info = {
/* n_bytes */ static_cast<uint32_t>(cursor->up_bytes + 1),
/* n_fields */ static_cast<uint16_t>(cursor->up_match),
/* left_side */ false
};
}
}
}第 2 段代碼用于首次或者重新確定構造信息，主要邏輯如下：
- 索引計數（info->hash_analysis）清零，下次調用 btr_search_info_update_hash() 時重新開始計數。
- 如果 left_side = true，并且本次定位記錄得到的下界字段數量等于 n_unique，使用下界作為新的構造信息。
- 如果 left_side = false，并且本次定位記錄得到的上界字段數量等于 n_unique，使用上界作為新的構造信息。
- 否則，選擇本次定位記錄得到的上界、下界中較小的那個作為新的構造信息。
ut_pair_cmp(up_match, up_bytes, low_match, low_bytes) 比較本次定位記錄得到的上界、下界，比較結果保存到 cmp 中。
如果 cmp 等于 0，命中 if_4，說明 btr_cur_search_to_nth_level() 定位記錄時，上界、下界相同（up_match 等于 low_match、up_bytes 等于 low_bytes），也就是沒有找到匹配的記錄，構造信息計數（info->n_hash_potential）重置為 0。
如果 cmp 大于 0，命中 elseif_5，說明本次定位記錄時，下界小于上界，構造信息（prefix_info）的 left_side 屬性都會被設置為 true。
if (cursor->up_match == n_unique) 條件成立，說明搜索條件能夠唯一確定索引中的一條記錄，使用 up_match 作為新構造信息的字段數量，構造信息計數（info->n_hash_potential）重置為 1，重新開始計數。
否則，剩下兩種情況，取下界（因為比上界小）作為新構造信息。
cursor->low_match、low_bytes 都從 0 開始，變成數量時需要加 1。
如果 cmp 小于 0，命中 else_1，說明本次定位記錄時，下界大于上界，構造信息（prefix_info）的 left_side 屬性都會被設置為 false。
if (cursor->low_match == n_unique) 條件成立，說明搜索條件能夠唯一確定索引中的一條記錄，使用 low_match 作為新構造信息的字段數量，構造信息計數（info->n_hash_potential）重置為 1，重新開始計數。
否則，剩下兩種情況，取上界（因為比下界小）作為新構造信息。
cursor->up_match、up_bytes 都從 0 開始，變成數量時需要加 1。
（3）數據頁計數
btr_search_update_block_hash_info() 的主要邏輯分為 2 段：
- 第 1 段：更新數據頁計數。
- 第 2 段：根據構造信息計數、數據頁計數，決定是否需要為 block 對應的數據頁構造或重新構造 AHI。
先來看第 1 段代碼：
// storage/innobase/btr/btr0sea.cc
/****** 第 1 段 ******/
static bool btr_search_update_block_hash_info(...) {
...
const auto info = cursor->index->search_info;
// last_hash_succ 用于判斷 where 條件是否命中了 AHI
// 先設置為 false
info->last_hash_succ = false;
...
// 數據頁計數是否大于 0
if (block->n_hash_helps > 0 &&
// 構造信息計數是否大于 0
info->n_hash_potential > 0 &&
// 數據頁對象中保存的構造信息
// （可能還沒有用來構造過 AHI）
// 和本次確定的構造信息是否相同
block->ahi.recommended_prefix_info.load() == info->prefix_info.load()) {
if (block->ahi.index &&
block->ahi.prefix_info.load() == info->prefix_info.load()) {
// 數據頁對象中保存的構造信息（用來構造過 AHI）
// 和本次確定的構造信息相同
// 說明 where 條件命中了 AHI
// 把 info->last_hash_succ 設置為 true
// 下一篇文章講 AHI 命中時會用到這個屬性
info->last_hash_succ = true;
}
// 構造信息沒有變化，構造信息計數加 1
block->n_hash_helps++;
} else {
// 構造信息變了，重置數據頁計數
block->n_hash_helps = 1;
// 新確定的構造信息保存到數據頁對象中
block->ahi.recommended_prefix_info = info->prefix_info.load();
}
...
}如果以下 3 個條件都滿足：
- 數據頁計數（block->n_hash_helps）大于 0。
- 構造信息計數（info->n_hash_potential）大于 0。
- 數據頁對象中保存的構造信息（block->ahi.recommended_prefix_info）和本次確定的構造信息相同。
說明數據頁的構造信息沒有變化，數據頁計數加 1（block->n_hash_helps++）。
否則，數據頁計數重置為 1，并且保存新的構造信息到數據頁對象中（block->ahi.recommended_prefix_info）。
// storage/innobase/btr/btr0sea.cc
/****** 第 2 段 ******/
static bool btr_search_update_block_hash_info(...) {
...
// BTR_SEARCH_BUILD_LIMIT = 100
// 同一個索引的 AHI 構造信息
// 連續 100 次相同
if (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT &&
// BTR_SEARCH_PAGE_BUILD_LIMIT = 16
// 同樣的 AHI 構造信息
// 命中同一個數據頁的次數
// 達到了該數據頁中記錄數量的十六分之一
block->n_hash_helps >
page_get_n_recs(block->frame) / BTR_SEARCH_PAGE_BUILD_LIMIT) {
// 滿足上面 2 個條件之后
// 如果之前沒有構造過 AHI，則返回 true
// 表示本次需要構造 AHI
if (!block->ahi.index ||
// 如果之前已經構造過 AHI
// 需要命中同一個數據頁的次數
// 達到該數據頁中記錄數量的 2 倍
// 或者 AHI 構造信息發生了變化
// 才會重新構造 AHI
block->n_hash_helps > 2 * page_get_n_recs(block->frame) ||
block->ahi.recommended_prefix_info.load() !=
block->ahi.prefix_info.load()) {
return true;
}
}
// 不滿足上面的一系列條件
// 返回 false
// 表示本次不需要構造 AHI
return false;
}第 2 段代碼，用于判斷是否需要為數據頁（block）構造或重新構造 AHI，滿足以下兩個條件，說明具備了為該數據頁構造 AHI 的資格：
- 構造信息計數（info->n_hash_potential）大于等于 100。
- 數據頁計數（block->n_hash_helps）大于數據頁中記錄數量的十六分之一。
數據頁（block）具備構造 AHI 的資格之后，只有以下三種情況會構造或重新構造 AHI：
- 該數據頁之前沒有構造過 AHI（!block->ahi.index 為 true）。
- 該數據頁之前構造過 AHI，構造信息沒有發生變化，但是數據頁計數大于數據頁中記錄數量的兩倍（2 * page_get_n_recs(block->frame)）。
- 該數據頁之前構造過 AHI，但是構造信息變了。
（4）構造 AHI
滿足前面一系列條件之后，就可以為數據頁構造 AHI 了。
// storage/innobase/btr/btr0sea.cc
static void btr_search_build_page_hash_index(...) {
...
// block 是本次需要構造 AHI 的數據頁控制塊
// page 是數據頁對象
const auto page = buf_block_get_frame(block);
// 數據頁的 AHI 構造信息
const auto prefix_info = block->ahi.recommended_prefix_info.load();
const auto n_fields_for_offsets = btr_search_get_n_fields(prefix_info);
// 刪除之前為該數據頁構造的 AHI 記錄
if (block->ahi.index && block->ahi.prefix_info.load() != prefix_info) {
btr_search_drop_page_hash_index(block);
}
...
// 數據頁中的記錄數量
const auto n_recs = page_get_n_recs(page);
...
// page_get_infimum_rec(page) 讀取 infimum 偽記錄
// page_rec_get_next() 讀取數據頁中的第 1 條用戶記錄
auto rec = page_rec_get_next(page_get_infimum_rec(page));
Rec_offsets offsets;
...
// 用于構造第 1 條用戶記錄的 AHI 的 hash 種子
const auto index_hash = btr_hash_seed_for_record(index);
// 計算第 1 條用戶記錄的 AHI hash 值
auto hash_value =
rec_hash(rec, offsets.compute(rec, index, n_fields_for_offsets),
prefix_info.n_fields, prefix_info.n_bytes, index_hash, index);
size_t n_cached = 0;
// left_side = true
// 對于前綴相同的一組記錄（可能有一條或多條記錄）
// 標記需要為這一組的第一條記錄構造 AHI
if (prefix_info.left_side) {
hashes[n_cached] = hash_value;
recs[n_cached] = rec;
n_cached++;
}
// 循環，標記需要為數據頁中第 2 條及以后的用戶記錄構造 AHI
for (;;) {
const auto next_rec = page_rec_get_next(rec);
if (page_rec_is_supremum(next_rec)) {
// left_side = false 時
// 標記需要為 supremum 偽記錄構造 AHI
// 然后結束循環
if (!prefix_info.left_side) {
hashes[n_cached] = hash_value;
recs[n_cached] = rec;
n_cached++;
}
break;
}
// 為當前循環的記錄計算用于構造 AHI 的 hash 值
const auto next_hash_value = rec_hash(
next_rec, offsets.compute(next_rec, index, n_fields_for_offsets),
prefix_info.n_fields, prefix_info.n_bytes, index_hash, index);
// hash_value != next_hash_value
// 說明換了一組記錄
if (hash_value != next_hash_value) {
/* Insert an entry into the hash index */
// left_side = true
// 為下一組的第一條記錄構造 AHI
if (prefix_info.left_side) {
hashes[n_cached] = next_hash_value;
recs[n_cached] = next_rec;
n_cached++;
} else {
// left_side = false
// 為本組的最后一條記錄構造 AHI
hashes[n_cached] = hash_value;
recs[n_cached] = rec;
n_cached++;
}
}
rec = next_rec;
hash_value = next_hash_value;
}
...
// 為數據頁構造 AHI 之后
// 重置數據頁計數
block->n_hash_helps = 0;
// 已經用來構造過 AHI 構造信息保存到
// 數據頁對象的 ahi.prefix_info 屬性中
block->ahi.prefix_info = prefix_info;
block->ahi.index = index;
// 把每條記錄的 AHI hash 值和記錄地址
// 插入到 AHI hash 表中
const auto table = btr_get_search_table(index);
for (size_t i = 0; i < n_cached; i++) {
ha_insert_for_hash(table, hashes[i], block, recs[i]);
}
...
}為數據頁構造 AHI 主要分為三大步驟：
- 循環讀取數據頁中的記錄，每讀取一條記錄，根據 AHI 構造信息計算記錄的哈希值，把哈希值保存到 hashes 數組中、記錄地址保存到 recs 數組中，一條記錄在 hashs、recs 數組中的下標一樣，都是 n_cached。這一步有個特殊邏輯需要處理，就是對于前綴相同的一組記錄，根據 left_side 決定為第一條還是最后一條記錄構造 AHI。
- 數據頁計數（block->n_hash_helps）重置為 0，重新開始計數，用于為該數據頁重新構造 AHI 作準備。然后，把構造信息（prefix_info）、數據頁所屬的索引（index）分別保存到數據頁對象的 ahi.prefix_info、ahi.index 屬性中，btr_search_update_block_hash_info() 會用到這兩個屬性。
- 把 hashs、recs 數組中的哈希值、記錄地址一一對應的插入到哈希表中，每條記錄的哈希值映射到該記錄的地址。
4、總結
AHI 構造流程的前三步都是在判斷是否滿足某些條件，這些條件的范圍從大到小。
先是索引級別，判斷索引被命中的次數。
然后，是索引級別的構造信息計數。
構造信息來源于定位記錄過程中產生的下界、上界，其源頭是 where 條件，我們可以把它看成對 where 條件的抽象，或者更具體點，把它看成 where 條件的分類。
某個構造信息的計數達到指定次數，意味著如果根據這個構造信息（或者說這類 where 條件）構造 AHI，命中率會比較高。
InnoDB 以數據頁為單位，一次性為某個數據頁中的所有記錄構造 AHI。
構造信息計數滿足條件之后，還需要進一步決定為哪些數據頁構造 AHI，于是就有了數據頁計數（實際上是數據頁級別的構造信息計數）。
當索引計數、構造信息計數、數據頁計數都滿足條件之后，某個數據頁就初步具備了構造 AHI 的資格，最后，還會根據該數據頁是否構造過 AHI、構造信息是否發生變化等條件，做出終極決定：是否為該數據頁構造 AHI。
本文轉載自微信公眾號「一樹一溪」，可以通過以下二維碼關注。轉載本文請聯系一樹一溪公眾號。
