介绍了使用索引、临时表+文件排序实现groupby，还有三篇分别介绍临时表的文章，多次以count(distinct)为例。count(distinct)还需要单独写一篇文章吗？这时，我想起了一句话：不问，非问不可。回到正题，MySQL在使用MEMORY引擎临时表实现count(distinct)去重功能时，又玩了一个新花样，值得一写。背景说明就这些，让我们快速开始吧。本文内容基于MySQL5.7.35源码。1.概述如果count(distinct)不能使用索引去重，则需要使用临时表。临时表的存储引擎有三种选择：MEMORY、MyISAM、InnoDB。使用MyISAM或InnoDB作为临时表的存储引擎的处理逻辑有些不同。如果MySQL决定使用MEMORY作为临时表的存储引擎，临时表会被创建，但只是作为辅助，表中不会写入任何数据。要解释为什么会有这么花哨的操作，还得从MEMORY引擎支持的两种索引结构说起。2.MEMORY支持的两种索引结构MEMORY引擎支持两种索引结构：HASH索引和B-TREE索引。HASH索引，顾名思义，索引的数据结构是一个哈希表。哈希键是根据索引字段的内容计算出的哈希值，哈希值是索引记录指向的数据行的地址。HASH索引中的记录并不是按照字段内容的顺序存储的，而是乱序的。优点是查找时间复杂度为O(1)，单值查找记录速度很快，但不能用于范围查询。HASH索引结构示意图MyISAM和InnoDB引擎B-TREE索引的数据结构是B+树，而MEMORY引擎B-TREE索引的数据结构是红黑树。B-TREE索引结构示意图MEMORY引擎的B-TREE索引节点存放索引字段的内容和对应数据行的地址。红黑树是平衡二叉排序树，所以B-TREE索引中的节点是有序的，支持范围查询，但是相比HASH索引，通过单个值查找记录的时间复杂度为O(logN)要低一些。基于两种数据结构的特点，HASH索引适用于单值查找场景，B-TREE索引适用于范围查询和需要排序记录的场景。3、如何选择去重方案？说完MEMORY引擎的两种索引结构及其适用场景，再介绍count(distinct)去重方案。按照正常流程，当MySQL选择使用MEMORY作为临时表的存储引擎，再加上为distinct字段创建的HASH索引，就可以完全实现去重操作。但是本着节约的精神，MySQL一直是能省就省的。只要有优化方案就一定要用，那怎么优化呢？要回答这个问题，我们需要抓住去重功能的关键，即表中记录的唯一性。临时表中为distinct创建的HASH索引默认是唯一索引。既然HASH索引本身保证了唯一性，那可不可以考虑只用HASH索引来实现count(distinct)的去重功能？这个想法是可行的。但是MEMORY引擎的HASH索引不能满足要求：HASH索引不保存索引字段的内容，只保存字段内容的哈希值。只用索引的数据结构去重，为什么还要保存字段内容？在介绍去重过程时会进行说明。最好在那种情况下解释它。既然HASH索引不能满足要求，别忘了MEMORY引擎还支持另一种索引结构：B-TREE索引。B-TREE索引还可以实现去重功能，字段内容也保存在索引节点中，完美满足需求。前面介绍了流式方式的三个备选去重方案，需要做一个总结：方案1，临时表+HASH索引，这个实现方案比较满意，可以满足要求，缺点是只针对实现去重功能，单独使用HASH索引就足够了，但是向表中写入一条数据需要更多的内存，浪费了宝贵的内存资源。方案二，如方案一所述，HASH索引本身就可以实现去重。这个毋庸置疑。只使用HASH索引也是备选方案之一，但是HASH索引中并没有保存索引字段的内容，所以只好out了。方案三，B-TREE索引，既可以实现去重功能，又可以保存索引中的字段内容，完美，就是它了。但是MySQL并没有在MEMORY临时表上创建B-TREE类型的唯一索引，而是使用了B-TREE索引使用的红黑树，并且由于不会向临时表写入数据，所以红-blacktree节点中只需要保存字段的内容，不需要保存指向表中数据行的地址。再解释一下：还是会创建MEMORY临时表，但是不会写入数据，是一张空表。在实现红黑树去重功能的过程中，会用到MEMORY临时表的字段信息和记录缓冲区。以后你用explain查看执行计划的时候，如果发现count(distinct)既没有使用索引也没有使用临时表，那你可能会想：这家伙估计默默用了红黑树吧。前面说了那么多，只是为了澄清一个问题：为什么要选择红黑树来实现去重功能。这个非常重要。我们需要知道它是什么，更重要的是，我们更容易理解，你不觉得吗？接下来我们会一点一点的讲红黑树是如何实现count(distinct)去重功能的。4、红黑树节点中存储的是什么？红黑树是一种平衡二叉排序树。由于是二叉树结构，所以会有指向左子树和右子树的指针。红黑树的节点分为红色和黑色。自然要有一个属性来标记节点的颜色。MySQL实现的红黑树也支持重复节点的插入，这是通过在节点上增加一个属性来实现的，该属性记录节点内容重复的次数。以上信息属于节点元数据，元数据占用24字节内存空间。在每个节点中，除了保存节点元数据外，还保存节点数据，也就是字段内容。节点元数据5.红黑树占用内存过大怎么办？红黑树去重虽然不需要向MEMORY临时表写入数据，但是红黑树不能无限占用内存。它能占用的最大内存和MEMORY引擎临时表一样，也是由tmp_table_size和max_heap_table_size这两个系统变量中较小的一个决定的。默认情况下，红黑树最大可占用内存为16M。由于内存大小有限，可能会出现红黑树没有空间容纳新节点的情况。这时候，磁盘文件就登场了。如果红黑树占用的内存达到最大值，则将所有节点数据（不包括元数据）写入磁盘文件，然后删除红黑树的所有节点，保留内存重复使用。一起写入磁盘文件的数据会形成一个数据块，数据块的相关信息（在磁盘文件中的位置，记录条数）存储在对应的Merge_chunk中。一个磁盘文件中可能有多个数据块。数据块相关信息数据块中的数据，由于来自红黑树，有两个特点：记录是按照字段内容从小到大的顺序存储的。记录的字段内容是唯一的，没有重复。数据块中的数据6.Mergebuffer通过上一节我们知道，当红黑树占用的内存达到最大值后，会产生一个数据块写入磁盘文件。所谓天下大势，合久必分，分久必合。虽然磁盘文件中的数据块是分开写入的，但毕竟要合并去重，分组统计。在磁盘文件的每个数据块内部，记录的字段内容是不重复的。但是，多个数据块之间的字段内容可能是重复的，需要在合并过程中对多个数据块之间的字段内容进行去重。Merge去重，有两种可选的实现方案：方案一，分为三步：①从磁盘文件的每个数据块中读取剩余记录中的最小记录到内存中，最小记录其实就是剩余的第一条记录在记录中。②在步骤①读取的记录中找出最小的记录。③判断当前最小记录是否与上一个最小记录相同，如果相同则表示重复，不处理；如果不同，它将被计算在内。循环执行步骤①～③，直到读取完当前组所有数据块中的记录，合并完成。从上面的描述中，你一定已经发现了这个方案的问题：需要频繁的从磁盘文件中读取数据，而且一次只能读取一条记录。频繁的磁盘IO必然会影响SQL语句的执行效率，还有第二种选择。方案二，既然不能频繁的从磁盘读取数据，那么还有一种方式就是每次读取一批记录，减少读取次数。但是，一批记录不同于一条记录，需要找一个更大的地方暂存，所以就有了mergebuffer。合并缓冲区的大小与红黑树占用的最大内存相同。它还由两个系统变量tmp_table_size和max_heap_table_size中较小的一个控制。默认大小为16M。mergebuffer会被分成N个部分（N=磁盘文件中数据块的个数），每个部分对应一个数据块，用来存放从数据块中读取的一批记录。Mergebuffer7.如何对红黑树进行去重和分组计数？介绍完前置知识点，重头戏来了。该说说红黑树去重和分组计数的过程了。为了描述方便，我们还是介绍一个具体的SQL。样表和SQL如下：CREATETABLE`t_group_by`(`id`int(10)unsignedNOTNULLAUTO_INCREMENT,`e1`enum('北京','上海','广州','深圳','天津','杭州','成都','重庆','苏州','南京','哈尔滨','沉阳','长春','厦门','福州','南昌','泉州','德清','长沙','武汉')DEFAULT'北京',`i1`int(10)unsignedDEFAULT'0',`c1`char(11)DEFAULT'',`d1`decimal(10,2)DEFAULTNULL,PRIMARYKEY(`id`),KEY`idx_e1`(`e1`)USINGBTREE)ENGINE=InnoDBDEFAULTCHARSET=utf8;selecte1,count(distincti1)fromt_group_bygroupbye1在调试过程中，我建t_group_by表的e1字段的索引，所以执行SQL时不需要对表中的记录进行排序。我们先看一下去重和分组统计过程的示意图。去重和分组计数的主要流程看完上面的示意图，想必大家对整个流程有了一个大概的印象。让我们仔细看看在流程的每个步骤中将完成什么。第一步，读取记录。从from子句中的表中读取一条记录，即示例SQL中的t_group_by表。第二步判断红黑树是否满。前面说过，红黑树的一个节点包含两类信息：节点元数据，占24字节。节点数据，示例SQL中的节点数据为i1字段的内容，长度为4字节。在示例SQL中，一个红黑树节点占用24+4=28字节。知道了红黑树最大可以占用的内存，以及每个节点占用的内存，就可以算出红黑树最多可以插入多少个节点，就可以轻松判断红黑树是否满了.如果红黑树已满，则转步骤3，将红黑树中的所有节点数据写入磁盘文件。如果红黑树未满，则转到第4步，插入一个新节点。第三步，将红黑树的所有节点数据写入磁盘文件。按照中序遍历，将红黑树中的所有节点数据依次写入磁盘文件。此时不需要节点元数据，不会写入磁盘文件。上面说了，这些数据会组成一个数组块，每个数据块的相关信息存储在对应的Merge_chunk类实例中。数据写入磁盘后，红黑树会删除所有节点，但会保留内存空间以供重复使用。此时红黑树为空，转入第4步，将刚刚因为红黑树满而没有插入的节点插入到空的红黑树中。第四步，插入一个新节点。从t_group_by表中读取一条记录后，将i1字段的值作为新节点的数据插入到红黑树中，然后返回步骤1继续执行。循环执行步骤1到4，直到将一个组的所有数据都插入到红黑树中，循环过程结束，进入步骤5。第五步，处理count(distinct)聚合逻辑。处理聚合逻辑有两种情况：没有使用磁盘文件，组记录很少，红黑树一次未填充，所有数据都在内存中。使用磁盘文件，组记录多，红黑树满。前N-1次写满后，将数据写入磁盘文件，最后的数据留在内存中。如果您不使用磁盘文件，请转到第6步。如果使用磁盘文件，请转到第7步。第6步，分组计数。红黑树的所有节点都在内存中，红黑树的节点个数就是count(distinct)函数的结果。处理完该步骤后，流程结束。第七步，对多个数据块进行合并去重，然后分组统计。红黑树是满的，一部分数据在磁盘文件里，一部分数据在内存里。需要将内存中红黑树的所有节点数据写入磁盘文件，形成最后一个数据块。将所有数据写入磁盘文件后，合并去重和组计数就可以开始了。首先，分配一块内存作为合并缓冲区。然后，将缓冲区平均分成N份。为了描述方便，我们称缓冲区的一部分为子缓冲区。假设示例SQL在磁盘文件中有4个数据块，将对应4个subbuffer。每个数据块对应的Merge_chunk存储了子缓冲区的起始位置和结束位置，可以存储的记录数，以及指向下一条要处理的记录在子缓冲区中的位置。mergebuffer中每个数据块内的记录按照字段内容从小到大排序。多个数据块的合并和去重的过程并不复杂。步骤如下：合并去重和分组计数过程①从文件中读取磁盘数据块到子缓冲区中。从每个数据块中读取一部分记录到子缓冲区，所有数据块对应的Merge_chunk组成一个优先级队列。此时每个Merge_chunk的m_current_key指向数据块的第一条记录，也是数据块中最小的记录，这条记录的内容代表了Merge_chunk的值。Merge_chunk的m_mem_count表示已经读入subbuffer而未处理的记录数。②获取优先级队列中最小的Merge_chunk，用top表示。优先级队列中的第一个Merge_chunk是所有Merge_chunk中最小的。③将topMerge_chunk的m_current_key指向的记录内容读到old_key。m_current_key指向的记录是topMerge_chunk中最小的记录，记录为old_key。然后，m_current_key指向数据块中的下一条记录，m_mem_count减1，表示已经读入子缓冲区的未处理记录减1。④如果m_mem_count等于0，表示表示该数据块对应的子缓冲区中的记录已经处理完毕，需要从磁盘文件中读取该数据块的一部分到子缓冲区中。如果数据块中的数据已经处理完毕，则将该数据块对应的Merge_chunk从优先级队列中删除，并将对应子缓冲区的内存空间全部合并到相邻的子缓冲区中。⑤更新优先级队列中的topMerge_chunk。③和④两步执行完后，可能最小的Merge_chunk发生了变化，所以需要更新优先级队列，保证优先级队列中的第一个Merge_chunk是最小的。⑥真正的去重操作。将新的topMerge_chunk中最小记录的内容与old_key的值进行比较。如果相同，说明该字段内容重复，不需要进行分组统计。回到③继续下一个循环。如果不相同，说明该字段内容不重复，统计topMerge_chunk中最小的记录，然后返回③继续下一次循环。③~⑥循环执行，直到优先级队列中的Merge_chunks个数小于等于1，循环结束。⑦处理最后一个数据块中的剩余数据。经过③~⑥的循环执行过程后，优先队列中还会剩下一个Merge_chunk。需要对Merge_chunk对应的数据块中的剩余记录进行分组统计，因为它是一个数据块的内部记录，所以不需要去重。之前没有显示的问题应该还有后续：因为在对一个磁盘文件的多个数据块中的记录进行合并去重时，需要使用字段内容进行比对，MEMORY引擎的HASH索引不保存字段内容，只保存表中数据行的首地址，这也是MySQL选择使用红黑树去重而不使用HASH的原因。8.sum(distinct)和avg(distinct)是不同的。sum(distinct)和avg(distinct)也需要去重，但是和count(distinct)不同的是sum(distinct)和avg(distinct)只会对整数和浮点数进行求和或求平均，而且只能有一个参数，需要比较小的内存空间，也就是说sum(distinct)和avg(distinct)在去重的时候不需要使用临时磁盘表。因此，对于sum(distinct)和avg(distinct)，只会选择红黑树去重，不会创建空的MEMORY临时表，这一点与count(distinct)不同。如果sum()和avg()函数的参数中的字段不是整型或浮点型字段，则不会报错，并将字段值转为浮点数，然后浮点数将被求和或平均。非整数和浮点数类型字段到浮点数的转换与开发语言中的转换逻辑基本相同。对于字符串内容，字符串前面的数字作为字段的数值。例如：91test转换成浮点数是91.0，test转换成浮点数是0.0。9.小结第2节介绍了MEMORY引擎支持的两种索引结构：HASH索引和B-TREE索引。HASH索引适用于单值查找较多的场景；B-TREE索引适用于范围查询和需要排序记录的场景。第3节逐步介绍MySQL为什么选择使用红黑树来实现count(distinct)去重功能。第4节介绍了红黑树单节点的结构。每个节点包含两类信息：节点元数据和节点数据。第5节介绍，当红黑树占用内存超过最大值后，会将所有节点数据写入磁盘文件，然后删除所有节点，保留内存以供重复使用。第6节逐步介绍了为什么要合并buffer，buffer的大小由两个系统变量tmp_table_size和max_heap_table_size控制。第7节介绍了对磁盘文件中所有数据块进行合并去重和分组计数的详细过程。Mergeanddeduplication和groupcounting分为红黑树满和红黑树未满两种情况，处理逻辑不同。第8节介绍了sum(distinct)和avg(distinct)只能用于整数和浮点数的求和和计算平均值。它们和count(distinct)的区别在于只能用红黑树来Heavy，不需要创建MEMORY临时表，更不用说磁盘临时表了。本文转载自微信公众号“一树一溪”，可通过以下二维码关注。转载本文请联系艺书艺熙公众号。
