Heim > Datenbank > MySQL-Tutorial > InnoDB Adaptive Hash Index浅析

InnoDB Adaptive Hash Index浅析

WBOY
Freigeben: 2016-06-07 16:37:28
Original
1172 Leute haben es durchsucht

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

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage