InnoDB Adaptive Hash Index浅析

InnoDB Adaptive Hash Index调研总结 #InnoDB Adaptive Hash Index# 定义 维护索引叶页面中所有记录的索引键值(或键值前缀)到索引叶页面位置的Hash映射关系，能够根据索引键值(前缀)快速定位到叶页面满足条件记录的Offset，减少了B+树Search Path的代价，将B

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

原文地址：InnoDB Adaptive Hash Index浅析, 感谢原作者分享。