從一個問題說起
五年前在騰訊的時候，發(fā)現(xiàn)分頁場景下，mysql請求速度非常慢。數(shù)據(jù)量只有10w的情況下，select xx from 單機大概2，3秒。
我就問我?guī)煾笧槭裁?，他反問“索引場景，mysql中獲得第n大的數(shù)，時間復(fù)雜度是多少？”
答案的追尋
確認(rèn)場景
假設(shè)status上面有索引。select * from table where status = xx limit 10 offset 10000。
會非常慢。數(shù)據(jù)量不大的情況就有幾秒延遲。
小白作答
那時候非常有安全感，有啥事都有師父兜著，反正技術(shù)都是組里最差的，就瞎猜了個log(N)，心想找一個節(jié)點不就是log(N)。自然而然，師父讓我自己去研究。
這一階段，用了10分鐘。
繼續(xù)解答
仔細(xì)分析一下，會發(fā)現(xiàn)通過索引去找很別扭。因為你不知道前100個數(shù)在左子樹和右子數(shù)的分布情況，所以其是無法利用二叉樹的查找特性。
通過學(xué)習(xí)，了解到mysql的索引是b+樹。
看了這個圖，就豁然開朗了?？梢灾苯油ㄟ^葉子節(jié)點組成的鏈表，以o(n)的復(fù)雜度找到第100大的樹。但是即使是o(n)，也不至于慢得令人發(fā)指，是否還有原因。
這一階段，主要是通過網(wǎng)上查資料，斷斷續(xù)續(xù)用了10天。
系統(tǒng)學(xué)習(xí)
這里推薦兩本書，一本《MySQL技術(shù)內(nèi)幕 InnoDB存儲引擎》，通過他可以對InnoDB的實現(xiàn)機制，如mvcc，索引實現(xiàn)，文件存儲會有更深理解。
第二本是《高性能MySQL》，這本書從著手使用層面，但講得比較深入，而且提到了很多設(shè)計的思路。
兩本書相結(jié)合，反復(fù)領(lǐng)會，mysql就勉強能登堂入室了。
這里有兩個關(guān)鍵概念：
- 聚簇索引：包含主鍵索引和對應(yīng)的實際數(shù)據(jù)，索引的葉子節(jié)點就是數(shù)據(jù)節(jié)點
- 輔助索引：可以理解為二級節(jié)點，其葉子節(jié)點還是索引節(jié)點，包含了主鍵id。
即使前10000個會扔掉，mysql也會通過二級索引上的主鍵id,去聚簇索引上查一遍數(shù)據(jù)，這可是10000次隨機io，自然慢成哈士奇。
這里可能會提出疑問，為什么會有這種行為，這是和mysql的分層有關(guān)系，limit offset 只能作用于引擎層返回的結(jié)果集。換句話說，引擎層也很無辜，他并不知道這10000個是要扔掉的。
以下是mysql分層示意圖，可以看到，引擎層和server層，實際是分開的。
直到此時，大概明白了慢的原因。這一階段，用了一年。
觸類旁通
此時工作已經(jīng)3年了，也開始看一些源碼。在看完etcd之后，看了些tidb的源碼。無論哪種數(shù)據(jù)庫，其實一條語句的查詢，是由邏輯算子組成。
邏輯算子介紹
在寫具體的優(yōu)化規(guī)則之前，先簡單介紹查詢計劃里面的一些邏輯算子。
- DataSource 這個就是數(shù)據(jù)源，也就是表，select * from t 里面的 t。
- Selection 選擇，例如 select xxx from t where xx = 5 里面的 where 過濾條件。
- Projection 投影， select c from t 里面的取 c 列是投影操作。
- Join 連接， select xx from t1, t2 where t1.c = t2.c 就是把 t1 t2 兩個表做 Join。
選擇，投影，連接（簡稱 SPJ） 是最基本的算子。其中 Join 有內(nèi)連接，左外右外連接等多種連接方式。
select b from t1, t2 where t1.c = t2.c and t1.a > 5變成邏輯查詢計劃之后，t1 t2 對應(yīng)的 DataSource，負(fù)責(zé)將數(shù)據(jù)撈上來。
上面接個 Join 算子，將兩個表的結(jié)果按 t1.c = t2.c連接，再按 t1.a > 5 做一個 Selection 過濾，最后將 b 列投影。
下圖是未經(jīng)優(yōu)化的表示：
所以說不是mysql不想把limit, offset傳遞給引擎層，而是因為劃分了邏輯算子，所以導(dǎo)致無法直到具體算子包含了多少符合條件的數(shù)據(jù)。
怎么解決
《高性能MySQL》提到了兩種方案
方案一
根據(jù)業(yè)務(wù)實際需求，看能否替換為下一頁，上一頁的功能，特別在ios, android端，以前那種完全的分頁是不常見的。
這里是說，把limit, offset，替換為>輔助索引（即搜索條件）id的方式。該id再調(diào)用時，需要返回給前端。
方案二
正面剛。這里介紹一個概念：索引覆蓋：當(dāng)輔助索引查詢的數(shù)據(jù)，只有id和輔助索引本身，那么就不必再去查聚簇索引。
思路如下：select xxx,xxx from in (select id from table where second_index = xxx limit 10 offset 10000)這句話是說，先從條件查詢中，查找數(shù)據(jù)對應(yīng)的數(shù)據(jù)庫唯一id值，因為主鍵在輔助索引上就有，所以不用回歸到聚簇索引的磁盤去拉取。再通過這些已經(jīng)被limit出來的10個主鍵id，去查詢聚簇索引。這樣只會十次隨機io。
在業(yè)務(wù)確實需要用分頁的情況下，使用該方案可以大幅度提高性能。通常能滿足性能要求。
寫在最后
非常感謝我?guī)煾冈谖耶厴I(yè)前三年的指導(dǎo)，給了我很多耐心。在節(jié)假日給我布置看書任務(wù)，在午休時候考察我學(xué)習(xí)的進展，通過提問的方式引導(dǎo)我去探索問題，在我從騰訊畢業(yè)后，每次見面也給我出了很多主意，傳授授業(yè)解惑，無一沒有做到極致。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- laravel自定義分頁的實現(xiàn)案例offset()和limit()
