最佳化器技術被公認為資料庫領域中最有挑戰性的技術之一，同時也是對資料庫效能影響最大的一個模組。最佳化器直接影響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 兩種不同模式的流量。

【相關閱讀】

#阿里雲# #資料庫#