作者：徒南
優化器技術被公認為資料庫領域中最有挑戰性的技術之一，同時也是對資料庫性能影響最大的一個子產品。優化器直接影響SQL具體如何運作的執行計劃，好的執行計劃可以在毫秒内完成計算，而壞的執行計劃則可能是分鐘級或小時級别，兩者性能可以相差成千上百倍。這篇文章将會為大家介紹PolarDB-X優化器的技術選型理由、技術架構與核心特性，幫助大家更深入地了解PolarDB-X優化器。
- 以INGRES、早期Oracle為代表的啟發式優化技術，主要優化手段有過濾條件下推，列裁剪，之後再做基于Cardinality的Join順序調整。純啟發式優點就是簡單，缺點是當查詢稍微複雜就會導緻找不到好的執行計劃，并且會依賴一些很trick的魔數來調優。
- 以System-R、早期IBM DB2、以及絕大多數開源資料庫(MySQL, PostgreSQL)為代表的啟發式+基于代價的Join Reorder優化技術。優點相比于純啟發式優化，優化器針對（複雜查詢）Join順序，會基于代價利用自底向上的動态規劃選擇最優的Join順序。缺點是搜尋空間比較受限不一定能找到最優的執行計劃，代價模型中需要顯式考慮像排序的實體屬性。
- 以IBM STARBURST、DB2、Oracle為代表的基于轉換規則及代價的優化器技術。相比于階段2，除了考慮代價，這類優化器已經抽象出作用于關系代數算子的轉換規則（可以通過DSL編寫）。優點是從工程角度上更易了解，維護，測試覆寫。缺點是優化規則會存在複雜的依賴關系，應用順序需要人為指定。
- 以 Volcano/Cascades、SQL Server為代表的基于規則轉換及代價的自頂向下動态規劃優化技術（Volcano/Cascades模型）。相比于階段3，它将優化的搜尋過程做成了統一的架構，添加新的優化隻需要關注優化規則本身，不需要關注規則的應用順序，具有很高的擴充性。同時自頂向下的搜尋具有一個很吸引人的特性就是搜尋空間的剪枝，剪枝可以保證執行計劃最優性的情況下減少搜尋空間的搜尋，提升優化效率。另外優化器作為一個資料庫領域中很複雜的子產品，任何的改動都可能涉及大量SQL的性能變化，從軟體工程的角度，借助Volcano/Cascades模型的子產品化及擴充性，優化器的性能可以被持續地調優和改進。
正是基于上面的考慮，PolarDB-X優化器被設計成一款以Volcano/Cascades模型作為架構的基于代價的優化器，它可以為每一條SQL構造出搜尋空間，并根據資料的統計資訊，基數估計，算子代價模型為搜尋空間中的執行機計劃估算出執行所需要的代價(CPU/MEM/IO/NET)，最終選出代價最小的執行計劃作為SQL的具體執行方式。我們知道PolarDB-X作為一款雲原生分布式資料庫，具有線上事務及分析的處理能力(HTAP)、計算存儲分離、全局二級索引等重要特性，PolarDB-X優化器在這些特性中扮演了非常核心的角色。
優化器架構
優化器接受到SQL後會将它解析、轉換成由關系代數算子組成的邏輯執行計劃。整個PolarDB-X優化器中的具體優化手段都通過轉換規則(Transformation Rule)來表達，轉換規則會比對特定結構的關系代數算子并将其轉成等價的算子。
PolarDB-X的優化器的優化階段主要分為三個：
- Query Rewriter，基于RBO的啟發式優化階段，處理傳統的邏輯優化如：子查詢去關聯化，列裁剪，謂詞推導與下推，啟發式Join Reorder（超多張表）等。這個優化階段的特性是不斷啟發式地對同一個執行計劃做邏輯優化，優化通常很快，且隻做收益非常明确的優化器。
- Plan Enumerator，基于CBO的Volcano/Cascades模型，是最為核心優化階段，它會應用轉換規則為計劃生成搜尋空間，既包含了邏輯優化如：Join Reorder（Bushy,Zig-Zag,Left Deep空間動态選擇），算子交換，計算下推等，也包含實體優化如：全局二級索引選擇，實體算法選擇等。搜尋空間被完全展開并搜尋過後，每個實體執行計劃都會根據具體的實體算子估算出執行所需要的代價（通過CPU/MEM/IO/NET表示）。最後代價最低的實體執行計劃将會被選擇出來。在整個優化過程中，這一步耗時占比最高，因為它需要考慮整個搜尋空間。
- MPP Planner，多機并行計算優化階段，處理并行算子生成，算子間Shuffle的選擇與消除，RunTimeFilter的生成及下推等。這一優化階段專門用于優化OLAP的查詢，保證可以充分利用多個節點的計算資源。
此外還有統計資訊、代價模型、基數估計(Cardinality Estimation)等重要子產品，好的優化效果依賴于準确的資料統計資訊，PolarDB-X維護了豐富的統計資訊用于輔助優化器，我們會為每張表維護行數，直方圖，列長度，NDV值等統計資訊。PolarDB-X的代價模型充分考慮了計算存儲分離架構下的算子執行代價，與傳統資料庫相比會更精細地考慮網絡的代價。
核心特性
HTAP
在HTAP混合負載處理方面，PolarDB-X提供智能路由的能力。我們知道傳統的OLTP和OLAP的解決方案是基于簡單的讀寫分離或者ETL模型，它們存在存儲成本高、實時性差、鍊路和維護成本高等劣勢。通過PolarDB-X可以統一處理HTAP負載，保證TP事務低延遲，同時保證AP分析查詢充分利用計算資源，且保證資料的強一緻。優化器在HTAP的負載識别中起了關鍵的作用。優化器會基于代價分析出查詢的CPU，記憶體，IO，網絡等核心資源消耗量，将請求區分為OLTP與OLAP請求。OLTP請求被路由至主副本執行, 相比于傳統的讀寫分離方案能夠提供更低的延遲。而分析出的OLAP請求将會通過MPP并行優化階段，生成多機分布式的執行計劃，下發至隻讀計算叢集計算，通路隻讀副本，提供實體隔離，同時可以利用隻讀副本一緻性讀能力，保證強一緻讀。通過智能路由，使用者可以非常透明地使用PolarDB-X同時處理OLTP及OLAP的訴求。
計算下推
PolarDB-X支援Partition Aware的計算下推。我們知道在計算與存儲分離的架構下，我們獲得了幾乎無限彈性擴充計算節點的scale out能力，但代價是計算與存儲間的網絡互動開銷。為了盡可能避免這一開銷，可以通過計算下推，減少網絡互動，計算離資料更近，計算效率獲得提升，是以計算下推成了非常重要的優化手段。PolarDB-X使用者大量使用拆分表（及廣播表），将資料根據拆分方式打散至不同的分片上。PolarDB-X可以基于代價充分考慮存儲（如存儲的計算模型）及資料（是否具有索引）等特性，将查詢中的部分計算(如：Join，Agg，Sort)下推至存儲層進行計算。以TP場景下的Join的下推為例：如果Join不下推，我們會面臨一個網絡Lookup，通過網絡Lookup的性能會劣于本地的磁盤Lookup，而通過計算下推我們就可以獲得彈性擴容的同時，享受單機資料庫的性能體驗。
全局二級索引選擇
PolarDB-X為使用者提供全局二級索引，并提供資料強一緻性。在建立全局二級索引後，優化器可以立馬感覺到表存在全局二級索引，并為查詢優化出更優的查詢計劃。以訂單為例子，使用者将訂單表按照買家次元作拆分，以買家次元作為查詢可以獲得非常好的性能。但按賣家次元進行查詢時，需要将所有資料分片查詢一遍才能得到完整結果。而通過為訂單表建立賣家次元的全局二級索引，優化器就可以優化出通路全局二級索引（回表）的執行計劃，避免全分片掃描，提升性能。另外，全局二級索引支援覆寫索引，優化器結合列裁剪優化，當發現使用者查詢表的列被全局二級索引覆寫時，可以做到隻通路全局二級索引，避免回表。全局二級索引還可以和Partition Aware的計算下推做共同優化，例如：兩張表的Join的場景，兩表的拆分方式不一緻導緻Join無法下推的時候，我們可以将表按照Join Key共同的次元建立全局二級索引，達到計算下推的目的。
優化例子
下面讓我們一起通過一個TPCH Q3作為例子看看PolarDB-X如何優化一條SQL吧。首先TPCH Q3這條SQL會被轉化為如下的邏輯執行計劃(LogicalPlan)
這個邏輯執行計劃包含Agg、Join、Filter、Project、LogicalView等關系代數算子，PolarDB-X通過LogicalView算子來抽象下發至存儲執行的Plan(是以下推算子在優化中就是将算子下推進LogicalVIew算子)。
接着我們一步一步看一下RBO，CBO，MPP三個優化階段分别做了哪些優化。
- RBO啟發式階段，可以看到經過RBO後的邏輯執行計劃已經将Filter，Project等算子下推到了LogicalVIew，也就是完成了列裁剪，謂詞下推等優化。同時我們可以看到原來Orders，Lineitem表也因為擁有相同拆分規則被下推到了同一個LogicalVIew，完成了計算的下推優化。
- CBO基于代價的優化階段，可以看到邏輯執行計劃變成了實體執行計劃，其中Join和Agg分表選擇使用HashJoin和HashAgg作為實體算子。在這背後，優化器實際上已經考慮了不同的Join順序，不同的Join與Agg算法，被選擇出來的就是具有最低代價的實體執行計劃。
- MPP分布式優化階段，可以看到在算子間多了Exchange算子，用于描述資料如何在多個計算節點間進行Shuffle。這使得執行器可以知道如何在多個計算節點中傳輸資料，并行計算。此外，還可以看到RunTimeFilter生成，并下推到存儲節點執行提前過濾資料，減少網絡傳輸開銷。
總結
PolarDB-X 查詢優化器主要基于 Volcano/Cascades 模型設計，是一個基于代價的優化器（CBO），優化過程主要分為查詢改寫、計劃枚舉、MPP 優化三個階段。其中，查詢改寫階段負責啟發式優化規則（例如查詢下推）；計劃枚舉階段負責索引選擇和決定 Join Order 等，是最核心的階段；如果優化器判斷執行計劃代價較高、需要 MPP 執行，則會通過 MPP 優化階段将執行計劃進一步優化為分布式執行計劃。通過這樣的設計，讓 PolarDB-X 能很好的适應 HTAP 場景，兼顧 TP 與 AP 兩種不同模式的流量。