MYSQL如何實現(xiàn)ORDER BY和LIMIT

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

一、MYSQL中的LIMIT和ORACLE中的分頁
在MYSQL官方文檔中描述limit是在結(jié)果集中返回你需要的數(shù)據(jù)，它可以盡快的返回需要的行而不用管剩下的行，
在ORACLE中也有相關的語法比如 12C以前的rownun<n，也是達到同樣的效果，同時limit也能做到分頁查詢?nèi)?br/>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列有索引那么就簡單了，索引本生就是排序好的，使用索引結(jié)構(gòu)即可，但是如果id列沒有索引呢？
那該如何完成，難道把id列全部排序好在返回需要的行？顯然這樣代價過高，違背了limit中盡快返回需要的行的精神
這樣我們必須使用一種合適的算法來完成，那這里就引入的堆排序和優(yōu)先隊列(Priority Queue 簡稱PQ)。
在MYSQL中執(zhí)行計劃沒有完全的表現(xiàn)，執(zhí)行計劃依然為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)


但是根據(jù)源碼的提示
DBUG_PRINT("info", ("filesort PQ is applicable"));
DBUG_PRINT("info", ("filesort PQ is not applicable"));
注意這里PQ可能棄用，什么時候棄用看后面
可以看到是否啟用了PQ也就是優(yōu)先隊列的簡寫 
可以再trace中找到相關說明:
[root@testmy tmp]# cat pq.trace |grep "filesort PQ is applicable"
T@2: | | | | | | | | | | info: filesort PQ is applicable


在ORACLE中使用執(zhí)行計劃：
--------------------------------------------------------------------------------
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沒有源碼沒法確切的證據(jù)使用了
優(yōu)先隊列和堆排序，只能猜測他使用了優(yōu)先隊列和堆排序

二、堆排序和優(yōu)先隊列

--大頂堆特性(小頂堆相似見代碼)
1、必須滿足完全二叉樹
關于完全二叉樹參考
http://blog.itpub.net/7728585/viewspace-2125889/
2、很方便的根據(jù)父節(jié)點的位置計算出兩個葉子結(jié)點的位置
如果父節(jié)點的位置為i/2
左子節(jié)點為 i，右子節(jié)點為i+1
這是完全二叉樹的特性決定
3、所有子節(jié)點都可以看做一個子堆那么所有結(jié)點都有
父節(jié)點>=左子節(jié)點 && 父節(jié)點>=右節(jié)點
4、很明顯的可以找到最大的元素，就是整個堆的根結(jié)點

--堆需要完成操作
堆排序方法也是最優(yōu)隊列的實現(xiàn)方法，MYSQL源碼中明顯的使用了優(yōu)先隊列來優(yōu)化order by limit n ，估計max也是用的這種算法
當然前提是沒有使用到索引的情況下。
根據(jù)這些特性明顯又是一個遞歸的成堆的操作。
參考算法導論第六章，里面的插圖能夠加深理解，這里截取一張構(gòu)建好的大頂堆


構(gòu)建方法：自下而上的構(gòu)建自左向右構(gòu)建堆，其實就是不斷調(diào)用維護方法的過程
維護方法：使用遞歸的逐級下降的方法進行維護，是整個算法的核心內(nèi)容，搞清楚了維護方法其他任何操作都來自于它。
排序方法：最大元素放到最后,然后逐層下降的方法進行調(diào)整。
數(shù)據(jù)庫中的應用：
order by asc/desc limit n：簡化的排序而已，只是排序前面n就可以了，不用全部排序完成，性能優(yōu)越，數(shù)據(jù)庫分頁查詢大量使用這個算法。參考代碼
max/min ：a[1]就是最大值,只能保證a[1]>=a[2]&&a[1]>=a[3]  不能保證a[3]>=a[4]，堆建立完成后就可以找到MAX值，但是MYSQL max并沒有使用這個算法

我在代碼中完成了這些操作，代碼中有比較詳細的注釋，這里就不詳細說明了。
我使用了2個數(shù)組用于作為測試數(shù)據(jù)
        int i,a[11]={0,999,3,2,9,34,5,102,90,2222,1}; //測試數(shù)據(jù) a[0]不使用
        int b[11]={0,999,3,2,9,999,888888,102,90,2222,111};//測試數(shù)據(jù) b[0]不使用

分別求a素組的最大值和最小前3位數(shù)字，求b數(shù)組的MAX/MIN值，結(jié)果如下：
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 
可以看到?jīng)]問題。


--優(yōu)先隊列：優(yōu)先隊列不同于普通隊列先進先出的規(guī)則，而定義為以某種規(guī)定先出，比如最大先出或者最小先出，這個沒什么難度了，不就和數(shù)據(jù)庫的order
            by limit是一回事嗎？當然是用大頂堆或者小頂堆完成
 
三、MYSQL中優(yōu)先隊列的接口

MYSQL中的優(yōu)先隊列類在
priority_queue.h中的class Priority_queue : public Less
他實現(xiàn)了很多功能，不過其他功能都很簡單主要是堆的維護
下面是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
一般來說快速排序的效率高于堆排序，但是堆排序有著天生的特點可以實現(xiàn)優(yōu)先隊列，來實現(xiàn)
order by limit 

(關于快速排序參考：http://blog.itpub.net/7728585/viewspace-2130743/)

那么這里就涉及一個問題，那就是快速排序和最優(yōu)的隊列的臨界切換，比如
表A 100W行記錄 id列沒有索引
select * from a order by id limit 10;
和
select * from a order by id limit 900000,10;

肯定前者應該使用最優(yōu)隊列，而后者實際上要排序好至少900010行數(shù)據(jù)才能返回。
那么這個時候應該使用快速排序,那么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函數(shù)，
簡單的說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函數(shù)
至少和下面有關
1、是否能夠在內(nèi)存中完成
2、排序行數(shù)
3、字段數(shù)


最后需要說明一點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).
     */

五、實現(xiàn)代碼，維護方法列出了2種實現(xiàn)，方法2是算法導論上的更容易理解

點擊(此處)折疊或打開

1. /*************************************************************************
   

2.   > File Name: heapsort.c
   

3.   > Author: gaopeng QQ:22389860 all right reserved
   

4.   > Mail: gaopp_200217@163.com
   

5.   > Created Time: Sun 08 Jan 2017 11:22:14 PM CST
   

6.  ************************************************************************/
   

7. 
   

8. #include<stdio.h>
   

9. #include<stdlib.h>
   

10. 
    

11. #define LEFT(i) i<<1
    

12. #define RIGTH(i) (i<<1)+1
    

13. //堆排序的性能不及快速排序但是在某些情況下非常有用
    

14. //數(shù)據(jù)庫的order by limit使用了優(yōu)先隊列，基于堆排序
    

15. 
    

16. int swap(int k[],int i,int j)
    

17. {
    

18.         int temp;
    

19. 
    

20.         temp = k[i];
    

21.         k[i] = k[j];
    

22.         k[j] = temp;
    

23.         return 0;

24. }
    

25. 
    

26. 
    

27. int bigheapad(int k[],int s,int n) //s=4,n=9
    

28. {
    

29.         /*
    

30.          * one:
    

31.          int i;
    

32.          int temp = k[s]; //temp=9=k[4] 父節(jié)點值保存到temp
    

33.          for(i=2*s;i<=n;i=i*2)// i=8
    

34.          {
    

35.          if(i<n && k[i]<k[i+1])//如果左子節(jié)點小于右子節(jié)點
    

36.          {
    

37.          i++; //右節(jié)點
    

38.          }
    

39. 
    

40.          if(temp>=k[i])
    

41.          {
    

42.          break;
    

43.          }
    

44. 
    

45.          k[s] = k[i];
    

46.          s = i;
    

47.          }
    

48. 
    

49.          k[s] = temp;
    

50.          */
    

51.         // two: 參考算法導論P155頁,整個方法更容易理解其原理，調(diào)整使用逐層下降的方法進行調(diào)整
    

52.         int l; //s 左節(jié)點編號
    

53.         int r; //s 右節(jié)點編號
    

54.         int largest;
    

55. 
    

56.         l=LEFT(s); //左節(jié)點編號
    

57.         r=RIGTH(s);//右節(jié)點編號
    

58. 
    

59.         if(s<=n/2) // n/2為最小節(jié)點編號的父親節(jié)點 如果s大于這個值說明這個節(jié)點不會有任何子節(jié)點不需要進行調(diào)整 ??！,這是整個算法的核心中的核心。搞了我老半天
    

60.         {
    

61.                 if (l<=n && k[l] > k[s])
    

62.                 {
    

63.                         largest = l;
    

64.                 }
    

65.                 else
    

66.                 {
    

67.                         largest = s;
    

68.                 }
    

69. 
    

70.                 if(r<=n && k[r] > k[largest])
    

71.                 {
    

72.                         largest = r;
    

73.                 }
    

74. 
    

75.                 if(largest != s)
    

76.                 {
    

77.                         swap(k,largest,s);
    

78.                         bigheapad(k,largest,n); //對數(shù)據(jù)調(diào)整后可能的子節(jié)點樹繼續(xù)進行調(diào)整直到達到遞歸退出條件
    

79.                 }
    

80.         }
    

81. return 0;

82. }
    

83. 
    

84. 
    

85. int bigheapbulid(int k[],int n)
    

86. {
    

87.         int i;
    

88.         for(i=n/2;i>0;i--)//采用自底向上的方法構(gòu)建 算法導論P156 EXP 1:i= n/2 p:4 l:8 r:9  2: i = p:3 l:6 r:7  n/2剛好是最后一個節(jié)點的父親節(jié)點所以自下而上
    

89.         {
    

90.                 bigheapad(k,i,n);
    

91.         }
    

92. return 0;

93. 
    

94. }
    

95. 
    

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

97. {
    

98.         int i;
    

99.         for(i=n;i>1;i--)
    

100.         {
     

101.                 swap(k,1,i);
     

102.                 bigheapad(k,1,i-1);
     

103.         }
     

104. return 0;

105. }
     

106. 
     

107. int biglimitn(int k[],int n,int limitn)//limit 也是我關心的 這里明顯可以看到他的優(yōu)勢實際它不需要對整個數(shù)組排序，你要多少我排多少給你就好，也是最大元素放到最后，然后逐層下降的方法進行調(diào)整的原理

108. {
     

109.         int i;
     

110.         for(i=n;i>n-limitn;i--)
     

111.         {
     

112.                 swap(k,1,i);
     

113.                 bigheapad(k,1,i-1);
     

114.         }
     

115. return 0;

116. }
     

117. 
     

118. int smallheapad(int k[],int s,int n) //s=4,n=9
     

119. {
     

120. 
     

121.         int l; //s 左節(jié)點編號
     

122.         int r; //s 右節(jié)點編號
     

123.         int smallest;
     

124. 
     

125.         l=LEFT(s); //左節(jié)點編號
     

126.         r=RIGTH(s);//右節(jié)點編號
     

127. 
     

128.         if(s<=n/2) // n/2為最小節(jié)點編號的父親節(jié)點 如果s大于這個值說明這個節(jié)點不會有任何子節(jié)點不需要進行調(diào)整 ！！
     

129.         {
     

130. 
     

131.                 if (l<=n && k[l] < k[s])
     

132.                 {
     

133. 
     

134.                         smallest = l;
     

135.                 }
     

136.                 else
     

137.                 {
     

138. 
     

139.                         smallest = s;
     

140.                 }
     

141. 
     

142.                 if(r<=n && k[r] < k[smallest])
     

143.                 {
     

144. 
     

145.                         smallest = r;
     

146.                 }
     

147. 
     

148.                 if(smallest != s)
     

149.                 {
     

150. 
     

151.                         swap(k,smallest,s);
     

152.                         smallheapad(k,smallest,n); //對數(shù)據(jù)調(diào)整后可能的子節(jié)點樹繼續(xù)進行調(diào)整直到達到遞歸退出條件
     

153.                 }
     

154.         } 
     

155. return 0;

156. }
     

157. 
     

158. 
     

159. int smallheapbulid(int k[],int n)
     

160. {
     

161. 
     

162.         int i;
     

163.         for(i=n/2;i>0;i--)
     

164.         {
     

165. 
     

166.                 smallheapad(k,i,n);
     

167.         }
     

168. return 0;

169. }
     

170. 
     

171. int smallheapsort(int k[],int n)
     

172. {
     

173. 
     

174.         int i;
     

175.         for(i=n;i>1;i--)
     

176.         {
     

177. 
     

178.                 swap(k,1,i);
     

179.                 smallheapad(k,1,i-1);
     

180.         }
     

181. return 0;
     

182. }
     

183. 
     

184. int smalllimitn(int k[],int n,int limitn)
     

185. {
     

186. 
     

187.         int i;
     

188.         for(i=n;i>n-limitn;i--)
     

189.         {
     

190. 
     

191.                 swap(k,1,i);
     

192.                 smallheapad(k,1,i-1);
     

193.         }
     

194. return 0;

195. }
     

196. 
     

197. 
     

198. int main()
     

199. {
     

200. 
     

201.         int i,a[11]={0,999,3,2,9,34,5,102,90,2222,1}; //測試數(shù)據(jù) a[0]不使用
     

202.         int b[11]={0,999,3,2,9,999,888888,102,90,2222,111};//測試數(shù)據(jù) b[0]不使用
     

203.         bigheapbulid(a,10);
     

204.         biglimitn(a,10,3);
     

205. 
     

206.         printf("大頂堆:\n");
     

207.         printf("order by desc a array limit 3 result:");
     

208.         for(i=10;i>10-3;i--)
     

209.         {
     

210.                 printf("%d ",a[i]);
     

211.         }
     

212.         printf("\n");
     

213.         bigheapbulid(b,10);
     

214.         printf("max values b array reulst:");
     

215.         printf("%d \n",b[1]);
     

216. 
     

217.         smallheapbulid(a,10);
     

218.         smalllimitn(a,10,3);
     

219.         printf("小頂堆:\n");
     

220.         printf("order by asc a array limit 3 result:");
     

221.         for(i=10;i>10-3;i--)
     

222.         {
     

223.                 printf("%d ",a[i]);
     

224.         }
     

225.         printf("\n");
     

226.         smallheapbulid(b,10);
     

227.         printf("min values b array reulst:");
     

228.         printf("%d \n",b[1]);
     

229. return 0;

230. }

以上是“MYSQL如何實現(xiàn)ORDER BY和LIMIT”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業(yè)資訊頻道！