Innodb Adaptive hash index 相关函数流程

这两天正在把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中,有两种情况会递增该变量:
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 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;
当前检索的列的个数小于推荐的列个数时,表示用户提供的列的值的个数,不足以进行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

原创文章,转载请注明: 转载自Simple Life

本文链接地址: Innodb Adaptive hash index 相关函数流程

Post Footer automatically generated by wp-posturl plugin for wordpress.


Comments

Leave a Reply

Your email address will not be published. Name and email are required


Current month ye@r day *