InnoDB Adaptive Hash Index浅析

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

原文转自：http://ourmysql.com/archives/1250