189 8069 5689
这篇文章主要介绍“MySQL中关于排序order by limit值不稳定分析”，在日常操作中，相信很多人在MySQL中关于排序order by limit值不稳定分析问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”MySQL中关于排序order by limit值不稳定分析”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
创新互联公司服务项目包括新晃网站建设、新晃网站制作、新晃网页制作以及新晃网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，新晃网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到新晃省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
数据如下：
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,14,'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, ¶m, &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 0x0000000000f50e62 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 times4 breakpoint keep y 0x0000000000f50d41 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=0x7fff300128c0, 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=0x7fff300128c0, 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个字节还是很少会超过的。
最后我还是想简单描述一下堆排序算法，也当复习一下。具体可以参考算法导论等书籍，我们以大顶堆为例，实际上任何一个待排序的数组都可以看成一棵完全二叉树，用算法导论的截图如下：
image.png
这棵树是满足大顶堆定义的，在大顶堆中有如下特性：
必须满足完全二叉树
很方便的根据父节点的位置计算出两个叶子结点的位置
如果父节点的位置为i/2，左子节点为 i，右子节点为i+1这是完全二叉树的特性决定
所有子节点都可以看做一个子堆那么所有结点都有
父节点>左子节点 && 父节点>右节点
很明显的可以找到最大的元素，就是整个堆的根结点
在这个算法中，最重要也是最主要的就是堆的维护，堆的构建。
维护：
维护：采用的是自上而下的维护，可以用递归完成。
这里电子版有点不清晰，黑色结点就是值4
image.png
对应我最后的代码 bigheapad函数
构建
构建：是采用自下而上的构建，构建就是不断循环的对各个父结点做维护，以达到对任何一个无序数组满足大顶堆的条件。因为下层的子树满足了大顶堆条件那么上层就一定满足大顶堆的条件。
image.png
image.png
对应我最后的代码bigheapbulid函数
排序
实际上排序就是将数组中的第一个数字也就是最大的数字和最后一个数字交换，然后再次做一次维护做好大顶堆结构即可，如果反复不断做这个操作那么整个素组都会排序完成。
image.png
image.png
我的函数参考biglimitn和bigheapsort函数。对于MySQL的源码中堆排序的代码存在于priority_queue.h文件中，其中可以看到一些方法如：
维护 heapify函数
构建 build_heap函数
排序 sort函数
当然源码的实现复杂得多，有兴趣的朋友可以深入。栈帧备查：