17 | 如何正确地显示随机消息?
我在上一篇文章,為你講解完order by語句的幾種執(zhí)行模式后,就想到了之前一個做英語學(xué)習(xí)App的朋友碰到過的一個性能問題。今天這篇文章,我就從這個性能問題說起,和你說說MySQL中的另外一種排序需求,希望能夠加深你對MySQL排序邏輯的理解。
這個英語學(xué)習(xí)App首頁有一個隨機(jī)顯示單詞的功能,也就是根據(jù)每個用戶的級別有一個單詞表,然后這個用戶每次訪問首頁的時候,都會隨機(jī)滾動顯示三個單詞。他們發(fā)現(xiàn)隨著單詞表變大,選單詞這個邏輯變得越來越慢,甚至影響到了首頁的打開速度。
現(xiàn)在,如果讓你來設(shè)計這個SQL語句,你會怎么寫呢?
為了便于理解,我對這個例子進(jìn)行了簡化:去掉每個級別的用戶都有一個對應(yīng)的單詞表這個邏輯,直接就是從一個單詞表中隨機(jī)選出三個單詞。這個表的建表語句和初始數(shù)據(jù)的命令如下:
mysql> CREATE TABLE `words` ( `id` int(11) NOT NULL AUTO_INCREMENT, `word` varchar(64) DEFAULT NULL, PRIMARY KEY (`id`) ) ENGINE=InnoDB;delimiter ;; create procedure idata() begin declare i int; set i=0; while i為了便于量化說明,我在這個表里面插入了10000行記錄。接下來,我們就一起看看要隨機(jī)選擇3個單詞,有什么方法實現(xiàn),存在什么問題以及如何改進(jìn)。
內(nèi)存臨時表
首先,你會想到用order by rand()來實現(xiàn)這個邏輯。
mysql> select word from words order by rand() limit 3;這個語句的意思很直白,隨機(jī)排序取前3個。雖然這個SQL語句寫法很簡單,但執(zhí)行流程卻有點復(fù)雜的。
我們先用explain命令來看看這個語句的執(zhí)行情況。
圖1 使用explain命令查看語句的執(zhí)行情況Extra字段顯示Using temporary,表示的是需要使用臨時表;Using filesort,表示的是需要執(zhí)行排序操作。
因此這個Extra的意思就是,需要臨時表,并且需要在臨時表上排序。
這里,你可以先回顧一下上一篇文章中全字段排序和rowid排序的內(nèi)容。我把上一篇文章的兩個流程圖貼過來,方便你復(fù)習(xí)。
圖2 全字段排序 圖3 rowid排序然后,我再問你一個問題,你覺得對于臨時內(nèi)存表的排序來說,它會選擇哪一種算法呢?回顧一下上一篇文章的一個結(jié)論:對于InnoDB表來說,執(zhí)行全字段排序會減少磁盤訪問,因此會被優(yōu)先選擇。
我強(qiáng)調(diào)了“InnoDB表”,你肯定想到了,對于內(nèi)存表,回表過程只是簡單地根據(jù)數(shù)據(jù)行的位置,直接訪問內(nèi)存得到數(shù)據(jù),根本不會導(dǎo)致多訪問磁盤。優(yōu)化器沒有了這一層顧慮,那么它會優(yōu)先考慮的,就是用于排序的行越少越好了,所以,MySQL這時就會選擇rowid排序。
理解了這個算法選擇的邏輯,我們再來看看語句的執(zhí)行流程。同時,通過今天的這個例子,我們來嘗試分析一下語句的掃描行數(shù)。
這條語句的執(zhí)行流程是這樣的:
創(chuàng)建一個臨時表。這個臨時表使用的是memory引擎,表里有兩個字段,第一個字段是double類型,為了后面描述方便,記為字段R,第二個字段是varchar(64)類型,記為字段W。并且,這個表沒有建索引。
從words表中,按主鍵順序取出所有的word值。對于每一個word值,調(diào)用rand()函數(shù)生成一個大于0小于1的隨機(jī)小數(shù),并把這個隨機(jī)小數(shù)和word分別存入臨時表的R和W字段中,到此,掃描行數(shù)是10000。
現(xiàn)在臨時表有10000行數(shù)據(jù)了,接下來你要在這個沒有索引的內(nèi)存臨時表上,按照字段R排序。
初始化 sort_buffer。sort_buffer中有兩個字段,一個是double類型,另一個是整型。
從內(nèi)存臨時表中一行一行地取出R值和位置信息(我后面會和你解釋這里為什么是“位置信息”),分別存入sort_buffer中的兩個字段里。這個過程要對內(nèi)存臨時表做全表掃描,此時掃描行數(shù)增加10000,變成了20000。
在sort_buffer中根據(jù)R的值進(jìn)行排序。注意,這個過程沒有涉及到表操作,所以不會增加掃描行數(shù)。
排序完成后,取出前三個結(jié)果的位置信息,依次到內(nèi)存臨時表中取出word值,返回給客戶端。這個過程中,訪問了表的三行數(shù)據(jù),總掃描行數(shù)變成了20003。
接下來,我們通過慢查詢?nèi)罩?#xff08;slow log)來驗證一下我們分析得到的掃描行數(shù)是否正確。
其中,Rows_examined:20003就表示這個語句執(zhí)行過程中掃描了20003行,也就驗證了我們分析得出的結(jié)論。
這里插一句題外話,在平時學(xué)習(xí)概念的過程中,你可以經(jīng)常這樣做,先通過原理分析算出掃描行數(shù),然后再通過查看慢查詢?nèi)罩?#xff0c;來驗證自己的結(jié)論。我自己就是經(jīng)常這么做,這個過程很有趣,分析對了開心,分析錯了但是弄清楚了也很開心。
現(xiàn)在,我來把完整的排序執(zhí)行流程圖畫出來。
圖4 隨機(jī)排序完整流程圖1圖中的pos就是位置信息,你可能會覺得奇怪,這里的“位置信息”是個什么概念?在上一篇文章中,我們對InnoDB表排序的時候,明明用的還是ID字段。
這時候,我們就要回到一個基本概念:MySQL的表是用什么方法來定位“一行數(shù)據(jù)”的。
在前面第4和第5篇介紹索引的文章中,有幾位同學(xué)問到,如果把一個InnoDB表的主鍵刪掉,是不是就沒有主鍵,就沒辦法回表了?
其實不是的。如果你創(chuàng)建的表沒有主鍵,或者把一個表的主鍵刪掉了,那么InnoDB會自己生成一個長度為6字節(jié)的rowid來作為主鍵。
這也就是排序模式里面,rowid名字的來歷。實際上它表示的是:每個引擎用來唯一標(biāo)識數(shù)據(jù)行的信息。
- 對于有主鍵的InnoDB表來說,這個rowid就是主鍵ID;
- 對于沒有主鍵的InnoDB表來說,這個rowid就是由系統(tǒng)生成的;
- MEMORY引擎不是索引組織表。在這個例子里面,你可以認(rèn)為它就是一個數(shù)組。因此,這個rowid其實就是數(shù)組的下標(biāo)。
到這里,我來稍微小結(jié)一下:order by rand()使用了內(nèi)存臨時表,內(nèi)存臨時表排序的時候使用了rowid排序方法。
磁盤臨時表
那么,是不是所有的臨時表都是內(nèi)存表呢?
其實不是的。tmp_table_size這個配置限制了內(nèi)存臨時表的大小,默認(rèn)值是16M。如果臨時表大小超過了tmp_table_size,那么內(nèi)存臨時表就會轉(zhuǎn)成磁盤臨時表。
磁盤臨時表使用的引擎默認(rèn)是InnoDB,是由參數(shù)internal_tmp_disk_storage_engine控制的。
當(dāng)使用磁盤臨時表的時候,對應(yīng)的就是一個沒有顯式索引的InnoDB表的排序過程。
為了復(fù)現(xiàn)這個過程,我把tmp_table_size設(shè)置成1024,把sort_buffer_size設(shè)置成 32768, 把 max_length_for_sort_data 設(shè)置成16。
set tmp_table_size=1024; set sort_buffer_size=32768; set max_length_for_sort_data=16; /* 打開 optimizer_trace,只對本線程有效 */ SET optimizer_trace='enabled=on'; /* 執(zhí)行語句 */ select word from words order by rand() limit 3; /* 查看 OPTIMIZER_TRACE 輸出 */ SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G 圖5 OPTIMIZER_TRACE部分結(jié)果然后,我們來看一下這次OPTIMIZER_TRACE的結(jié)果。
因為將max_length_for_sort_data設(shè)置成16,小于word字段的長度定義,所以我們看到sort_mode里面顯示的是rowid排序,這個是符合預(yù)期的,參與排序的是隨機(jī)值R字段和rowid字段組成的行。
這時候你可能心算了一下,發(fā)現(xiàn)不對。R字段存放的隨機(jī)值就8個字節(jié),rowid是6個字節(jié)(至于為什么是6字節(jié),就留給你課后思考吧),數(shù)據(jù)總行數(shù)是10000,這樣算出來就有140000字節(jié),超過了sort_buffer_size 定義的 32768字節(jié)了。但是,number_of_tmp_files的值居然是0,難道不需要用臨時文件嗎?
這個SQL語句的排序確實沒有用到臨時文件,采用是MySQL 5.6版本引入的一個新的排序算法,即:優(yōu)先隊列排序算法。接下來,我們就看看為什么沒有使用臨時文件的算法,也就是歸并排序算法,而是采用了優(yōu)先隊列排序算法。
其實,我們現(xiàn)在的SQL語句,只需要取R值最小的3個rowid。但是,如果使用歸并排序算法的話,雖然最終也能得到前3個值,但是這個算法結(jié)束后,已經(jīng)將10000行數(shù)據(jù)都排好序了。
也就是說,后面的9997行也是有序的了。但,我們的查詢并不需要這些數(shù)據(jù)是有序的。所以,想一下就明白了,這浪費(fèi)了非常多的計算量。
而優(yōu)先隊列算法,就可以精確地只得到三個最小值,執(zhí)行流程如下:
(對數(shù)據(jù)結(jié)構(gòu)印象模糊的同學(xué),可以先設(shè)想成這是一個由三個元素組成的數(shù)組)
取下一個行(R’,rowid’),跟當(dāng)前堆里面最大的R比較,如果R’小于R,把這個(R,rowid)從堆中去掉,換成(R’,rowid’);
重復(fù)第2步,直到第10000個(R’,rowid’)完成比較。
這里我簡單畫了一個優(yōu)先隊列排序過程的示意圖。
圖6 優(yōu)先隊列排序算法示例圖6是模擬6個(R,rowid)行,通過優(yōu)先隊列排序找到最小的三個R值的行的過程。整個排序過程中,為了最快地拿到當(dāng)前堆的最大值,總是保持最大值在堆頂,因此這是一個最大堆。
圖5的OPTIMIZER_TRACE結(jié)果中,filesort_priority_queue_optimization這個部分的chosen=true,就表示使用了優(yōu)先隊列排序算法,這個過程不需要臨時文件,因此對應(yīng)的number_of_tmp_files是0。
這個流程結(jié)束后,我們構(gòu)造的堆里面,就是這個10000行里面R值最小的三行。然后,依次把它們的rowid取出來,去臨時表里面拿到word字段,這個過程就跟上一篇文章的rowid排序的過程一樣了。
我們再看一下上面一篇文章的SQL查詢語句:
select city,name,age from t where city='杭州' order by name limit 1000 ;你可能會問,這里也用到了limit,為什么沒用優(yōu)先隊列排序算法呢?原因是,這條SQL語句是limit 1000,如果使用優(yōu)先隊列算法的話,需要維護(hù)的堆的大小就是1000行的(name,rowid),超過了我設(shè)置的sort_buffer_size大小,所以只能使用歸并排序算法。
總之,不論是使用哪種類型的臨時表,order by rand()這種寫法都會讓計算過程非常復(fù)雜,需要大量的掃描行數(shù),因此排序過程的資源消耗也會很大。
再回到我們文章開頭的問題,怎么正確地隨機(jī)排序呢?
隨機(jī)排序方法
我們先把問題簡化一下,如果只隨機(jī)選擇1個word值,可以怎么做呢?思路上是這樣的:
取得這個表的主鍵id的最大值M和最小值N;
用隨機(jī)函數(shù)生成一個最大值到最小值之間的數(shù) X = (M-N)*rand() + N;
取不小于X的第一個ID的行。
我們把這個算法,暫時稱作隨機(jī)算法1。這里,我直接給你貼一下執(zhí)行語句的序列:
mysql> select max(id),min(id) into @M,@N from t ; set @X= floor((@M-@N+1)*rand() + @N); select * from t where id >= @X limit 1;這個方法效率很高,因為取max(id)和min(id)都是不需要掃描索引的,而第三步的select也可以用索引快速定位,可以認(rèn)為就只掃描了3行。但實際上,這個算法本身并不嚴(yán)格滿足題目的隨機(jī)要求,因為ID中間可能有空洞,因此選擇不同行的概率不一樣,不是真正的隨機(jī)。
比如你有4個id,分別是1、2、4、5,如果按照上面的方法,那么取到 id=4的這一行的概率是取得其他行概率的兩倍。
如果這四行的id分別是1、2、40000、40001呢?這個算法基本就能當(dāng)bug來看待了。
所以,為了得到嚴(yán)格隨機(jī)的結(jié)果,你可以用下面這個流程:
取得整個表的行數(shù),并記為C。
取得 Y = floor(C * rand())。 floor函數(shù)在這里的作用,就是取整數(shù)部分。
再用limit Y,1 取得一行。
我們把這個算法,稱為隨機(jī)算法2。下面這段代碼,就是上面流程的執(zhí)行語句的序列。
mysql> select count(*) into @C from t; set @Y = floor(@C * rand()); set @sql = concat("select * from t limit ", @Y, ",1"); prepare stmt from @sql; execute stmt; DEALLOCATE prepare stmt;由于limit 后面的參數(shù)不能直接跟變量,所以我在上面的代碼中使用了prepare+execute的方法。你也可以把拼接SQL語句的方法寫在應(yīng)用程序中,會更簡單些。
這個隨機(jī)算法2,解決了算法1里面明顯的概率不均勻問題。
MySQL處理limit Y,1 的做法就是按順序一個一個地讀出來,丟掉前Y個,然后把下一個記錄作為返回結(jié)果,因此這一步需要掃描Y+1行。再加上,第一步掃描的C行,總共需要掃描C+Y+1行,執(zhí)行代價比隨機(jī)算法1的代價要高。
當(dāng)然,隨機(jī)算法2跟直接order by rand()比起來,執(zhí)行代價還是小很多的。
你可能問了,如果按照這個表有10000行來計算的話,C=10000,要是隨機(jī)到比較大的Y值,那掃描行數(shù)也跟20000差不多了,接近order by rand()的掃描行數(shù),為什么說隨機(jī)算法2的代價要小很多呢?我就把這個問題留給你去課后思考吧。
現(xiàn)在,我們再看看,如果我們按照隨機(jī)算法2的思路,要隨機(jī)取3個word值呢?你可以這么做:
取得整個表的行數(shù),記為C;
根據(jù)相同的隨機(jī)方法得到Y(jié)1、Y2、Y3;
再執(zhí)行三個limit Y, 1語句得到三行數(shù)據(jù)。
我們把這個算法,稱作隨機(jī)算法3。下面這段代碼,就是上面流程的執(zhí)行語句的序列。
mysql> select count(*) into @C from t; set @Y1 = floor(@C * rand()); set @Y2 = floor(@C * rand()); set @Y3 = floor(@C * rand()); select * from t limit @Y1,1; //在應(yīng)用代碼里面取Y1、Y2、Y3值,拼出SQL后執(zhí)行 select * from t limit @Y2,1; select * from t limit @Y3,1;小結(jié)
今天這篇文章,我是借著隨機(jī)排序的需求,跟你介紹了MySQL對臨時表排序的執(zhí)行過程。
如果你直接使用order by rand(),這個語句需要Using temporary 和 Using filesort,查詢的執(zhí)行代價往往是比較大的。所以,在設(shè)計的時候你要量避開這種寫法。
今天的例子里面,我們不是僅僅在數(shù)據(jù)庫內(nèi)部解決問題,還會讓應(yīng)用代碼配合拼接SQL語句。在實際應(yīng)用的過程中,比較規(guī)范的用法就是:盡量將業(yè)務(wù)邏輯寫在業(yè)務(wù)代碼中,讓數(shù)據(jù)庫只做“讀寫數(shù)據(jù)”的事情。因此,這類方法的應(yīng)用還是比較廣泛的。
最后,我給你留下一個思考題吧。
上面的隨機(jī)算法3的總掃描行數(shù)是 C+(Y1+1)+(Y2+1)+(Y3+1),實際上它還是可以繼續(xù)優(yōu)化,來進(jìn)一步減少掃描行數(shù)的。
我的問題是,如果你是這個需求的開發(fā)人員,你會怎么做,來減少掃描行數(shù)呢?說說你的方案,并說明你的方案需要的掃描行數(shù)。
你可以把你的設(shè)計和結(jié)論寫在留言區(qū)里,我會在下一篇文章的末尾和你討論這個問題。感謝你的收聽,也歡迎你把這篇文章分享給更多的朋友一起閱讀。
上期問題時間
我在上一篇文章最后留給你的問題是,select * from t where city in (“杭州”," 蘇州 ") order by name limit 100;這個SQL語句是否需要排序?有什么方案可以避免排序?
雖然有(city,name)聯(lián)合索引,對于單個city內(nèi)部,name是遞增的。但是由于這條SQL語句不是要單獨(dú)地查一個city的值,而是同時查了"杭州"和" 蘇州 "兩個城市,因此所有滿足條件的name就不是遞增的了。也就是說,這條SQL語句需要排序。
那怎么避免排序呢?
這里,我們要用到(city,name)聯(lián)合索引的特性,把這一條語句拆成兩條語句,執(zhí)行流程如下:
執(zhí)行select * from t where city=“杭州” order by name limit 100; 這個語句是不需要排序的,客戶端用一個長度為100的內(nèi)存數(shù)組A保存結(jié)果。
執(zhí)行select * from t where city=“蘇州” order by name limit 100; 用相同的方法,假設(shè)結(jié)果被存進(jìn)了內(nèi)存數(shù)組B。
現(xiàn)在A和B是兩個有序數(shù)組,然后你可以用歸并排序的思想,得到name最小的前100值,就是我們需要的結(jié)果了。
如果把這條SQL語句里“l(fā)imit 100”改成“l(fā)imit 10000,100”的話,處理方式其實也差不多,即:要把上面的兩條語句改成寫:
select * from t where city="杭州" order by name limit 10100;和
select * from t where city="蘇州" order by name limit 10100。這時候數(shù)據(jù)量較大,可以同時起兩個連接一行行讀結(jié)果,用歸并排序算法拿到這兩個結(jié)果集里,按順序取第10001~10100的name值,就是需要的結(jié)果了。
當(dāng)然這個方案有一個明顯的損失,就是從數(shù)據(jù)庫返回給客戶端的數(shù)據(jù)量變大了。
所以,如果數(shù)據(jù)的單行比較大的話,可以考慮把這兩條SQL語句改成下面這種寫法:
select id,name from t where city="杭州" order by name limit 10100;和
select id,name from t where city="蘇州" order by name limit 10100。然后,再用歸并排序的方法取得按name順序第10001~10100的name、id的值,然后拿著這100個id到數(shù)據(jù)庫中去查出所有記錄。
上面這些方法,需要你根據(jù)性能需求和開發(fā)的復(fù)雜度做出權(quán)衡。
?
轉(zhuǎn)載于:https://www.cnblogs.com/gaosf/p/11142166.html
總結(jié)
以上是生活随笔為你收集整理的17 | 如何正确地显示随机消息?的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 还呗上征信吗?注意逾期有这些后果!
- 下一篇: 来分期有额度不能提现?怎么提现?