詳解MySQL中Order By排序和filesort排序的原理及實現

Posted on by

1.Order By原理

MySQL的Order By操作用於排序，並且會有多種不同的排序算法，他們的性能都是不一樣的。

假設有一個表，建表的sql如下：

CREATE TABLE `obtest` (
`id` BIGINT NOT NULL AUTO_INCREMENT,
`a` VARCHAR ( 100 ) NOT NULL,
`b` VARCHAR ( 100 ) NOT NULL,
`c` VARCHAR ( 100 ) NOT NULL,
PRIMARY KEY ( `id` ),
UNIQUE KEY `a` ( `a` ),
KEY `b` ( `b` ) 
) ENGINE = INNODB DEFAULT CHARSET = utf8mb4;

存儲過程插入10000條數據：

CREATE PROCEDURE `obtest`( )
BEGIN
DECLARE
	i INT DEFAULT 0;
DECLARE
	j VARCHAR ( 100 ) DEFAULT 'a';
DECLARE
	k VARCHAR ( 100 ) DEFAULT 'b';
DECLARE
	l VARCHAR ( 100 ) DEFAULT 'c';

SET i = 0;
START TRANSACTION;
WHILE
	i < 10000 DO

IF
	MOD ( i, 10 ) = 0 THEN
	
	SET k = CONCAT( 'b', i );

END IF;
IF
	MOD ( i, 15 ) = 0 THEN
	
	SET l = CONCAT( 'c', i );

END IF;
INSERT INTO obtest ( a, b, c )
VALUES
	( CONCAT( j, i ), k, l );

SET i = i + 1;

END WHILE;
COMMIT;

END

如果不能使用索引消除排序，那麼EXPLAIN展示的執行計劃的Extra這個字段中的“Using filesort”表示的就是需要額外的排序操作，MySQL會給每個線程分配一塊內存用於排序，稱為sort_buffer。

這裡的filesort有可能是內存排序，也有可能是文件排序，但它們都統稱filessort。在內存中對數據進行排序，這個我相信大傢都是不陌生的，如果sort_buffer_size超過瞭需要排序的數據量的大小，表示排序可以直接在內存中完成。

那麼文件排序又是什麼意思呢？實際上如果需要排序的數據量太大，內存放不下，則不得不利用磁盤臨時文件輔助排序。文件排序就是所謂的外部排序。所以說，MySQL的Order By的實現，就有可能利用到外部排序這種排序算法！

外部文件排序一般使用歸並排序算法。MySQL將需要排序的數據分成N份，每一份單獨排序後存在這些臨時文件中，然後把這N個有序文件再一步步的合並成一個有序的大文件。

怎麼看一個排序是否使用到瞭臨時文件呢？我們執行下面的SQL：

/* 打開optimizer_trace，隻對本線程有效 */
SET optimizer_trace='enabled=on'; 

/* @a保存Innodb_rows_read的初始值 */
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 執行語句 */
 select * from obtest ORDER BY a LIMIT 1000;

/* 查看 OPTIMIZER_TRACE 輸出 */
select * FROM `information_schema`.`OPTIMIZER_TRACE`;

/* @b保存Innodb_rows_read的當前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 計算Innodb_rows_read差值 */
select @b-@a;

通過查看 OPTIMIZER_TRACE 的結果來確認的，你可以從 number_of_tmp_files中看到是否使用瞭臨時文件。

number_of_tmp_files表示排序過程中使用的臨時輔助文件數。可以這麼簡單理解，MySQL將需要排序的數據分成12份，每一份單獨排序後存在這些臨時文件中。然後把這12個有序文件再合並成一個有序的大文件。

examined_rows表示參與排序的行數，一共5000行，即所有數據都參與瞭排序。

sort_mode 裡面的packed_additional_fields的意思是，排序過程對字符串做瞭“緊湊”處理。即使a、b、c字段的定義是varchar(50)，在排序過程中還是要按照實際長度來分配空間的。

同時，最後一個查詢語句select @b-@a 的返回結果是5000，表示整個執行過程隻掃描瞭5000行。實際可能顯示為5001，這是InnoDB的幹擾，為瞭避免對結論造成幹擾，可以把internal_tmp_disk_storage_engine參數設置成MyISAM。

SET GLOBAL  internal_tmp_disk_storage_engine=MyISAM;

這是因為查詢OPTIMIZER_TRACE這個表時，需要用到臨時表，而internal_tmp_disk_storage_engine的默認值是InnoDB。如果使用的是InnoDB引擎的話，把數據從臨時表取出來的時候，會讓Innodb_rows_read的值加1。臨時表默認大小為16M。

2.filesort排序算法

實際上文件輔助排序同樣有兩種算法，一種是全字段排序，另一種是rowid排序，也稱為"原始排序模式（MySQL 4.1之前的）"。

全字段排序是將要查詢的一行的所有字段都放入sort_buffer中，並按照指定的字段進行過排序，排序完畢之後，直接取出排序好的數據返回給客戶端，因為排序後的數據包括瞭需要返回的所有數據，這種方法稱為全字段排序。

全字段排序步驟可以歸納為：

  • 讀取<固定長度的排序列, 需要返回的列> 組成元組，放入sort buffer。
  • 如果sort buffer滿， 根據排序列執行一次quicksort, 將其寫入臨時文件。
  • 重復1 2 步驟直到文件結束。
  • 對臨時文件執行歸並排序。
  • 從排好序的臨時文件中讀取需要返回的列返回給客戶端即可。

上面的查詢語句就是使用的全字段排序，這種排序方法隻對原表的數據讀瞭一遍，剩下的操作都是在sort_buffer和臨時文件中執行的。但這個算法有一個問題，就是如果查詢要返回的字段很多的話，那麼sort_buffer裡面要放的字段數太多，這樣內存裡能夠同時放下的行數很少，要分成很多個臨時文件，排序的性能會很差。

max_length_for_sort_data，是MySQL中專門控制用於排序的行數據的長度的一個參數，默認值是1024字節。它的意思是，如果單行的長度超過這個值，MySQL就認為單行太大，要換一個另一個rowid算法。

我們知道，上面的sql中兩個字段b和d加起來長度是不會超過1024字節的，因此就會使用全字段排序。如果我們將查詢返回字段改為：*，即全部返回，這些字段的總長度肯定大於1024瞭，此時MySQL將會使用rowid排序算法。

rowid排序算法的大概流程為：

  • 讀取 固定長度的排序列 + rowid組成元組，放入sort buffer。
  • 如果sort buffer滿， 根據排序列執行一次quicksort, 將其寫入臨時文件。
  • 重復1 2 步驟直到文件結束。
  • 對臨時文件執行歸並排序。
  • 從排好序的臨時文件中讀取需要返回的列的rowid。
  • 然後再根據這些id進行回表操作，查詢出需要的字段值直接返回給客戶端。

對比全字段排序流程會發現，rowid排序多訪問瞭一次表的主鍵索引，就是步驟6，返回的結果也有變化：

可以看到examined_rows的值還是5000，表示用於排序的數據是5000行。但是select @b-@a這個語句的值變成8000瞭。因為這時候除瞭排序過程外，在排序完成後，還要根據id去原表取值。由於語句是limit 3000，因此會多讀3000行。

sort_mode變成瞭<sort_key, rowid>，表示參與排序的隻有a和id這兩個字段，即rowid排序。

number_of_tmp_files變成3瞭，是因為這時候參與排序的行數雖然仍然是5000行，但是每一行的數據量都變小瞭，因此需要排序的總數據量就變小瞭，需要的臨時文件也相應地變少瞭。

總結：

如果MySQL認為內存足夠大，會優先選擇全字段排序，把需要的字段都放到sort_buffer中，這樣排序後就會直接從內存裡面返回查詢結果瞭，不用再回到原表去取數據，但這會導致它需要多次向臨時文件寫入內容，增加IO操作，當需要返回的列的總長度很長時尤其明顯。而如果一行的數據大小超過max_length_for_sort_data這個限制值時，才會采用rowid排序算法，這樣排序過程中一次可以排序更多行，但是需要再回到原表去取數據，即需要讀兩次表，並且第二次讀取是隨機的。

3.優化排序

這也就體現瞭MySQL的一個設計思想：如果內存夠，就要多利用內存，盡量減少磁盤訪問。

從上面也能看出來，MySQL的排序操作的成本還是很高的，MySQL之所以需要生成臨時表，並且在臨時表上做排序操作，其原因是原來的數據都是無序的。

如果能夠保證從b這個索引上取出來的行，天然就是遞增排序的話，那就可以不用再排序瞭，這是就可以用到索引。

比如我們有如下查詢：

select id,a,b from obtest ORDER BY a LIMIT 3000;

此時如果我們建立(a,b)的聯合索引，則不但可以利用索引消除排序，還能夠避免回表查詢，一舉兩得！如果沒有采用額外的排序手段，則沒有filesort_summary的一系列數據。

另外，如果需要取出的排序數據較少，則可能使用additional_fields排序，這種方式同樣不需要回表查詢，但是相比於packed_additional_fields，沒有進行緊密打包操作。比如：

select * from obtest ORDER BY a LIMIT 100;

如果number_of_tmp_files值為0，則可能是用到瞭優先隊列排序算法，如果filesort_priority_queue_optimization部分的chosen=true，就表示使用瞭優先隊列排序算法，這個過程不需要臨時文件，因此對應的number_of_tmp_files是0。

因為limit所要取的數據量比較少，采用文件歸並排序的話，就需要對全部數據進行排序，內存時間復雜度為O(nlogn)，但由於有文件IO實際需要更多時間。而如果使用優先隊列排序，實際上就是堆排序，這樣的排序是一種偏序排序，能夠計算出所需的最大或者最小的幾個值，但是其他的數據的順序是不確定的，實際上如果使用堆排序對所有數據排序，那麼時間復雜度也是O(nlogn)，但這裡隻需要在大量數據中取出少量有序數據，並且是內存中操作的，這樣耗費的時間遠小於文件歸並排序。

如果limit取出的數據量小於sort_buffer_size，則采用優先隊列排序。

到此這篇關於詳解MySQL中Order By排序和filesort排序的原理及實現的文章就介紹到這瞭,更多相關MySQL Order By排序 filesort排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：