一、重塑

過去一年是 Doris 商業(yè)化的元年，遇到了很多新的場景和挑戰(zhàn)。在這些挑戰(zhàn)中，我們發(fā)現(xiàn)老優(yōu)化器有很多問題。首先是缺少優(yōu)化規(guī)則的抽象。有些規(guī)則并不適用于所有的場景，對某些場景，有些規(guī)則有幫助，有些規(guī)則沒有幫助。因為缺少規(guī)則的抽象，不方便細粒度控制規(guī)則的使用，給 query 的調(diào)優(yōu)帶來很大麻煩。同時，為了適應(yīng)更多的數(shù)據(jù)場景，需要增加新的規(guī)則。添加規(guī)則的成本，除了實現(xiàn)規(guī)則本身，還要讓規(guī)則融入優(yōu)化器，這就帶來很多額外的成本。最后，老優(yōu)化器不方便我們觀察一個規(guī)則究竟給 plan 帶來了怎樣的變化。

除了優(yōu)化規(guī)則的抽象，還有一個更重要的問題是我們?nèi)鄙?CBO 的框架。老優(yōu)化器缺少統(tǒng)計信息收集的能力。代價模型代碼也零散的分布在整個優(yōu)化器中。所以只能做一些很簡單很有限的 CBO 的規(guī)則。如果拿到復(fù)雜的 query，基本只會生成一個左深樹。

最后優(yōu)化器本身的架構(gòu)，基本只是做樹的兩輪遍歷。這對優(yōu)化規(guī)則的有很大限制。

于是在去年，Doris 決定做一個新的優(yōu)化器。從此拉開了新優(yōu)化器的序幕。

經(jīng)過來自美團、百度、小米、騰訊、京東、SelectDB 等公司的工程師們 400 多天的努力工作后，我們的優(yōu)化器終于與大家見面了，我們會在 Doris2.0 的時候正式推出。在前面的研發(fā)過程當(dāng)中，我們也在不斷做測試。比如在 SSB、TPCH 500G/1T 這些測試中，我們都超過了由專家人工改寫的 SQL。也就是說，即使是經(jīng)驗豐富的 DBA 用老優(yōu)化器改寫的 SQL 仍然比新優(yōu)化器自動生成的 plan 要差一些。圖中是我們測試的對比，大多達到了 50% 以上的提升。同時為了檢驗泛化能力，在用戶 POC 測試中，超過 10 個測試使用了新優(yōu)化器，在這些測試中，新優(yōu)化器為用戶減輕了很多負擔(dān)，SQL的調(diào)優(yōu)的工作幾乎都是自動完成。

二、優(yōu)化的本質(zhì)

下面從 SQL 的本質(zhì)來講解一下優(yōu)化器的地位。

首先，SQL 的本質(zhì)是一個描述性的語言，用戶只需要描述需要的數(shù)據(jù)是什么，數(shù)據(jù)怎么拿到是由優(yōu)化器決定的。可以說執(zhí)行引擎是車的發(fā)動機，優(yōu)化器是車的方向盤，如果沒有一個正確的優(yōu)化器，越強勁的引擎只會讓我們以越快的速度撞到內(nèi)存溢出的南墻上面。所以優(yōu)化器是 SQL 中最有特色的部分。

優(yōu)化器在一條 SQL 的旅程中處于什么位置呢？如上圖中所示，它處于紅框范圍內(nèi)。一條 SQL 首先經(jīng)過語法解析，生成抽象語法樹，然后進行語義分析后，第一階段對邏輯計劃進行改寫，改寫中會引入很多規(guī)則。改寫完成后，會生成多個候選的 plan，通過代價模型估計，從中挑出一個最優(yōu)的執(zhí)行計劃，交給查詢引擎執(zhí)行。Nereids 優(yōu)化器主要是指改寫查詢計劃、優(yōu)化查詢計劃兩部分。

具體來說，改寫的部分稱之為 RBO，代價估算稱之為 CBO，為了和之前的優(yōu)化器、執(zhí)行引擎兼容，還需要“plan 翻譯”才可以把新優(yōu)化器生成的 plan 轉(zhuǎn)換成 BE端可理解的查詢計劃。

在 RBO 規(guī)則中，包括了：謂詞下推、表達式改寫、常量折疊、消除空算子等等。這些規(guī)則一般來說會提高查詢的效率。所以這些規(guī)則生成的 plan 會替代輸入的 plan。有時一組規(guī)則會反復(fù)使用，知道 plan 不再變化為止。

當(dāng) RBO 改寫完成后，生成的 plan 作為 CBO 階段的輸入。CBO 階段最主要的任務(wù)是決定 join 的順序。因為 join 的順序?qū)?plan 的影響是非常大的。除了 join 順序的選擇，還有許多需要代價估算的點：包括 CTE，即一些 with 語句生成的 view，是單獨算出來還是嵌入到 SQL 中；還有聚合選用哪一種策略，是一階段還是兩階段、三階段做甚至四階段做。這些都是 CBO 階段做的事情。

上面講了很多優(yōu)化規(guī)則，其核心思想就是讓 SQL 執(zhí)行更快。但是就像做科學(xué)研究，定義好一個問題比解決問題更有價值。怎么叫定義好一個問題？就是需要找到一個好的指標來衡量這個問題。如果我們用查詢的時間來衡量，這是一個正確但是無用的指標。所以根據(jù)我的理解，應(yīng)該將這個問題定義為：盡早降低數(shù)據(jù)規(guī)模。下面我們從這個角度來審視優(yōu)化的規(guī)則。

用一個簡單的例子來看。上面是一個 TPC-H 的例子，我們做了改寫。描述的是有很多訂單，訂單的買方和賣方都有國籍，我們需要選出中國和美國之間貿(mào)易往來的訂單，生成下面的表格。

理解了這個 SQL 的做法，我們就能夠理解優(yōu)化器在其中做了什么事情。根據(jù)條件：（賣方的國籍=中國，并且買方的國籍=美國）或者（賣方的國籍=美國，并且買方的國籍=中國）表示中美之間往來的訂單，這個條件無法拆開，一個最自然的做法是把 orders 表和 customer表先 join，然后和 supplier 表 join，再和 nation join，最后做過濾。這是第一種做法，效率比較低。

好一些的做法是，既然挑出的是中美之間的貿(mào)易，那么可以推導(dǎo)出一個條件：customer 只選出中國或美國的 customer，supplier 只選出中國或美國的s upplier，這就是我們優(yōu)化器所做的一個優(yōu)化，我們會推導(dǎo)出一些看似冗余的條件，但這些條件作用非常大，可以幫助我們盡早將 customer 和 supplier 的數(shù)據(jù)規(guī)模降低。數(shù)據(jù)規(guī)模降低再來與 orders 表做 join 時，右表的數(shù)量就不再是全體 customer，而只是 customer 的一部分。再和 supplier 做 join 時，右表的數(shù)量也只是一部分的 supplier，左表的數(shù)量也不是全體的 order，而只是 customer 是中國或美國的 order，所以對這個 join 來說，也降低了數(shù)據(jù)量。這兩個 join 在 TPC-H 查詢中的性能提高是非常顯著的，有 2-3 倍的提升。這里的核心思想就是盡早把數(shù)據(jù)規(guī)模降低。希望這個例子能幫大家理解我們的優(yōu)化器殫精竭慮想要達到的目的。

除了上面的方法，還有一個更重要的降低數(shù)據(jù)規(guī)模的途徑是：調(diào)整 join 的順序。在事實表和維度表做 join 的時候，往往維度表會有一些過濾條件，會對事實表有很強的過濾效果。但是這時候又面臨一個問題：我們知道 join reorder 是一個 NP的問題，當(dāng)表的數(shù)量增加時，候選 plan 會呈幾何級數(shù)增長。這么多年來，這個問題沒有特別創(chuàng)新的突破，NP 問題一般只能通過動態(tài)規(guī)劃的方法，找一些次優(yōu)的解。我們現(xiàn)在看到的所有方法，都是動態(tài)規(guī)劃不同的應(yīng)用，比如有：DPSize、DPSub、DPhyper、Cascading......我們的新優(yōu)化器 Nereids 上面，同時采用了兩種動態(tài)規(guī)劃的方法，基礎(chǔ)的有 Cascading 方法，同時也加上了 DPhyper 的方法，兩者相互補充。

三、優(yōu)化瓶頸

艱苦奮戰(zhàn)了大半年后，系統(tǒng)基本成型。接著就開始關(guān)注性能。

第一個很重要的性能提升來源于 RBO 階段的一次重要重構(gòu)。Cascading 框架有一個 Memo 結(jié)構(gòu)，相當(dāng)于一個小賬本，所有規(guī)則產(chǎn)生的 plan 都用 Memo 記下來。這是CBO階段執(zhí)行動態(tài)規(guī)劃算法所需要的。我們知道所有動態(tài)規(guī)劃方法都有小賬本，在 Cascading 中的小賬本就叫做 Memo。我們一開始就像論文中的流程一樣，將 plan 放在 Memo 中，對plan進行改造時再從 Memo 中把 plan 片段取出來，這個過程叫 copyIn，copyOut。RBO 階段，總是用一個新的 plan 來替代老的 plan，我們?nèi)匀蛔裱系奶茁罚看紊尚碌膒lan，就放入 Memo 中，進行下一個規(guī)則替換時，再將這個 plan 從 Memo 中拿出來。反復(fù) copyIn，copyOut 的動作其實是多余的。于是美團的華建老師閉關(guān)好幾周，給大家提交了一個巨大的pr，RBO 的效率得到了飛速的提升。當(dāng)然我們也很痛苦，因為需要重新看一遍RBO 的所有代碼。但我們非常歡迎有越來越多這樣的痛苦。

RBO 階段有了一個性能的飛躍之后，CBO 階段的性能問題就凸顯出來了。于是我們團隊里的 ACM 冠軍，莫琛輝同學(xué)出場了。在那幾個星期里，他分析了上百個火焰圖，改寫了好幾輪代碼，最終將很多秒級的分析時間壓縮到 20 毫秒左右。如果將來你也需要實現(xiàn)一個 cascade 礦建，那么 CostAndEnforce 部分的性能調(diào)優(yōu)一定值得深入挖掘。

四、挑戰(zhàn)

下面再介紹下開發(fā)過程中所面臨的各種各樣的挑戰(zhàn)。這部分可能是介紹中最有意義的部分。

第一個問題就是公平與效率的平衡。這個問題的本質(zhì)是，做 join reorder 時候，希望找出做好的 plan，但是這是個 NP 問題，這就意味著我們一定要做裁剪，不可能公平地給每個可能的 plan 檢驗的機會，有一些plan未經(jīng)檢驗就直接被淘汰掉了。最簡單的樹結(jié)構(gòu)是 Left Deep Tree。這種樹，一般大表放在最左邊，隱含了一個假設(shè)：我們現(xiàn)在做的都是 hash join，用右表 build hash table, 左表做probe。因為一行數(shù)據(jù)構(gòu)建hash table的成本遠遠高于探測 hash table 的成本，所以要把成本高的計算放在行數(shù)少的表上做，單行成本低的計算放在行數(shù)大的表上做。這就是最基本的思想。所以構(gòu)造出一個左深樹，把最大的表（事實表）放在最左邊，依次把小表（維度表）放在右邊，和大表 join。這個方法的優(yōu)點是搜索空間小（比后面兩種小很多），因此優(yōu)化器的執(zhí)行就會快。但是這樣往往會錯過很多優(yōu)秀的執(zhí)行計劃，讓引擎端的負擔(dān)太大。一個更好的平衡是 ZigZag Tree。它背后的思想是：當(dāng)大表和小表 join 后，得到的結(jié)果可能數(shù)據(jù)量比較小，再和另外的表join 時，可能就需要放在右邊，于是生成了中間所示的執(zhí)行計劃，每一步都去需要判斷左表和右表誰大誰小，就得到了 ZigZag Tree。如果將搜索空間再擴大一點，稱之為 Bushy Tree，就是把所有的二叉樹都放進來考慮，Bushy Tree 的搜索空間因此會暴漲上去。當(dāng)表的數(shù)量太多時，就會導(dǎo)致優(yōu)化器執(zhí)行時間超過了執(zhí)行引擎的執(zhí)行時間。所以很多情況下，不能搜索整個空間的 Bushy Tree。

這里有一個基于表數(shù)量和 Left Deep Tree、ZigZag Tree、Bushy Tree 增長幅度的估算。在實際實踐當(dāng)中，當(dāng)表的數(shù)量較少時，會采用 Cascading，優(yōu)勢是可以把除了 join reorder 外的各種 rule 和 join reorder 混合使用。但是效率不是太高，所以當(dāng)表的數(shù)量較多時，會切換到 DPhyper 上去。

第二個挑戰(zhàn)是我們始終與誤差共存。與誤差共存不代表我們不去努力消除誤差。先來看看誤差是怎么產(chǎn)生的。剛才說要做 join reorder，這步需要很多的統(tǒng)計信息，需要估算每次 join 的結(jié)果有多少行，經(jīng)過過濾有多少行等。所以第一個誤差是統(tǒng)計信息，誤差來源是抽樣。比如計算某個字段不同值的個數(shù)（distinct），稱之為NDV(number of distinct values)，不可能全量做真實計算，一般會使用抽樣的方式，就會帶來誤差。

對表里數(shù)據(jù)統(tǒng)計后開始計算，比如一張表里有學(xué)生信息，有過濾條件：選出其中男同學(xué)數(shù)量。假設(shè)表有 100 行，優(yōu)化器估計選中男同學(xué)數(shù)量為 50%，但如果表來自國防科大，可能選出男同學(xué)數(shù)量占 98%，就會導(dǎo)致統(tǒng)計信息的推導(dǎo)出現(xiàn)誤差。在這些例子中，誤差產(chǎn)生的主要原因一是統(tǒng)計信息有誤差，二是加入了一些假設(shè)，比如假設(shè)數(shù)據(jù)均勻分布，假設(shè)字段之間沒有相關(guān)性等。所以統(tǒng)計信息推導(dǎo)時候，在統(tǒng)計信息誤差基礎(chǔ)上，又加入了一些誤差。這些誤差中，有一些是需要努力消除的，有一些是特殊應(yīng)用場景引入的。

如何檢驗統(tǒng)計信息的推導(dǎo)是否準確呢？我們開發(fā)了一個工具叫 qError，它會把每個算子推導(dǎo)的行數(shù)和實際執(zhí)行的行數(shù)做比較計算，來檢驗推導(dǎo)是否準確。當(dāng)我們把推導(dǎo)信息也做出來后，就開始計算各個 plan 真實的代價，這一步稱為代價模型。這部分需要考慮引擎的特點，環(huán)境的差異等，要看更需要減少數(shù)據(jù)在網(wǎng)絡(luò)的傳輸？還是更看重機器內(nèi)存的代價，或是 CPU 的代價等。不同情況要做不同的權(quán)衡。所以代價模型在統(tǒng)計信息推導(dǎo)誤差的基礎(chǔ)上，又會有新的誤差。如何衡量代價模型呢？我們推出了 Plan Ranker 工具。不管是 Cascading 還是 DPhyper，都是動態(tài)規(guī)劃方法，我們都加入了 Memo 記錄不同的 plan。我們可以取出認為排名前十的 plan，實際執(zhí)行中，他們的效率是否和我們預(yù)期的排序是一致的呢，可以通過實際執(zhí)行來檢驗。將檢驗后的 plan 序列與推斷的 plan 序列進行距離計算，來衡量代價模型的好壞。

最后，還有一個“顛覆者”。它的出現(xiàn)顛覆了我們對 join reorder 以及做優(yōu)化時的很多認識。先用一個簡單的例子來理解下 Runtime Filter，它對我們做 join 時有非常大的影響。假設(shè)有一個訂單表，有訂單號、商品id和其他字段。還有一個商品表，有商品 id、品牌，一個品牌下有多個商品。現(xiàn)在要找出“華為”這個品牌下的訂單。首先對商品表做過濾，找出品牌“華為”的商品，然后和訂單表做 join。剛才我們說過，優(yōu)化的目的是要盡早降低數(shù)據(jù)規(guī)模，那么這時候會有個想法。

假設(shè)商品表過濾出“華為”品牌的商品 id 是 p001、p003，作為集合 A，是否可以把A發(fā)送給訂單表，先用商品 id 對訂單集合做一次過濾，過濾后 6 億條數(shù)據(jù)只剩2400 萬條做j oin。這個是來自 TPC-H 里的典型場景，數(shù)據(jù)比例也是這樣。這樣就可以大大降低最后一步 join 的負擔(dān)，提高整個查詢的效率。本來 Runtime Filter 一開始的出現(xiàn)被認為是額外的 bonus，如果優(yōu)化器里的規(guī)則是一等公民的話，它就是二等公民，可是這個二等公民顛覆了我們的想法。

換一個稍微復(fù)雜的例子。假設(shè)需要找出亞洲的 supplier，supplier 有 nation id，nation id 有 region id（這里只選出亞洲）。supplier 先和 nation join，再和 region join。在 TPCH 里，region 有 5 大洲，nation 表有 25 個國家，每個洲5 個國家。每個國家有一些供應(yīng)商，supplier 表有 1 千萬條數(shù)據(jù)，并且每個國家的 supplier 是均勻分布的。左冊的破爛相對右側(cè) plan，就不夠高效。右邊首先選出亞洲，和 nation 做 join，這樣只選出亞洲的 5 個國家，再和 supplier 做 join，就直接選出了亞洲國家的 2 百萬 supplier。可以看到，左表和右邊都有兩個 join，但是處理的數(shù)據(jù)量級是不一樣的。顯然右邊處理的數(shù)據(jù)量級小了很多。因為 1 千萬的數(shù)據(jù) join，右邊只做了一次，而左邊做了兩次。傳統(tǒng)觀點下，右邊plan 是遠遠優(yōu)于左邊 plan 的。下面就會看到為什么將 Runtime Filter 稱為顛覆者。

顛覆效果是這樣的。左邊是我們剛才認為優(yōu)秀的 plan，右邊是認為不優(yōu)秀的plan。但是加上 Runtime Filter 后，右邊因為 region 只選擇亞洲，所以會把亞洲的 region id 發(fā)送給 nation，于是 nation 表在掃描時候只會取出 5 條數(shù)據(jù)，因為 nation 表通過 Runtime Filter 做了過濾。Nation 表過濾后，會生成下一個Runtime Filter，把5個國家的 id 發(fā)送給 supplier，于是 supplier 表直接過濾出2 百萬數(shù)據(jù)出來。如果采用右邊的 plan，參與 join 的數(shù)據(jù)規(guī)模就沒有出現(xiàn)過1千萬。這樣，右邊執(zhí)行反而更占優(yōu)勢。而且可以看到，除了 join 以外，它對延遲物化也非常有幫助。在 Doris 存儲層里，除了要取 key 字段外，還要取很多其他字段。Doris是 列存數(shù)據(jù)，當(dāng)把 nation 表過濾出的 5 個 id 發(fā)送給 supplier 以后，supplier 上其他字段的訪問數(shù)據(jù)量也會減少，我們把這稱為延遲物化。像左邊這樣，supplier 其他字段都需要讀取出來。而在右邊情況下，可以通過 index，只需要點查取出相關(guān)的行。所以，有了 Runtime Filter 加持后，右邊的 plan 反而比左邊更有效了。但是 Runtime Filter 又有不確定性，因為無法確定 Runtime Filter 有多高的過濾率，這個依賴統(tǒng)計推導(dǎo)。同時，可能因為 Runtime Filter 等待時間過長，導(dǎo)致整個查詢時間變長。如果要實現(xiàn)剛才那種理想的運行效果，supplier 掃描必須要等到 region 掃描完成，nation 掃描完成，才能得到有效的Runtime Filter。假設(shè) region 掃描變慢了，nation 沒有等到 region 的掃描結(jié)果，直接生成 Runtime Filter 交給 supplier，其實沒有任何過濾效果。所以Runtime Filter 的過濾效果比較動態(tài)，這給查詢優(yōu)化帶來非常大的挑戰(zhàn)。這也是我們下一步要去解決的重要問題。

五、問答

1、CostAndEnforce 在優(yōu)化器優(yōu)化的思路是什么？

打出火焰圖，找出熱點，分析熱點部分有沒有做重復(fù)計算，比如有沒有做重復(fù)的統(tǒng)計信息推導(dǎo)，有沒有重復(fù)計算 cost。通過火焰圖，可以得到一些線索，更快找到從哪里分析出現(xiàn)的重復(fù)計算。

2、當(dāng)過濾條件很多，或者非等值的條件下，Runtime Filter 效率是否會下降很多？

不會。如果對右表有越多的過濾條件，Runtime Filter 效率會越高，因為對左表的過濾性會更強。如果沒有等值條件，不會生成 runtimeFilter

3、Runtime Filter 對 left join 是否有優(yōu)化效果？

對 left outer join 沒有優(yōu)化效果。因為不能在左表的掃描端把數(shù)據(jù)過濾掉，因為左表不管能否跟右表匹配，都需要把數(shù)據(jù)輸出。所以 left outer join 不能運用Runtime Filter。

4、Doris 支持分頁查詢么？

分頁查詢支持。

5、左表等 Runtime Filter 要等多久？

這是經(jīng)驗參數(shù)，我們默認等 1 秒。

6、優(yōu)化器以后可以交給 AI 嗎？

DB for AI 是一個新的研究方向。幾十年來，優(yōu)化器我覺得沒有本質(zhì)的進展，都是拿著同一件武器——動態(tài)規(guī)劃，只是打的不同的拳法。可能 AI 是一個新的武器，但是目前還沒有看到特別的效果，特別是 ad-hoc 查詢中。