1.Order By原理

MySQL的Order By操作用于排序，并且會(huì)有多種不同的排序算法，他們的性能都是不一樣的。

假設(shè)有一個(gè)表，建表的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;

存儲(chǔ)過(guò)程插入10000條數(shù)據(jù)：

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展示的執(zhí)行計(jì)劃的Extra這個(gè)字段中的“Using filesort”表示的就是需要額外的排序操作，MySQL會(huì)給每個(gè)線程分配一塊內(nèi)存用于排序，稱為sort_buffer。

這里的filesort有可能是內(nèi)存排序，也有可能是文件排序，但它們都統(tǒng)稱filessort。在內(nèi)存中對(duì)數(shù)據(jù)進(jìn)行排序，這個(gè)我相信大家都是不陌生的，如果sort_buffer_size超過(guò)了需要排序的數(shù)據(jù)量的大小，表示排序可以直接在內(nèi)存中完成。

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

外部文件排序一般使用歸并排序算法。MySQL將需要排序的數(shù)據(jù)分成N份，每一份單獨(dú)排序后存在這些臨時(shí)文件中，然后把這N個(gè)有序文件再一步步的合并成一個(gè)有序的大文件。

怎么看一個(gè)排序是否使用到了臨時(shí)文件呢？我們執(zhí)行下面的SQL：

/* 打開optimizer_trace，只對(duì)本線程有效 */
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';

/* 執(zhí)行語(yǔ)句 */
 select * from obtest ORDER BY a LIMIT 1000;

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

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

/* 計(jì)算Innodb_rows_read差值 */
select @b-@a;

通過(guò)查看 OPTIMIZER_TRACE 的結(jié)果來(lái)確認(rèn)的，你可以從 number_of_tmp_files中看到是否使用了臨時(shí)文件。

number_of_tmp_files表示排序過(guò)程中使用的臨時(shí)輔助文件數(shù)?？梢赃@么簡(jiǎn)單理解，MySQL將需要排序的數(shù)據(jù)分成12份，每一份單獨(dú)排序后存在這些臨時(shí)文件中。然后把這12個(gè)有序文件再合并成一個(gè)有序的大文件。

examined_rows表示參與排序的行數(shù)，一共5000行，即所有數(shù)據(jù)都參與了排序。

sort_mode 里面的packed_additional_fields的意思是，排序過(guò)程對(duì)字符串做了“緊湊”處理。即使a、b、c字段的定義是varchar(50)，在排序過(guò)程中還是要按照實(shí)際長(zhǎng)度來(lái)分配空間的。

同時(shí)，最后一個(gè)查詢語(yǔ)句select @b-@a 的返回結(jié)果是5000，表示整個(gè)執(zhí)行過(guò)程只掃描了5000行。實(shí)際可能顯示為5001，這是InnoDB的干擾，為了避免對(duì)結(jié)論造成干擾，可以把internal_tmp_disk_storage_engine參數(shù)設(shè)置成MyISAM。

SET GLOBAL  internal_tmp_disk_storage_engine=MyISAM;

這是因?yàn)椴樵?code>OPTIMIZER_TRACE這個(gè)表時(shí)，需要用到臨時(shí)表，而internal_tmp_disk_storage_engine的默認(rèn)值是InnoDB。如果使用的是InnoDB引擎的話，把數(shù)據(jù)從臨時(shí)表取出來(lái)的時(shí)候，會(huì)讓Innodb_rows_read的值加1。臨時(shí)表默認(rèn)大小為16M。

2.filesort排序算法

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

全字段排序是將要查詢的一行的所有字段都放入sort_buffer中，并按照指定的字段進(jìn)行過(guò)排序，排序完畢之后，直接取出排序好的數(shù)據(jù)返回給客戶端，因?yàn)榕判蚝蟮臄?shù)據(jù)包括了需要返回的所有數(shù)據(jù)，這種方法稱為全字段排序。

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

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

上面的查詢語(yǔ)句就是使用的全字段排序，這種排序方法只對(duì)原表的數(shù)據(jù)讀了一遍，剩下的操作都是在sort_buffer和臨時(shí)文件中執(zhí)行的。但這個(gè)算法有一個(gè)問(wèn)題，就是如果查詢要返回的字段很多的話，那么sort_buffer里面要放的字段數(shù)太多，這樣內(nèi)存里能夠同時(shí)放下的行數(shù)很少，要分成很多個(gè)臨時(shí)文件，排序的性能會(huì)很差。

max_length_for_sort_data，是MySQL中專門控制用于排序的行數(shù)據(jù)的長(zhǎng)度的一個(gè)參數(shù)，默認(rèn)值是1024字節(jié)。它的意思是，如果單行的長(zhǎng)度超過(guò)這個(gè)值，MySQL就認(rèn)為單行太大，要換一個(gè)另一個(gè)rowid算法。

我們知道，上面的sql中兩個(gè)字段b和d加起來(lái)長(zhǎng)度是不會(huì)超過(guò)1024字節(jié)的，因此就會(huì)使用全字段排序。如果我們將查詢返回字段改為：*，即全部返回，這些字段的總長(zhǎng)度肯定大于1024了，此時(shí)MySQL將會(huì)使用rowid排序算法。

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

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

對(duì)比全字段排序流程會(huì)發(fā)現(xiàn)，rowid排序多訪問(wèn)了一次表的主鍵索引，就是步驟6，返回的結(jié)果也有變化：

可以看到examined_rows的值還是5000，表示用于排序的數(shù)據(jù)是5000行。但是select @b-@a這個(gè)語(yǔ)句的值變成8000了。因?yàn)檫@時(shí)候除了排序過(guò)程外，在排序完成后，還要根據(jù)id去原表取值。由于語(yǔ)句是limit 3000，因此會(huì)多讀3000行。

sort_mode變成了<sort_key, rowid>，表示參與排序的只有a和id這兩個(gè)字段，即rowid排序。

number_of_tmp_files變成3了，是因?yàn)檫@時(shí)候參與排序的行數(shù)雖然仍然是5000行，但是每一行的數(shù)據(jù)量都變小了，因此需要排序的總數(shù)據(jù)量就變小了，需要的臨時(shí)文件也相應(yīng)地變少了。

總結(jié)：

如果MySQL認(rèn)為內(nèi)存足夠大，會(huì)優(yōu)先選擇全字段排序，把需要的字段都放到sort_buffer中，這樣排序后就會(huì)直接從內(nèi)存里面返回查詢結(jié)果了，不用再回到原表去取數(shù)據(jù)，但這會(huì)導(dǎo)致它需要多次向臨時(shí)文件寫入內(nèi)容，增加IO操作，當(dāng)需要返回的列的總長(zhǎng)度很長(zhǎng)時(shí)尤其明顯。而如果一行的數(shù)據(jù)大小超過(guò)max_length_for_sort_data這個(gè)限制值時(shí)，才會(huì)采用rowid排序算法，這樣排序過(guò)程中一次可以排序更多行，但是需要再回到原表去取數(shù)據(jù)，即需要讀兩次表，并且第二次讀取是隨機(jī)的。

3.優(yōu)化排序

這也就體現(xiàn)了MySQL的一個(gè)設(shè)計(jì)思想：如果內(nèi)存夠，就要多利用內(nèi)存，盡量減少磁盤訪問(wèn)。

從上面也能看出來(lái)，MySQL的排序操作的成本還是很高的，MySQL之所以需要生成臨時(shí)表，并且在臨時(shí)表上做排序操作，其原因是原來(lái)的數(shù)據(jù)都是無(wú)序的。

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

比如我們有如下查詢：

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

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

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

select * from obtest ORDER BY a LIMIT 100;

如果number_of_tmp_files值為0，則可能是用到了優(yōu)先隊(duì)列排序算法，如果filesort_priority_queue_optimization部分的chosen=true，就表示使用了優(yōu)先隊(duì)列排序算法，這個(gè)過(guò)程不需要臨時(shí)文件，因此對(duì)應(yīng)的number_of_tmp_files是0。

因?yàn)閘imit所要取的數(shù)據(jù)量比較少，采用文件歸并排序的話，就需要對(duì)全部數(shù)據(jù)進(jìn)行排序，內(nèi)存時(shí)間復(fù)雜度為O(nlogn)，但由于有文件IO實(shí)際需要更多時(shí)間。而如果使用優(yōu)先隊(duì)列排序，實(shí)際上就是堆排序，這樣的排序是一種偏序排序，能夠計(jì)算出所需的最大或者最小的幾個(gè)值，但是其他的數(shù)據(jù)的順序是不確定的，實(shí)際上如果使用堆排序?qū)λ袛?shù)據(jù)排序，那么時(shí)間復(fù)雜度也是O(nlogn)，但這里只需要在大量數(shù)據(jù)中取出少量有序數(shù)據(jù)，并且是內(nèi)存中操作的，這樣耗費(fèi)的時(shí)間遠(yuǎn)小于文件歸并排序。

如果limit取出的數(shù)據(jù)量小于sort_buffer_size，則采用優(yōu)先隊(duì)列排序。

到此這篇關(guān)于詳解MySQL中Order By排序和filesort排序的原理及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)MySQL Order By排序 filesort排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論