听原作者为你深度解读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 条评论
登录 后参与评论

相关文章

来自专栏维C果糖

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

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

2247
来自专栏PingCAP的专栏

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

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

4588
来自专栏Albert陈凯

2018-11-22 10 个实战及面试常用 Shell 脚本编写

注意事项 1)开头加解释器:#!/bin/bash 2)语法缩进,使用四个空格;多加注释说明。 3)命名建议规则:变量名大写、局部变量小写,函数名小写,名...

962
来自专栏Kevin-ZhangCG

Oracle学习笔记四

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

792
来自专栏FreeBuf

基于约束的SQL攻击

前言 值得庆幸的是如今开发者在构建网站时,已经开始注重安全问题了。绝大部分开发者都意识到SQL注入漏洞的存在,在本文我想与读者共同去探讨另一种与SQL数据库相关...

2165
来自专栏数据库

使用VBA创建Access数据表

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

2367
来自专栏陈本布衣

SQLite 带你入门

SQLite数据库相较于我们常用的Mysql,Oracle而言,实在是轻量得不行(最低只占几百K的内存)。平时开发或生产环境中使用各种类型的数据库,可能都需要...

4065
来自专栏用户画像

mysql模拟题二

  3) MSSQLServer2005Enterprise Edition是哪一种版本?

996
来自专栏恰同学骚年

Hadoop学习笔记—9.Partitioner与自定义Partitioner

  在第四篇博文《初识MapReduce》中,我们认识了MapReduce的八大步凑,其中在Map阶段总共五个步骤,如下图所示:

702
来自专栏PHP实战技术

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

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

992

扫码关注云+社区