这两天正在把Percona5.5的Multi AHI补丁port到5.6.11，顺便过了下AHI相关的代码逻辑，因此写的比较散乱，慎入！！
以下的分析基于5.6.11原版，主要包括AHI的存储结构，以及在检索BTREE时如何使用AHI，
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;
创建哈希表
btr_search_sys->hash_index = ha_create(hash_size, 0,
MEM_HEAP_FOR_BTR_SEARCH, 0);其他相关结构体:
每个索引对象为维护的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中，有两种情况会递增该变量： 在需要更新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，并且要满足一系列的条件： / 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_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 | number of matched bytes to the right at the time cursor positioned;
only used internally in searches: not defined after the search |
| ulint n_fields | 用于在检索AHI时赋值 |
| ulint n_bytes | 同上 |
| ulint fold | 查询AHI时，根据tuple计算的hash key值 |
AHI的使用
btr_cur_search_to_nth_level -> btr_search_guess_on_hash
只有满足如下条件，才会进入函数：
if (rw_lock_get_writer(&btr_search_latch) == RW_LOCK_NOT_LOCKED
&& latch_mode <= BTR_MODIFY_LEAF
&& info->last_hash_succ
&& !estimate
# ifdef PAGE_CUR_LE_OR_EXTENDS
&& mode != PAGE_CUR_LE_OR_EXTENDS
# endif /* PAGE_CUR_LE_OR_EXTENDS */
/* If !has_search_latch, we do a dirty read of
btr_search_enabled below, and btr_search_guess_on_hash()
will have to check it again. */
&& UNIV_LIKELY(btr_search_enabled)
&& btr_search_guess_on_hash(index, info, tuple, mode,
latch_mode, cursor,
has_search_latch, mtr)) {主要函数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;
cursor->n_bytes = info->n_bytes;
当前检索的列的个数小于推荐的列个数时，表示用户提供的列的值的个数，不足以进行AHI检索，因此直接返回(dtuple_get_n_fields(tuple) < cursor->n_fields + (cursor->n_bytes > 0))
b.根据当前tuple构建fold，并去检索AHI
fold = dtuple_fold(tuple, cursor->n_fields, cursor->n_bytes, index_id); cursor->fold = fold; cursor->flag = BTR_CUR_HASH; rec = (rec_t*) ha_search_and_get_data(btr_search_sys->hash_index, fold);
将cursor定位到该记录
btr_cur_position(index, (rec_t*) rec, block, cursor);
c.检查记录的有效性(btr_search_check_guess)：
if (UNIV_UNLIKELY(index_id != btr_page_get_index_id(block->frame))
|| !btr_search_check_guess(cursor,
has_search_latch,
tuple, mode, mtr)) {
if (UNIV_LIKELY(!has_search_latch)) {
btr_leaf_page_release(block, latch_mode, mtr);
}
goto failure;
}
if (UNIV_LIKELY(info->n_hash_potential < BTR_SEARCH_BUILD_LIMIT + 5)) {
info->n_hash_potential++;
}btr_search_check_guess函数流程如下：
c1)获取记录的
offsets = rec_get_offsets(rec, cursor->index, offsets,
n_unique, &heap);
cmp = page_cmp_dtuple_rec_with_match(tuple, rec, //return 1, 0, -1, if dtuple is greater, equal, less than rec
offsets, &match, &bytes);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;
AHI的维护
在函数btr_cur_search_to_nth_level 中，当完成了搜索之后，如果最终定位的层是叶子节点，才去调用btr_search_info_update：
cursor->low_match = low_match;
cursor->low_bytes = low_bytes;
cursor->up_match = up_match;
cursor->up_bytes = up_bytes;
#ifdef BTR_CUR_ADAPT
/* We do a dirty read of btr_search_enabled here. We
will properly check btr_search_enabled again in
btr_search_build_page_hash_index() before building a
page hash index, while holding btr_search_latch. */
if (btr_search_enabled) {
btr_search_info_update(index, cursor);
}
#endif注意，如果我们成功使用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)
cmp = ut_pair_cmp(info->n_fields, info->n_bytes,
cursor->low_match, cursor->low_bytes);
if (info->left_side ? cmp <= 0 : cmp > 0)3)设置新的recommand值
info->hash_analysis = 0; //将hash_analysis值设为0，防止频繁更新
cmp = ut_pair_cmp(cursor->up_match, cursor->up_bytes,
cursor->low_match, cursor->low_bytes);当cmp为0时，设置:
info->n_hash_potential = 0;
info->n_fields = 1;
info->n_bytes = 0;
info->left_side = TRUE;否则根据cmp是大于0还是小于0 ，设置info->n_fields 和info->n_bytes的值，并设置info->n_hash_potential = 1，具体判断逻辑为：
} else if (cmp > 0) {
info->n_hash_potential = 1;
if (cursor->up_match >= n_unique) {
info->n_fields = n_unique;
info->n_bytes = 0;
} else if (cursor->low_match < cursor->up_match) {
info->n_fields = cursor->low_match + 1;
info->n_bytes = 0;
} else {
info->n_fields = cursor->low_match;
info->n_bytes = cursor->low_bytes + 1;
}
info->left_side = TRUE;
} else { //cmp <0
info->n_hash_potential = 1;
if (cursor->low_match >= n_unique) {
info->n_fields = n_unique;
info->n_bytes = 0;
} else if (cursor->low_match > cursor->up_match) {
info->n_fields = cursor->up_match + 1;
info->n_bytes = 0;
} else {
info->n_fields = cursor->up_match;
info->n_bytes = cursor->up_bytes + 1;
}
info->left_side = FALSE;
}
b.当满足如下条件时，info->n_hash_potential++，并直接从函数返回
1)info->n_fields >= n_unique && cursor->up_match >= n_unique
2)
cmp = ut_pair_cmp(info->n_fields, info->n_bytes,
cursor->up_match, cursor->up_bytes);
if (info->left_side ? cmp <= 0 : cmp > 0)>判断是否需要在这个block上创建一个新的索引entry （build_index = btr_search_update_block_hash_info(info, block, cursor) )
返回TRUE表示需要创建
info->last_hash_succ = FALSE;
if ((block->n_hash_helps > 0) //n_hash_helps >0，则block的n_fields等变量必然被赋值了
&& (info->n_hash_potential > 0)
&& (block->n_fields == info->n_fields) //由于info上的n_fields等可能发生变化，如果在一段时间内保持和block的一致，那可以认为info建议的列前缀长度是有效的
&& (block->n_bytes == info->n_bytes)
&& (block->left_side == info->left_side)) {
if ((block->index)
&& (block->curr_n_fields == info->n_fields)
&& (block->curr_n_bytes == info->n_bytes)
&& (block->curr_left_side == info->left_side)) {
info->last_hash_succ = TRUE; // 认为上次block使用AHI成功
}
block->n_hash_helps++;
} else {
block->n_hash_helps = 1;
block->n_fields = info->n_fields;
block->n_bytes = info->n_bytes;
block->left_side = info->left_side;
}
if ((block->n_hash_helps > page_get_n_recs(block->frame)
/ BTR_SEARCH_PAGE_BUILD_LIMIT) // 该block上的n_hash_helps值超过了该page上记录总数的16分之一时，
&& (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT)) { //且该索引的n_hash_potential大于100时
if ((!block->index) //block上没有建AHI
|| (block->n_hash_helps //或者block上的n_hash_helps大于2倍的记录数
> 2 * page_get_n_recs(block->frame))
|| (block->n_fields != block->curr_n_fields) //或者block上之前为记录创建AHI所使用的前缀列的个数(curr_)和当前的不相同
|| (block->n_bytes != block->curr_n_bytes)
|| (block->left_side != block->curr_left_side)) {
/* Build a new hash index on the page */
return(TRUE); //需要为这个page构建AHI
}
}
return(FALSE);>当需要为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，直接返回
if ((info->n_hash_potential > 0)
&& (block->curr_n_fields == info->n_fields)
&& (block->curr_n_bytes == info->n_bytes)
&& (block->curr_left_side == info->left_side)) {
mem_heap_t* heap = NULL;
ulint offsets_[REC_OFFS_NORMAL_SIZE];
rec_offs_init(offsets_);
rec = btr_cur_get_rec(cursor);
if (!page_rec_is_user_rec(rec)) {
return;
}
fold = rec_fold(rec,
rec_get_offsets(rec, index, offsets_,
ULINT_UNDEFINED, &heap),
block->curr_n_fields,
block->curr_n_bytes, index->id);
if (UNIV_LIKELY_NULL(heap)) {
mem_heap_free(heap);
}
ha_insert_for_fold(btr_search_sys->hash_index, fold, //更新当前检索到的AHI记录项
block, rec);
}>如果需要创建一个新的entry（即函数btr_search_update_block_hash_info返回TRUE）
params = (ulint*) mem_alloc(3 * sizeof(ulint));
params[0] = block->n_fields;
params[1] = block->n_bytes;
params[2] = block->left_side;
btr_search_build_page_hash_index(cursor->index,
block,
params2[0],
params2[1],
params2[2]);
mem_free(params);btr_search_build_page_hash_index函数用于为当前PAGE上的所有记录建立AHI索引
a.当block上有老的不同的AHI记录时，将其删除掉：
if (block->index && ((block->curr_n_fields != n_fields)
|| (block->curr_n_bytes != n_bytes)
|| (block->curr_left_side != left_side))) {
rw_lock_s_unlock(&btr_search_latch);
btr_search_drop_page_hash_index(block);b.
if (dict_index_get_n_unique_in_tree(index) < n_fields
|| (dict_index_get_n_unique_in_tree(index) == n_fields
&& n_bytes > 0)) {
return;
}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锁后，再次检查：
if (block->index && ((block->curr_n_fields != n_fields)
|| (block->curr_n_bytes != n_bytes)
|| (block->curr_left_side != left_side))) {
goto exit_func;
}如果这是第一次为该block建立AHI,index->search_info->ref_count++，ref_count表示这个索引上有多少个block建立了AHI
block->n_hash_helps = 0;
block->curr_n_fields = n_fields;
block->curr_n_bytes = n_bytes;
block->curr_left_side = left_side;
block->index = index;然后依次将之前搜集的记录插入到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