开发者学堂课程【第八届大学生创新创业大赛阿里命题数据库命题解析：基于 PolarDB for MySQL 实现并行创建索引赛题解析】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1045/detail/15270
基于 PolarDB for MySQL 实现并行创建索引赛题解析
内容介绍：
一、相关背景
二、创建索引核心流程
三、并行创建索引
四、解题要求
首先会以 PolarDB for MySQL 的真实应用场景做切入，介绍索引对于关系型数据库的重要性以及并行创建索引的重要性。介绍PolarDB存储引擎为例创建索引的传统流程，介绍并行创建索引的思路并且展示PolarDB for MySQL实现并行创建索引能够达到的效果，最后回归到赛题本身，了解解题的要求。
一、相关背景
1、PolarDB 是阿里巴巴自研的新一代云原生关系型数据库，PolarDB采用计算节点与存储节点分离的架构，底层的存储使用的是云上的分布式存储，可以突破单机的存储容量限制，并且降低存储成本。PolarDB的集群版采用的是一写多读的架构，集群中有主节点，可写可读的节点以及至少一个只读节点，当用户的应用程序使用集群地址的时候，请求会首先到达PolarDB的代理层，代理层通过一定的解析和分发之后，请求才会来到具体的数据节点，代理层不仅可以做安全认证和保护，还可以对用户的sql进行解析，把请求中的写操作发放到主节点，如果操作是指读操作，代理层会把读操作均匀的发放到多个只读节点，实现自动的读写分离，所以对于用户使用PolarDB的集群版就像使用单节点的数据库一样。
2.PolarDB的应用场景有很多，跟赛题密切相关的场景，海量存储，PolarDB可以支持上百T B级别的数据，现在互联网上各种形形色色的业务，不管是传统的企业随着长时间的发展，历史数据大量的积累，还是新兴的企业在现如今数据量爆炸的时代下都会越来越多的面临数据量庞大的问题，PolarDB采用的是计算节点和存储节点分离的架构，使用云上的分布式存储，所以单个实例最高可以支持到100TB的存储容量，在线上实际的运维中也遇到很多用户单表数据量非常的庞大，一张表的容量却已经达到几个T的大小。
3、单表数据量的庞大对于数据库的访问性能是很大的考验，在关系数据库中索引对于数据检索的加速是非常重要的，以简单的sql语句为例，select (a, b) from t1 where b > 5000;t1的表只有两个字段，a字段和b字段，把结构简化，在a字段上创建有主健索引，b字段上什么也没有，用户想要做查询，由于b字段上没有索引，所以在组件索引上b字段的排列是无序的，想要找到b字段大于5000的数据的时候，需要进行全表的数据扫描，对于一张非常庞大的表，操作的耗时是非常久的，如果b字段上有二级索引，对于性能提升就非常大，但是对于一张非常庞大的表，要创建索引需要耗费的时间也非常长，可能会需要数个小时，甚至数天的时间，对于用户的体验非常糟糕，现在的计算机可以提供越来越多的CPU核数，越来越大的内存容量，在云原生的环境下分布式存储也可以让磁盘的IO得到极大的提升，但是数据库提供的传统的创建索引的操作却是针对单核处理器和传统硬盘进行设计，所以即便在现如今的硬件资源环境下创建索引也并不能充分的发挥硬件资源的优势。
二、创建索引核心流程
以innodb引擎为例，innodb存储引擎中索引使用的是b+树的结构，左图就是T1表的主键索引，T1表按照之前假设的结构还有两个字段
a字段b字段，a字段是它的主键索引，在左图中可以看到在b+树上分叶节存储主键的t，而叶子节点会存储每一行完整的数据，包括t，a字段以及b字段，如果想在b字段上创建二级索引，创建索引的流程，分为三个步骤，第一个步骤叫扫描，当需要构建二级索引的时候，首先需要拿到对应的数据，会扫描主键获取所需要的数据，因为主键上已经包含整个表的全部数据，第二步时排序，第一步扫描拿到的数据，对于需要创建二级索引的字段不一定是有序的，对于需要创建的二级索引的字段上无序的数据进行排序，得到有序的数据，第三步构建索引，把第二步排完序的数据，构建成一颗新的b+树，新的b+树就是需要的二级索引，
具体的过程，第一步扫描主键，扫描主键的时候可以直接从叶子节点开始扫描，因为叶子节点上保存了全部的数据，从图中可以看到经过一轮扫描之后拿到全表的全部数据，包括a字段的数据和b字段的数据，现在的数据对于主键字段a是有序的，但是对于即将要创建的新的二级索引，在B字段上的二级索引，它的数据是无序的，需要对B字段进行排序。
第二步索引字段排序，将原本在主键上有序的数据，即将建立索引的字段b字段为t进行排序，得到在b字段上有序的数据。
在索引上有序排列的数据构建一棵b+树，构建完成之后和主键索引一样，在分叶子节点只保存索引的T的值，叶子节点会保存二级节点的t以及主键的值才能够通过二级索引，查找到数据的时候，根据它的主键值能够快速的回到主键索引进行二次查找，拿到全部需要的数据，在新的b+树，在b字段上的新的二级索引创建完成。传统创建索引的流程。
三、并行创建索引
1、并行创建索引最核心的问题就是如何把创建索引最耗时的三个步骤用并行的方式进行加速，为达到更好的并行加速的效果，就会要求设计出高效的并行方案，当拿到给定的可用的cpu核数的时候，如何充分的利用cpu，让多个工作线程一起进行创建索引的操作，创建索引主要的耗时操作可以分为三个过程，扫描数据，从主键上扫描全表的数据，拿到创建二级索引需要的数据，根据要创建索引的字段进行排序，得到在索引字段上有序的数据，最后一步构建索引，用索引字段上有序的数据创建新的b+树，新的索引，三个过程或者整个流程，进行任务的切割和分配，让多个工作线程协同的完成索引的创建，是并行创建索引需要思考和实现的地方，也是每一位参赛同学需要思考的问题，是在方案设计之初就需要花大量脑筋思考的。
2、看实现的并行创建索引达到的效果，测试的时候使用的表结构依然是举例的简单的表结构，它只有两个字段，a字段和b字段，两个字段都是整数，在a字段上有主键索引，测试环境使用的是规格为16核内存128gb标准版，PolarDB MySQL8.0版本的集群，实验数据上面使用脚本随机的生成数据。
DELIMITER //
CREATE PROCEDURE populate._t0()
BEGIN
DECLARE i int DEFAULT 1;
WHILE (i <= $table_ size) DO
INSERT INTO t0 VALUES (i, 1000000 * RAND());
SETi =i+ 1;
END WHILE;
END 1/
DELIMITER ;
CALL populate_ tO() ;
存储过程，生成的数据在a字段上是有序的，主键索引上有序，但是在b段上是无序的，随机的数据，拿到表和数据之后，在表上创建需要对比传统的创建索引的过程和并行创建索引的过程，它们之间的效率。
3、实验的结果，从图上可以看到一二四八十六三十二表示在并行创建索引中使用并行的线程数，不同颜色表示生成表的数据量的大小，从左到右分别是一百万的数据量，一千万的，一亿的数据量，十亿的数据量以及1tb的数据量，当线程数为1的时候，就是传统的创建索引的流程是基准值，也就是100%，高度表示使用并行创建索引之后，对于传统创建索引加速的比例，图上可以看到随着线程数的提升，越来越多的人加入之后，并行创建索引的性能得到明显的提升，当表上的数据量越大，性能的提升越明显，在32线层的1tb的表上，性能达到15倍左右的提升，PolarDB MySQL的实现为什么在数据量越大的情况下性能提升的比例越明显。
四、解题要求
1、并行创建索引题目的解题要求，需要设计进行创建索引的方案，需要思考如何设计各个阶段的运行方案，需要在能够保证正确性的前提下，让整个过程的并行度尽可能高，加速的比例尽可能高。如果硬件资源提供八个线程，如何能够让整个并行创建索引的过程中八个工作线程可以最大程度的保持着高效的工作。
2、要求实现并行创建给定的demo，能够在给定的表结构表数据下创建指定的索引，不可以造成数据的错误，要尽可能的提升索引创建的速度，编程语言上要求使用C和C++，最后需要提交设计文档Demo代码使用说明以及测试用例等材料，最后提供PolarDB for MySQL并行的官方文档，可以在https://help. aliyun.com/document detail/193259.html链接下找到文档或者在阿里云的官网的标签(首页>云原生关系型数据库PolarDB MySQL引擎>内核功能> DDL优化>并行DDL )下找到文档。
