MySQL 自適應(yīng)哈希索引—構(gòu)造

作者：操盛春 2023-07-31 08:24:34

數(shù)據(jù)庫(kù) MySQL

AHI 構(gòu)造流程的前三步都是在判斷是否滿(mǎn)足某些條件，這些條件的范圍從大到小。先是索引級(jí)別，判斷索引被命中的次數(shù)。然后，是索引級(jí)別的構(gòu)造信息計(jì)數(shù)。

曾經(jīng)優(yōu)化慢查詢(xún)時(shí)，經(jīng)常在日志中看到 truncate，當(dāng)時(shí)一直疑惑 truncate 為什么會(huì)慢。

轉(zhuǎn)到數(shù)據(jù)庫(kù)方向之后，又碰到過(guò)幾次 truncate 執(zhí)行時(shí)間過(guò)長(zhǎng)，導(dǎo)致 MySQL 短暫卡住的問(wèn)題。

經(jīng)過(guò)源碼分析和同事測(cè)試驗(yàn)證，發(fā)現(xiàn)這幾次的問(wèn)題都跟自適應(yīng)哈希索引有關(guān)，所以，深入研究下自適應(yīng)哈希索引就很有必要了。

自適應(yīng)哈希索引大概會(huì)有 3 篇文章。第 1 篇，我們來(lái)看看自適應(yīng)哈希索引的構(gòu)造過(guò)程。

本文基于 MySQL 8.0.32 源碼，存儲(chǔ)引擎為 InnoDB。

1、準(zhǔn)備工作

創(chuàng)建測(cè)試表：

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

插入測(cè)試數(shù)據(jù)：

INSERT INTO `t1`(`id`, `i1`)
VALUES (10, 101), (20, 201), (30, 301);

示例 SQL：

SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 301

2、AHI 有什么好處？

自適應(yīng)哈希索引，英文全稱(chēng) Adaptive Hash Index，簡(jiǎn)稱(chēng) AHI。

根據(jù)上下文需要，后續(xù)內(nèi)容會(huì)混用自適應(yīng)哈希索引和 AHI，不再單獨(dú)說(shuō)明。

顧名思義，自適應(yīng)哈希索引也是一種索引，使用哈希表作為存儲(chǔ)結(jié)構(gòu)，自適應(yīng)的意思是我們無(wú)法干涉它的創(chuàng)建、使用、更新、刪除，而是由 InnoDB 自行決定什么時(shí)候創(chuàng)建、怎么創(chuàng)建、什么時(shí)候更新和刪除。

我們知道 InnoDB 的主鍵索引、二級(jí)索引都是 B+ 樹(shù)結(jié)構(gòu)。執(zhí)行 SQL 語(yǔ)句時(shí)，以下幾種場(chǎng)景都需要定位到索引葉子結(jié)點(diǎn)中的某條記錄：

insert 需要定位到插入目標(biāo)位置的前一條記錄。
查詢(xún)優(yōu)化階段，select、update、delete 預(yù)估掃描區(qū)間記錄數(shù)量時(shí)，需要定位到掃描區(qū)間的第一條和最后一條記錄。
查詢(xún)執(zhí)行階段，select、update、delete 需要定位到掃描區(qū)間的第一條記錄。

得益于多叉結(jié)構(gòu)，B+ 樹(shù)的層級(jí)一般都比較少，通常情況下，從根結(jié)點(diǎn)開(kāi)始，最多經(jīng)過(guò) 3 ~ 4 層就能定位到葉子結(jié)點(diǎn)中的記錄。

這個(gè)定位過(guò)程看起來(lái)挺快的，單次執(zhí)行也確實(shí)比較快，但是對(duì)于頻繁執(zhí)行的場(chǎng)景，還是有一點(diǎn)優(yōu)化空間的。

為了追求極致性能，InnoDB 實(shí)現(xiàn)了 AHI，目的就是能夠根據(jù)搜索條件直接定位到索引葉子結(jié)點(diǎn)中的記錄。

圖片

上圖是一棵高為 4 的 B+ 樹(shù)示意圖，定位索引葉子結(jié)點(diǎn)記錄，需要從根結(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)內(nèi)結(jié)點(diǎn)、葉結(jié)點(diǎn)，最后定位到記錄，路徑為：① -> ② -> ③ -> ④

圖片

AHI 會(huì)使用多個(gè) hash 桶來(lái)存儲(chǔ)哈希值到記錄地址的映射，上圖是一個(gè) hash 桶的示意圖。

橙色塊表示記錄地址組成的鏈表，因?yàn)槎鄺l記錄可能被映射到 hash 桶中的同一個(gè)位置。

AHI 定位一條記錄時(shí)，根據(jù) where 條件中的某些字段計(jì)算出哈希值，然后直接到 hash 桶中找到對(duì)應(yīng)的記錄。

如果多條記錄被映射到 hash 桶中的同一個(gè)位置，那么找到的是個(gè)鏈表，需要遍歷這個(gè)鏈表以找到目標(biāo)記錄。

3、原理介紹

AHI 能提升定位記錄的效率，但是，有得到必然有付出，天上掉餡餅的事在計(jì)算機(jī)世界里是不會(huì)發(fā)生的。

為了簡(jiǎn)潔，這里我們把定位索引葉子結(jié)點(diǎn)中的記錄簡(jiǎn)稱(chēng)為定位記錄，后面內(nèi)容也依此定義，不再單獨(dú)說(shuō)明。

高效定位記錄，付出的代價(jià)是存儲(chǔ)哈希值到記錄地址的映射占用的內(nèi)存空間、以及構(gòu)造映射花費(fèi)的時(shí)間。

因?yàn)橛袝r(shí)間、空間成本，所以，InnoDB 希望構(gòu)造 AHI 之后，能夠盡可能多的用上，做到收益大于成本。直白點(diǎn)說(shuō)，就是需要滿(mǎn)足一定的條件，才能構(gòu)造 AHI。

AHI 采用的是組團(tuán)構(gòu)造邏輯，也就是以數(shù)據(jù)頁(yè)為單位，滿(mǎn)足一定條件之后，就會(huì)為數(shù)據(jù)頁(yè)中的所有記錄構(gòu)造 AHI，主要流程如下：

圖片

第 1 步，為數(shù)據(jù)頁(yè)所屬的索引計(jì)數(shù)（index->search_info->hash_analysis）。

SQL 執(zhí)行過(guò)程中，每次定位某個(gè)索引葉子結(jié)點(diǎn)中的記錄，該索引的計(jì)數(shù)都會(huì)加 1。

如果索引計(jì)數(shù)達(dá)到 17，進(jìn)入第 2 步，否則，執(zhí)行流程到此結(jié)束。

因?yàn)榈?2、3 步為構(gòu)造信息計(jì)數(shù)、為數(shù)據(jù)頁(yè)計(jì)數(shù)也是需要時(shí)間成本的，所以，這里設(shè)置了第 1 道檻，只有索引被使用一定次數(shù)之后，才會(huì)執(zhí)行第 2、3 步。

第 2 步，為構(gòu)造信息計(jì)數(shù)（index->search_info->n_hash_potential）。

對(duì)于 select、insert、update、delete，定位記錄時(shí)，搜索條件和葉子結(jié)點(diǎn)中的記錄比較，會(huì)產(chǎn)生兩個(gè)邊界，左邊為下界，右邊為上界，基于下界和上界可以得到用于構(gòu)造 AHI 的信息，我們稱(chēng)之為構(gòu)造信息。

圖片

以上是定位記錄時(shí)產(chǎn)生的下界、上界示意圖。定位記錄過(guò)程中，下界和上界會(huì)不斷向目標(biāo)記錄靠近，最終，下界或上界的其中一個(gè)會(huì)指向目標(biāo)記錄。

如果某次定位記錄時(shí)，基于下界或上界得到的構(gòu)造信息，和索引對(duì)象中保存的構(gòu)造信息一致，該構(gòu)造信息計(jì)數(shù)加 1。否則，該索引計(jì)數(shù)清零，構(gòu)造信息計(jì)數(shù)清零或重置為 1（具體見(jiàn)下一小節(jié)的介紹）。

第 3 步，為數(shù)據(jù)頁(yè)計(jì)數(shù)（block->n_hash_helps）。

定位到索引葉子結(jié)點(diǎn)記錄之后，就知道了該記錄所屬的數(shù)據(jù)頁(yè)，如果本次得到的構(gòu)造信息和數(shù)據(jù)頁(yè)對(duì)象中保存的構(gòu)造信息相同，數(shù)據(jù)頁(yè)計(jì)數(shù)加 1，否則數(shù)據(jù)頁(yè)計(jì)數(shù)重置為 1。

第 4 步，為數(shù)據(jù)頁(yè)構(gòu)造 AHI。

如果滿(mǎn)足以下兩個(gè)條件，第 3 步的數(shù)據(jù)頁(yè)就具備了構(gòu)造 AHI 的資格：

構(gòu)造信息計(jì)數(shù)大于等于 100。
數(shù)據(jù)頁(yè)計(jì)數(shù)大于數(shù)據(jù)頁(yè)中記錄數(shù)量的十六分之一。

具備構(gòu)造 AHI 的資格之后，對(duì)于以下三種情況之一，會(huì)為數(shù)據(jù)頁(yè)構(gòu)造 AHI：

該數(shù)據(jù)頁(yè)之前沒(méi)有構(gòu)造過(guò) AHI。
該數(shù)據(jù)頁(yè)之前構(gòu)造過(guò) AHI，并且構(gòu)造 AHI 之后，數(shù)據(jù)頁(yè)會(huì)從零開(kāi)始重新計(jì)數(shù)，重新計(jì)數(shù)大于數(shù)據(jù)頁(yè)中記錄數(shù)量的兩倍。
該數(shù)據(jù)頁(yè)之前構(gòu)造過(guò) AHI，但是本次確定的構(gòu)造信息和之前不一樣了。

注意：從各個(gè)條件判斷，到最終構(gòu)造 AHI 的整個(gè)流程，并不是在執(zhí)行一條 SQL 的過(guò)程中完成的，而是在執(zhí)行多條 SQL 的過(guò)程中完成的。

到這里，構(gòu)造 AHI 的主要流程就介紹完了，構(gòu)造過(guò)程的具體細(xì)節(jié)，請(qǐng)繼續(xù)往下看。

4、構(gòu)造過(guò)程

定位記錄會(huì)調(diào)用 btr_cur_search_to_nth_level()，這也是 AHI 的構(gòu)造入口：

// storage/innobase/btr/btr0cur.cc
void btr_cur_search_to_nth_level(...) {
  ...
  if (btr_search_enabled && 
      !index->disable_ahi) {
    // AHI 的構(gòu)造入口
    btr_search_info_update(cursor);
  }
  ...
}

btr_search_enabled = true（默認(rèn)值），表示 InnoDB 啟用了 AHI。

!index->disable_ahi = true，即 index->disable_ahi = false，表示 index 對(duì)應(yīng)的索引沒(méi)有禁用 AHI。

只有內(nèi)部臨時(shí)表、沒(méi)有主鍵的表禁用了 AHI。

也就是說(shuō)，對(duì)于正常的用戶(hù)表、系統(tǒng)表，!index->disable_ahi = true，會(huì)調(diào)用 btr_search_info_update()，進(jìn)入 AHI 的構(gòu)造流程。

（1）索引計(jì)數(shù)

構(gòu)造 AHI 的第 1 步，就是調(diào)用 btr_search_info_update() 進(jìn)行索引計(jì)數(shù)。

// storage/innobase/include/btr0sea.ic
static inline void btr_search_info_update(btr_cur_t *cursor) {
  const auto index = cursor->index;
  ...
  // 索引計(jì)數(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() 每次被調(diào)用都會(huì)增加索引計(jì)數(shù)（++index->search_info->hash_analysis）。

自增之后，如果索引計(jì)數(shù)小于 17，不需要進(jìn)入 AHI 構(gòu)造流程的下一步，直接返回。

如果索引計(jì)數(shù)大于等于 17，調(diào)用 btr_search_info_update_slow()，進(jìn)入 AHI 構(gòu)造流程的下一步。

看到這里，大家是否會(huì)有疑問(wèn)：對(duì)于一條能使用索引的 select 語(yǔ)句，如果 where 條件只有一個(gè)掃描區(qū)間，執(zhí)行過(guò)程中，btr_search_info_update() 最多會(huì)被調(diào)用幾次？

我們通過(guò) 1. 準(zhǔn)備工作小節(jié)的示例 SQL 來(lái)揭曉答案，SQL 如下：

SELECT * FROM `t1`
WHERE `i1` >= 101 AND `i1` < 301

執(zhí)行計(jì)劃如下：

圖片

通過(guò)執(zhí)行計(jì)劃可知，示例 SQL 執(zhí)行過(guò)程中，會(huì)使用索引 idx_i1。

查詢(xún)優(yōu)化階段，MySQL 需要定位到掃描區(qū)間的第一條和最后一條記錄，用于計(jì)算掃描區(qū)間覆蓋的記錄數(shù)量：

定位掃描區(qū)間的第一條記錄，即滿(mǎn)足 id >= 101 的第一條記錄，第 1 次調(diào)用 btr_cur_search_to_nth_level()。
定位掃描掃描區(qū)間的最后一條記錄，即滿(mǎn)足 id < 301 的最后一條記錄，第 2 次調(diào)用 btr_cur_search_to_nth_level()。

查詢(xún)執(zhí)行階段，從存儲(chǔ)引擎讀取第一條記錄之前，需要定位掃描區(qū)間的第一條記錄，即滿(mǎn)足 id >= 101 的第一條記錄，第 3 次調(diào)用 btr_cur_search_to_nth_level()。

定位掃描區(qū)間的第一條和最后一條記錄，都是定位索引葉子結(jié)點(diǎn)中的記錄。

到這里，我們就得到了前面那個(gè)問(wèn)題的答案：3 次。

（2）構(gòu)造信息計(jì)數(shù)

如果某個(gè)索引的計(jì)數(shù)達(dá)到了 17，就會(huì)進(jìn)入 AHI 構(gòu)造流程的第 2 步，根據(jù)本次定位記錄過(guò)程中得到的下界和上界，確定使用索引的前幾個(gè)字段構(gòu)造 AHI，以及對(duì)于索引中前幾個(gè)字段值相同的一組記錄，構(gòu)造 AHI 時(shí)選擇這組記錄的第一條還是最后一條。

3.原理介紹小節(jié)的第 2 步，我們已經(jīng)把這些信息命名為構(gòu)造信息。

基于定位記錄時(shí)得到的下界和上界確定構(gòu)造信息、為構(gòu)造信息計(jì)數(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() 的代碼有點(diǎn)長(zhǎng)，我們分 2 段介紹。

介紹第 1 段代碼之前，我們先來(lái)看看表示構(gòu)造信息的結(jié)構(gòu)體定義（index->search_info->prefix_info）：

// storage/innobase/include/buf0buf.h
// 為了方便閱讀，以下結(jié)構(gòu)體定義對(duì)源碼做了刪減
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 個(gè)屬性：

n_fields、n_bytes：索引的前 n_fields 個(gè)字段，第 n_fields + 1 個(gè)字段的前 n_bytes 字節(jié)用于構(gòu)造 AHI。
left_side：如果索引中多條記錄的前 n_fields 個(gè)字段內(nèi)容、第 n_fields + 1 個(gè)字段前 n_bytes 字節(jié)的內(nèi)容相同，我們把這樣的一組記錄稱(chēng)為前綴相同的記錄。對(duì)于前綴相同的記錄：left_side = true 時(shí)，選擇最左邊的記錄（第一條記錄）構(gòu)造 AHI。left_side = false 時(shí)，選擇最右邊的記錄（最后一條記錄）構(gòu)造 AHI。

接下來(lái)，我們開(kāi)始介紹 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;
  ...
  // 索引中，通過(guò)幾個(gè)字段能唯一確定一條記錄？
  // 對(duì)于主鍵索引，n_unique = 主鍵段字?jǐn)?shù)量
  // 對(duì)于二級(jí)索引，n_unique = 二級(jí)索引字段數(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 ******/
  // 構(gòu)造信息計(jì)數(shù)不等于 0
  // 說(shuō)明之前已經(jīng)確定過(guò)構(gòu)造信息了
  if (info->n_hash_potential != 0) {
    // info->prefix_info 中
    // 保存了之前確定的構(gòu)造信息
    const auto prefix_info = info->prefix_info.load();
    ...

    /****** if_2 ******/
    // prefix_info.n_fields
    //   表示之前確定的構(gòu)造信息的字段數(shù)量
    // std::max(up_match, low_match)
    //   表示下界或上界字段數(shù)量中較大的那個(gè)
    if (prefix_info.n_fields == n_unique &&
        std::max(cursor->up_match, cursor->low_match) == n_unique) {
      // 兩個(gè)條件都滿(mǎn)足，說(shuō)明：
      //   如果本次通過(guò)下界、上界確定構(gòu)造信息
      //   會(huì)和之前確定的構(gòu)造信息相同
      //   那么，構(gòu)造信息計(jì)數(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 ******/
    // 這里的構(gòu)造信息指的是：
    //   索引對(duì)象中保存的之前確定的構(gòu)造信息
    // prefix_info.left_side = true
    //   如果構(gòu)造信息【大于】下界，且【小于等于】上界
    //   構(gòu)造信息計(jì)數(shù)（n_hash_potential）加 1
    // prefix_info.left_side = false
    //   如果構(gòu)造信息【小于等于】下界，且【大于】上界
    //   構(gòu)造信息計(jì)數(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;
    }
  }
  ...
}

如果構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）不等于 0，if_1 條件成立，說(shuō)明索引對(duì)象中已經(jīng)保存了之前確定的構(gòu)造信息。

但是，確定索引的 AHI 構(gòu)造信息之后，還需要該索引的構(gòu)造信息計(jì)數(shù)、某個(gè)數(shù)據(jù)頁(yè)的計(jì)數(shù)滿(mǎn)足條件，InnoDB 才會(huì)為該索引的該數(shù)據(jù)頁(yè)構(gòu)造 AHI。

所以，索引對(duì)象中已經(jīng)保存了之前確定的構(gòu)造信息對(duì)應(yīng)兩種情況：

已經(jīng)用索引中保存的構(gòu)造信息為某個(gè)（些）數(shù)據(jù)頁(yè)構(gòu)造了 AHI。
只確定了構(gòu)造信息，還沒(méi)有用它構(gòu)造過(guò) AHI。

構(gòu)造信息計(jì)數(shù)被命名為 n_hash_potential（潛在的），就是因?yàn)榇嬖诘?2 種情況。

if_2、if_3 用于判斷：通過(guò)本次定位記錄時(shí)產(chǎn)生的下界或上界得到構(gòu)造信息，是否和索引對(duì)象中保存的構(gòu)造信息一致，如果一致，則增加構(gòu)造信息計(jì)數(shù)。

if_2 包含兩個(gè)表達(dá)式，如果值都為 true，說(shuō)明上面的判斷結(jié)果為 true，構(gòu)造信息計(jì)數(shù)加 1（info->n_hash_potential++）。

如果 if_2 不成立，再判斷 if_3 是否成立。

前面介紹過(guò)，對(duì)于前綴相同的一組記錄，構(gòu)造 AHI 時(shí)，由 left_side 決定選擇最左邊還是最右邊的記錄。

對(duì)于本次定位記錄得到的下界、上界，left_side 決定它們?cè)趺春退饕龑?duì)象中保存的構(gòu)造信息比較。

left_side = true 時(shí)，如果以下兩個(gè)條件同時(shí)滿(mǎn)足，構(gòu)造信息計(jì)數(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í)，如果以下兩個(gè)條件同時(shí)滿(mǎn)足，構(gòu)造信息計(jì)數(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 成立，說(shuō)明本次定位記錄得到的下界或上界的字段數(shù)量、字節(jié)數(shù)，和索引對(duì)象中保存的構(gòu)造信息的字段數(shù)量（n_fields）、字節(jié)數(shù)（n_bytes）一致，構(gòu)造信息計(jì)數(shù)加 1（info->n_hash_potential++）。

如果 if_3 不成立，說(shuō)明構(gòu)造信息變了，需要執(zhí)行第 2 段代碼，確定新的構(gòu)造信息，并且重置構(gòu)造信息計(jì)數(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 條件沒(méi)有定位到匹配的記錄
    // 構(gòu)造信息計(jì)數(shù)清零
    info->n_hash_potential = 0;
    // 雖然給構(gòu)造信息賦值了，但是這個(gè)信息不會(huì)被使用
    /* 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 都會(huì)設(shè)置為 true
    // 構(gòu)造信息計(jì)數(shù)重置為 1
    info->n_hash_potential = 1;

    ut_ad(cursor->up_match <= n_unique);
    // 如果上界字段數(shù)量等于 n_unique
    // 使用上界作為新的構(gòu)造信息
    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）
    // 使用下界作為新的構(gòu)造信息
    } 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）
    // 使用下界作為新的構(gòu)造信息
    } 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 都會(huì)設(shè)置為 false
    // 構(gòu)造信息計(jì)數(shù)重置為 1
    info->n_hash_potential = 1;

    ut_ad(cursor->low_match <= n_unique);
    // 如果下界字段數(shù)量等于 n_unique
    // 使用下界作為新的構(gòu)造信息
    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）
    // 使用上界作為新的構(gòu)造信息
    } 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）
    // 使用上界作為新的構(gòu)造信息
    } 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 段代碼用于首次或者重新確定構(gòu)造信息，主要邏輯如下：

索引計(jì)數(shù)（info->hash_analysis）清零，下次調(diào)用 btr_search_info_update_hash() 時(shí)重新開(kāi)始計(jì)數(shù)。
如果 left_side = true，并且本次定位記錄得到的下界字段數(shù)量等于 n_unique，使用下界作為新的構(gòu)造信息。
如果 left_side = false，并且本次定位記錄得到的上界字段數(shù)量等于 n_unique，使用上界作為新的構(gòu)造信息。
否則，選擇本次定位記錄得到的上界、下界中較小的那個(gè)作為新的構(gòu)造信息。

ut_pair_cmp(up_match, up_bytes, low_match, low_bytes) 比較本次定位記錄得到的上界、下界，比較結(jié)果保存到 cmp 中。

如果 cmp 等于 0，命中 if_4，說(shuō)明 btr_cur_search_to_nth_level() 定位記錄時(shí)，上界、下界相同（up_match 等于 low_match、up_bytes 等于 low_bytes），也就是沒(méi)有找到匹配的記錄，構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）重置為 0。

如果 cmp 大于 0，命中 elseif_5，說(shuō)明本次定位記錄時(shí)，下界小于上界，構(gòu)造信息（prefix_info）的 left_side 屬性都會(huì)被設(shè)置為 true。

if (cursor->up_match == n_unique) 條件成立，說(shuō)明搜索條件能夠唯一確定索引中的一條記錄，使用 up_match 作為新構(gòu)造信息的字段數(shù)量，構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）重置為 1，重新開(kāi)始計(jì)數(shù)。

否則，剩下兩種情況，取下界（因?yàn)楸壬辖缧。┳鳛樾聵?gòu)造信息。

cursor->low_match、low_bytes 都從 0 開(kāi)始，變成數(shù)量時(shí)需要加 1。

如果 cmp 小于 0，命中 else_1，說(shuō)明本次定位記錄時(shí)，下界大于上界，構(gòu)造信息（prefix_info）的 left_side 屬性都會(huì)被設(shè)置為 false。

if (cursor->low_match == n_unique) 條件成立，說(shuō)明搜索條件能夠唯一確定索引中的一條記錄，使用 low_match 作為新構(gòu)造信息的字段數(shù)量，構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）重置為 1，重新開(kāi)始計(jì)數(shù)。

否則，剩下兩種情況，取上界（因?yàn)楸认陆缧。┳鳛樾聵?gòu)造信息。

cursor->up_match、up_bytes 都從 0 開(kāi)始，變成數(shù)量時(shí)需要加 1。

（3）數(shù)據(jù)頁(yè)計(jì)數(shù)

btr_search_update_block_hash_info() 的主要邏輯分為 2 段：

第 1 段：更新數(shù)據(jù)頁(yè)計(jì)數(shù)。
第 2 段：根據(jù)構(gòu)造信息計(jì)數(shù)、數(shù)據(jù)頁(yè)計(jì)數(shù)，決定是否需要為 block 對(duì)應(yīng)的數(shù)據(jù)頁(yè)構(gòu)造或重新構(gòu)造 AHI。

先來(lái)看第 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
  // 先設(shè)置為 false
  info->last_hash_succ = false;
  ...
  // 數(shù)據(jù)頁(yè)計(jì)數(shù)是否大于 0
  if (block->n_hash_helps > 0 && 
      // 構(gòu)造信息計(jì)數(shù)是否大于 0
      info->n_hash_potential > 0 &&
      // 數(shù)據(jù)頁(yè)對(duì)象中保存的構(gòu)造信息
      //  （可能還沒(méi)有用來(lái)構(gòu)造過(guò) AHI）
      // 和本次確定的構(gòu)造信息是否相同
      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ù)頁(yè)對(duì)象中保存的構(gòu)造信息（用來(lái)構(gòu)造過(guò) AHI）
      // 和本次確定的構(gòu)造信息相同
      // 說(shuō)明 where 條件命中了 AHI
      // 把 info->last_hash_succ 設(shè)置為 true
      // 下一篇文章講 AHI 命中時(shí)會(huì)用到這個(gè)屬性
      info->last_hash_succ = true;
    }
    // 構(gòu)造信息沒(méi)有變化，構(gòu)造信息計(jì)數(shù)加 1
    block->n_hash_helps++;
  } else {
    // 構(gòu)造信息變了，重置數(shù)據(jù)頁(yè)計(jì)數(shù)
    block->n_hash_helps = 1;
    // 新確定的構(gòu)造信息保存到數(shù)據(jù)頁(yè)對(duì)象中
    block->ahi.recommended_prefix_info = info->prefix_info.load();
  }
  ...
}

如果以下 3 個(gè)條件都滿(mǎn)足：

數(shù)據(jù)頁(yè)計(jì)數(shù)（block->n_hash_helps）大于 0。
構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）大于 0。
數(shù)據(jù)頁(yè)對(duì)象中保存的構(gòu)造信息（block->ahi.recommended_prefix_info）和本次確定的構(gòu)造信息相同。

說(shuō)明數(shù)據(jù)頁(yè)的構(gòu)造信息沒(méi)有變化，數(shù)據(jù)頁(yè)計(jì)數(shù)加 1（block->n_hash_helps++）。

否則，數(shù)據(jù)頁(yè)計(jì)數(shù)重置為 1，并且保存新的構(gòu)造信息到數(shù)據(jù)頁(yè)對(duì)象中（block->ahi.recommended_prefix_info）。

// storage/innobase/btr/btr0sea.cc
/****** 第 2 段 ******/
static bool btr_search_update_block_hash_info(...) {
  ...
  // BTR_SEARCH_BUILD_LIMIT = 100
  // 同一個(gè)索引的 AHI 構(gòu)造信息
  // 連續(xù) 100 次相同
  if (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT &&
      // BTR_SEARCH_PAGE_BUILD_LIMIT = 16
      // 同樣的 AHI 構(gòu)造信息
      // 命中同一個(gè)數(shù)據(jù)頁(yè)的次數(shù)
      // 達(dá)到了該數(shù)據(jù)頁(yè)中記錄數(shù)量的十六分之一
      block->n_hash_helps >
          page_get_n_recs(block->frame) / BTR_SEARCH_PAGE_BUILD_LIMIT) {
    // 滿(mǎn)足上面 2 個(gè)條件之后
    // 如果之前沒(méi)有構(gòu)造過(guò) AHI，則返回 true
    // 表示本次需要構(gòu)造 AHI
    if (!block->ahi.index ||
        // 如果之前已經(jīng)構(gòu)造過(guò) AHI
        // 需要命中同一個(gè)數(shù)據(jù)頁(yè)的次數(shù)
        //   達(dá)到該數(shù)據(jù)頁(yè)中記錄數(shù)量的 2 倍
        // 或者 AHI 構(gòu)造信息發(fā)生了變化
        // 才會(huì)重新構(gòu)造 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;
    }
  }

  // 不滿(mǎn)足上面的一系列條件
  // 返回 false
  // 表示本次不需要構(gòu)造 AHI
  return false;
}

第 2 段代碼，用于判斷是否需要為數(shù)據(jù)頁(yè)（block）構(gòu)造或重新構(gòu)造 AHI，滿(mǎn)足以下兩個(gè)條件，說(shuō)明具備了為該數(shù)據(jù)頁(yè)構(gòu)造 AHI 的資格：

構(gòu)造信息計(jì)數(shù)（info->n_hash_potential）大于等于 100。
數(shù)據(jù)頁(yè)計(jì)數(shù)（block->n_hash_helps）大于數(shù)據(jù)頁(yè)中記錄數(shù)量的十六分之一。

數(shù)據(jù)頁(yè)（block）具備構(gòu)造 AHI 的資格之后，只有以下三種情況會(huì)構(gòu)造或重新構(gòu)造 AHI：

該數(shù)據(jù)頁(yè)之前沒(méi)有構(gòu)造過(guò) AHI（!block->ahi.index 為 true）。
該數(shù)據(jù)頁(yè)之前構(gòu)造過(guò) AHI，構(gòu)造信息沒(méi)有發(fā)生變化，但是數(shù)據(jù)頁(yè)計(jì)數(shù)大于數(shù)據(jù)頁(yè)中記錄數(shù)量的兩倍（2 * page_get_n_recs(block->frame)）。
該數(shù)據(jù)頁(yè)之前構(gòu)造過(guò) AHI，但是構(gòu)造信息變了。

（4）構(gòu)造 AHI

滿(mǎn)足前面一系列條件之后，就可以為數(shù)據(jù)頁(yè)構(gòu)造 AHI 了。

// storage/innobase/btr/btr0sea.cc
static void btr_search_build_page_hash_index(...) {
  ...
  // block 是本次需要構(gòu)造 AHI 的數(shù)據(jù)頁(yè)控制塊
  // page 是數(shù)據(jù)頁(yè)對(duì)象
  const auto page = buf_block_get_frame(block);
  // 數(shù)據(jù)頁(yè)的 AHI 構(gòu)造信息
  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ù)頁(yè)構(gòu)造的 AHI 記錄
  if (block->ahi.index && block->ahi.prefix_info.load() != prefix_info) {
    btr_search_drop_page_hash_index(block);
  }
  ...
  // 數(shù)據(jù)頁(yè)中的記錄數(shù)量
  const auto n_recs = page_get_n_recs(page);
  ...
  // page_get_infimum_rec(page) 讀取 infimum 偽記錄
  // page_rec_get_next() 讀取數(shù)據(jù)頁(yè)中的第 1 條用戶(hù)記錄
  auto rec = page_rec_get_next(page_get_infimum_rec(page));

  Rec_offsets offsets;
  ...
  // 用于構(gòu)造第 1 條用戶(hù)記錄的 AHI 的 hash 種子
  const auto index_hash = btr_hash_seed_for_record(index);
  // 計(jì)算第 1 條用戶(hù)記錄的 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
  // 對(duì)于前綴相同的一組記錄（可能有一條或多條記錄）
  // 標(biāo)記需要為這一組的第一條記錄構(gòu)造 AHI
  if (prefix_info.left_side) {
    hashes[n_cached] = hash_value;
    recs[n_cached] = rec;
    n_cached++;
  }

  // 循環(huán)，標(biāo)記需要為數(shù)據(jù)頁(yè)中第 2 條及以后的用戶(hù)記錄構(gòu)造 AHI
  for (;;) {
    const auto next_rec = page_rec_get_next(rec);
    if (page_rec_is_supremum(next_rec)) {
      // left_side = false 時(shí)
      // 標(biāo)記需要為 supremum 偽記錄構(gòu)造 AHI
      // 然后結(jié)束循環(huán)
      if (!prefix_info.left_side) {
        hashes[n_cached] = hash_value;
        recs[n_cached] = rec;
        n_cached++;
      }

      break;
    }
    // 為當(dāng)前循環(huán)的記錄計(jì)算用于構(gòu)造 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
    // 說(shuō)明換了一組記錄
    if (hash_value != next_hash_value) {
      /* Insert an entry into the hash index */
      // left_side = true
      // 為下一組的第一條記錄構(gòu)造 AHI
      if (prefix_info.left_side) {
        hashes[n_cached] = next_hash_value;
        recs[n_cached] = next_rec;
        n_cached++;
      } else {
        // left_side = false
        // 為本組的最后一條記錄構(gòu)造 AHI
        hashes[n_cached] = hash_value;
        recs[n_cached] = rec;
        n_cached++;
      }
    }

    rec = next_rec;
    hash_value = next_hash_value;
  }
  ...
  // 為數(shù)據(jù)頁(yè)構(gòu)造 AHI 之后
  // 重置數(shù)據(jù)頁(yè)計(jì)數(shù)
  block->n_hash_helps = 0;
  // 已經(jīng)用來(lái)構(gòu)造過(guò) AHI 構(gòu)造信息保存到
  // 數(shù)據(jù)頁(yè)對(duì)象的 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ù)頁(yè)構(gòu)造 AHI 主要分為三大步驟：

循環(huán)讀取數(shù)據(jù)頁(yè)中的記錄，每讀取一條記錄，根據(jù) AHI 構(gòu)造信息計(jì)算記錄的哈希值，把哈希值保存到 hashes 數(shù)組中、記錄地址保存到 recs 數(shù)組中，一條記錄在 hashs、recs 數(shù)組中的下標(biāo)一樣，都是 n_cached。這一步有個(gè)特殊邏輯需要處理，就是對(duì)于前綴相同的一組記錄，根據(jù) left_side 決定為第一條還是最后一條記錄構(gòu)造 AHI。
數(shù)據(jù)頁(yè)計(jì)數(shù)（block->n_hash_helps）重置為 0，重新開(kāi)始計(jì)數(shù)，用于為該數(shù)據(jù)頁(yè)重新構(gòu)造 AHI 作準(zhǔn)備。然后，把構(gòu)造信息（prefix_info）、數(shù)據(jù)頁(yè)所屬的索引（index）分別保存到數(shù)據(jù)頁(yè)對(duì)象的 ahi.prefix_info、ahi.index 屬性中，btr_search_update_block_hash_info() 會(huì)用到這兩個(gè)屬性。
把 hashs、recs 數(shù)組中的哈希值、記錄地址一一對(duì)應(yīng)的插入到哈希表中，每條記錄的哈希值映射到該記錄的地址。

4、總結(jié)

AHI 構(gòu)造流程的前三步都是在判斷是否滿(mǎn)足某些條件，這些條件的范圍從大到小。

先是索引級(jí)別，判斷索引被命中的次數(shù)。

然后，是索引級(jí)別的構(gòu)造信息計(jì)數(shù)。

構(gòu)造信息來(lái)源于定位記錄過(guò)程中產(chǎn)生的下界、上界，其源頭是 where 條件，我們可以把它看成對(duì) where 條件的抽象，或者更具體點(diǎn)，把它看成 where 條件的分類(lèi)。

某個(gè)構(gòu)造信息的計(jì)數(shù)達(dá)到指定次數(shù)，意味著如果根據(jù)這個(gè)構(gòu)造信息（或者說(shuō)這類(lèi) where 條件）構(gòu)造 AHI，命中率會(huì)比較高。

InnoDB 以數(shù)據(jù)頁(yè)為單位，一次性為某個(gè)數(shù)據(jù)頁(yè)中的所有記錄構(gòu)造 AHI。

構(gòu)造信息計(jì)數(shù)滿(mǎn)足條件之后，還需要進(jìn)一步?jīng)Q定為哪些數(shù)據(jù)頁(yè)構(gòu)造 AHI，于是就有了數(shù)據(jù)頁(yè)計(jì)數(shù)（實(shí)際上是數(shù)據(jù)頁(yè)級(jí)別的構(gòu)造信息計(jì)數(shù)）。

當(dāng)索引計(jì)數(shù)、構(gòu)造信息計(jì)數(shù)、數(shù)據(jù)頁(yè)計(jì)數(shù)都滿(mǎn)足條件之后，某個(gè)數(shù)據(jù)頁(yè)就初步具備了構(gòu)造 AHI 的資格，最后，還會(huì)根據(jù)該數(shù)據(jù)頁(yè)是否構(gòu)造過(guò) AHI、構(gòu)造信息是否發(fā)生變化等條件，做出終極決定：是否為該數(shù)據(jù)頁(yè)構(gòu)造 AHI。

本文轉(zhuǎn)載自微信公眾號(hào)「一樹(shù)一溪」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系一樹(shù)一溪公眾號(hào)。