首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >听原作者为你深度解读InnoDB批量建索引原理

听原作者为你深度解读InnoDB批量建索引原理

作者头像
腾讯数据库技术
发布2018-06-05 17:18:48
1.4K0
发布2018-06-05 17:18:48
举报

InnoDB批量建索引深度揭秘

InnoDB在MySQL 5.7版本中推出了批量建索引的功能。WL#7277 InnoDB: Bulk Load for Create Index这个功能就由本人设计与实现的。本文将对该功能的设计与实现进行详尽的介绍。


一、InnoDB Fast Index Build介绍

最简单的建索引的方法就是走正常的数据库插入流程,将数据逐条插入到索引B树中。要对B树进行查找合适的插入位置,对B树节点进行正常的加锁,对页面记录redo log,undo log,当页面满时进行分裂(split)。这样做最大的缺点就是建立索引速度慢,另外事务回滚慢,系统故障恢复(crash recovery)也慢(因为redo log apply + undo)。

MySQL从5.5开始提供了快速建索引的功能(Fast Index Build)。在这个功能中,把建索引的过程分成了三个阶段:

1.1读取阶段:读取聚簇索引(cluster index)

在InnoDB中,表的所有数据都在聚簇索引中。我们需要扫描聚簇索引,生成要创建的索引的记录,并写到排序缓冲区中(innodb_sort_buffer_size),默认大小是1G。当缓冲区写满后,先进行排序(quick sort),然后写入临时文件中。如果一次建立多个索引,聚簇索引的扫描只扫描一次。每个新建的索引用有独立的排序缓冲区。

1.2 排序阶段:对索引临时文件进行排序

如果索引的临时文件有多个,则对多个文进行外排序。采用的算法则是经典二路归并(two way merge sort)。排序的时间主要取决于归并的轮数(run),每一轮都读取和写入同样数量的文件。 以上两个阶段都涉及到排序。如果要创建的索引是唯一索引,在排序过程中发现重复的键值(duplicate key),则会直接报错。

1.3建立阶段:插入记录建索引

读取临时文件,依次将记录插入到索引B树中。与最原始的插入方案相比,这里对B树节点不上锁,不记录undo日志,每次默认都是从叶子节点的最右边(rightmost)插入新的记录,因为索引记录是有序的。因此快速建索引要快很多。

这里有一个实现细节值得注意。在没有排序插入的时候,节点分裂会比较多,由此带来的另外一个问题是很多节点处于没有填满的状态,有的甚至为半满状态。快速建索引解决了这个问题,保证叶子节点为满的状态(最左和最右节点除外,稍后解释)。具体实现如下:当一个子节点无法插入新的记录时,如果当前要插入的位置和上一次插入的位置相同,而且当前位置的下一条记录为最大记录标识时,不分裂该节点,分配新的节点,新记录插入该节点,作为该节点第一条记录。

最右的节点会因为插入的记录少而达不到满的状态,而最左叶子(中间节点除外)的节点为什么会出现半满状态呢?当根节点进行第一次分裂的时候,一半的记录移到了新的最左叶子节点,另一半移到了新的最右节点,新插入的记录则继续在右节点插入。根节点作为B树的入口,最先分配,一般是保持不变的。


二、自底向上建索引(Bottom up Index Build)

2.1自底向上建索引原理

记录首先插入到叶子节点,当叶子节点填满时,在往中间节点插入一条记录。这样为什么会快?其一,省去了每次从根节点到最右节点的寻路过程,因为我们为每层保存当前插入页和插入位置;其二,一个页的所有记录插入用一个mtr(mini-transaction)完成,而之前都是一条记录使用一个mtr完成;其三,数据页不记录redo日志,页面的分配依然记redo日志,保证系统崩溃后,数据页可以正常回收。

2.2 脏页写盘方案

因为没有记redo日志,那么在索引创建完成,变成可用之前,需要把所有索引叶写入磁盘。最初的实现方案就是等待系统所有脏页写盘(做一个检查点),测试中发现系统负载大的时候,等待时间太长。新的优化方案则是利用观察者模式(observer)进行处理,只等待相关的脏页写盘。在建索引之前,我们创建一个flush observer对象,然后脏页进入flush list之前,设置该页的flush observer对象,并将flush计数器加一。当这个脏页被写入磁盘之后,则对flush observer对象的remove计数器加一。索引创建完成之后,等待flush计数和remove计数相等,则所有脏页写盘完成。注意:这里的计数器是针对单个buffer pool实例的。如果索引创建失败,在flush list中所有含有该flush observer对象的脏页都会被清除。

2.3 压缩表(compressed table)的处理

压缩表正常的插入流程是同时插入到压缩页和非压缩页中。为了简化流程,在批量建索引中,记录只插入到非压缩页中。当页面填满时,再对整页进行压缩。如果达不到设定的大小,则进行分裂。

2.4 填充因子(fillfactor)

在批量建索引中,我们添加了全局配置参数innodb_fill_factor,其取值范围为10-100,即数据页(包括叶子节点和非叶子节点)的填充比例从10%到100%。保持页面有一定的空闲空间,为将来的数据的增删改预留,否则,如果页面都填满的话,新的插入必然导致页的分裂,影响插入的效率。 对于压缩页,我们则依然保持了原有插入的自适应padding机制。

2.5 其他

在对批量建索引进行设计的时候,有一个不经过buffer pool的方案:直接分配页面,进行插入,单独写盘。最终因为实现稍复杂而放弃。另外对于是否写redo日志也有过讨论。写redo日志相对简单,因为只需要在页面填满时,对整页进行写日志即可。但考虑到如果系统崩溃之后,恢复的时间长而舍弃。


三、结语

在批量建索引中,还有一些值得优化的地方。比如填充因子可以根据单表指定(即DDL中进行语法支持);Online DDL时,online log的应用也可以不写redo日志,直接利用现行机制写脏页等等。 在批量建索引的基础上,我们还可以做如下工作:

  1. LOAD DATA时,如果表为空,则可以直接利用批量建索引接口进数据的加载。
  2. 优化建索引的第一和第二阶段。第一阶段读取可以采用逻辑预读(Logical Read Ahead);第二阶段可以才用多路归并,以及多线程排序。
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-02-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 腾讯数据库技术 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、InnoDB Fast Index Build介绍
  • 1.1读取阶段:读取聚簇索引(cluster index)
  • 1.2 排序阶段:对索引临时文件进行排序
  • 1.3建立阶段:插入记录建索引
  • 二、自底向上建索引(Bottom up Index Build)
  • 2.1自底向上建索引原理
  • 2.2 脏页写盘方案
  • 2.3 压缩表(compressed table)的处理
  • 2.4 填充因子(fillfactor)
  • 2.5 其他
  • 三、结语
相关产品与服务
云数据库 SQL Server
腾讯云数据库 SQL Server (TencentDB for SQL Server)是业界最常用的商用数据库之一,对基于 Windows 架构的应用程序具有完美的支持。TencentDB for SQL Server 拥有微软正版授权,可持续为用户提供最新的功能,避免未授权使用软件的风险。具有即开即用、稳定可靠、安全运行、弹性扩缩等特点。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档