MYSQL如何實現ORDER BY和LIMIT

197次閱讀

共計 8036 個字符，預計需要花費 21 分鐘才能閱讀完成。

這篇文章主要為大家展示了“MYSQL 如何實現 ORDER BY 和 LIMIT”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓丸趣 TV 小編帶領大家一起研究并學習一下“MYSQL 如何實現 ORDER BY 和 LIMIT”這篇文章吧。

一、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

但是根據源碼的提示
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

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=4,n=9

{

/*

* one:

int i;

int temp = k[s]; //temp=9=k[4] 父節點值保存到 temp

for(i=2*s;i 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 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);

}

return 0;

}

int bigheapsort(int k[],int n) //sort 的過程就是將最大元素放到最后，然后逐層下降的方法進行調整

{

int i;

for(i=n;i i–)

{

swap(k,1,i);

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 i–)

{

smallheapad(k,i,n);

}

return 0;

}

int smallheapsort(int k[],int n)

{

int i;

for(i=n;i 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”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注丸趣 TV 行業資訊頻道！

正文完

發表至：數據庫

2023-07-27

轉載說明：除特殊說明外本站除技術相關以外文章皆由網絡搜集發布，轉載請注明出處。

oracle如何創建、刷新物化視圖

Ubuntu上怎么設置MySQL遠程訪問

mysql中怎么允許用戶遠程連接

Javascript中如何使用Date對象

如何使用load data導入數據到mysql

久久精品人人爽,华人av在线,亚洲性视频网站,欧美专区一二三

MYSQL如何實現ORDER BY和LIMIT