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

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);第二阶段可以才用多路归并,以及多线程排序。

原文发布于微信公众号 - 腾讯数据库技术(gh_83eebc796d5d)

原文发表时间:2018-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏L宝宝聊IT

数据库和表的管理

16130
来自专栏维C果糖

详述 SQL 中的 distinct 和 row_number() over() 的区别及用法

1 前言 在咱们编写 SQL 语句操作数据库中的数据的时候,有可能会遇到一些不太爽的问题,例如对于同一字段拥有相同名称的记录,我们只需要显示一条,但实际上数据库...

29770
来自专栏数据库

使用VBA创建Access数据表

导读: 本期介绍如何在Access数据库中创建一张空数据表。下期将介绍如何将工作表中的数据存入数据库对应的表中,随后还将介绍如何从数据库的表中取出数据输出到Ex...

30370
来自专栏文渊之博

索引初探(三)

由于前一篇写的有点匆忙很多地方不是很简单,这一片再描述一些概念和细节。 首先,我们都知道在数据库中的存储分为两种结构,一是堆;二是B树。堆的数据是没有排序也就没...

19490
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(六)Select 语句概览

Select 语句只会讲解最简单的情况:全表扫描+过滤,暂时不考虑索引等复杂情况,更复杂的情况会在后续章节中介绍。语句为:

50880
来自专栏Kevin-ZhangCG

Oracle学习笔记四

在写java程序中有集合的概念,那么在pl/sq中也会用到多条记录,这时候我们就要用到游标,游标可以存储查询返回的多条数据。

12030
来自专栏PHP实战技术

这些Mysql基础设计思路以及优化思路我都给你总结好了

4、btree索引,就是用树形结构存储在磁盘上,其中操作是用2分发,找一个中间点,然后把大比这个大的分在一边,小的放在一边,然后当你查询的时候,从数字头开始,大...

11820
来自专栏L宝宝聊IT

T-SQL查询语句

18770
来自专栏用户画像

mysql模拟题二

  3) MSSQLServer2005Enterprise Edition是哪一种版本?

11360
来自专栏农夫安全

注入学习之sqli-labs-4(第三关)

前言 说明一下问什么没有less2、less3、less4的讲解? 前两篇如果你弄懂了,第2、3、4关卡原理都是一样的,无非是sql语句的稍微不同 比如: 第一...

34960

扫码关注云+社区

领取腾讯云代金券