一、重塑

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

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

最后優化器本身的架構，基本只是做樹的兩輪遍歷。這對優化規則的有很大限制。

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

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

二、優化的本質

下面從 SQL 的本質來講解一下優化器的地位。

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

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

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

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

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

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

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

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

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

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

三、優化瓶頸

艱苦奮戰了大半年后，系統基本成型。接著就開始關注性能。

第一個很重要的性能提升來源于 RBO 階段的一次重要重構。Cascading 框架有一個 Memo 結構，相當于一個小賬本，所有規則產生的 plan 都用 Memo 記下來。這是CBO階段執行動態規劃算法所需要的。我們知道所有動態規劃方法都有小賬本，在 Cascading 中的小賬本就叫做 Memo。我們一開始就像論文中的流程一樣，將 plan 放在 Memo 中，對plan進行改造時再從 Memo 中把 plan 片段取出來，這個過程叫 copyIn，copyOut。RBO 階段，總是用一個新的 plan 來替代老的 plan，我們仍然遵循老的套路，每次生成新的plan，就放入 Memo 中，進行下一個規則替換時，再將這個 plan 從 Memo 中拿出來。反復 copyIn，copyOut 的動作其實是多余的。于是美團的華建老師閉關好幾周，給大家提交了一個巨大的pr，RBO 的效率得到了飛速的提升。當然我們也很痛苦，因為需要重新看一遍RBO 的所有代碼。但我們非常歡迎有越來越多這樣的痛苦。

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

四、挑戰

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

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

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

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

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

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

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

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

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

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

五、問答

1、CostAndEnforce 在優化器優化的思路是什么？

打出火焰圖，找出熱點，分析熱點部分有沒有做重復計算，比如有沒有做重復的統計信息推導，有沒有重復計算 cost。通過火焰圖，可以得到一些線索，更快找到從哪里分析出現的重復計算。

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

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

3、Runtime Filter 對 left join 是否有優化效果？

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

4、Doris 支持分頁查詢么？

分頁查詢支持。

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

這是經驗參數，我們默認等 1 秒。

6、優化器以后可以交給 AI 嗎？

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