01、概述
對于資料庫來說，其中倆個核心的子產品是：優化器和執行引擎。優化器負責給執行引擎提供輸入，它接收來自 SQL Parser 解析好的 AST 樹，然後需要從所有可能的計劃中選擇代價最優的計劃提供給執行引擎。基于代價的優化器本質上是一個複雜的搜尋問題，想要解決好這個問題，需要從四個方向入手：
1）搜尋架構：既然是搜尋問題，那麼就需要一個搜尋架構來承載這個問題。從資料庫的發展曆程來看，基于 Cascades 的搜尋架構已經成為了業界标準，包括商業資料庫 SQL Server 以及開源資料庫 GP/ORCA 都采用 Cascades 實作。AnalyticDB CBO 也是基于 Cascades 論文實作的。
2）分布式并行計劃：相對于傳統的單機版資料庫，AnalyticDB 是一個分布式 MPP 資料庫，優化器生成的計劃是一個分布式并行計劃。是以需要把分布式并行計劃的生成和搜尋架構結合起來，基于代價選擇最佳的分布式并行計劃。
3）代價估算：代價估算是優化器能否尋找到最優計劃的關鍵因素，代價估算做不好，優化器不可能做好。代價估算涉及到統計資訊的推導和代價模型。統計資訊的推導依賴于：原始表的統計資訊、中間算子的推導算法、對資料的各種假設（均勻性假設、獨立性假設、包括性假設、包含性假設）以及在一些極端情況下的猜測。是以統計資訊的推導存在大量的不确定性，也正是因為這些不确定性，極大的加劇了優化器尋找最優解的難度。
4）統計資訊收集：收集必要的統計資訊是 CBO 工作的前提，CBO 和統計資訊之間的關系猶如一把槍和彈藥之間的關系，槍再好如果沒有充足的彈藥的話，那麼無異于巧婦難為無米之炊。統計資訊需要做到：基本資訊能夠自動化收集，自動化更新，進階統計資訊可以手動收集，為 CBO 提供可靠的、多元度的統計資訊。
02、架構
搜尋架構
搜尋架構在整個 CBO 中處于非常中心的一個位置，它會調用 Property Enforcement 架構，生成分布式執行計劃，然後調用代價估算子產品，給每一種候選分布式執行計劃評估代價，最終基于代價選擇最優的分布式執行計劃。搜尋架構包括以下幾個部分：
Memo 表示搜尋空間：對于一個查詢計劃來說，首先需要把它初始化，形成初始化的搜尋空間。随着搜尋的進行，搜尋空間會不斷擴充。由于搜尋空間會非常龐大，是以 Memo 需要做到高效存儲。
Search 表示搜尋算法：搜尋算法由三部分組成，第一部分用于遞歸周遊搜尋空間，第二部分用于調用展開規則産生新的等價候選計劃，擴充搜尋空間，第三分部用于用于推導分布式計劃的屬性要求并計算代價值，進而尋求最優的分布式執行計劃。
Scheduler 表示排程搜尋算法的排程器：在目前的 AnalyticDB CBO 版本中，基于單線程和棧實作：把搜尋任務壓入到一個棧中，然後循環取棧中的任務去執行，直到任務結束。
考慮到其他開源優化器産品，例如 ORCA 提到了多線程并行搜尋的理念，我們預留了多線程排程器的接口，相對于優化器衆多棘手的問題來說，它的優先級并不是那麼高，實作并行搜尋的好處是非常明顯的，它可以顯著降低任務排程的執行時間，充分發揮多核并行的能力，從整個查詢的角度來看，可以縮短查詢優化的耗時，進而降低整體查詢的耗時。但是并行搜尋帶來的線程同步問題，以及線程間依賴處理問題，挑戰還是很大的。
Rule 表示展開規則：展開規則用于生成等價候選計劃，等價候選計劃會被放入到 Memo 中，形成完整的搜尋空間。展開規則決定了優化器可以展開多少種候選計劃，是以展開規則的種類，以及每種展開規則的算法效率對 CBO 來說也是至關重要的。展開規則種類越多，搜尋空間就越完善，也就更有可能尋求到最優解，同時每種展開規則的算法越高效，生成完整的搜尋空間就越高效，查詢優化就越快。
分布式并行計劃
相對于傳統的單機版資料庫來說，分布式 MPP 資料庫給優化器帶來了新的挑戰。在分布式 MPP 資料庫中，資料的分布屬性變得十分的重要，它會直接影響到資料的正确性。為了滿足不同算子對資料分布的要求，我們往往需要做資料重分布。
然而資料的重分布，也就是資料 shuffle 的代價非常昂貴，是以，在保證資料正确性的前提下，盡可能的減少資料 shuffle，可以大幅度提升分布式計劃的執行性能。作為分布式 MPP 資料庫優化器來說，需要把資料的 Partitioning 屬性，以及 Sorting、Grouping 屬性，也納入到搜尋空間來綜合考慮，基于代價選擇最優的分布式并行執行計劃。
是以我們設計實作了一套完整的 Property Enforcement 架構，用于描述在分布式場景下，分布式計劃對資料分布的要求。同時我們把 Property Enforcement 的過程和搜尋架構無縫的結合在一起，實作了面向分布式 MPP 資料庫的 CBO。
代價估算
代價估算是整個 CBO 品質好壞的關鍵因素，代價估算做的好，CBO 才有可能選擇出最優的計劃，它包括三個部分。
Statistics 用于描述原始表的統計資訊。包括表級别的統計資訊 Row Count，單個字段的統計資訊：每個字段的 NDV 值（distinct 值），Max 值，Min 值，NULL 值，Histogram 值（分布資訊，用于區間查詢）, Count-Min Sketch 值(用于等值查詢)，DataSize 值。這些統計資訊我們把它歸納為基礎統計資訊，需要做到自動收集，自動更新。
同時考慮到多個字段之間的關聯度、Functional deplendency、資料的傾斜等這些因素對統計資訊估算的影響，還會提供指令行工具，手動收集這些資訊，對于這些需要手動收集的資訊，我們把它歸納為進階統計資訊，隻有在必要的時候，才需要顯示的手動收集。另外，對于一些複雜的 predicate，例如 like，那麼即使收集了 Histogram 也無法支援這種場景，是以我們也會在運作時基于動态采樣來擷取對應的統計資訊。
Stats Derivation 用于推導經過各個算子之後的統計資訊。統計資訊的推導依賴于原始表的統計資訊，數學公式，對資料屬性的假設（例如，資料的分布是均勻的，多列之間的選擇率是沒有相關性的），以及極端情況下，啟發式的假設（例如對于一個使用者自定義的 UDF，它的選擇率隻能給一個預設值）。
統計資訊的推導的好壞對優化器來說至關重要，這也一直是學術界的研究熱點。本質上來說，隻有打破對資料屬性的假設，才有可能使得統計資訊的估算做到知其然知其是以然，然而打破這些假設，依賴于對原始資料的分析，生成更多元度的統計資訊，必然也要付出更多的代價。
Cost Model 表示代價模型。代價模型的工作必須要建立在合理的統計資訊推導的基礎之上，否則它的意義不會很大。代價模型需要對實際的計算模型進行評估，把統計資訊轉換為可以量化的代價值，進而為優化器提供決策依據。
統計資訊收集
Analyze 用于收集統計資訊。對于商業資料庫來說，為了提升使用者體驗，做到開箱即用，都緻力于 Auto analyze，即統計資訊收集的自動化，以及自動更新。但是收集本身也是有代價的，是以我們把統計資訊分為倆類：基礎統計資訊和進階統計資訊。
基礎統計資訊就是前面提到的：表級别的統計資訊 row count，單個字段的統計資訊：每個字段的 NDV 值（distinct 值），Max 值，Min 值，NULL 值，Histogram 值（分布資訊，用于區間查詢），Count-Min Sketch 值(用于等值查詢)，DataSize 值。基礎統計資訊必須要做到自動化收集、自動化更新，否則很可能由于這些統計資訊的缺失，導緻優化器産生災難性的計劃。
同時為了提升優化器在複雜情況下的決策品質，還提供了一些進階的指令用于收集更加複雜的統計資訊，例如可以收集 column group 的統計資訊，來擷取多個字段之間的關聯度資訊。進階統計資訊需要手工觸發收集，隻有在必要的時候才會收集。
基于 Analyze 指令收集統計資訊，無論是自動化收集，還是手工收集，本質上來說所，它都是一個獨立的程序：Analyze 會調用 Data Profiling 任務，對原始資料進行分析，生成統計資訊，并存儲在 Metadata 庫中。
考慮到實際情況下，可能存在一些非常複雜的查詢條件，不管是基礎的統計資訊還是進階統計資訊，都無法很好的對它做合理的估算，這個時候，dynamic sampling 動态采樣就可以發揮它的價值，動态采樣會實時下發采樣，擷取必要的統計資訊，提升優化器的決策品質。
其次，動态采樣也可以作為統計資訊收集的一種兜底政策，當基礎統計資訊由于某些原因導緻未收集的情況下，動态采樣的存在可以避免優化器由于缺失統計資訊而産生災難性的計劃。但是動态采樣是在查詢優化階段同步阻塞執行的，是以它必然會增加查詢優化的整體耗時，同時也會增加整個資料庫系統的負載，是以我們嚴格限制動态采樣的使用場景。
03、設計與實作
接下來我們會通過一個例子來展開搜尋架構、Property Enforcement 架構、以及代價估算的設計與實作。
查詢語句
這一個簡化版的 TPCH q3，非常典型的三表 Join。其中 customer 表按照 c_custkey 進行分區，orders 表按照o_orderkey 進行分區，lineitem 表按照 l_orderkey 進行分區。
SELECT
l_orderkey,
o_orderdate,
o_shippriority
FROM
customer,
orders,
lineitem
WHERE
c_custkey = o_custkey
AND l_orderkey = o_orderkey 查詢優化
在進入到 CBO 之前，原始的執行計劃如下圖所示，customer 表和 orders 表先 Join，Join 的結果再和 lineitem 表 Join，然後輸出結果。
進入到 CBO 後，首先需要把查詢計劃轉換為 Group 和 GroupExpression，并初始化 Memo 搜尋空間。可以看到共有 6 個 Group，每個 Group 都有一個 GroupExpression。Group 和 GroupExpression 都是搜尋空間裡面的重要概念，關于它的詳細介紹可以參考：AnalyticDB Cost based Optimizer 搜尋架構，這裡不展開。
簡單來說：對于邏輯等價的，可以産生相同結果的 Logical Expression 和 Physical Expression 的集合稱為 Group，GroupExpression 則包括 Logical GroupExpression 和 Physical GroupExpression，每一種 GroupExpression 表示一種等價候選計劃。
在這裡，我們為了簡化描述，隻考慮 Join 的 Order，以及分布式 Join 情況下，Repartition Join 和 Replicate Join 這兩種屬性要求，對于 Join 的算法預設隻考慮 Hash-join 實體實作。
其他算子：TableScan 和 Output 也預設隻有一種實體實作。排程器排程搜尋任務，執行搜尋流程，擴充搜尋空間。可以看到随着搜尋算法的不斷疊代，Memo 裡面的 Group 和 GroupExpression 會新增：白色表示 Logical GroupExpression，灰色表示 Physical GroupExpression。
可以看到，在應用了 Join 的結合律之後，新産生了 Group7 和 Group8 這倆個 Group；同時應用了 Join 的交換律之後，Group5 和 Group3 裡面新增了很多等價的 Logical GroupExpression；同樣 Group7 和 Group8 裡面也有等價的 Logical GroupExpression。
最終考慮倆種分布式 Join 實作：Repartition Join 和 Replicate Join，這樣就生成了完整的搜尋空間。
當整個搜尋空間被完整的擴充出來之後，接下來需要調用 Property Enforcement 架構，對每一種實體執行計劃，去 Enforce 必要的屬性，進而滿足分布式執行計劃的要求，然後再調用代價估算子產品，去計算每一種分布式計劃的代價，并把代價最小的計劃标記為最優解，也就是 Winner。當每一個 Group 的 Winner 都被計算出來之後，将每個 Winner 串接起來，就是最優的分布式執行計劃。
關于 Property Enforcement 和代價估算的詳情，可以參考下面這三篇文章，這裡不展開。
AnalyticDB Cost based Optimizer 分布式并行計劃
AnalyticDB Cost based Optimizer 代價估算
AnalyticDB Cost based Optimizer 統計資訊收集
下圖中黑色意味着 Winner，表示的是在滿足某種屬性要求的情況下，代價最低最低的實體執行計劃。
我們周遊每個 Group 的 Winner，将 Winner 串接起來，就形成了最優的分布式執行計劃。
每一個 Winner 經過 Property Enforcement 之後，都會在必要的時候插入必要的 Exchange 節點，來滿足分布式計劃的屬性要求，是以生成的分布式執行計劃如下圖所示。可以看到：首先 customer 表做了一個全表廣播到所有節點，進而滿足和 orders 表 Join 的要求，Join 之後的結果按照 order 表分布，orders 表和 lineitem 表資料分布本身就滿足 Join 的要求，是以不需要插入 Exchange 節點，最終 Join 的結果要輸出到 Output 節點，是以插入 Gather 節點，彙總到單節點。
04、參考
An Overview of Query Optimization in Relational Systems
The Cascades Framework for Query Optimization
Efficiency in the columbia database query optimizer
Orca: A Modular Query Optimizer Architecture for Big Data
Incorporating Partitioning and Parallel Plans into the SCOPE Optimizer
Profiling Relational Data – A Survey