Innodb Adaptive hash index 相關函數流程AHI初始化AHI的使用AHI的維護

這兩天正在把percona5.5的multi ahi更新檔port到5.6.11，順便過了下ahi相關的代碼邏輯，是以寫的比較散亂，慎入！！

以下的分析基于5.6.11原版，主要包括ahi的存儲結構，以及在檢索btree時如何使用ahi，

ahi的初始化發生在innodb啟動時，在為buffer pool配置設定完記憶體後(buf_pool_init)，建立ahi相關結構體，配置其所需要的記憶體:

      btr_search_sys_create(buf_pool_get_curr_size() / sizeof(void*) / 64);

記憶體占用預設不超過buffer pool大小的64分之一

ahi的初始化主要包括以下幾個重要的對象：

btr_search_latch_temp  讀寫鎖對象，但外部使用的是btr_search_latch：

#define btr_search_latch     (*btr_search_latch_temp)

btr_search_sys，ahi的全局控制結構體，隻有一個成員：

      hash_table_t*     hash_index;

建立哈希表

其他相關結構體:

每個索引對象為維護的index->search_info，類型為btr_search_t，其成員包括：

ulint   ref_count

該index上被ahi索引的block數量，需要通過btr_search_latch保護

buf_block_t* root_guess

上次擷取的root page

ulint   hash_analysis

當該值超過btr_search_hash_analysis時，才會去更新ahi的entry.

這主要是為了避免太過頻繁的更新ahi(預設超過17次查詢後，才會去嘗試更新ahi)

在為search info重設新的n_fields和n_bytes時，會重設該字段為0

ibool   last_hash_succ

如果上次的搜尋成功了，并使用了ahi，則設定為true

ulint   n_hash_potential

使用ahi持續成功檢索的次數.

在函數btr_search_guess_on_hash中，當成功使用了一次ahi後，如果目前n_hash_potential<btr_search_build_limit+5=105，則将n_hash_potential++

在函數btr_search_info_update_hash中，有兩種情況會遞增該變量：

a.info->n_fields >= n_unique && cursor->up_match >= n_unique   //目前推薦的n_fields 和cursor->up_match能夠唯一決定一個記錄

b.當info->left_side為true時，info->n_fields, info->n_bytes需要小于大于cursor的n_fields和n_bytes，當為false時，前者大于後者。這兩種情況下，也會遞增n_hash_potential

在需要更新search info時，該變量可能會被重置

ulint   n_fields

推薦的比對列的個數

ulint   n_bytes

推薦的第一個部分比對列的位元組數

ibool   left_side

布爾變量，其值取決于多個有相同字首的最左邊的記錄是否應該被索引

block控制結構體上相關變量(buf_block_t)

ulint           n_hash_helps

用于控制是否為該block建立新的ahi項，在函數btr_search_update_block_hash_info中被遞增或重置。當block上的n_fields，n_bytes以及left_side和info上的對應值相同時，才可能去遞增該變量；

當n_hash_helps大于該page記錄總數的1/16分之一時，才可能為該該block上的全部使用者記錄建立ahi，并且要滿足一系列的條件：

if ((block->n_hash_helps > page_get_n_recs(block->frame)

             / btr_search_page_build_limit)

            && (info->n_hash_potential >= btr_search_build_limit)) {

                if ((!block->index)

                    || (block->n_hash_helps

                        > 2 * page_get_n_recs(block->frame))

                    || (block->n_fields != block->curr_n_fields)

                    || (block->n_bytes != block->curr_n_bytes)

                    || (block->left_side != block->curr_left_side)) {

                        /* build a new hash index on the page */

                        return(true);      //傳回true表示需要為該page上所有使用者記錄建ahi

                }

}

當重新為該block建立ahi後(btr_search_build_page_hash_index)，block->n_hash_helps被重置為0

ulint           n_fields

該變量，及下面兩個變量，在兩個函數中被設定

btr_search_move_or_delete_hash_entries，用于當諸如發生索引分裂時，将老block上的curr_* 指派給新block，并為其建立ahi

btr_search_update_block_hash_info  将info的對應變量指派給block

block->n_hash_helps = 1;

                block->n_fields = info->n_fields;

                block->n_bytes = info->n_bytes;

block->left_side = info->left_side;

隻有當上述這幾個值和info對應的變量在一段時間内保持一緻,才會去考慮為該block上的全部使用者記錄建立ahi

ulint           n_bytes

同上

ibool           left_side

unsigned        curr_n_fields:10

該變量及以下兩個變量，隻在在該block全部使用者記錄建立ahi時(btr_search_build_page_hash_index)才會被設定

unsigned        curr_n_bytes:15

unsigned        curr_left_side:1

dict_index_t*   index

該block對應的索引指針，在為該block建立ahi時被指派

cursor結構體btr_cur_t （懶得翻譯，注釋的很清楚）

ulint          up_match

if the search mode was page_cur_le,   the number of matched fields to the the first user record to the right of

the cursor record after btr_cur_search_to_nth_level;

for the mode page_cur_ge, the matched fields to the first user record at the

cursor or to the right of it;

note that the up_match and low_match values may exceed the correct values for comparison to the adjacent user

record if that record is on a different leaf page! (see the note in row_ins_duplicate_error_in_clust.)

ulint          up_bytes

number of matched bytes to the right at the time cursor positioned;

only used internally in searches: not defined after the search

ulint          low_match

if search mode was page_cur_le, the number of matched fields to the first user record at the cursor or to the left of it after btr_cur_search_to_nth_level;

not defined for page_cur_ge or any other search modes; see also the note in up_match!

ulint          low_bytes

ulint          n_fields

用于在檢索ahi時指派

ulint          n_bytes

ulint          fold

查詢ahi時，根據tuple計算的hash key值

btr_cur_search_to_nth_level -> btr_search_guess_on_hash

隻有滿足如下條件，才會進入函數：

主要函數btr_search_guess_on_hash：

a.滿足如下任一情況直接傳回

a1)info->n_hash_potential = 0時，直接傳回false

a2)

     cursor->n_fields = info->n_fields;

cursor->n_bytes = info->n_bytes;

目前檢索的列的個數小于推薦的列個數時，表示使用者提供的列的值的個數，不足以進行ahi檢索，是以直接傳回(dtuple_get_n_fields(tuple)  < cursor->n_fields + (cursor->n_bytes > 0))

b.根據目前tuple建構fold，并去檢索ahi

将cursor定位到該記錄

btr_cur_position(index, (rec_t*) rec, block, cursor);

c.檢查記錄的有效性(btr_search_check_guess)：

btr_search_check_guess函數流程如下：

c1)擷取記錄的

match表示比對的完整列的個數，bytes表示第一個部分比對的位元組數

随後設定cursor->up_match 和cursor->low_match，主要根據tuple和ahi中的記錄的比較結果來區分

c2)

當查詢模式為page_cur_ge（>=）時，如果cmp =1，表示tuple比ahi的記錄要大，傳回false，否則設定cursor->up_match = match；如果match >= n_unique，直接傳回true

當查詢模式為page_cur_le時，如果cmp = -1，表示tuple比ahi的記錄要小，傳回false，否則設定cursor->low_match = match

當查詢模式為page_cur_g時， 如果cmp != -1，表示tuple>=ahi的記錄，傳回false；

當查詢模式為page_cur_l時，如果cmp != 1，表示tuple <= ahi的記錄，傳回false

當查詢模式為page_cur_ge 或者page_cur_g時，找到目前從ahi讀取的記錄的前一個記錄，并跟tuple進行對比，當查詢模式為page_cur_ge時，隻有tuple大于prev_rec時，才傳回true，而對于page_cur_g，隻有當tuple>= prev_rec時，才傳回true

當查詢模式為page_cur_le或者page_cur_l時，找到目前從ahi讀取的記錄的下一條記錄，并跟tuple進行對比， 當查詢模式為page_cur_le時，隻有tuple <prev_prec時，才傳回true，并設定cursor->up_match = match；而對于page_cur_l，隻有當tuple<=prev_rec時，才傳回true

通過上述比較，實際上也可以借助ahi來優化範圍查詢

d.

成功讀取一個ahi記錄，設定last_hash_succ為true(info->last_hash_succ = true)

如果失敗，則設定：

cursor->flag = btr_cur_hash_fail;

info->last_hash_succ = false;

在函數btr_cur_search_to_nth_level 中，當完成了搜尋之後，如果最終定位的層是葉子節點，才去調用btr_search_info_update：

注意，如果我們成功使用ahi 獲得了記錄位置，就不會來到這個邏輯，而是直接從btr_cur_search_to_nth_level函數傳回。

1.info->hash_analysis++ ，當info->hash_analysis < btr_search_hash_analysis(預設為17)時，直接從函數傳回，不做任何更新。

這主要是為了避免頻繁的更新ahi所帶來的開銷

2.btr_search_info_update_slow

>更新目前索引的 search info( btr_search_info_update_hash(info, cursor))

a.當滿足如下條件時，需要設定新的recommand值

1)info->n_hash_potential = 0

2)

3)設定新的recommand值

當cmp為0時，設定:

否則根據cmp是大于0還是小于0 ，設定info->n_fields 和info->n_bytes的值，并設定info->n_hash_potential = 1，具體判斷邏輯為：

b.當滿足如下條件時，info->n_hash_potential++，并直接從函數傳回

1)info->n_fields >= n_unique && cursor->up_match >= n_unique

>判斷是否需要在這個block上建立一個新的索引entry （build_index = btr_search_update_block_hash_info(info, block, cursor) )

傳回true表示需要建立

>當需要為page建立ahi(build_index 不為空，或者cursor->flag == btr_cur_hash_fail)，檢查hash index中是否有足夠的空間(btr_search_check_free_space_in_heap)

>cursor->flag == btr_cur_hash_fail 表示之前使用ahi檢索失敗，則調用btr_search_update_hash_ref來更新目前curosr對應記錄的ahi

btr_cur_hash_fail 表示使用ahi檢索失敗了，需要持有btr_search_latch的x鎖的情況下，進行如下判斷

block->index為null，表明未為該block建立ahi，直接傳回

>如果需要建立一個新的entry（即函數btr_search_update_block_hash_info傳回true）

btr_search_build_page_hash_index函數用于為目前page上的所有記錄建立ahi索引

a.當block上有老的不同的ahi記錄時，将其删除掉：

b.

c.

讀取目前block對應page上的所有使用者記錄，建立ahi項

fold = rec_fold(rec, offsets, n_fields, n_bytes, index->id);

對于left_side為true還是false有不同的選擇，

例如一個page上有如下記錄

1  2

2  2

3  5

4  5

5  7

6  8

如果block->left_side為true，存儲的記錄為

1，3，5，6

如果為false，存儲的記錄為：

2, 4,5,6

left_side決定了當遇到相同記錄字首時，是選擇最左邊的還是最右邊的記錄。

d.找到需要建立ahi的記錄後，

檢查是否有空閑空間     btr_search_check_free_space_in_heap（）

擷取btr_search_latch的x鎖後，再次檢查：

如果這是第一次為該block建立ahi,index->search_info->ref_count++，ref_count表示這個索引上有多少個block建立了ahi

然後依次将之前搜集的記錄插入到ahi中（ha_insert_for_fold）

3.執行dml時更新ahi，沒啥好說的，代碼邏輯非常簡單，就是更新對應的hash表記錄

     btr_search_update_hash_on_insert

     btr_search_update_hash_node_on_insert

     btr_search_update_hash_on_delete