More  

收藏本站

電腦請使用 Ctrl + D 加入最愛
手機請使用 收藏
關閉

小編的世界 優質文選 資料

mysql 002|order by的排序算法竟然是這樣的!


字體大小:
2020年12月10日 -
:        
 

酷扯兒

《酷扯兒》官方帳號

前言

平常寫業務的時候,我們經常需要對一些業務數據進行排序,例如點贊排名,瀏覽量排名等等。雖然這個字段很常用了,可能出於對服務器是 MySQL 的原因,使我們會膽怯或不想去了解它背後的執行流程,純黑箱子使用。但是如果不了解其內部機制,又何談以優化使用?今天決定在這篇文章介紹一些

Order By

相關知識。

拋出本文問題

order by 的排序流程是什麼?

order by 的排序算法是什麼?

order by 的優化點在於什麼?

解答疑問

排序流程

關於排序過程,MySQL 會通過判斷

sort_buffer_size

來執行不同的排序流程。

其實是

MySQL

的一個系統參數,它可以控制

會在排序的時候分配的緩沖區大小,這個參數可以作用於

Global

或者

Session

級別。它的特點是允許動態變化,而且不針對特定的存儲引擎。每每當有新的線程的時候,都會分配相應參數值的排序緩沖區大小。

了解完了這個參數值,我們可以介紹兩種排序流程:

一次排序

二次排序

一次排序不是一個專業術語,按照我的理解來解讀,

排序流程需要一次讀取磁盤

可能你會感覺困惑,那麼來了解一下整個流程:

會初始化排序緩沖區,然後讀取目標

SQL

所有涉及到的字段(選擇列,篩選列,排序列) 。

如果篩選列是索引,則會根據索引進行查找數據;如果非索引就全局掃描

根據選擇列將所需的數據加進排序緩沖區

現在去尋找第二條數據,所以它會重複去走 2,3 步。直到所有符合篩選列的數據都被加載進緩沖區完。

目前進入了排序階段,根據排序列的要求,把排序緩沖區的數據加載進內存進行排序

返回客戶端

看完了一次排序,或許你對二次排序也有一定的明白了。是的,

二次排序流程需要對磁盤進行兩次讀取

那我們還是對這個流程梳理:

會初始化排序緩沖區,僅僅把

的目標表的主鍵ID以及排序列加載進去。

根據篩選列進行數據的篩選。如果篩選列是索引,則會根據索引進行查找數據;如果非索引就全局掃描

假設查找到了第一條數據,然後將這條數據的主鍵ID和排序列加載進內存。

現在去尋找第二條數據,所以它會重複去走 2,3 步,直到獲取了所有符合篩選列的數據。

目前進入了排序階段,根據排序列的要求,對排序緩沖區的數據進行排序並結果

拿到了排序後的結果,根據每一條數據的主鍵ID回到原表掃描,獲取到選擇列的信息。

返回給客戶端

比對

排序算法

剛剛在排序流程中我們可以知道,實際進行排序的操作是放在內存的。其實上面的流程的都是在內存進行排序。但是實際應用場景上,有可能是一次性需要排序的數據集超出了內存範圍;或者選擇列太多,,導致即使是少數據量也會內存爆滿。所以當

面對大數據量的情況下,會使用臨時文件進行輔助存儲已排序數據。

內存

內存當中主要使用的是比較常見的快速排序,基本思想是:

通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列

內存+物理文件

由於內存不足的問題,

會對數據集進行多次讀取,多次排序處理。假設目前內存已經滿了,

會對內存的數據集使用快速排序,然後將結果保存到一個臨時文件當中。然後

會將內存清掉,重新根據篩選列再次讀取數據。當內存再次爆滿,然後會繼續在內存進行排序,然後保存到臨時文件。當數據完全准備好了,那麼

會使用多路歸並排序對文件進行排序,原理跟

歸並排序中的二路歸並

比較類型,建議去了解一下。

優化點

提高

。該值應該足夠大,可以讓大數據集也能加載進去,這樣可以讓

減少在排序的過程中對排序數據進行切分,避免讀寫磁盤和合並文件。

根據系統情況調節

max_length_for_sort_data

,因為這個參數的大小會影響

選擇使用

還是

。當值比較小的時候,會使用

,相反使用

。(如果數值設的太高,會導致磁盤活動太高,CPU 活動太低)。

read_rnd_buffer_size

可以提高讀取的行數,減少的讀的時間。

盡量在

上使用索引滿足

order by

的,避免執行文件排序操作時涉及的額外排序。而且有些通過索引掃描比通過表掃描更加廉價。