InnoDB Adaptive Hash Index淺析

　　InnoDB Adaptive Hash Index調研總結

　　#InnoDB Adaptive Hash Index# 定義

　　維護索引葉頁面中所有記錄的索引鍵值(或鍵值前綴)到索引葉頁面位置的Hash映射關系，能夠根據索引鍵值(前綴)快速定位到葉頁面滿足條件記錄的Offset，減少了B+樹Search Path的代價，將B+樹從Root頁面至Leaf頁面的路徑定位，優化為Hash Index的快速查詢。

　　#InnoDB Adaptive Hash Index# 使用

　　Adaptive Hash Index是針對B+樹Search Path的優化，因此所有會涉及到Search Path的操作，均可使用此Hash索引進行優化，這些可優化的操作包括：Unique Scan/Range Scan(Locate First Key Page)/Insert/Delete/Purge等等，幾乎涵蓋InnoDB所有的操作類型。

　　#InnoDB Adaptive Hash Index# 維護

　　Adaptive，意味著不是所有的葉頁面都會以Hash索引維護，葉頁面進入Hash索引的條件是：同種類型的操作(Scan/Insert…)，命中同一葉頁面的次數，超過此頁面記錄數量的1/16，則可將當前葉頁面加入Hash索引，用以優化后續可能的相同Search Path。

　　#InnoDB Adaptive Hash Index#

　　Adaptive Hash Index，是一個臨時的Hash索引(針對一類特定的語句進行的優化，一般而言，當前的Hash優化，對于下一條語句，不一定有用)，針對不同的Scan/Insert/Delete，Search Path的條件不同，導致最終提取出來的Search Info的n_fields與n_bytes也不同(n_fileds + b_bytes構成了索引的鍵值前綴，或者是完整的索引鍵值)，同一頁面的前一個Hash索引，在下一個查詢中可能就失效了。此時，進行hash guess會失敗(會設置Search Info的last_hash_succ = false，接下來不會使用此Hash Index)，在Search Path之后，進行Hash索引的更新(btr0sea.ic::btr_search_info_update())，會重設Search Info的n_fields，n_bytes，進而重設buffer header上的n_fields，n_bytes，在滿足頁面重新進入Hash Index的條件之后(見下面的分析，一共有三個條件)，當判斷出buffer header上的[n_fields, n_bytes]與[curr_n_fields, curr_n_bytes]不同，則對頁面重新進行Hash計算，步驟是：

　　首先刪除頁面舊的Hash索引項;

　　然后根據[n_fields, n_bytes]組合計算新的Hash索引項，存入Hash Index;

　　#InnoDB Adaptive Hash Index#

　　對需要維護Hash Index的B+樹索引葉頁面，按照一定的[n_fields, n_bytes]組合，提取索引鍵值前綴，計算hash值，維護頁內所有Records至葉頁面offset的Hash項。但是，由于index->search_info是索引全局所有的，其中保存的[n_fields, n_bytes]會根據不同的SQL語句發生變化，此組合一變，原來進入Hash索引的項就無法摘除了(計算Hash值也會變化，找不到原有的Hash項)。因此，InnoDB在每一個Buffer Header上維護了自身進入Hash索引時的[n_fields, n_bytes]組合，后續根據此組合可以將頁面對應的Hash項完全刪除。更進一步，Buffer Header之上還有[curr_n_fields, curr_n_bytes]組合，這個標識的當前頁面在Hash索引中真正使用的組合。Buffer Header上維護兩組[n_fields, n_bytes]，[curr_n_fields, curr_n_bytes]的目的：

　　[n_fields, n_bytes]

　　此組合隨著index->search_info上的[n_fields, n_bytes]組合的變化而變化，若二者不同，則更新Buffer Header組合，重新開始統計新的組合潛在可用的次數(n_hash_helps);

　　[curr_n_fields, curr_n_bytes]

　　此組合維護的是葉頁面進入Hash Index時使用的索引鍵值前綴組合。在將頁面從Hash索引刪除時，需要根據此組合構建Hash值刪除hash索引項;若此組合與buffer header上的[n_fields, n_bytes]組合不同，并且滿足了頁面重新進入Hash索引的條件，則按照新的[n_fields, n_bytes]組合計算Hash值，維護頁面的hash索引。

　　Adaptive Hash Index的維護

　　Adaptive Hash Index的維護，包括多個動作：索引葉頁面何時進入Hash Index;何時可以使用Hash Index加鎖查詢;何時將索引葉頁面從Hash Index中移除，等等。

　　B+樹葉頁面進入Adaptive Hash Index

　　新增B+樹索引葉頁面的Hash索引，則是在Search Path之后，btr_cur_search_to_nth_level() -> btr0sea.ic::btr_search_info_update()。

　　B+樹葉頁面進入Hash Index的條件

　　InnoDB不是每一次進行Search Path之后，就將當前定位到的葉頁面中的所有Records按照鍵值前綴做Hash，并存入Hash表，而是有至少三個前提：

　　前提一：一定的次數的Search Path(btr_search_info_update()函數)：

　　#define BTR_SEARCH_HASH_ANALYSIS 17

　　/* After change in n_fields or n_bytes in info, this many rounds are waited before starting the hash analysis again: this is to save CPU time when there is no hope in building a hash index. */

　　前提二：同種類型的查詢(給定索引鍵值或索引前綴)，通過Search Path命中同一葉頁面的次數，超過頁面記錄數量的1/16 (頁面級別約束)：

　　/* 更新Buffer Header上的Adaptive Hash Index相關信息：Search Info */

　　btr0sea.cc::btr_search_update_block_hash_info();

　　…

　　// block->n_hash_helps

　　// 表示當前索引鍵值(前綴)Hash索引，針對

　　// 當前block有效的次數，定位到此Block的Search Path可優化;

　　// BTR_SEARCH_PAGE_BUILD_LIMIT(16)

　　// 定義了是否啟用頁面Hash Index的

　　// 下限，當n_hash_helps值超過頁面記錄數的

　　// BTR_SEARCH_PAGE_BUILD_LIMIT分之一，則可以將此頁面進行Hash索引;

　　if ((block->n_hash_helps > page_get_n_recs() / BTR_SEARCH_PAGE_BUILD_LIMIT)

　　&& (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT))

　　…

　　return(TRUE);

　　前提三：查詢已經連續成功使用Hash Index，或者是可能成功使用Hash Index的次數 (索引級別約束)：

原文轉自：http://ourmysql.com/archives/1250