时间：2021-07-01 10:21:17 帮助过：38人阅读
InnoDB Adaptive Hash Index调研总结 #InnoDB Adaptive Hash Index# 定义 维护索引叶页面中所有记录的索引键值(或键值前缀)到索引叶页面位置的Hash映射关系，能够根据索引键值(前缀)快速定位到叶页面满足条件记录的Offset，减少了B+树Search Path的代价，将B
#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的维护，包括多个动作：索引叶页面何时进入Hash Index；何时可以使用Hash Index加锁查询；何时将索引叶页面从Hash Index中移除，等等。
新增B+树索引叶页面的Hash索引，则是在Search Path之后，btr_cur_search_to_nth_level() -> btr0sea.ic::btr_search_info_update()。
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+树索引叶页面，对其进行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的使用流程：
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浅析, 感谢原作者分享。