歡迎閱讀數(shù)據(jù)庫內(nèi)核雜談芦倒，讓大家久等啦艺挪。提前祝大家五一勞動(dòng)節(jié)快樂！上一期兵扬，我們著重介紹了對(duì)于一個(gè)SQL語句麻裳，數(shù)據(jù)庫是怎么生成一個(gè)執(zhí)行計(jì)劃，并根據(jù)這個(gè)執(zhí)行計(jì)劃器钟，一步一步地讀取津坑，計(jì)算并獲得最后結(jié)果的。這一期傲霸，我們來聊一下兩個(gè)非常重要的算子(operator, 上一期我把operator翻譯成操作符疆瑰，后來讀了其他前輩寫的文章眉反，發(fā)現(xiàn)還是算子更貼切): 排序(Sort)和聚合(Aggregate)的實(shí)現(xiàn)。為什么要把這兩個(gè)算子放在一起說呢穆役？其實(shí)寸五，它們之間有很多的共同點(diǎn)，比如耿币，都是Blocking的算子梳杏，即需要得到所有的輸入tuple，才能完成計(jì)算后輸出淹接。這就使得它們會(huì)遇到同樣的困難秘狞，比如內(nèi)存無法存放所有的輸入tuple，怎么辦蹈集？除了這個(gè)問題，排序和聚合還有很多其他藕斷絲連的地方雇初。帶著這個(gè)問題拢肆，我們一起進(jìn)入今天的內(nèi)容吧。
排序
首先靖诗，來了解一下排序算子能夠?qū)崿F(xiàn)哪些SQL語法郭怪。 既然是排序，第一想到的當(dāng)然是ORDER BY語句啦刊橘。下圖給出了一些示例語句鄙才。
簡單介紹一下，數(shù)據(jù)庫系統(tǒng)會(huì)按照ORDER BY鍵的排列順序輸出結(jié)果促绵。默認(rèn)是升序(ASEC)攒庵，也可以通過聲明來要求按照降序(DESC)輸出。示例二展示了可以對(duì)多個(gè)列進(jìn)行組合排序败晴，排序會(huì)按照排序列的先后順序依次進(jìn)行浓冒。示例三展示了一類ORDER BY語句的語法糖(syntax sugar)〖饫ぃ可以用編號(hào)1稳懒， 2來指定。示例四展示了排序的鍵并非一定要是某一個(gè)列慢味，也可以是列組成的表達(dá)式场梆。
除了可以實(shí)現(xiàn)ORDER BY，排序還能實(shí)現(xiàn)其他什么語句嗎纯路？答案是肯定的或油，比如下面這個(gè)示例：
上例展示了一個(gè)distinct的聚合語句，要求輸出所有不重復(fù)的class-id感昼。讀者可能有疑問装哆，排序怎么實(shí)現(xiàn)這個(gè)聚合語句呢？哈，是不是覺得這兩個(gè)算子的關(guān)系有點(diǎn)緊密了蜕琴？其實(shí)答案也并不難想到：先對(duì)所有學(xué)生以class-id進(jìn)行排序萍桌，然后在上一層的聚合算子里，只需要維護(hù)一個(gè)當(dāng)前的class-id凌简，并且同新的輸入做對(duì)比上炎，如果不同就輸出class-id, 如果相同就保留。示例代碼如下：
除了幫助實(shí)現(xiàn)這個(gè)聚合雏搂，排序帶來的另一個(gè)好處在于藕施，把這個(gè)聚合變成了一個(gè)non-blocking的算子：不再需要等待所有的輸入，只要輸入的class-id和當(dāng)前不匹配凸郑，即可輸出當(dāng)前class-id裳食，內(nèi)存的問題也一并消失了。排序是不是挺厲害的芙沥，給大家留一個(gè)思考題诲祸？你還能想到其他SQL語句可以用排序來幫忙實(shí)現(xiàn)的嗎？答案在文末揭曉而昨。
聊完了作用救氯，來聊聊具體實(shí)現(xiàn)。前文已經(jīng)說到歌憨，排序是blocking的着憨，實(shí)現(xiàn)的難點(diǎn)就在于內(nèi)存消耗。假設(shè)輸入的數(shù)據(jù)可以完全存放在內(nèi)存中务嫡，那我們直接用快速排序就萬事大吉了甲抖。如果還要精益求精，那就需要看如何才能減少比較和交換的次數(shù)心铃，更有甚者惧眠，去追求CPU register或者L1, L2緩存的利用率。如果數(shù)據(jù)量太大于个，不能一次性全存放在內(nèi)存中呢氛魁。這就需要用到我們上一期提到過的spill to disk技巧了：需要把數(shù)據(jù)暫存到文件系統(tǒng)中。這里厅篓，就引出今天提到的第一個(gè)算法：外部歸并排序(external merge sort)秀存。工程中要實(shí)現(xiàn)一個(gè)正確并且高效的外部歸并排序是挺有挑戰(zhàn)的，所以有些數(shù)據(jù)庫系統(tǒng)在執(zhí)行時(shí)需要消耗大量的內(nèi)存或者干脆要求加入limit語句來限制排序數(shù)量羽氮。
首先或链，我們應(yīng)該明確，如何來衡量一個(gè)外部歸并排序的好壞档押。對(duì)于排序澳盐，你可能會(huì)脫口而出“快速排序祈纯，時(shí)間復(fù)雜度O(n * log(n))”。但是一旦牽涉到了文件IO叼耙，什么O(n * log(n))都是浮云腕窥。因?yàn)槲募x寫的速度和內(nèi)存差了兩個(gè)量級(jí)(100X)，正確的衡量方法應(yīng)該是大致需要讀寫多少次的數(shù)據(jù)筛婉。為了方便衡量簇爆，我們先假設(shè)數(shù)據(jù)都是以頁(page)的形式存放在文件系統(tǒng)中，并且以頁的形式讀取到內(nèi)存中(即爽撒，每次讀取的最小單位為1頁)入蛆。
外部歸并排序的思路和歸并排序(merge sort)一樣，都是利用了分治算法硕勿。整個(gè)算法分成兩個(gè)階段：階段0）把所有數(shù)據(jù)分成小段哨毁，并對(duì)每一段進(jìn)行排序(這里假設(shè)每一小段都能夠存放在內(nèi)存中所以我們可以用各種排序算法實(shí)現(xiàn)); 階段1) 把每一小段逐漸合并，最終完成全部排序源武。具體實(shí)現(xiàn)起來挑庶，我們至少需要分配給這個(gè)排序算子3頁的內(nèi)存(2個(gè)用來作為輸入緩存，1個(gè)用來作為輸出緩存)：假設(shè)輸入數(shù)據(jù)總共有n頁软能，排序只能2頁2頁地讀取，排序举畸，然后輸出到文件系統(tǒng)暫存查排；然后對(duì)于已經(jīng)排序完的n/2個(gè)文件(每個(gè)文件2頁)，再依次讀取抄沮，排序跋核，然后再輸出文件系統(tǒng)暫存，直至得到一個(gè)n頁的全排序文件叛买。下圖給出了一個(gè)示例：
上述的外排算法砂代，總共讀取了多少文件頁呢。我們這樣來算：
n #總共n頁數(shù)據(jù)# * 2 #讀寫各一次# * (1 #第一次讀和最后一次讀# + log2(n) #總共log2(n)次歸并#) 即：
如果要對(duì)n頁大小的數(shù)據(jù)進(jìn)行排序并且只有3頁的內(nèi)存率挣，需要讀寫2n * (1 + log2(n))頁刻伊。
現(xiàn)在假設(shè)排序算子能分配b頁的內(nèi)存，又該如何計(jì)算呢椒功？思路是每一次可以合并b-1個(gè)頁面捶箱，最后答案是：
2n * ( 1 + log_b-1(N/b) )：這里對(duì)數(shù)的底變成了b-1而不是原來的2。留給大家自行推導(dǎo)啦动漾。
據(jù)我所知丁屎，所有數(shù)據(jù)庫的spill to disk排序大體思路都是外部歸并排序，當(dāng)然最后的快慢還是需要工程實(shí)踐中的精益求精旱眯。
除了外排晨川，還有什么方法能夠過實(shí)現(xiàn)排序证九？不知大家是否回想起索引那一篇(數(shù)據(jù)庫內(nèi)核雜談 - 索引)里留的思考題：B+樹索引的另一個(gè)好處在哪？Bingo共虑！答案就是如果對(duì)要排序的鍵已經(jīng)建有B+樹索引愧怜，可以通過B+樹索引查找到指定的葉節(jié)點(diǎn)，然后依次讀取數(shù)據(jù)即可看蚜。
總結(jié)一下叫搁，我們討論了排序能夠過實(shí)現(xiàn)哪些SQL語句，并且介紹了兩種排序的實(shí)現(xiàn)供炎，分別是外部歸并排序和讀取B+樹索引結(jié)果渴逻。
聚合(aggregation)
聊完了排序，我們?cè)賮砜淳酆纤阕右艚搿＞酆纤阕雍途酆险Z句類型一一對(duì)應(yīng)惨奕，那常見的聚合語句又有哪些呢？首先是單項(xiàng)聚合(scalar aggregation), 指聚合后的結(jié)果集是一個(gè)單一值(線性代數(shù)里稱標(biāo)量)竭钝。比如下面這些示例：
其次就是組隊(duì)聚合(group aggregation)梨撞，其結(jié)果是先對(duì)所有數(shù)據(jù)根據(jù)group by鍵分組，然后對(duì)每個(gè)組分別計(jì)算聚合值香罐。比如下面示例：
考考大家卧波，下面這個(gè)聚合屬于哪個(gè)類別呢？
乍看之下庇茫，似乎是單項(xiàng)聚合因?yàn)榻Y(jié)果集是一個(gè)標(biāo)量港粱，求總共有多少個(gè)不同的班級(jí)。但其實(shí)旦签，這個(gè)語句可以看成是一個(gè)單項(xiàng)聚合和組隊(duì)聚合的疊加查坪，如下圖所示：
語句中先對(duì)班級(jí)進(jìn)行組隊(duì)聚合，雖然聚合值是空宁炫，然后對(duì)班級(jí)再進(jìn)行單項(xiàng)聚合求COUNT偿曙。
聊完了作用，來聊實(shí)現(xiàn)羔巢。單項(xiàng)聚合的實(shí)現(xiàn)非常簡單望忆，算子只需要保存一個(gè)聚合的中間值(running aggregate value)，然后根據(jù)新輸入不斷更新即可竿秆。而且炭臭，絕大部分聚合函數(shù)的是不需要存儲(chǔ)原始輸入的，比如max, min, count, avg等袍辞，因此內(nèi)存消耗也不大鞋仍。示例代碼如下：
再考考大家，你能想到有什么單項(xiàng)聚合函數(shù)的實(shí)現(xiàn)是需要消耗大量內(nèi)存的嗎搅吁？我唯一想到的就是求整個(gè)輸入集合的熵(因?yàn)橐y(tǒng)計(jì)所有不同元素的出現(xiàn)概率威创，相當(dāng)于內(nèi)部建立一個(gè)哈希表), 雖然感覺好像熵并不是一個(gè)SQL標(biāo)準(zhǔn)的聚合函數(shù)落午。
再來看組隊(duì)聚合的實(shí)現(xiàn)。單從聚合函數(shù)角度出發(fā)肚豺，組隊(duì)聚合于單項(xiàng)聚合的唯一區(qū)別就是溃斋，先要把group by鍵相同的輸入放到一個(gè)組里，然后對(duì)每個(gè)組求解聚合函數(shù)即可吸申。具體實(shí)現(xiàn)方法又有哪些呢梗劫？一就是上文提過的排序。我們可以借助排序先把輸入按照group by鍵進(jìn)行排序截碴，然后我們只要針對(duì)相同的鍵來計(jì)算聚合函數(shù)即可梳侨。示例代碼如下：
從示例代碼來看，由于臟活累活都讓排序替我們干了日丹，實(shí)現(xiàn)和單項(xiàng)聚合類似走哺，并且從內(nèi)存消耗角度來看，依然不大哲虾。
除了排序丙躏，還有什么辦法能夠幫我們實(shí)現(xiàn)聚合？ 相信讀者馬上就能想到了束凑，對(duì)group by鍵建立哈希表來維系鍵和中間值的狀態(tài)晒旅。示例代碼如下：
從示例代碼來看，邏輯依然簡單明了汪诉。但難點(diǎn)在于废恋，如果數(shù)據(jù)量特別大，就需要維護(hù)一個(gè)超級(jí)大的哈希表摩瞎。考慮到需要維護(hù)哈希表的性能孝常，一般維持使用率在50%左右旗们，所以真正使用的內(nèi)存空間應(yīng)該會(huì)更大。這就遇到和前面排序一樣內(nèi)存不夠的問題了构灸。所以說上渴，出來混，遲早要還的喜颁。
解決思路當(dāng)然依舊是借助文件系統(tǒng)暫存數(shù)據(jù)稠氮。這里，我們引出外部哈希表的算法半开。算法的思路依然是分而治之隔披。我們假設(shè)聚合算子總共能分配到b個(gè)頁面的內(nèi)存。預(yù)留1頁用作輸入緩存寂拆，b-1頁用作分區(qū)(partition)奢米，對(duì)于那1頁輸入緩存中的所有數(shù)據(jù)抓韩，根據(jù)group by鍵求一個(gè)簡單的哈希來分配到其他b-1頁中(可以用下面這樣的哈希函數(shù)：hash_fun(key) % (b -1 ))。這b-1個(gè)頁作為b-1個(gè)分區(qū)的輸出緩存鬓长，一旦寫滿就輸出到文件系統(tǒng)中谒拴。掃描過一遍數(shù)據(jù)后，我們把整個(gè)數(shù)據(jù)就分成了b-1個(gè)文件涉波。假設(shè)每個(gè)文件的大小在b頁以內(nèi)英上，那對(duì)于每一個(gè)文件，就可以利用上述的哈希表方法來實(shí)現(xiàn)組隊(duì)聚合啤覆，并且能夠保證不會(huì)超出b頁內(nèi)存苍日。
讀者可能會(huì)有疑問，萬一有文件依然大于b頁呢城侧？有句名人名言怎么說的來著易遣，沒有什么事情是一頓火鍋不能解決的，如果有嫌佑，就兩頓豆茫。解決思路就是對(duì)這個(gè)超大文件再用一次分區(qū)算法：換一個(gè)哈希函數(shù)，再把這些數(shù)據(jù)分成b-1個(gè)小分區(qū)屋摇。一層分區(qū)理論上能夠解決b^2頁大小的數(shù)據(jù)揩魂，而二層分區(qū)就能解決b^3大小。因此即使輸入數(shù)據(jù)很大炮温，也不會(huì)需要很多層的分區(qū)火脉。
至此，我們介紹了外部哈希表的算法來解決聚合算子的內(nèi)存消耗問題柒啤。
總結(jié)
今天倦挂，我們分別討論了排序和聚合這兩個(gè)算子用來實(shí)現(xiàn)哪些SQL語義，詳細(xì)介紹了工程實(shí)現(xiàn)的要點(diǎn)担巩，即通過外部歸并排序和外部哈希表方法來解決內(nèi)存消耗問題方援。并且也從中了解了排序算子可以用來協(xié)助實(shí)現(xiàn)聚合算子。
解答開篇的思考題涛癌，排序除了能夠幫助實(shí)現(xiàn)ORDER BY犯戏，GROUP BY語句，還能實(shí)現(xiàn)表的聯(lián)合JOIN：思路和歸并排序一樣拳话，對(duì)于二元聯(lián)合 table_a JOIN table_b先匪，我們只要針對(duì)聯(lián)合鍵分別對(duì) table_a 和 table_b 進(jìn)行排序，然后弃衍，對(duì)于兩個(gè)表分別維護(hù)一個(gè)指針呀非，不斷往后迭代，當(dāng)兩邊的鍵值相同的時(shí)候镜盯，就可以輸出聯(lián)合的結(jié)果姜钳。具體的實(shí)現(xiàn)坦冠，咱們就放在下期表的聯(lián)合(JOIN)的時(shí)候再聊。下期再見哥桥！
