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

时间： 2024-04-20 12:52:21

Innodb Adaptive hash index 相关函数流程的相关文章

数据库内核月报 － 2015 / 09-MySQL · 引擎特性 · InnoDB Adaptive hash index介绍

前言 我们知道InnoDB的索引组织结构为Btree.通常情况下,我们需要根据查询条件,从根节点开始寻路到叶子节点,找到满足条件的记录.为了减少寻路开销,InnoDB本身做了几点优化. 首先,对于连续记录扫描,InnoDB在满足比较严格的条件时采用row cache的方式连续读取8条记录(并将记录格式转换成MySQL Format),存储在线程私有的row_prebuilt_t::fetch_cache中:这样一次寻路就可以获取多条记录,在server层处理完一条记录后,可以直接从cache中取

MySQL · 引擎特性 · InnoDB Adaptive hash index介绍

前言 我们知道InnoDB的索引组织结构为Btree.通常情况下,我们需要根据查询条件,从根节点开始寻路到叶子节点,找到满足条件的记录.为了减少寻路开销,InnoDB本身做了几点优化. 首先,对于连续记录扫描,InnoDB在满足比较严格的条件时采用row cache的方式连续读取8条记录(并将记录格式转换成MySQL Format),存储在线程私有的row_prebuilt_t::fetch_cache中:这样一次寻路就可以获取多条记录,在server层处理完一条记录后,可以直接从cache中取

InnoDB中Adaptive hash index存在问题、Percona改进及一个bug

背景   Adaptive hash index  (AHI) 是InnoDB中用于加速索引查找的一个结构.InnoDB本身不支持hash索引,所有的索引检索都走B树查询.AHI可以认为是"索引的索引".当对一个页面的访问次数满足一定条件后,将这个页面的地址存在一个hash表中,下次查询可以直接访问到页面,不需要走B树查询. 问题   天下没有免费的午餐,在加速查询的同时,AHI与其他缓存结构一样,也面临维护的问题.作为一个全局结构,在更新时必然有一个全局锁操作(btr_search_

MySQL索引之哈希索引和自适应哈希索引（Adaptive Hash Index）

MySQL索引之哈希索引和自适应哈希索引(Adaptive Hash Index)  官网:https://dev.mysql.com/doc/refman/5.6/en/innodb-adaptive-hash.html 索引(Index)是帮助MySQL高效获取数据的数据结构.提取句子主干,就可以得到索引的本质:索引是数据结构. 从MySQL逻辑架构来看,MySQL有三层架构,第一层连接,第二层查询解析.分析.优化.视图.缓存,第三层,存储引擎. 索引通过分开查询片,节省了扫描查找时间,大大

MySQL hash index VS Btree index

MySQL AHI(adaptive hash index):没有牺牲任何的事物特点和可靠性; 根据搜索的匹配模式,MySQL会利用 B-Tree index key 前半部分(利用btree index 所能找到的部分)长度任意建立hash index.hash index根据需求只对访问频率较高的page中的index建立hashindex 如果一个表的数据全部在内存里面,hash index可以加快查询速度:innodb本身有监控index 查询频率的机制:通过hash index提高查询

PostgreSQL 10.0 preview 性能增强 - hash index metapage cache、高并发增强

标签 PostgreSQL , 10.0 , hash index 背景 hash index是PostgreSQL中一个非常老的索引访问方法,也是非常经典的索引. hash index中存储的是索引字段的hash value,而不是原始值,btree索引中存储的是原始值. 因此,当字段非常大时,btree索引可能无法使用. 例如 postgres=# create table test_hash_btree(c1 text); CREATE TABLE postgres=# insert in

PostgreSQL 10.0 preview 功能增强 - hash index 支持wal(灾难恢复)

标签 PostgreSQL , 10.0 , hash index , wal , 灾难恢复 背景 PostgreSQL 10.0 将支持hash index WAL. 因此建hash index再也不怕数据库crash或者备库hash index不可用了. $SUBJECT will make hash indexes reliable and usable on standby. AFAIU, currently hash indexes are not recommended to be

PostgreSQL 为什么不要滥用unlogged table &amp; hash index

unlogged table和hash index同样都不会写XLOG,所以如果你用流复制来搞HA,一定概要搞清楚一个问题,切换到备库的话unlogged table数据会被清掉,而hash index也没有,走hash index会失败. unlogged table 的风险以及修复手段可以见 : http://blog.163.com/digoal@126/blog/static/163877040201582621345351/ hash index则风险略小,但是也必须重建,但是个人还是

解析MySQL 5.7 OOM问题诊断

Inside 君最近把金庸先生的笑傲江湖重看了三遍,感慨良多.很多工作.管理.生活.学习上的问题都能在其中一窥究竟,而那是年轻时所不能体会的一种感悟.比如下面风清扬的这段话: 风清扬又道:"单以武学而论,这些魔教长老们也不能说真正已窥上乘武学之门.他们不懂得,招数是死的,发招之人却是活的.死招数破得再妙,遇上了活招数,免不了缚手缚脚,只有任人屠戮.这个'活'字,你要牢牢记住了.学招时要活学,使招时要活使.倘若拘泥不化,便练熟了几千万手绝招,遇上了真正高手,终究还是给人家破得干干净净."