一、MYSQL中的LIMIT和ORACLE中的分頁
在MYSQL官方文檔中描述limit是在結果集中傳回你需要的資料，它可以盡快的傳回需要的行而不用管剩下的行，
在ORACLE中也有相關的文法比如 12C以前的rownun<n，也是達到同樣的效果，同時limit也能做到分頁查詢如
limit n,m 則代表傳回n開始的m行，ORACLE 12C以前也有分頁方式但是相對比較麻煩
那麼如果涉及到排序呢？我們需要傳回按照字段排序後的某幾行：
MYSQL:
select * from test order by id limit 51,100
ORACLE 12C以前：
SELECT *
FROM (SELECT tt.*, ROWNUM AS rowno
FROM (SELECT t.*
FROM test t)
ORDER BY id desc) tt
WHERE ROWNUM <= 100) table_alias
WHERE table_alias.rowno > 50;
當然如上的文法如果id列有索引那麼就簡單了，索引本生就是排序好的，使用索引結構即可，但是如果id列沒有索引呢？
那該如何完成，難道把id列全部排序好在傳回需要的行？顯然這樣代價過高，違背了limit中盡快傳回需要的行的精神
這樣我們必須使用一種合适的算法來完成，那這裡就引入的堆排序和優先隊列(Priority Queue 簡稱PQ)。
在MYSQL中執行計劃沒有完全的表現，執行計劃依然為filesort：
mysql> explain select * from testshared3 order by id limit 10,20;
+----+-------------+-------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
| 1 | SIMPLE | testshared3 | NULL | ALL | NULL | NULL | NULL | NULL | 1023820 | 100.00 | Using filesort |
1 row in set, 1 warning (0.02 sec)
但是根據源碼的提示
DBUG_PRINT("info", ("filesort PQ is applicable"));
DBUG_PRINT("info", ("filesort PQ is not applicable"));
注意這裡PQ可能棄用，什麼時候棄用看後面
可以看到是否啟用了PQ也就是優先隊列的簡寫
可以再trace中找到相關說明:
[root@testmy tmp]# cat pq.trace |grep "filesort PQ is applicable"
T@2: | | | | | | | | | | info: filesort PQ is applicable
在ORACLE中使用執行計劃：
--------------------------------------------------------------------------------
Plan hash value: 1473139430
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)|
| 0 | SELECT STATEMENT | | 100 | 77900 | | 85431 (1)|
|* 1 | VIEW | | 100 | 77900 | | 85431 (1)|
|* 2 | COUNT STOPKEY | | | | | |
| 3 | VIEW | | 718K| 524M| | 85431 (1)|
|* 4 | SORT ORDER BY STOPKEY| | 718K| 325M| 431M| 85431 (1)|
| 5 | TABLE ACCESS FULL | TEST10 | 718K| 325M| | 13078 (1)|
這裡SORT ORDER BY STOPKEY就代表了排序停止，但是ORACLE沒有源碼沒法确切的證據使用了
優先隊列和堆排序，隻能猜測他使用了優先隊列和堆排序
二、堆排序和優先隊列
--大頂堆特性(小頂堆相似見代碼)
1、必須滿足完全二叉樹
關于完全二叉樹參考
http://blog.itpub.net/7728585/viewspace-2125889/
2、很友善的根據父節點的位置計算出兩個葉子結點的位置
如果父節點的位置為i/2
左子節點為 i，右子節點為i+1
這是完全二叉樹的特性決定
3、所有子節點都可以看做一個子堆那麼所有結點都有
父節點>=左子節點 && 父節點>=右節點
4、很明顯的可以找到最大的元素，就是整個堆的根結點
--堆需要完成操作
堆排序方法也是最優隊列的實作方法，MYSQL源碼中明顯的使用了優先隊列來優化order by limit n ，估計max也是用的這種算法
當然前提是沒有使用到索引的情況下。
根據這些特性明顯又是一個遞歸的成堆的操作。
參考算法導論第六章，裡面的插圖能夠加深了解，這裡截取一張建構好的大頂堆
建構方法：自下而上的建構自左向右建構堆，其實就是不斷調用維護方法的過程
維護方法：使用遞歸的逐級下降的方法進行維護，是整個算法的核心内容，搞清楚了維護方法其他任何操作都來自于它。
排序方法：最大元素放到最後,然後逐層下降的方法進行調整。
資料庫中的應用：
order by asc/desc limit n：簡化的排序而已，隻是排序前面n就可以了，不用全部排序完成，性能優越，資料庫分頁查詢大量使用這個算法。參考代碼
max/min ：a[1]就是最大值,隻能保證a[1]>=a[2]&&a[1]>=a[3] 不能保證a[3]>=a[4]，堆建立完成後就可以找到MAX值，但是MYSQL max并沒有使用這個算法
我在代碼中完成了這些操作，代碼中有比較詳細的注釋，這裡就不詳細說明了。
我使用了2個數組用于作為測試資料
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]不使用
分别求a素組的最大值和最小前3位數字，求b數組的MAX/MIN值，結果如下：
gaopeng@bogon:~/datas$ ./a.out
大頂堆:
order by desc a array limit 3 result:2222 999 102
max values b array reulst:888888
小頂堆:
order by asc a array limit 3 result:1 2 3
min values b array reulst:2
可以看到沒問題。
--優先隊列：優先隊列不同于普通隊列先進先出的規則，而定義為以某種規定先出，比如最大先出或者最小先出，這個沒什麼難度了，不就和資料庫的order
by limit是一回事嗎？當然是用大頂堆或者小頂堆完成
三、MYSQL中優先隊列的接口
MYSQL中的優先隊列類在
priority_queue.h中的class Priority_queue : public Less
他實作了很多功能，不過其他功能都很簡單主要是堆的維護
下面是MYSQL源碼中的堆的維護代碼
void heapify(size_type i, size_type last)
{
DBUG_ASSERT(i < size());
size_type largest = i;
do
{
i = largest;
size_type l = left(i);
size_type r = right(i);
if (l < last && Base::operator()(m_container[i], m_container[l]))
{
largest = l;
}
if (r < last && Base::operator()(m_container[largest], m_container[r]))
largest = r;
if (largest != i)
std::swap(m_container[i], m_container[largest]);
} while (largest != i);
}
可以看見實際和我寫的差不多。
四、MYSQL如何判斷是否啟用PQ
一般來說快速排序的效率高于堆排序，但是堆排序有着天生的特點可以實作優先隊列，來實作
order by limit
(關于快速排序參考：http://blog.itpub.net/7728585/viewspace-2130743/)
那麼這裡就涉及一個問題，那就是快速排序和最優的隊列的臨界切換，比如
表A 100W行記錄 id列沒有索引
select * from a order by id limit 10;
和
select * from a order by id limit 900000,10;
肯定前者應該使用最優隊列，而後者實際上要排序好至少900010行資料才能傳回。
那麼這個時候應該使用快速排序,那麼trace資訊應該為
filesort PQ is not applicable
[root@testmy tmp]# cat pqdis.trace |grep "filesort PQ "
T@2: | | | | | | | | | | info: filesort PQ is not applicable
那麼MYSQL值确定是否使用PQ，其判定接口為check_if_pq_applicable函數，
簡單的說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函數
至少和下面有關
1、是否能夠在記憶體中完成
2、排序行數
3、字段數
最後需要說明一點PQ排序關閉了一次通路排序的pack功能如下：
/*
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).
*/
五、實作代碼，維護方法列出了2種實作，方法2是算法導論上的更容易了解
點選(此處)折疊或打開
/*************************************************************************
> File Name: heapsort.c
> Author: gaopeng QQ:22389860 all right reserved
> Mail: [email protected]
> 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=4,n=9
/*
* 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); //左節點編号
r=RIGTH(s);//右節點編号
if(s<=n/2) // n/2為最小節點編号的父親節點 如果s大于這個值說明這個節點不會有任何子節點不需要進行調整 ！！,這是整個算法的核心中的核心。搞了我老半天
{
if (l<=n && k[l] > k[s])
{
largest = l;
}
else
largest = s;
if(r<=n && k[r] > k[largest])
largest = r;
if(largest != s)
swap(k,largest,s);
bigheapad(k,largest,n); //對資料調整後可能的子節點樹繼續進行調整直到達到遞歸退出條件
}
return 0;
int bigheapbulid(int k[],int n)
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剛好是最後一個節點的父親節點是以自下而上
bigheapad(k,i,n);
int bigheapsort(int k[],int n) //sort的過程就是将最大元素放到最後，然後逐層下降的方法進行調整
for(i=n;i>1;i--)
swap(k,1,i);
bigheapad(k,1,i-1);
int biglimitn(int k[],int n,int limitn)//limit 也是我關心的 這裡明顯可以看到他的優勢實際它不需要對整個數組排序，你要多少我排多少給你就好，也是最大元素放到最後，然後逐層下降的方法進行調整的原理
for(i=n;i>n-limitn;i--)
int smallheapad(int k[],int s,int n) //s=4,n=9
int smallest;
if(s<=n/2) // n/2為最小節點編号的父親節點 如果s大于這個值說明這個節點不會有任何子節點不需要進行調整 ！！
if (l<=n && k[l] < k[s])
smallest = l;
smallest = s;
if(r<=n && k[r] < k[smallest])
smallest = r;
if(smallest != s)
swap(k,smallest,s);
smallheapad(k,smallest,n); //對資料調整後可能的子節點樹繼續進行調整直到達到遞歸退出條件
}
int smallheapbulid(int k[],int n)
for(i=n/2;i>0;i--)
smallheapad(k,i,n);
int smallheapsort(int k[],int n)
smallheapad(k,1,i-1);
int smalllimitn(int k[],int n,int limitn)
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:");
smallheapbulid(b,10);
printf("min values b array reulst:");
</n，也是達到同樣的效果，同時limit也能做到分頁查詢如
![【MySQL資料庫】資料庫索引事務1.索引2.事務[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)