InnoDB Adaptive Hash Index浅析

12月 7th, 2012

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的次数 (索引级别约束):

btr0sea.cc::btr_search_update_block_hash_info();


// info->n_hash_potential

//     表示查询已经连续成功使用Hash Index,

//     或者是可能成功使用Hash Index的次数;

//BTR_SEARCH_BUILD_LIMIT

//     相同索引键值(键值前缀),针对当前索引

//     Search Pach能够以Hash Index优化的次数,索引级别的;

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

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

    …

    return(TRUE);

B+树叶页面Adaptive Hash Index维护

 

一个B+树索引叶页面,对其进行Hash Index索引的流程:

 

btr0cur.cc::btr_cur_search_to_nth_level();

    btr0sea.ic::btr_search_info_update();

        btr0sea.cc::btr_search_info_update_slow();

            // 根据当前Search Path的定位结果(cursor),以及Index的

            // hash Index search info,重新计算Hash索引所需要的Key,

            // 是完整的索引键值,或者是索引键值前缀

            // 此处的判断逻辑较为复杂,需要持续学习!!

            btr_search_info_update_hash();

                …

            // 根据前面提到的,判断当前页面是否需要进行Hash索引

            btr_search_update_block_hash_info();

            // 对当前页面中的所有记录,创建Hash索引,Hash键值为前面

            // 提到的提取出来的完整索引键值或者键值前缀

            // 若当前页面已经被Hash,则首先删除旧的Hash,然后增加新Hash

            // 注意:

// 1. buffer header上有一个重要的参数——left_side,用于控制

// 拥有相同hash值的记录,是保持第一条,还是保存最后一条

// 2. index->search_info->ref_count:此参数用于标识当前索引有多少

// 页面被Hash索引了,在删除、关闭索引前,需要保证此计数归零

            btr_search_build_page_hash_index();

 

Adaptive Hash Index的使用流程

 

Adaptive Hash Index的使用流程

 

btr0cur.c::btr_cur_search_to_nth_level();

    btr0sea.c::btr_search_guess_on_hash();

        // 获取上一个进入Hash Index的叶页面,使用了索引中的多少个完全列,

        // 以及最后一列使用了多少个Bytes用于计算Hash键值

        cursor->n_fields = index->search_info->n_fields;

        cursor->n_bytes = index->search_info->n_bytes;

        // 根据选择的索引键值前缀,计算给定Tuple对应的Hash索引值

        // 前提是,必须保证给定Tuple的列数量,要超过键值前缀数量;

        fold = dtuple_fold(tuple, cursor->n_fields, cursor->n_bytes, index_id);

        // 根据计算得来的fold,查询Adaptive Hash Index;

        ha_search_and_get_data(btr_search_sys->hash_index, fold);

        …

        // 检查当前Hash Index命中的叶页面,是否满足Search Path的条件

        btr0sea.cc::btr_search_check_guess();

            page0page.ic::page_cmp_dtuple_rec_with_match();

  // 对比叶页面中通过Hash Index定位到的当前记录,以及

                // 用户给定的tuple (完整 or Partial),n_cmp为对比的列数,

                // matched_fields为完全匹配的列数,*_bytes为第一个不匹配

                // 列中匹配的字节数

                // @return 1, 0, -1

                // 1:    dtuple大于页面中的rec

                // 0:    dtuple与页面中的rec相等

                // -1:    dtuple小于页面中的rec

                rem0cmp.cc::cmp_dtuple_rec_with_match_low(dtuple, rec,

offsets, n_cmp, matched_fields, matched_bytes);

// 设置本次完全匹配的列数,以及最后一列匹配的字节数

*matched_fields = cur_field;

*matched_bytes = cur_bytes;

                // 若查询模式为L or LE,则判断当前位置是否满足条件

      // 1. 条件一:当前Rec是否比查询条件更小

                if (mode == PAGE_CUR_L)

if (cmp != 1)

goto exit_func;

       // 2. 条件二:当前Record的下一条记录比查询条件更大

                // (一).  next_rec为SUPREMUM记录,并且当前页面为索引最后一个页面

                // 则一定满足条件;

                // (二).  next_rec不为SUPREMUM记录,则比较next_rec与tuple,判断

                // 比较的返回值是否为-1,标识tuple小于next_rec;

   if((mode == PAGE_CUR_L) || (mode == PAGE_CUR_LE))

                    next_rec = page_rec_get_next(rec);

 

// 总结:当以上的条件均满足时,说明当前通过Hash Index定位的叶节点的位置是正确的。

// Hash Index命中,减少了B+-Tree Search Path开销,直接定位到了叶页面的正确位置

// 接下来,根据操作类型的不同,可以进行接下来的操作,例如:

// Range Scan操作:从当前位置开始,读取Range的第一条记录

// Unique Scan操作:从当前位置,读取满足Unique记录

// Insert操作:将记录Insert到当前位置;

// Delete操作: 删除当前位置的记录;


         


 

参考资料

[1] http://dev.mysql.com/doc/refman/5.5/en/innodb-adaptive-hash.html        Adaptive Hash Indexes

目前还没有任何评论.