溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“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函數
當然源碼的實現復雜得多，有興趣的朋友可以深入。棧幀備查：
#0 Priority_queue<uchar*, std::vector<uchar*, Malloc_allocator<uchar*> >, <unnamed>::Mem_compare>::heapify(size_t, size_t) (this=0x7ffff0115650, i=0, last=8) at /root/mysql5.7.14/percona-server-5.7.14-7/include/priority_queue.h:124#1 0x0000000000f5807a in Priority_queue<uchar*, std::vector<uchar*, Malloc_allocator<uchar*> >, <unnamed>::Mem_compare>::heapify(size_t) (this=0x7ffff0115650, i=0) at /root/mysql5.7.14/percona-server-5.7.14-7/include/priority_queue.h:147#2 0x0000000000f57d1e in Priority_queue<uchar*, std::vector<uchar*, Malloc_allocator<uchar*> >, <unnamed>::Mem_compare>::update_top(void) (this=0x7ffff0115650) at /root/mysql5.7.14/percona-server-5.7.14-7/include/priority_queue.h:354#3 0x0000000000f57814 in Bounded_queue<uchar*, uchar*, Sort_param, <unnamed>::Mem_compare>::push(uchar *) (this=0x7ffff0115650, element=0x7fff309166a0 "o") at /root/mysql5.7.14/percona-server-5.7.14-7/sql/bounded_queue.h:106#4 0x0000000000f52da7 in find_all_keys(Sort_param *, QEP_TAB *, Filesort_info *, IO_CACHE *, IO_CACHE *, Bounded_queue<uchar*, uchar*, Sort_param, <unnamed>::Mem_compare> *, ha_rows *) (param=0x7ffff01154c0, qep_tab=0x7fff309268e8, fs_info=0x7ffff0115550, chunk_file=0x7ffff0115200, tempfile=0x7ffff0115360, pq=0x7ffff0115650, found_rows=0x7ffff0115898) at /root/mysql5.7.14/percona-server-5.7.14-7/sql/filesort.cc:1013#5 0x0000000000f51165 in filesort (thd=0x7fff30000bc0, filesort=0x7fff30926bd8, 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:425
下面是一個我以前參考算法導論第六章堆排序寫的一個實現，其中包含了大頂堆和小頂堆，供大家參考：
/*************************************************************************
> File Name: heapsort.c
> Author: gaopeng QQ:22389860 all right reserved
> Mail: gaopp_200217@163.com
> Created Time: Sun 08 Jan 2017 11:22:14 PM CST
************************************************************************/#include<stdio.h>#include<stdlib.h>#define LEFT(i) i<<1#define RIGTH(i) (i<<1)+1//堆排序的性能不及快速排序但是在某些情況下非常有用//數據庫的order by limit使用了優先隊列，基于堆排序int swap(int k[],int i,int j){ int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp; return 0;
}int bigheapad(int k[],int s,int n) //s=5,n=10 自上而下的維護{ /*
* one:
int i;
int temp = k[s]; //temp=9=k[4] 父節點值保存到temp
for(i=2*s;i<=n;i=i*2)// i=8
{
if(i<n && k[i]<k[i+1])//如果左子節點小于右子節點
{
i++; //右節點
}
if(temp>=k[i])
{
break;
}
k[s] = k[i];
s = i;
}
k[s] = temp;
*/
// two: 參考算法導論P155頁,整個方法更容易理解其原理，調整使用逐層下降的方法進行調整
int l; //s 左節點編號
int r; //s 右節點編號
int largest;
l=LEFT(s); //左節點編號 10
r=RIGTH(s);//右節點編號 11
if(s<=n/2) // n/2為最小節點編號的父親節點 如果s大于這個值說明這個節點不會有任何子節點不需要進行調整 ！！,這是整個算法的核心中的核心。搞了我老半天
{ if (l<=n && k[l] > k[s])
{
largest = l; //10
} else
{
largest = s;
} if(r<=n && k[r] > k[largest]) //11<=10 不成立直接不運行
{
largest = r;
} if(largest != s) //如果較大的數字在孩子節點則交換父節點和孩子節點的值，否則不動
{
swap(k,largest,s); //這里做孩子節點和父節點的交換
bigheapad(k,largest,n); //這里做遞歸下層操作，需要做到本次操作不會破壞堆的特性
}
}return 0;
}int bigheapbulid(int k[],int n) // bigheapbulid(a,10);{ int i; for(i=n/2;i>0;i--)//采用自底向上的方法構建 算法導論P156 EXP 1:i= n/2 p:4 l:8 r:9 2: i = p:3 l:6 r:7 n/2剛好是最后一個節點的父親節點所以自下而上
{ //eg 10 i=5 4 3 2 1
bigheapad(k,i,n); //i=5 n=10
}return 0;
}int bigheapsort(int k[],int n) //sort的過程就是將最大元素放到最后，然后逐層下降的方法進行調整{ int i; for(i=n;i>1;i--)
{
swap(k,1,i); // 這里k[1] 就是最大值了，我們將他交換到最后面
bigheapad(k,1,i-1);//重新構建大頂堆
}return 0;
}int biglimitn(int k[],int n,int limitn)//limit 也是我關心的 這里明顯可以看到他的優勢實際它不需要對整個數組排序，你要多少我排多少給你就好，也是最大元素放到最后，然后逐層下降的方法進行調整的原理{ int i; for(i=n;i>n-limitn;i--)
{
swap(k,1,i);
bigheapad(k,1,i-1);
}return 0;
}int smallheapad(int k[],int s,int n) //s=4,n=9{ int l; //s 左節點編號
int r; //s 右節點編號
int smallest;
l=LEFT(s); //左節點編號
r=RIGTH(s);//右節點編號
if(s<=n/2) // n/2為最小節點編號的父親節點 如果s大于這個值說明這個節點不會有任何子節點不需要進行調整 ！！
{ if (l<=n && k[l] < k[s])
{
smallest = l;
} else
{
smallest = s;
} if(r<=n && k[r] < k[smallest])
{
smallest = r;
} if(smallest != s)
{
swap(k,smallest,s);
smallheapad(k,smallest,n); //對數據調整后可能的子節點樹繼續進行調整直到達到遞歸退出條件
}
}
return 0;
}int smallheapbulid(int k[],int n){ int i; for(i=n/2;i>0;i--)
{
smallheapad(k,i,n);
}return 0;
}int smallheapsort(int k[],int n) { int i; for(i=n;i>1;i--)
{
swap(k,1,i);
smallheapad(k,1,i-1);
}return 0;
}int smalllimitn(int k[],int n,int limitn){ int i; for(i=n;i>n-limitn;i--)
{
swap(k,1,i);
smallheapad(k,1,i-1);
}return 0;
}int main(){ int i,a[11]={0,999,3,2,9,34,5,102,90,2222,1}; //測試數據 a[0]不使用
int b[11]={0,999,3,2,9,999,888888,102,90,2222,111};//測試數據 b[0]不使用
bigheapbulid(a,10);
biglimitn(a,10,3);
printf("大頂堆:\n"); printf("order by desc a array limit 3 result:"); for(i=10;i>10-3;i--)
{ printf("%d ",a[i]);
} printf("\n");
bigheapbulid(b,10); printf("max values b array reulst:"); printf("%d \n",b[1]);
smallheapbulid(a,10);
smalllimitn(a,10,3); printf("小頂堆:\n"); printf("order by asc a array limit 3 result:"); for(i=10;i>10-3;i--)
{ printf("%d ",a[i]);
} printf("\n");
smallheapbulid(b,10); printf("min values b array reulst:"); printf("%d \n",b[1]);return 0;
}到此，關于“MySQL中關于排序order by limit值不穩定分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
