DARTS#01這期我把三個看起來很散的詞湊到了一起Tournament Sort算法、MySQL深度翻頁優(yōu)化、字節(jié)切片編碼論文ByteSlice。如果你只是被其中一個詞吸引點進來我也建議把另外幾節(jié)掃完因為它們其實是同一根技術主線上的三段基礎算法決定你對排序的直覺SQL改寫解決你手頭的線上問題論文則給你往后看兩三年的視野。這是DARTS系列的第一篇后面會沿用這種“一道算法、一個工程優(yōu)化、一篇論文速讀”的格式。1. 為什么把排序算法、翻頁優(yōu)化和一篇論文放在同一期1.1 DARTS的定位和選題邏輯做這個系列的初衷很簡單我發(fā)現很多做后端開發(fā)和數據庫維護的人知識結構往往是“點狀”的——懂索引、懂EXPLAIN、懂幾條優(yōu)化SQL但碰上復雜問題還是很難串成一條線。今天這條線是“數據如何被排序、如何被翻頁、如何被壓縮存儲”。三個看似無關的話題其實都指向數據庫吃不消時的典型場景。排序算法是數據庫執(zhí)行計劃的地基MySQL的filesort和外部歸并都建立在樹形比較結構上深度翻頁是OLTP系統(tǒng)最常見的性能殺手一條只取20行的查詢能把機器拖到IO瓶頸ByteSlice則是OLAP列式存儲里的編碼思路讓你理解列存為什么能在海量數據上跑得比行存快一個數量級。1.2 三個關鍵詞之間的隱藏主線我先說一個自己的體會調優(yōu)MySQL查詢從來不是背幾條SQL寫法就能解決的。你得先弄清楚數據庫在執(zhí)行這條SQL時把數據從磁盤搬進內存后做了什么。Tournament Sort是“怎么用最少的比較找出最小值”的算法答案深度翻頁優(yōu)化是“怎么讓數據庫少做無用功”的工程答案ByteSlice是“怎么讓數據在磁盤上占更少空間、掃描時讀更少字節(jié)”的存儲答案。三條答案放在一起才是一份完整的性能優(yōu)化認知框架。1.3 適合誰來讀這篇文章如果你是后端開發(fā)建議重點看第3章和第4章里面是可落地的SQL改寫方案如果你是準備面試的候選人第2章的算法推導和第5章的論文拆解可以給你提供不錯的談資如果你已經在維護千萬級數據表那第3章的量化分析可能能解釋你上周遇到的那次慢查詢。整體閱讀大概需要15分鐘代碼可以直接抄。2. Tournament Sort樹形選擇排序如何點亮外部歸并2.1 從簡單選擇排序到錦標賽為什么要兩兩對戰(zhàn)先回憶一下最簡單的選擇排序每次線性掃描整個數組找到最小值把它放到結果數組里下次再掃描剩余部分。這個算法的問題很明顯——找第k個最小值時前面比較過的信息全部丟棄下次又要從頭比一遍。n個元素找最小平均要比較n/2次找n個最小值總比較量就變成O(n2)。Tournament Sort的思路是既然要反復找最小值那把每一輪比較的“勝者”記錄下來避免重復勞動。這就像世界杯淘汰賽32支球隊決出冠軍不是讓每支球隊和其他31支都打一場而是兩兩分組、勝者晉級最后只需要31場比賽就能知道誰是冠軍。選出冠軍后如果想讓亞軍的產生也高效只需要重新比較冠軍所在那條晉級路徑上的球隊即可。放到數組里先讓所有元素兩兩比較產生一組勝者勝者再兩兩比較依次向上形成一棵完全二叉樹。樹的根節(jié)點就是全局最小值。取出根節(jié)點后把對應葉子節(jié)點置為正無窮再沿著這條路徑重新比較一次新的根節(jié)點就是第二小的值。這個過程保證每次取出一個有序值只需進行l(wèi)og?n次比較。2.2 時間復雜度與堆排序、歸并排序的對比建樹階段需要n-1次比較之后每次選出一個最小元素需要約log?n次比較整體時間復雜度和堆排序一樣是O(n log n)。但空間上錦標賽排序需要額外的一棵二叉樹屬于非原地算法這是它不如堆排序普及的主要原因。不過在工程上錦標賽思想有一個堆排序替代不了的變體多路歸并。外部排序把大文件拆成多個有序段后需要把k個有序段合并成一個有序段。每次從k個段的頭部選最小值如果用線性掃描是O(k)但如果用敗者樹勝者樹的對稱版本只需要O(log k)。MySQL filesort產生臨時文件后的歸并階段以及各種數據庫的external merge sort底層都是這個套路。這也是為什么我始終覺得Tournament Sort不是一道孤立的算法題。它表面上是一棵二叉樹實際上是連接選擇排序、堆排序、歸并排序三者的橋梁。理解了它你對“排序”這兩個字的理解就不再是調用一個sort函數而是明白在內存放不下時算法如何被迫改變形態(tài)。2.3 MySQL ORDER BY里的樹形排序影子MySQL執(zhí)行ORDER BY時會先看排序字段能不能直接走索引。能走索引B樹本身維護了有序性直接順序掃描返回即可。不能走索引就需要filesort。filesort不是真的“文件排序”它優(yōu)先使用內存中的sort buffer默認sort_buffer_size通常為256KB或更大。當sort buffer放不下全部數據時MySQL會把數據分成多個塊每塊內部排序后寫成臨時文件最后對這些有序臨時文件做多路歸并。多路歸并的每一步就是從每個有序塊中取當前最小再比較選出全局最小這正是錦標賽思想的經典應用。還有一個容易被忽略的細節(jié)當查詢帶ORDER BY和LIMIT時MySQL 8.0會嘗試用優(yōu)先隊列堆來優(yōu)化排序只維護LIMIT大小的堆而不是把所有行都排好序。這種做法的時間復雜度是O(n log m)m是LIMIT大小n是參與排序的行數。如果你只需要前20條它絕不會傻到把100萬行全部排完再截斷。理解這一點對后面深度翻頁優(yōu)化很有幫助。2.4 一個最小的錦標賽排序演示我用Python寫了一個最直白的演示版本只為展示算法骨架生產代碼不建議這么寫。def tournament_sort(arr): n len(arr) size 1 while size n: size 1 tree [float(inf)] * (2 * size) tree[size:size n] arr # 自底向上建樹比較得到冠軍 for i in range(size - 1, 0, -1): tree[i] min(tree[2 * i], tree[2 * i 1]) res [] for _ in range(n): v tree[1] res.append(v) # 定位冠軍對應的葉子置為無窮大后重新向上比較 pos next(i for i in range(size, 2 * size) if tree[i] v) tree[pos] float(inf) pos // 2 while pos: tree[pos] min(tree[2 * pos], tree[2 * pos 1]) pos // 2 return res注意這個實現用next線性查找冠軍葉子所以實際復雜度不夠嚴謹只適合演示原理。工程實現需要用一個left/right數組記錄每輪比賽贏家來自哪個分支或者用敗者樹降低更新代價。演示代碼的核心意圖是讓你看到“每次只更新冠軍路徑”這件事——這是整個算法最精華的部分。3. MySQL深度翻頁的真實成本從回表到臨時文件3.1 一條LIMIT 1000000, 20背后的物理操作先給一個具體的慢查詢現場還原。假設我在維護一張訂單表orders已經積累到200萬行業(yè)務端做了一個分頁列表頁用戶翻到第5萬頁時前端發(fā)起的就是這種請求SELECT id, user_id, amount, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20;這條SQL的意圖是跳過前100萬行取接下來的20行。但數據庫的執(zhí)行計劃不會聰明到“直接從某個位置開始讀”它必須老老實實掃描到第1000020行再丟棄前面的1000000行。等于你點了一個20行的外賣廚師把前面100萬份菜全部炒了一遍然后倒掉。如果ORDER BY的字段沒有索引MySQL還會先把所有滿足status1的行讀出來做filesort。更壞的情況是排序的列不在索引里需要回表讀取完整數據行再把數據放進sort buffer排序完成后再次回表取列。光是回表這一步就可能觸發(fā)幾十萬次隨機IO。3.2 用EXPLAIN和實測數據還原慢查詢現場在我本機測試環(huán)境里MySQL 8.0orders表約200萬行innodb_buffer_pool_size設了1GB執(zhí)行上面的SQLEXPLAIN結果大致是這樣的EXPLAIN SELECT id, user_id, amount, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20;列值typerefrows約1850000filtered100.00ExtraUsing index condition; Using filesortrows估算185萬這還只是估算值。實際執(zhí)行時由于需要把185萬行讀進sort buffer并做外部排序耗時輕松超過900ms。隨著offset繼續(xù)增大掃描范圍還會線性增長。如果把offset換成2000000這條查詢可能直接變成秒級。EXPLAIN里出現Using filesort意味著排序過程沒有索引可用。即使有二級索引支撐回表的次數也會被放大到“offsetlimit”的規(guī)模。這就是為什么很多報表接口翻到后面會越來越慢不是數據庫變卡了而是每次翻頁都在重復做同樣的超大排序和超大跳躍。3.3 翻頁越深越慢的三個放大因素第一個是回表放大。InnoDB的二級索引只存索引列和主鍵要取其他字段必須回到聚簇索引。深翻頁時回表次數接近offset這些回表操作對散落的隨機主鍵發(fā)起讀取在沒有被緩存的情況下每次都可能是物理IO。第二個是排序放大。如果排序字段沒有索引參與排序的是全部滿足條件的行而不是從第1000000行開始的20行。這意味著一半以上的數據被讀進sort buffer又被寫出臨時文件做了大量無意義的排序工作。第三個是重復計算。分頁接口每次翻頁都是獨立SQL上一頁產生的排序結果和掃描位置完全不被重用。用戶連續(xù)翻10頁數據庫就做10次幾乎一樣的全量排序。頁數越深這個重復成本越離譜。想解決深翻頁就得從這三個放大因素下手減少回表、減少排序規(guī)模、消滅大offset。4. 針對深度翻頁的SQL改寫方案與適用邊界4.1 延遲關聯用覆蓋索引先縮小回表范圍延遲關聯的核心思路是先用最小代價查出這一頁需要的20個主鍵再用主鍵回表取完整數據。最小代價怎么實現讓子查詢的WHERE、排序字段、主鍵都在同一個覆蓋索引里。對上面的例子先建一個聯合索引(status, created_at, id)或者(created_at, id)然后改寫SQLSELECT o.* FROM ( SELECT id, created_at FROM orders WHERE status 1 ORDER BY created_at DESC LIMIT 1000000, 20 ) AS t JOIN orders o ON o.id t.id ORDER BY t.created_at DESC;子查詢只掃描覆蓋索引不需要回表取出所有列索引天然有序Using filesort會消失LIMIT階段處理的都是索引頁的小記錄占用sort buffer非常少。拿到20個主鍵后再JOIN原表只做20次聚簇索引查詢。我實測這條改寫語句耗時降到約55ms和之前的900ms相比幾乎不是一個量級。注意外層又加了一個ORDER BY t.created_at DESC因為JOIN是亂序匹配的如果業(yè)務要求保持分頁順序需要在外層重新排序。子查詢里同時select id和created_at是為了外層能夠穩(wěn)定排序。4.2 游標分頁讓offset從SQL里消失延遲關聯依然要掃描offset之前的100萬個索引項雖然比回表全行快但offset繼續(xù)增大到百萬、千萬時還是會感覺到壓力。真正讓深翻頁成本恒定的是游標分頁也叫keyset分頁。思路很簡單客戶端記住上一頁最后一條記錄的排序字段和主鍵下一頁從這條記錄后面接著取。SQL寫成這樣SELECT id, user_id, amount, created_at FROM orders WHERE status 1 AND (created_at, id) (:last_created_at, :last_id) ORDER BY created_at DESC, id DESC LIMIT 20;聯合索引(status, created_at, id)可以直接支撐這個查詢。數據庫通過索引定位到游標位置然后順序向后掃描20行整個過程與offset完全沒有關系。不管當前在第幾頁查詢時間都穩(wěn)定在個位數毫秒級別。這個方案最痛的點在于不支持常見的頁碼跳轉。產品要做“跳到第100000頁”這種需求游標分頁就無能為力了。所以它更適合信息流、下拉加載、按時間線瀏覽這類“只關心下一頁”的場景。我的建議是新項目優(yōu)先按游標分頁設計接口老項目如果需要兼容頁碼至少把延遲關聯用起來。4.3 覆蓋索引與穩(wěn)定排序的細節(jié)還有一個常見陷阱如果排序字段不是唯一列比如排created_at時同一秒有幾十條記錄那么分頁結果可能在不同頁之間出現重復或遺漏。解決方案也很簡單排序條件里同時帶上主鍵讓排序組合(created_at, id)成為唯一序。前面游標分頁的SQL已經通過(id :last_id)體現了這一約束延遲關聯的SQL也要確保子查詢里按created_at, id并列排序。如果你只需要返回排序字段本身和主鍵不想接業(yè)務字段覆蓋索引查詢就夠了SELECT id, created_at FROM orders WHERE status 1 ORDER BY created_at DESC, id DESC LIMIT 1000000, 20;這種方式幾乎沒有回表成本可以當成一個輕量的數據導出查詢。但實際業(yè)務列表幾乎總是要展示多個字段所以延遲關聯仍然是更通用的做法。4.4 不同深翻頁場景的選型對照我整理了一個決策表按業(yè)務場景直接選即可場景首選方案原因備選方案用戶點頁碼可跳轉延遲關聯兼容任意頁實現成本低緩存熱點頁信息流/瀑布流加載游標分頁成本恒定體驗最順滑延遲關聯兜底數據導出/后臺任務覆蓋索引避免回表速度最快游標分頁排序字段非唯一游標分頁主鍵競態(tài)保證穩(wěn)定不重不漏延遲關聯復合排序字段一句話總結只要有辦法繞過offset就別用offset如果必須支持跳頁那就把掃描成本從全行回表降為覆蓋索引掃描這是性價比最高的折中。5. ByteSlice論文精讀字節(jié)切片編碼的設計與收益5.1 論文在解決什么問題如果說前面兩章是在“減少數據庫做的無用功”ByteSlice思考的是更底層的事數據以什么形態(tài)放在磁盤上才能讓掃描更快。傳統(tǒng)行式存儲按行存數據讀一行就要把整行的所有字段讀出來即使你只需要其中兩列。列式存儲則把同一列的數據連續(xù)存放掃描時只需要讀取目標列天然節(jié)省大量IO。但連續(xù)存放只是第一步。分析型查詢往往要掃描幾億行數值數據即使只讀一列數據量依然巨大。ByteSlice就是針對這類定長數值列提出的一種編碼與其把每個整數看成一個整體去壓縮不如把每個整數的字節(jié)拆開按字節(jié)位置分組成連續(xù)切片再對每個切片做更有效的壓縮。這套思路之所以有效是因為數值數據存在天然的字節(jié)分布規(guī)律。舉個例子int32正數的高位兩個字節(jié)通常全是0int64負數的最高位字節(jié)又往往是0xFF。把這些高位字節(jié)放在一起你會發(fā)現它們的形式非常單一非常容易被壓縮。5.2 編碼過程拆解從列數據到字節(jié)切片我用一組具體數字演示ByteSlice的處理過程。假設一列int32數據為[1024, 1025, 4096, 4097]小端序下每個數占4字節(jié)1024 - 00 04 00 001025 - 01 04 00 004096 - 00 10 00 004097 - 01 10 00 00ByteSlice不是按行存這4個整數而是按字節(jié)偏移重新組織切片內容特點第0字節(jié)切片00 01 00 01低位字節(jié)變化較隨機第1字節(jié)切片04 04 10 10基數低適合bit-packing第2字節(jié)切片00 00 00 00全零直接標記跳過即可第3字節(jié)切片00 00 00 00全零直接標記跳過即可第2、第3字節(jié)切片全是0根本不需要存儲第1字節(jié)切片只有兩個不同取值可以用很小的bit寬度做位打包第0字節(jié)切片數值分布相對分散但也可以配合Delta編碼或Varint壓縮。查詢時也不需要解碼全部切片。比如你要過濾 x 3000可以先看高字節(jié)切片如果高字節(jié)部分已經說明該值大于或小于閾值就不用繼續(xù)處理低位切片。這種按切片級別的Skip邏輯配合SIMD能夠在掃描初期就排除大量不滿足條件的行。5.3 與RLE、字典、Delta編碼的橫向對比ByteSlice不是唯一的選擇。數據庫列存中常見的編碼還有幾種編碼適合的數據特征優(yōu)點缺點RLE行程編碼連續(xù)重復值壓縮率極高數據亂序時失效Dictionary基數低的字符串/枚舉查詢友好高基數場景開銷大Delta單調遞增的時間戳/ID差值小存儲緊湊對波動大的數據效果差ByteSlice數值分布集中、高位重復壓縮率高且支持隨機過濾只適用于定長數值實現復雜ByteSlice最大優(yōu)勢在于它不依賴數據的排列順序不需要相鄰值相同或遞增只要數值在字節(jié)層面有模式就能獲得壓縮收益。這在真實業(yè)務里是很常見的價格、年齡、數量、狀態(tài)碼這些字段往往數值范圍不大但行與行之間未必有規(guī)律。5.4 代價與適用邊界ByteSlice不是沒有成本。它要求列是定長數值類型對VARCHAR/字符串類型基本無能為力隨機寫入場景字節(jié)切片后會破壞一行數據的連續(xù)性更新一小塊數據可能涉及多個切片的修改代價很大實現層面編碼器和解碼器都要處理位偏移、切片切分、bit-packing對齊等細節(jié)沒有成熟的庫支持時開發(fā)成本不低。所以ByteSlice更適合OLAP系統(tǒng)里的只讀或追加寫表而不是高并發(fā)OLTP。很多列式存儲引擎之所以選擇它是因為分析型查詢注重掃描吞吐而OLTP的點查和更新場景完全用不上這種編碼。理解這個邊界比記住編碼本身更重要。這類“字節(jié)切片”思想給我的啟發(fā)是數據的物理布局直接影響查詢性能。你在設計MySQL表時如果能把高頻查詢的少量字段放在一個寬表里減少無謂的大字段讀入本質上也是在用更窄的數據布局換取更快的掃描速度。6. 三個主題連起來看一條數據庫性能優(yōu)化主線6.1 算法階段排序的優(yōu)化空間在哪里回到Tournament Sort。它告訴我們的第一件事是排序不是一件一錘子買賣的事信息可以復用。數據庫index有序掃描、filesort的優(yōu)先隊列優(yōu)化、外部歸并的敗者樹全部建立在這個認知之上。日常寫SQL時如果你發(fā)現ORDER BY在慢查詢里出現先別急著加緩存。問自己三個問題排序字段能不能命中索引LIMIT能不能和ORDER BY一起告訴優(yōu)化器讓它使用堆排序而不是全量排序排序字段是不是唯一的能不能加上主鍵保證穩(wěn)定大多數排序慢的問題問完這三個問題就解決了七成。6.2 工程階段把查詢改成可預期的低成本路徑深度翻頁優(yōu)化給我們的工程啟發(fā)是查詢性能應該可預期而不是依賴數據量碰運氣。用游標分頁后不管第100頁還是第10000000頁查詢時間都維持在幾毫秒用延遲關聯后回表次數從offsetlimit降為limit。這些手段的核心都是把“不確定的全表掃描”改成“確定的索引定位”。我見過不少團隊花大價錢加緩存、上搜索引擎卻忽略了把深翻頁SQL改成游標分頁這種只需要半天就能完成的改造。優(yōu)化是有順序的先改SQL和索引再考慮架構層緩存。前者往往是性價比最高的。6.3 進階階段用存儲編碼反向影響查詢設計ByteSlice讓我意識到數據庫性能優(yōu)化不僅有“查詢層”和“索引層”還有“存儲層”。同樣的數據以行存、列存、字節(jié)切片、字典壓縮等不同形式存放查詢性能可能差出兩個數量級。作為應用開發(fā)者雖然很難直接去改InnoDB的存儲格式但在做表結構設計時可以借鑒這種思想盡量讓行窄一些、讓熱點列集中一些、避免無意義的寬表和大字段查詢。在線業(yè)務如果確實需要大范圍報表查詢該考慮把數據同步到分析型引擎時也可以優(yōu)先選擇支持列存和字節(jié)級編碼的方案。這不是讓你拋棄MySQL而是知道在什么場景下什么樣的存儲形態(tài)更適合。6.4 一點個人實操體會這三個主題我是在一次線上事故里串起來的。當時業(yè)務報表接口在深翻頁后頻繁超時我第一反應是加索引加了還是慢才開始研究EXPLAIN、回表、覆蓋索引最后用延遲關聯把耗時降了下來。后來去讀列存編碼相關的論文才意識到自己過去對“數據如何存放”的理解一直停留在表結構層面對物理布局和編碼收益幾乎沒有概念。這段經歷讓我形成了一個固定習慣每遇到一個性能問題先想清楚它屬于算法問題、執(zhí)行計劃問題還是存儲表示問題再決定怎么下手。這個習慣比任何具體SQL技巧都管用。DARTS系列后續(xù)也會繼續(xù)沿著“算法基礎、工程優(yōu)化、論文精讀”這個三明治結構來寫下一期打算聊聊Hash Join的底層設計以及在真實業(yè)務里如何選擇Join策略。