PolarDB：列存索引技術架構介紹

通過一套白名單機制來實現相容性。 使用白名單機制是基於如下幾點考量。

• 系統可用資源（主要是記憶體）限制。

  一般情況下，不會為資料庫中全部表的所有列上都建立列索引。當一條查詢語句中使用到的列沒有在列存中存在時，其不能在列存上執行。

• 效能。

  重寫一套面向列存的SQL執行引擎，包括所有的物理執行運算元和運算式計算，其所覆蓋的情境相對MySQL原生行存能夠支援的範圍有欠缺。當下發的SQL語句中包含一些列存索引不支援的運算元片段或者列類型時，需要能夠識別攔截並切換回行存執行。

目前，白名單規則校正的內容包含SQL語句中的資料類型、運算元、計算運算式以及其他情境。其他情境如不支援multi statement等。

MySQL已經發展了數十年，其支援的各種列類型和SQL文法非常豐富。在IMCI中，初期重點最佳化在分析型查詢語句中最常見的SQL效能問題。即使適用情境有所限制，IMCI能夠啟動並執行SQL文法對MySQL功能的相容性也遠超絕大部分OLAP系統。對於那些不能在列存上執行的SQL，則直接回退到MySQL原生執行引擎，因此實現了100%的MySQL相容。

Plan轉換的目的是將MySQL的原生邏輯執行計畫表示方式AST轉換為IMCI的Logical Plan。在產生IMCI的Logical Plan之後，會經過Optimize過程，繼而產生Physical Plan。

Plan轉換隻需要遍曆整個執行計畫樹，將MySQL最佳化後的AST轉換成以relation operator為節點的樹狀結構即可。在這個過程中，會進行類型的隱式轉換，以相容MySQL靈活的類型系統。

Plan轉換產生的是一個等價的Logical Plan，其需要被轉換成Physical Plan才能被執行器執行。目前IMCI的Optimizer比較簡單，除了一些基本的執行計畫最佳化（如決策是使用HashJoin還是使用NestedLoop Join）外，Optimizer最主要的作用是將目前IMCI執行器不支援的子查詢轉換為一個等價的Join操作。

由於存在行存和列存兩套執行引擎，最佳化器在選擇執行計畫時有了更多的選擇，其可以對比行存執行計畫的Cost和列存執行計畫的Cost，並使用代價最低的執行計畫。

在PolarDB中，除原生MySQL的行存串列執行外，還有能夠發揮多核計算能力的基於行存的Parallel Query功能。因此，實際最佳化器會在行存串列執行、行存Parallel Query、以及IMCI三個之中選擇其一。在目前的迭代階段，最佳化器按如下的流程執行：

1. 執行SQL的Parse過程並產生LogicalPlan，然後調用MySQL原生最佳化器，並執行最佳化操作（join order等）。同時該階段獲得的邏輯執行計畫會轉給IMCI的執行計畫編譯模組，並嘗試產生一個列存的執行計畫（此處可能會被白名單攔截並復原回行存）。

2. PolarDB的Optimizer會根據行存計劃，計算得出一個面向行存的執行Cost。如果此Cost超過一定閾值，則會嘗試下推到IMCI執行器使用IMCI_Plan執行。

3. 如果IMCI無法執行此SQL，則PolarDB會嘗試編譯出一個Parallel Query的執行計畫並執行。如果無法產生PQ的執行計畫，則說明IMCI和PQ均無法執行此SQL，則復原回行存執行。

上述策略是基於這樣一個判斷，從執行效能上進行對比：行存串列執行 < 行存並存執行 < IMCI。 對比SQL相容性，IMCI < 行存並存執行 < 行存串列執行。但是實際情況會更加複雜，例如：某些情況下，基於行存有序索引覆蓋的並行Index Join會比基於列存的Sort Merge join有更低的Cost。按照當前策略，則會選擇IMCI列存執行。

IMCI執行器引擎使用經典的火山模型，但是藉助了列存儲存以及向量執行來提升執行效能。

火山模型中，SQL產生的文法樹所對應的關係代數中，每一種操作會抽象為一個Operator，執行引擎會將整個SQL構建成一個Operator樹，查詢樹自頂向下調用Next()介面，資料則自底向上被拉取處理。該方法的優點是其計算模型簡單直接，通過把不同物理運算元抽象成一個個迭代器。每一個運算元只關心自己內部的邏輯即可，使得各個運算元之間的耦合性降低，從而比較容易寫出一個邏輯正確的執行引擎。

• 在IMCI執行引擎中，每個Operator也使用迭代器函數來訪問資料，但不同的是每次調用迭代器會返回一批資料，而不是一行，可以認為這是一個使用了向量化模式的火山模型。

  

• 串列執行受制於單核計算效率、訪存延時、IO延遲等限制，執行能力有限。而IMCI執行器在幾個關鍵物理運算元（Scan/Join/Agg等）上均並存執行。除物理運算元需要支援並行外，IMCI的最佳化器也支援產生並存執行計劃，最佳化器在確定一個表的訪問方式時，會根據需要訪問的資料量來決定是否啟用並存執行，如果確定啟用並存執行，則會參考一系列狀態資料（包括當前系統可用的CPU/Memory/IO資源、目前已經調度和在排隊的任務資訊、統計資訊、query的複雜程度、使用者可配置的參數等）。 根據這些資料會計算出一個推薦的DOP值給一個運算元，而一個運算元內部會使用相同的DOP。同時，DOP也支援使用者使用Hint進行設定。

  

基於以上兩點最佳化思路，重新實現了所有物理執行運算元，包括TableScan、HashJoin、NestedLoopJoin、Groupby等。下面以HashJoin為例展示執行器的並行化及向量化加速效果。在IMCI中，HashJoin按如下流程執行：

向量化執行解決了單核執行效率低的問題，而並存執行突破了單核的計算瓶頸。二者結合使得IMCI執行速度相比傳統MySQL行式執行有了數量級的提升。

AP型情境，SQL中經常會包含很多涉及到一個或者多個值、運算子和函數組成的計算過程，這都是屬於運算式計算的範疇。運算式的求值是一個計算密集型的任務，因此，運算式的計算效率是影響整體效能的一個關鍵的因素。

傳統MySQL的運算式計算體系以一行為一個單位的逐行運算，一般稱其為迭代器模型實現。由於迭代器對整張表進行了抽象，整個運算式實現為一個樹形結構。但是，這種抽象會同時帶來效能上的損耗，因為在迭代器進行迭代的過程中，每一行資料的擷取都會引發多層的函數調用。同時，逐行地擷取資料會帶來過多的 I/O，對緩衝也不友好。MySQL採用樹形迭代器模型，是受到儲存引擎存取方法的限制，導致其很難對這些計算複雜的邏輯進行最佳化。

而在列存格式下，由於每一列的資料都單獨順序儲存，涉及到某一個特定列上的運算式計算過程都可以批量進行。對每一個計算運算式，其輸入和輸出都以Batch為單位，在Batch的處理模式下，計算過程可以使用SIMD指令進行加速。

向量化運算式的關鍵最佳化點：

• 充分利用列式儲存的優勢，使用分批處理的模型代替迭代器模型，使用SIMD指令重寫了大部分常用資料類型的運算式核心實現。例如，所有數字類型（int、decimal、double）的基本數學運算（+、 -、*、/、abs），全部都使用對應的SIMD指令實現。在AVX512指令集的加持下，單核運算效能數倍提升。

  

• 採用了與PostgreSQL類似運算式實現方法：在SQL編譯及最佳化階段，IMCI的運算式以一個樹形結構來儲存（與現有行式迭代器模型的表現方法類似）。但是，在執行之前會對該運算式樹狀架構進行一個後序遍曆，將其轉換為一維數組來儲存，在後續計算時只需要遍曆該一維數組結構即可以完成運算。由於消除了樹形迭代器模型中的遞迴過程，計算效率更高。同時該方法對計算過程提供簡潔的抽象，將資料和計算過程分離，適合并行計算。

在MySQL外掛程式式的儲存引擎架構下，增加列存支援最簡單的方案是實現一個單獨的儲存引擎，如Inforbright以及MarinaDB的ColumnStore都採用了這種方案。而PolarDB採用了將列存實現為InnoDB的二級索引方案，主要基於如下幾點考量：

• InnoDB原生支援多索引，Insert、Update和Delete操作都會以行粒度apply到Primary Index和所有的Secondary Index上，並且保證事務。將列存實現為一個二級索引可以複用這套交易處理架構。

• 在資料編碼格式上，二級索引的列存可以和其他行存索引使用完全一樣的格式，直接記憶體拷貝即可，不需要考慮charset和collation等資訊。

• 二級索引操作非常靈活，可以在建表時指定索引所包含的列，也可以後續通過DDL語句對一個二級索引中包含的列進行增加或者刪除操作。例如，使用者可以將需要分析的int、float和double列加入列索引，而對於一般只需要點查但是又佔用大量空間的text和blob欄位，則可以保留在行存中。

• 崩潰恢複過程可以複用InnoDB的Redo交易記錄模組，與現有實現無縫相容。同時也方便PolarDB的物理複製過程，支援在獨立RO節點或者Standby節點上產生列存索引提供分析服務。

• 二級索引與主表有一樣的生命週期，方便管理。

  

如上圖所示，在PolarDB中，所有Primary Index和Secondary Index都實現為一個B+Tree。而列索引在定義上是一個Index，但其實是一個虛擬索引，用於捕獲對該索引覆蓋列的增刪改操作。

對於上面的表，其主表（Primary Index）包含（C1、C2、C3、C4、C5） 5列資料， Secondary Index索引包含（C2、C1）兩列資料，在普通二級索引中，C2與C1編碼成一行儲存在B+tree中。而其中的列存索引包含（C2、C3、C4）三列資料。在實際實體儲存體時，會對三列進行拆分隔離儲存區 (Isolated Storage)，每一列都會按寫入順序轉成列存格式。

列存實現為二級索引的另一個好處是執行器的工程實現非常簡單，在MySQL中已經存在覆蓋索引的概念，即一個查詢所需要的列都在一個二級索引中儲存，則這個二級索引中的資料滿足查詢需求，使用二級索引相對於使用Primary Index可以極大減少讀取的資料量進而提升查詢效能。當一個查詢所需要的列都被列索引覆蓋時，藉助列存的加速作用，可以數十倍甚至數百倍的提升查詢效能。

對Column Index中的每一列，其儲存都使用了無序且追加寫的格式。結合標記刪除及後台非同步compaction實現空間回收。其具體實現上有如下幾個關鍵點：

• 列索引中記錄按RowGroup進行組織（目前每個RowGroup包含64K行），每個RowGroup中不同的列會各自打包形成DataPack。

• 每個RowGroup都採用追加寫，分屬每個列的DataPack也是採用追加寫入模式。對於一個列索引，只有Active RowGroup負責接受新的寫入。當該RowGroup寫滿之後即凍結，其包含的所有Datapack會轉為壓縮格儲存到磁碟上，同時記錄每個資料區塊的統計資訊便於過濾。

• 列存RowGroup中每新寫入一行都會分配一個RowID用於定位，屬於一行的所有列都可以用該RowID計算定位，同時系統維護PK到RowID的映射索引，以支援後續的刪除和修改操作。

• 更新操作採用標記刪除的方式，對於刪除操作直接設定BitMap即可。對於更新操作，首先根據RowID計算出其原始位置並設定刪除標記，然後在ActiveRowGroup中寫入新的資料版本。

• 當一個RowGroup中的無效記錄超過一定閾值，則會觸發後台非同步compaction操作，其作用一方面是回收空間，另一方面可以讓有效資料存放區更加緊湊，提升分析型查詢單的效率。

  

採用這種資料群組織方式，一方面滿足了分析型查詢按列進行批量掃描過濾的要求。另一方面對於TP型事務操作影響非常小，寫入操作只需要按列追加寫到記憶體即可，刪除操作只需要設定一個刪除標記位。而更新操作則是一個標記刪除附加一個追加寫。列存在支援事務層級更新的同時，幾乎不影響OLTP的效能。

以下兩種情況會執行行轉列操作：

• 第一種情況：使用DDL語句對部分列建立列索引（對一張已存在的表有分析型需求），此時需要掃描全表資料以建立列索引。

• 第二種情況：在事務操作過程中對涉及到的列執行行轉列。

對於全錶行轉列的情形，使用並行掃描的方式對InnoDB中的Primary Key進行掃描，並依次將所有涉及到的列轉換為列存形式，該操作的速度非常快，其基本僅受限於伺服器可用的IO吞吐速度和CPU資源。該操作是一個online-DDL過程，不會阻塞線上業務的運行。

在一張表上建立列索引之後，所有的更新事務將會同步更新行存和列存資料，以保證二者的事務一致性。下圖示範了開啟和關閉IMCI功能的差異性。

• 未開啟IMCI功能時，事務對所有行的更新都會先加鎖，然後在對資料頁進行修改，在事務提交之前會對所有加鎖的記錄一次性釋放鎖。

• 開啟IMCI功能之後，事務系統會建立一個列存更新緩衝，在所有資料頁被修改的同時，會記錄所涉及到的列存的修改操作，在事務結束並釋放鎖之前，該緩衝會應用到列存系統。

對於一般的OLTP型請求，最後的記憶體資料頁更新只佔事務操作過程的很少一部分時間，因此此方法對TP型事務時延的影響非常小。對於操作了非常多的行的大事務，則會直接將其對列索引的更新即時應用到列存儲存，但是在事務提交之前不對外可見，也保證了大事務的提交延時增加在一個非常小的時間範圍。同時為了更進一步的降低對TP效能的影響，當AP型查詢對資料的即時性要求不高時, 列索引支援非同步應用對列存的更新操作。

列存儲存提供了與行存一樣的交易隔離等級。對於每個寫操作，RowGroup中的每一行都會記錄修改該行的事務編號，而對於DeleteBitMap，每個標記刪除操作也會記錄該標誌位的事務編號。藉助寫入事務號和刪除事務號，AP型查詢可以用非常輕量級的方式獲得一個全域一致性的快照。

由前述列舉的儲存格式可以看出，IMCI中所有的Datapack都採用無序且追加寫的方式，因此無法像InnoDB的普通有序索引那樣，可以精準的過濾掉不符合要求的資料。在IMCI中，藉助統計資訊來進行資料區塊過濾，以此來達到降低資料訪問單價的目的。

• 在每個Active Datapack終結寫入的時候，會預先進行計算，並產生Datapack所包含資料的最小值、最大值、數值的總和、空值的個數和記錄總條數等資訊。所有這些資訊會維護在DataPacks Meta元資訊地區並常駐記憶體。由於凍結的Datapack中還會存在資料的刪除操作，因此統計資訊的更新維護會放到後台完成。

• 對於查詢請求，會根據查詢條件將Datapacks分為相關、不相關、可能相關三大類，從而減少實際的資料區塊訪問。而對於一些彙總查詢操作，如count和sum等，可以通過預先計算好的統計值進行簡單的運算得出，這些資料區塊甚至都不需要進行解壓。

採用基於統計資訊的粗糙索引方案，對於一些需要精準定位部分資料的查詢並不是很友好。但是在一個行列混合儲存引擎中，列索引只需要輔助加速那些會涉及到大量資料掃描的查詢，在這個情境下使用列存索引會具有顯著的優勢。而對於那些只會訪問到少量資料的SQL，最佳化器通常會基於代價模型計算得出基於行存而得到的一個成本更低的方案。

行列混合儲存可以在一個叢集中同時支援AP型查詢和TP型查詢。但很多業務有很高的OLTP型負載，而突發性的OLAP型負載可能干擾到TP型業務的響應時延。因此負載隔離在HTAP資料庫中是一個必須支援的功能。藉助一寫多讀架構，可以非常方便地對AP型負載和TP型負載進行隔離。在PolarDB技術架構下，有如下幾個部署方式：

• 第一種方式：在RW上開啟行列混合儲存，此種部署模式可以支援輕量級的AP查詢，以TP負載為主，且AP型請求比較少時可以採用。或者使用PolarDB進行報表查詢，且資料來自批量資料匯入的情境。

• 第二種方式：RW支援OLTP型負載，並啟動一個AP型RO開啟行列混合儲存以支援查詢，此種部署模式下CPU資源可以實現100%隔離，同時該AP型RO節點上的記憶體可以100%分配給列存儲存和執行器。但是，由於使用相同的共用儲存，因此在IO上會相互產生一定影響。

• 第三種方式：RW和RO均支援OLTP型負載，在單獨的Standby節點開啟行列混合儲存以支援AP型查詢，由於Standby是使用獨立的共用儲存叢集，這種方案在第二種方案支援CPU和記憶體資源隔離的基礎上，還可以實現IO資源的隔離。

除上述部署架構上的不同，和可以支援的資源隔離不同之外。在PolarDB內部對於一些需要使用並存執行的大查詢，支援動態並行度調整（Auto DOP），這個機制會綜合考慮當前系統的負載以及可用的CPU和記憶體資源，對單個查詢所用的資源進行限制，以避免單個查詢消耗的資源太多，影響其他請求的處理。