MySQL 自適應哈希索引—構造
曾經(jīng)優(yōu)化慢查詢時，經(jīng)常在日志中看到 truncate，當時一直疑惑 truncate 為什么會慢。
轉到數(shù)據(jù)庫方向之后，又碰到過幾次 truncate 執(zhí)行時間過長，導致 MySQL 短暫卡住的問題。
經(jīng)過源碼分析和同事測試驗證，發(fā)現(xiàn)這幾次的問題都跟自適應哈希索引有關，所以，深入研究下自適應哈希索引就很有必要了。
自適應哈希索引大概會有 3 篇文章。第 1 篇，我們來看看自適應哈希索引的構造過程。
本文基于 MySQL 8.0.32 源碼，存儲引擎為 InnoDB。
1、準備工作
創(chuàng)建測試表：
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插入測試數(shù)據(jù)：
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。
根據(jù)上下文需要，后續(xù)內容會混用自適應哈希索引和 AHI，不再單獨說明。
顧名思義，自適應哈希索引也是一種索引，使用哈希表作為存儲結構，自適應的意思是我們無法干涉它的創(chuàng)建、使用、更新、刪除，而是由 InnoDB 自行決定什么時候創(chuàng)建、怎么創(chuàng)建、什么時候更新和刪除。
我們知道 InnoDB 的主鍵索引、二級索引都是 B+ 樹結構。執(zhí)行 SQL 語句時，以下幾種場景都需要定位到索引葉子結點中的某條記錄：
- insert 需要定位到插入目標位置的前一條記錄。
- 查詢優(yōu)化階段，select、update、delete 預估掃描區(qū)間記錄數(shù)量時，需要定位到掃描區(qū)間的
第一條和最后一條記錄。 - 查詢執(zhí)行階段，select、update、delete 需要定位到掃描區(qū)間的
第一條記錄。
得益于多叉結構，B+ 樹的層級一般都比較少，通常情況下，從根結點開始，最多經(jīng)過 3 ~ 4 層就能定位到葉子結點中的記錄。
這個定位過程看起來挺快的，單次執(zhí)行也確實比較快，但是對于頻繁執(zhí)行的場景，還是有一點優(yōu)化空間的。
為了追求極致性能，InnoDB 實現(xiàn)了 AHI，目的就是能夠根據(jù)搜索條件直接定位到索引葉子結點中的記錄。
圖片
上圖是一棵高為 4 的 B+ 樹示意圖，定位索引葉子結點記錄，需要從根結點開始，經(jīng)過內結點、葉結點，最后定位到記錄，路徑為：① -> ② -> ③ -> ④
圖片
AHI 會使用多個 hash 桶來存儲哈希值到記錄地址的映射，上圖是一個 hash 桶的示意圖。
橙色塊表示記錄地址組成的鏈表，因為多條記錄可能被映射到 hash 桶中的同一個位置。
AHI 定位一條記錄時，根據(jù) where 條件中的某些字段計算出哈希值，然后直接到 hash 桶中找到對應的記錄。
如果多條記錄被映射到 hash 桶中的同一個位置，那么找到的是個鏈表，需要遍歷這個鏈表以找到目標記錄。
3、原理介紹
AHI 能提升定位記錄的效率，但是，有得到必然有付出，天上掉餡餅的事在計算機世界里是不會發(fā)生的。
為了簡潔，這里我們把定位索引葉子結點中的記錄簡稱為定位記錄，后面內容也依此定義，不再單獨說明。
高效定位記錄，付出的代價是存儲哈希值到記錄地址的映射占用的內存空間、以及構造映射花費的時間。
因為有時間、空間成本，所以，InnoDB 希望構造 AHI 之后，能夠盡可能多的用上，做到收益大于成本。直白點說，就是需要滿足一定的條件，才能構造 AHI。
AHI 采用的是組團構造邏輯，也就是以數(shù)據(jù)頁為單位，滿足一定條件之后，就會為數(shù)據(jù)頁中的所有記錄構造 AHI，主要流程如下：
圖片
第 1 步，為數(shù)據(jù)頁所屬的索引計數(shù)（index->search_info->hash_analysis）。
SQL 執(zhí)行過程中，每次定位某個索引葉子結點中的記錄，該索引的計數(shù)都會加 1。
如果索引計數(shù)達到 17，進入第 2 步，否則，執(zhí)行流程到此結束。
因為第 2、3 步為構造信息計數(shù)、為數(shù)據(jù)頁計數(shù)也是需要時間成本的，所以，這里設置了第 1 道檻，只有索引被使用一定次數(shù)之后，才會執(zhí)行第 2、3 步。
第 2 步，為構造信息計數(shù)（index->search_info->n_hash_potential）。
對于 select、insert、update、delete，定位記錄時，搜索條件和葉子結點中的記錄比較，會產(chǎn)生兩個邊界，左邊為下界，右邊為上界，基于下界和上界可以得到用于構造 AHI 的信息，我們稱之為構造信息。
圖片
以上是定位記錄時產(chǎn)生的下界、上界示意圖。定位記錄過程中，下界和上界會不斷向目標記錄靠近，最終，下界或上界的其中一個會指向目標記錄。
如果某次定位記錄時，基于下界或上界得到的構造信息，和索引對象中保存的構造信息一致，該構造信息計數(shù)加 1。否則，該索引計數(shù)清零，構造信息計數(shù)清零或重置為 1（具體見下一小節(jié)的介紹）。
第 3 步，為數(shù)據(jù)頁計數(shù)（block->n_hash_helps）。
定位到索引葉子結點記錄之后，就知道了該記錄所屬的數(shù)據(jù)頁，如果本次得到的構造信息和數(shù)據(jù)頁對象中保存的構造信息相同，數(shù)據(jù)頁計數(shù)加 1，否則數(shù)據(jù)頁計數(shù)重置為 1。
第 4 步，為數(shù)據(jù)頁構造 AHI。
如果滿足以下兩個條件，第 3 步的數(shù)據(jù)頁就具備了構造 AHI 的資格：
- 構造信息計數(shù)大于等于 100。
- 數(shù)據(jù)頁計數(shù)大于數(shù)據(jù)頁中記錄數(shù)量的十六分之一。
具備構造 AHI 的資格之后，對于以下三種情況之一，會為數(shù)據(jù)頁構造 AHI：
- 該數(shù)據(jù)頁之前沒有構造過 AHI。
- 該數(shù)據(jù)頁之前構造過 AHI，并且構造 AHI 之后，數(shù)據(jù)頁會從零開始重新計數(shù)，重新計數(shù)大于數(shù)據(jù)頁中記錄數(shù)量的兩倍。
- 該數(shù)據(jù)頁之前構造過 AHI，但是本次確定的構造信息和之前不一樣了。
注意：從各個條件判斷，到最終構造 AHI 的整個流程，并不是在執(zhí)行一條 SQL 的過程中完成的，而是在執(zhí)行多條 SQL 的過程中完成的。
到這里，構造 AHI 的主要流程就介紹完了，構造過程的具體細節(jié)，請繼續(xù)往下看。
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。
也就是說，對于正常的用戶表、系統(tǒng)表，!index->disable_ahi = true，會調用 btr_search_info_update()，進入 AHI 的構造流程。
（1）索引計數(shù)
構造 AHI 的第 1 步，就是調用 btr_search_info_update() 進行索引計數(shù)。
// storage/innobase/include/btr0sea.ic
static inline void btr_search_info_update(btr_cur_t *cursor) {
const auto index = cursor->index;
...
// 索引計數(shù)加 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() 每次被調用都會增加索引計數(shù)（++index->search_info->hash_analysis）。
自增之后，如果索引計數(shù)小于 17，不需要進入 AHI 構造流程的下一步，直接返回。
如果索引計數(shù)大于等于 17，調用 btr_search_info_update_slow()，進入 AHI 構造流程的下一步。
看到這里，大家是否會有疑問：對于一條能使用索引的 select 語句，如果 where 條件只有一個掃描區(qū)間，執(zhí)行過程中，btr_search_info_update() 最多會被調用幾次？
我們通過 1. 準備工作小節(jié)的示例 SQL 來揭曉答案，SQL 如下：
SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 301執(zhí)行計劃如下：
圖片
通過執(zhí)行計劃可知，示例 SQL 執(zhí)行過程中，會使用索引 idx_i1。
查詢優(yōu)化階段，MySQL 需要定位到掃描區(qū)間的第一條和最后一條記錄，用于計算掃描區(qū)間覆蓋的記錄數(shù)量：
- 定位掃描區(qū)間的第一條記錄，即滿足 id >= 101 的第一條記錄，第 1 次調用 btr_cur_search_to_nth_level()。
- 定位掃描掃描區(qū)間的最后一條記錄，即滿足 id < 301 的最后一條記錄，第 2 次調用 btr_cur_search_to_nth_level()。
查詢執(zhí)行階段，從存儲引擎讀取第一條記錄之前，需要定位掃描區(qū)間的第一條記錄，即滿足 id >= 101 的第一條記錄，第 3 次調用 btr_cur_search_to_nth_level()。
定位掃描區(qū)間的第一條和最后一條記錄，都是定位索引葉子結點中的記錄。
到這里，我們就得到了前面那個問題的答案：3 次。
（2）構造信息計數(shù)
如果某個索引的計數(shù)達到了 17，就會進入 AHI 構造流程的第 2 步，根據(jù)本次定位記錄過程中得到的下界和上界，確定使用索引的前幾個字段構造 AHI，以及對于索引中前幾個字段值相同的一組記錄，構造 AHI 時選擇這組記錄的第一條還是最后一條。
3.原理介紹小節(jié)的第 2 步，我們已經(jīng)把這些信息命名為構造信息。
基于定位記錄時得到的下界和上界確定構造信息、為構造信息計數(shù)的邏輯由 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 字節(jié)用于構造 AHI。
- left_side：如果索引中多條記錄的前 n_fields 個字段內容、第 n_fields + 1 個字段前 n_bytes 字節(jié)的內容相同，我們把這樣的一組記錄稱為前綴相同的記錄。對于前綴相同的記錄：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 = 主鍵段字數(shù)量
// 對于二級索引，n_unique = 二級索引字段數(shù)量 + 主鍵字段數(shù)量
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 ******/
// 構造信息計數(shù)不等于 0
// 說明之前已經(jīng)確定過構造信息了
if (info->n_hash_potential != 0) {
// info->prefix_info 中
// 保存了之前確定的構造信息
const auto prefix_info = info->prefix_info.load();
...
/****** if_2 ******/
// prefix_info.n_fields
// 表示之前確定的構造信息的字段數(shù)量
// std::max(up_match, low_match)
// 表示下界或上界字段數(shù)量中較大的那個
if (prefix_info.n_fields == n_unique &&
std::max(cursor->up_match, cursor->low_match) == n_unique) {
// 兩個條件都滿足，說明：
// 如果本次通過下界、上界確定構造信息
// 會和之前確定的構造信息相同
// 那么，構造信息計數(shù)加 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
// 如果構造信息【大于】下界，且【小于等于】上界
// 構造信息計數(shù)（n_hash_potential）加 1
// prefix_info.left_side = false
// 如果構造信息【小于等于】下界，且【大于】上界
// 構造信息計數(shù)（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;
}
}
...
}如果構造信息計數(shù)（info->n_hash_potential）不等于 0，if_1 條件成立，說明索引對象中已經(jīng)保存了之前確定的構造信息。
但是，確定索引的 AHI 構造信息之后，還需要該索引的構造信息計數(shù)、某個數(shù)據(jù)頁的計數(shù)滿足條件，InnoDB 才會為該索引的該數(shù)據(jù)頁構造 AHI。
所以，索引對象中已經(jīng)保存了之前確定的構造信息對應兩種情況：
- 已經(jīng)用索引中保存的構造信息為某個（些）數(shù)據(jù)頁構造了 AHI。
- 只確定了構造信息，還沒有用它構造過 AHI。
構造信息計數(shù)被命名為 n_hash_potential（潛在的），就是因為存在第 2 種情況。
if_2、if_3 用于判斷：通過本次定位記錄時產(chǎn)生的下界或上界得到構造信息，是否和索引對象中保存的構造信息一致，如果一致，則增加構造信息計數(shù)。
if_2 包含兩個表達式，如果值都為 true，說明上面的判斷結果為 true，構造信息計數(shù)加 1（info->n_hash_potential++）。
如果 if_2 不成立，再判斷 if_3 是否成立。
前面介紹過，對于前綴相同的一組記錄，構造 AHI 時，由 left_side 決定選擇最左邊還是最右邊的記錄。
對于本次定位記錄得到的下界、上界，left_side 決定它們怎么和索引對象中保存的構造信息比較。
left_side = true 時，如果以下兩個條件同時滿足，構造信息計數(shù)（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 時，如果以下兩個條件同時滿足，構造信息計數(shù)（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 成立，說明本次定位記錄得到的下界或上界的字段數(shù)量、字節(jié)數(shù)，和索引對象中保存的構造信息的字段數(shù)量（n_fields）、字節(jié)數(shù)（n_bytes）一致，構造信息計數(shù)加 1（info->n_hash_potential++）。
如果 if_3 不成立，說明構造信息變了，需要執(zhí)行第 2 段代碼，確定新的構造信息，并且重置構造信息計數(shù)。
// 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 條件沒有定位到匹配的記錄
// 構造信息計數(shù)清零
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
// 構造信息計數(shù)重置為 1
info->n_hash_potential = 1;
ut_ad(cursor->up_match <= n_unique);
// 如果上界字段數(shù)量等于 n_unique
// 使用上界作為新的構造信息
if (cursor->up_match == n_unique) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ n_unique,
/* left_side */ true
};
// 下界字段數(shù)量（low_match）小于上界字段數(shù)量（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
};
// 下界字段數(shù)量（low_match）等于上界字段數(shù)量（up_match）
// 下界字節(jié)數(shù)（low_bytes）小于上界字節(jié)數(shù)（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
// 構造信息計數(shù)重置為 1
info->n_hash_potential = 1;
ut_ad(cursor->low_match <= n_unique);
// 如果下界字段數(shù)量等于 n_unique
// 使用下界作為新的構造信息
if (cursor->low_match == n_unique) {
info->prefix_info = {
/* n_bytes */ 0,
/* n_fields */ n_unique,
/* left_side */ false
};
// 下界字段數(shù)量（low_match）大于上界字段數(shù)量（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
};
// 下界字段數(shù)量（low_match）等于上界字段數(shù)量（up_match）
// 下界字節(jié)數(shù)（low_bytes）大于上界字節(jié)數(shù)（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 段代碼用于首次或者重新確定構造信息，主要邏輯如下：
- 索引計數(shù)（info->hash_analysis）清零，下次調用 btr_search_info_update_hash() 時重新開始計數(shù)。
- 如果 left_side = true，并且本次定位記錄得到的下界字段數(shù)量等于 n_unique，使用下界作為新的構造信息。
- 如果 left_side = false，并且本次定位記錄得到的上界字段數(shù)量等于 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），也就是沒有找到匹配的記錄，構造信息計數(shù)（info->n_hash_potential）重置為 0。
如果 cmp 大于 0，命中 elseif_5，說明本次定位記錄時，下界小于上界，構造信息（prefix_info）的 left_side 屬性都會被設置為 true。
if (cursor->up_match == n_unique) 條件成立，說明搜索條件能夠唯一確定索引中的一條記錄，使用 up_match 作為新構造信息的字段數(shù)量，構造信息計數(shù)（info->n_hash_potential）重置為 1，重新開始計數(shù)。
否則，剩下兩種情況，取下界（因為比上界小）作為新構造信息。
cursor->low_match、low_bytes 都從 0 開始，變成數(shù)量時需要加 1。
如果 cmp 小于 0，命中 else_1，說明本次定位記錄時，下界大于上界，構造信息（prefix_info）的 left_side 屬性都會被設置為 false。
if (cursor->low_match == n_unique) 條件成立，說明搜索條件能夠唯一確定索引中的一條記錄，使用 low_match 作為新構造信息的字段數(shù)量，構造信息計數(shù)（info->n_hash_potential）重置為 1，重新開始計數(shù)。
否則，剩下兩種情況，取上界（因為比下界小）作為新構造信息。
cursor->up_match、up_bytes 都從 0 開始，變成數(shù)量時需要加 1。
（3）數(shù)據(jù)頁計數(shù)
btr_search_update_block_hash_info() 的主要邏輯分為 2 段：
- 第 1 段：更新數(shù)據(jù)頁計數(shù)。
- 第 2 段：根據(jù)構造信息計數(shù)、數(shù)據(jù)頁計數(shù)，決定是否需要為 block 對應的數(shù)據(jù)頁構造或重新構造 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;
...
// 數(shù)據(jù)頁計數(shù)是否大于 0
if (block->n_hash_helps > 0 &&
// 構造信息計數(shù)是否大于 0
info->n_hash_potential > 0 &&
// 數(shù)據(jù)頁對象中保存的構造信息
// （可能還沒有用來構造過 AHI）
// 和本次確定的構造信息是否相同
block->ahi.recommended_prefix_info.load() == info->prefix_info.load()) {
if (block->ahi.index &&
block->ahi.prefix_info.load() == info->prefix_info.load()) {
// 數(shù)據(jù)頁對象中保存的構造信息（用來構造過 AHI）
// 和本次確定的構造信息相同
// 說明 where 條件命中了 AHI
// 把 info->last_hash_succ 設置為 true
// 下一篇文章講 AHI 命中時會用到這個屬性
info->last_hash_succ = true;
}
// 構造信息沒有變化，構造信息計數(shù)加 1
block->n_hash_helps++;
} else {
// 構造信息變了，重置數(shù)據(jù)頁計數(shù)
block->n_hash_helps = 1;
// 新確定的構造信息保存到數(shù)據(jù)頁對象中
block->ahi.recommended_prefix_info = info->prefix_info.load();
}
...
}如果以下 3 個條件都滿足：
- 數(shù)據(jù)頁計數(shù)（block->n_hash_helps）大于 0。
- 構造信息計數(shù)（info->n_hash_potential）大于 0。
- 數(shù)據(jù)頁對象中保存的構造信息（block->ahi.recommended_prefix_info）和本次確定的構造信息相同。
說明數(shù)據(jù)頁的構造信息沒有變化，數(shù)據(jù)頁計數(shù)加 1（block->n_hash_helps++）。
否則，數(shù)據(jù)頁計數(shù)重置為 1，并且保存新的構造信息到數(shù)據(jù)頁對象中（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 構造信息
// 連續(xù) 100 次相同
if (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT &&
// BTR_SEARCH_PAGE_BUILD_LIMIT = 16
// 同樣的 AHI 構造信息
// 命中同一個數(shù)據(jù)頁的次數(shù)
// 達到了該數(shù)據(jù)頁中記錄數(shù)量的十六分之一
block->n_hash_helps >
page_get_n_recs(block->frame) / BTR_SEARCH_PAGE_BUILD_LIMIT) {
// 滿足上面 2 個條件之后
// 如果之前沒有構造過 AHI，則返回 true
// 表示本次需要構造 AHI
if (!block->ahi.index ||
// 如果之前已經(jīng)構造過 AHI
// 需要命中同一個數(shù)據(jù)頁的次數(shù)
// 達到該數(shù)據(jù)頁中記錄數(shù)量的 2 倍
// 或者 AHI 構造信息發(fā)生了變化
// 才會重新構造 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 段代碼，用于判斷是否需要為數(shù)據(jù)頁（block）構造或重新構造 AHI，滿足以下兩個條件，說明具備了為該數(shù)據(jù)頁構造 AHI 的資格：
- 構造信息計數(shù)（info->n_hash_potential）大于等于 100。
- 數(shù)據(jù)頁計數(shù)（block->n_hash_helps）大于數(shù)據(jù)頁中記錄數(shù)量的十六分之一。
數(shù)據(jù)頁（block）具備構造 AHI 的資格之后，只有以下三種情況會構造或重新構造 AHI：
- 該數(shù)據(jù)頁之前沒有構造過 AHI（!block->ahi.index 為 true）。
- 該數(shù)據(jù)頁之前構造過 AHI，構造信息沒有發(fā)生變化，但是數(shù)據(jù)頁計數(shù)大于數(shù)據(jù)頁中記錄數(shù)量的兩倍（2 * page_get_n_recs(block->frame)）。
- 該數(shù)據(jù)頁之前構造過 AHI，但是構造信息變了。
（4）構造 AHI
滿足前面一系列條件之后，就可以為數(shù)據(jù)頁構造 AHI 了。
// storage/innobase/btr/btr0sea.cc
static void btr_search_build_page_hash_index(...) {
...
// block 是本次需要構造 AHI 的數(shù)據(jù)頁控制塊
// page 是數(shù)據(jù)頁對象
const auto page = buf_block_get_frame(block);
// 數(shù)據(jù)頁的 AHI 構造信息
const auto prefix_info = block->ahi.recommended_prefix_info.load();
const auto n_fields_for_offsets = btr_search_get_n_fields(prefix_info);
// 刪除之前為該數(shù)據(jù)頁構造的 AHI 記錄
if (block->ahi.index && block->ahi.prefix_info.load() != prefix_info) {
btr_search_drop_page_hash_index(block);
}
...
// 數(shù)據(jù)頁中的記錄數(shù)量
const auto n_recs = page_get_n_recs(page);
...
// page_get_infimum_rec(page) 讀取 infimum 偽記錄
// page_rec_get_next() 讀取數(shù)據(jù)頁中的第 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++;
}
// 循環(huán)，標記需要為數(shù)據(jù)頁中第 2 條及以后的用戶記錄構造 AHI
for (;;) {
const auto next_rec = page_rec_get_next(rec);
if (page_rec_is_supremum(next_rec)) {
// left_side = false 時
// 標記需要為 supremum 偽記錄構造 AHI
// 然后結束循環(huán)
if (!prefix_info.left_side) {
hashes[n_cached] = hash_value;
recs[n_cached] = rec;
n_cached++;
}
break;
}
// 為當前循環(huán)的記錄計算用于構造 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;
}
...
// 為數(shù)據(jù)頁構造 AHI 之后
// 重置數(shù)據(jù)頁計數(shù)
block->n_hash_helps = 0;
// 已經(jīng)用來構造過 AHI 構造信息保存到
// 數(shù)據(jù)頁對象的 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]);
}
...
}為數(shù)據(jù)頁構造 AHI 主要分為三大步驟：
- 循環(huán)讀取數(shù)據(jù)頁中的記錄，每讀取一條記錄，根據(jù) AHI 構造信息計算記錄的哈希值，把哈希值保存到 hashes 數(shù)組中、記錄地址保存到 recs 數(shù)組中，一條記錄在 hashs、recs 數(shù)組中的下標一樣，都是 n_cached。這一步有個特殊邏輯需要處理，就是對于前綴相同的一組記錄，根據(jù) left_side 決定為第一條還是最后一條記錄構造 AHI。
- 數(shù)據(jù)頁計數(shù)（block->n_hash_helps）重置為 0，重新開始計數(shù)，用于為該數(shù)據(jù)頁重新構造 AHI 作準備。然后，把構造信息（prefix_info）、數(shù)據(jù)頁所屬的索引（index）分別保存到數(shù)據(jù)頁對象的 ahi.prefix_info、ahi.index 屬性中，btr_search_update_block_hash_info() 會用到這兩個屬性。
- 把 hashs、recs 數(shù)組中的哈希值、記錄地址一一對應的插入到哈希表中，每條記錄的哈希值映射到該記錄的地址。
4、總結
AHI 構造流程的前三步都是在判斷是否滿足某些條件，這些條件的范圍從大到小。
先是索引級別，判斷索引被命中的次數(shù)。
然后，是索引級別的構造信息計數(shù)。
構造信息來源于定位記錄過程中產(chǎn)生的下界、上界，其源頭是 where 條件，我們可以把它看成對 where 條件的抽象，或者更具體點，把它看成 where 條件的分類。
某個構造信息的計數(shù)達到指定次數(shù)，意味著如果根據(jù)這個構造信息（或者說這類 where 條件）構造 AHI，命中率會比較高。
InnoDB 以數(shù)據(jù)頁為單位，一次性為某個數(shù)據(jù)頁中的所有記錄構造 AHI。
構造信息計數(shù)滿足條件之后，還需要進一步?jīng)Q定為哪些數(shù)據(jù)頁構造 AHI，于是就有了數(shù)據(jù)頁計數(shù)（實際上是數(shù)據(jù)頁級別的構造信息計數(shù)）。
當索引計數(shù)、構造信息計數(shù)、數(shù)據(jù)頁計數(shù)都滿足條件之后，某個數(shù)據(jù)頁就初步具備了構造 AHI 的資格，最后，還會根據(jù)該數(shù)據(jù)頁是否構造過 AHI、構造信息是否發(fā)生變化等條件，做出終極決定：是否為該數(shù)據(jù)頁構造 AHI。
本文轉載自微信公眾號「一樹一溪」，可以通過以下二維碼關注。轉載本文請聯(lián)系一樹一溪公眾號。
