作者:高鹏(重庆八怪)

原文地址:

本系列文章将持续更新,欢迎关注~

源码版本:5.7.14本文约定:PQ 就是  Priority Queue 及优先队列其实现算法是堆排序。

数据如下:

CREATE TABLE `testse` (  `id` int(11) NOT NULL,  `nu` int(11) DEFAULT NULL,  `name` varchar(20) DEFAULT NULL,  PRIMARY KEY (`id`),  KEY `nu` (`nu`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8; INSERT INTO `testse` VALUES (-1,14,'gaopeng'),(0,14,'gaopeng'),(1,1,'gaopeng'),(2,99,'gaopeng'),(3,55,'gaopeng'),(4,20,'gaopeng'),(5,24,'gaopeng'),(6,14,'gaopeng'),(7,1 4,'gaopeng'),(8,13,'gaopeng'),(9,9,'gaopeng'),(10,19,'gaopeng'),(11,20,'gaopeng'),(12,14,'gaopeng'),(13,15,'gaopeng'),(14,16,'gaopeng'),(15,20,'gaopeng'),(100,14,'gaope ng'),(111,14,'gaopeng');问题如下:

mysql>  select *  from testse order by  nu limit 3,1; +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ | 111 |   14 | gaopeng | +-----+------+---------+ 1 row in set (2.76 sec) mysql>  select *  from testse force index(nu) order by  nu limit 3,1; +----+------+---------+ | id | nu   | name    | +----+------+---------+ | -1 |   14 | gaopeng | +----+------+---------+ 1 row in set (0.00 sec)问为什么这两个语句得到的数据不一样?

这里首先给出原因:在MySQL排序的时候可以使用索引来避免排序及不需要使用filesort,其次当使用filesort的时候可能在内存中出现两种情况及堆排序列和快速排序两种方式。所以MySQL内存排序可以使用的途径包含:

直接利用索引避免排序

快速排序

具体使用哪一种排序方式是优化器决定的,总的说来如下:

直接利用索引避免排序:用于有索引且回表效率高的情况下

快速排序算法:如果没有索引大量排序的情况下

堆排序算法:如果没有索引排序量不大的情况下

而快速排序和堆排序是不稳定的排序算法,也就是对于重复值是不能保证顺序的。而直接利用索引的话其返回数据是稳定的,因为索引的B+树叶子结点的顺序是唯一且一定的。如上的key nu,其叶子结点包含了nu+id,它是唯一的顺序也是递增的。因此在这种不稳定的算法情况下上面的查询出现了不一样的结果,归根结底就是使用索引避免排序和堆排序对于重复值的处理上是不同的。也许你会问为什么存在两种排序方式,实际上在大量排序的情况下快速排序是有优势的,而堆排序使用优先队列只完成少量的排序是有优势的,因为它根本不需要排序完成只排序你需要的数据量就可以了。

MySQL认为快速排序的速度是堆排序的3倍如下:

/*    How much Priority Queue sort is slower than qsort.    Measurements (see unit test) indicate that PQ is roughly 3 times slower.  */  const double PQ_slowness= 3.0;那么在使用排序算法的时候会根据待排序数据量的大小进行切换具体根据函数check_if_pq_applicable进行判定的。在filesort函数里面有如下代码:

if (check_if_pq_applicable(trace, &param, &table_sort,                             table, num_rows, memory_available,                             subselect != NULL))  {    DBUG_PRINT("info", ("filesort PQ is applicable")); //使用堆排序    /*      For PQ queries (with limit) we know exactly how many pointers/records      we have in the buffer, so to simplify things, we initialize      all pointers here. (We cannot pack fields anyways, so there is no      point in doing lazy initialization).     */    table_sort.init_record_pointers();    .....   filesort->using_pq= true;    param.using_pq= true;  }  else//使用快速排序  {    DBUG_PRINT("info", ("filesort PQ is not applicable"));    filesort->using_pq= false;    param.using_pq= false; .....  }三、如何确定是使用的哪种方法返回排序的结果

对于直接利用索引避免排序,这个直接看执行计划就好了,不会出现filesort字样。但是对于到底使用额快速排序还是堆排序则不好判断因为执行计划是一样的,我想到的只能是在调试的时候做断点,不知道还有其他办法没有。因此我在上面代码的if分支里面做了2个断点,其中一个断点在堆排序算法里面,一个断点在快速排序算法里面如下:

3       breakpoint     keep y   0x00f50e62 in filesort(THD*, Filesort*, bool, ha_rows*, ha_rows*, ha_rows*)                                               at /root/mysql5.7.14/percona-server-5.7.14-7/sql/filesort.cc:359        breakpoint already hit 3 times 4       breakpoint     keep y   0x00f50d41 in filesort(THD*, Filesort*, bool, ha_rows*, ha_rows*, ha_rows*)                                               at /root/mysql5.7.14/percona-server-5.7.14-7/sql/filesort.cc:333        breakpoint already hit 1 time其中断点3代表快速排序命中,断点4代表堆排序命中。

如上所述我们可以将结果的返回定义为三种方式,我们将在这里测试这三种方式的得到数据不同。

使用索引避免排序的结果

语句:select *  from testse force index(nu) order by  nu;

mysql> desc select *  from testse force index(nu) order by  nu; +----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+-------+ | id | select_type | table  | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra | +----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+-------+ |  1 | SIMPLE      | testse | NULL       | index | NULL          | nu   | 5       | NULL |   19 |   100.00 | NULL  | +----+-------------+--------+------------+-------+---------------+------+---------+------+------+----------+-------+ 1 row in set, 1 warning (0.00 sec) mysql> select *  from testse force index(nu) order by  nu; +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | |  -1 |   14 | gaopeng | |   0 |   14 | gaopeng | |   6 |   14 | gaopeng | |   7 |   14 | gaopeng | |  12 |   14 | gaopeng | | 100 |   14 | gaopeng | | 111 |   14 | gaopeng | |  13 |   15 | gaopeng | |  14 |   16 | gaopeng | |  10 |   19 | gaopeng | |   4 |   20 | gaopeng | |  11 |   20 | gaopeng | |  15 |   20 | gaopeng | |   5 |   24 | gaopeng | |   3 |   55 | gaopeng | |   2 |   99 | gaopeng | +-----+------+---------+ 19 rows in set (0.01 sec)

使用快速排序的结果

语句:select *  from testse order by  nu;

因为我前面设置了断点,其断点命中如下:

Breakpoint 3, filesort (thd=0x7fffc0, filesort=0x7fff30963e90, sort_positions=false, examined_rows=0x7ffff01158a0, found_rows=0x7ffff0115898,    returned_rows=0x7ffff0115890) at /root/mysql5.7.14/percona-server-5.7.14-7/sql/filesort.cc:359 359         DBUG_PRINT("info", ("filesort PQ is not applicable"));可以看到PQ 没有开启,也就是堆排序没有使用使用的优先队列堆排序方式。那么它的结果是:

mysql> desc select *  from testse order by  nu; +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ | id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra          | +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ |  1 | SIMPLE      | testse | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   19 |   100.00 | Using filesort | +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ 1 row in set, 1 warning (0.00 sec) mysql> select *  from testse order by  nu; +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | | 111 |   14 | gaopeng | | 100 |   14 | gaopeng | |  12 |   14 | gaopeng | |   7 |   14 | gaopeng | |   6 |   14 | gaopeng | |   0 |   14 | gaopeng | |  -1 |   14 | gaopeng | |  13 |   15 | gaopeng | |  14 |   16 | gaopeng | |  10 |   19 | gaopeng | |   4 |   20 | gaopeng | |  11 |   20 | gaopeng | |  15 |   20 | gaopeng | |   5 |   24 | gaopeng | |   3 |   55 | gaopeng | |   2 |   99 | gaopeng | +-----+------+---------+ 19 rows in set (1.74 sec)使用堆排序

语句:select *  from testse order by  nu limit 8;

其断点命中

Breakpoint 4, filesort (thd=0x7fffc0, filesort=0x7fff3095ecc8, sort_positions=false, examined_rows=0x7ffff01158a0, found_rows=0x7ffff0115898,    returned_rows=0x7ffff0115890) at /root/mysql5.7.14/percona-server-5.7.14-7/sql/filesort.cc:333 333         DBUG_PRINT("info", ("filesort PQ is applicable"));可以看到PQ 开启了,也就是堆排序。

mysql> desc  select *  from testse order by  nu limit 8; +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ | id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra          | +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ |  1 | SIMPLE      | testse | NULL       | ALL  | NULL          | NULL | NULL    | NULL |   19 |   100.00 | Using filesort | +----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+----------------+ 1 row in set, 1 warning (0.00 sec) mysql> select *  from testse order by  nu limit 8; +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | |  -1 |   14 | gaopeng | |   0 |   14 | gaopeng | |  12 |   14 | gaopeng | | 111 |   14 | gaopeng | |   6 |   14 | gaopeng | +-----+------+---------+ 8 rows in set (2.20 sec)可以看到从前面8行来看,每种方法返回的数据是不一样的:

使用索引避免排序: +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | |  -1 |   14 | gaopeng | |   0 |   14 | gaopeng | |   6 |   14 | gaopeng | |   7 |   14 | gaopeng | |  12 |   14 | gaopeng | 使用快速排序: +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | | 111 |   14 | gaopeng | | 100 |   14 | gaopeng | |  12 |   14 | gaopeng | |   7 |   14 | gaopeng | |   6 |   14 | gaopeng | 使用堆排序: +-----+------+---------+ | id  | nu   | name    | +-----+------+---------+ |   1 |    1 | gaopeng | |   9 |    9 | gaopeng | |   8 |   13 | gaopeng | |  -1 |   14 | gaopeng | |   0 |   14 | gaopeng | |  12 |   14 | gaopeng | | 111 |   14 | gaopeng | |   6 |   14 | gaopeng | +-----+------+---------+

可以看到在不同的获取数据的方式得到的数据是不一样的,但是这只是重复数据排序的部分,这是排序算法的不稳定性决定的。快速排序适合大数据量排序,堆排序在少量排序上有优势,因此当order by limit n,n到了一个数量级的时候会切换排序算法,这个在执行计划是看不到的,具体使用那种算法是优化器通过函数check_if_pq_applicable进行判定的。其次这只是一种造成排序数据不一致的情况还有一种情况是由于参数 max_length_for_sort_data的参数影响的一次排序和二次排序,这个有机会在研究一下代码。一般默认1024个字节还是很少会超过的。

最后我还是想简单描述一下堆排序算法,也当复习一下。具体可以参考算法导论等书籍,我们以大顶堆为例,实际上任何一个待排序的数组都可以看成一棵完全二叉树,用算法导论的截图如下:

这棵树是满足大顶堆定义的,在大顶堆中有如下特性:

必须满足完全二叉树关于完全二叉树参考-2125889/

很方便的根据父节点的位置计算出两个叶子结点的位置如果父节点的位置为i/2,左子节点为 i,右子节点为i+1这是完全二叉树的特性决定

所有子节点都可以看做一个子堆那么所有结点都有父节点>左子节点 && 父节点>右节点

很明显的可以找到最大的元素,就是整个堆的根结点

在这个算法中,最重要也是最主要的就是堆的维护,堆的构建。

维护:维护:采用的是自上而下的维护,可以用递归完成。这里电子版有点不清晰,黑色结点就是值4

构建构建:是采用自下而上的构建,构建就是不断循环的对各个父结点做维护,以达到对任何一个无序数组满足大顶堆的条件。因为下层的子树满足了大顶堆条件那么上层就一定满足大顶堆的条件。

实际上排序就是将数组中的第一个数字也就是最大的数字和最后一个数字交换,然后再次做一次维护做好大顶堆结构即可,如果反复不断做这个操作那么整个数组都会排序完成。

对于MySQL的源码中堆排序的代码存在于priority_queue.h文件中,其中可以看到一些方法如:

维护 heapify函数

构建 build_heap函数

排序 sort函数当然源码的实现复杂得多,有兴趣的朋友可以深入。栈帧备查:

对本文有任何疑问可扫码添加原文作者微信

加入知数堂

挑战40万+年薪!

叶金荣与吴炳锡联合打造

领跑IT精英培训

行业资深专家强强联合,倾心定制

MySQL实战/MySQL优化/MongoDB/

Python/ SQL优化/Hadoop+ELK

数门精品课程

“阅读原文”可获更多正课试听视频

密码:hg3h

紧随技术发展趋势,定期优化培训教案

融入大量生产案例,贴合企业一线需求

社群陪伴学习,一次报名,可学1年

DBA、开发工程师必修课

上千位学员已华丽转身,薪资翻番,职位提升

改变已悄然发生,你还在等什么?

MySQL 8.0|MGR研究院-ZST