400倍加速，PolarDB HTAP實時資料分析技術解密

前言

最近分析型資料庫在資本市場和技術社群都非常的火熱，各種創業公司的創新型產品如雨後春筍般出現。這一方面是因為當前階段企業日益依賴從資料中尋找增長潛力帶來需求的增長，另一方面雲原生技術的發展帶來現有技術體系的進化和變革，諸如Snowflakes這類產品的成功證明，使用雲原生技術再造分析型資料庫技術體系是必要的且存在很大的市場機會。

PolarDB MySQL是因雲而生的一個數據庫系統， 除了雲上OLTP場景，大量客戶也對PolarDB提出了實時資料分析的效能需求。對此PolarDB技術團隊提出了In-Memory Column Index（IMCI）的技術方案，在複雜分析查詢場景獲得的數百倍的加速效果。

本文闡述了IMCI背後技術路線的思考和具體方案的取捨。PolarDB MySQL 列存分析功能即將在阿里雲上線，敬請期待。

一 MySQL生態HTAP資料庫解決方案

MySQL是一款主要面向OLTP型場景設計的開源資料庫，開源社群的研發方向側重於加強其事務處理的能力，如提升單核效能/多核擴充套件性/增強叢集能力以提升可用性等。在處理大資料量下複雜查詢所需要的能力方面，如最佳化器處理子查詢的能力，高效能運算元HashJoin， SQL並行執行等，社群一直將其放在比較低優先順序上，因此MySQL的資料分析能力提升進展緩慢。

隨著MySQL發展為世界上最為流行的開源資料庫系統，使用者在其中儲存了大量的資料，並且執行著關鍵的業務邏輯，對這些資料進行實時分析成為一個日益增長的需求。當單機MySQL不能滿足需求時，使用者尋求一個更好的解決方案。

1 MySQL + 專用AP資料庫的搭積木方案

專用分析型資料庫產品選項眾多，一個可選方案是使用兩套系統來分別滿足的OLTP和OLAP型需求，在兩套系統中間透過資料同步工具等進行資料的實時同步。更進一步，使用者甚至可以增加一層proxy，自動將TP型負載路由到MySQL上，而將分析型負載路由到OLAP資料庫上，對應用層遮蔽底層資料庫的部署拓撲。

這樣的架構有其靈活之處，例如對於TP資料庫和AP資料庫都可以各自選擇最好的方案，而且實現了TP/AP負載的完全隔離。但是其缺點也是顯而易見的。首先，在技術上需要維護兩套不同技術體系的資料庫系統，其次由於兩套系統處理機制的差異，維護上下游的資料實時一致性也非常具有挑戰。而且由於同步延遲的存在，下游AP系統儲存的經常是過時的資料，導致無法滿足實時分析的需求。

2 基於多副本的Divergent Design方法

隨著網際網路而興起的新興資料庫產品很多都相容了MySQL協議，因此成為替代MySQL的一個可選項。而這些分散式資料庫產品大部分採用了分散式Share Nothing的方案，其一個核心特點是使用分散式一致性協議來保障單個partition多副本之間的資料一致性。由於一份資料在多個副本之間上完全獨立，因此在不同副本上使用不同格式進行儲存，來服務不同的查詢負載是一個易於實施的方案。典型的如TiDB，其從TiDB4。0開始，在一個Raft Group中的其中一個副本上，使用列式儲存（TiFlash）來響應AP型負載， 並透過TiDB的智慧路由功能來自動選取資料來源。這樣實現了一套資料庫系統同時服務OLTP型負載和OLAP型負載。

該方法在諸多Research及Industry領域的工作中都被借鑑並使用，並日益成為分散式資料領域一體化HTAP的事實標準方案。但是應用這個方案的前提是使用者需要遷移到對應的NewSQL資料庫系統，而這往往帶來各種相容性適配問題。

3 一體化的行列混合儲存方案

比多副本Divergent Design方法更進一步的，是在同一個資料庫例項中採用行列混合儲存的方案，同時響應TP型和AP型負載。這是傳統商用資料庫Oracle/SQL Server/DB2等不約而同採用的方案。

Oracle公司在在2013年發表的Oracle 12C上，釋出了Database In-Memory套件，其最核心的功能即為In-Memory Column Store，透過提供行列混合儲存/高階查詢最佳化（物化表示式，JoinGroup）等技術提升OLAP效能。

微軟在SQL Server 2016 SP1上，開始提供Column Store Indexs功能，使用者可以根據負載特徵，靈活的使用純行存表，純列存表，行列混合表，列存表+行存索引等多種模式。

IBM在2013年釋出的10。5版本（Kepler）中，增加了DB2 BLU Acceleration元件，透過列式資料儲存配合記憶體計算以及DataSkipping技術，大幅提升分析場景的效能。

三家領先的商用資料庫廠商，均同時採用了行列混合儲存結合記憶體計算的技術路線，這是有其底層技術邏輯的：列式儲存由於有更好的IO效率（壓縮，DataSkipping，列裁剪）以及CPU計算效率（Cache Friendly）， 因此要達到最極致的分析效能必須使用列式儲存，而列式儲存中索引稀疏導致的索引精準度問題決定它不可能成為TP場景的儲存格式，如此行列混合儲存成為一個必選方案。但在行列混合儲存架構中，行存索引和列存索引在處理隨機更新時存在效能鴻溝， 必須藉助DRAM的低讀寫延時來彌補列式儲存更新效率低的問題。因此在低延時線上事務處理和高效能實時資料分析兩大前提下，行列混合儲存結合記憶體計算是唯一方案。

對比上述三種方法，從組合搭積木的方法到Divergent Design方法再到一體化的行列混合儲存，其整合度越來越高，使用者的使用體驗也越來越好。但是其對核心工程實現上的挑戰也一個比一個大。基礎軟體的作用就是把複雜留給自己把簡單留給使用者，因此一體化的方法是符合技術發展趨勢的。

二 PolarDB MySQL AP能力的演進

PolarDB MySQL能力棧與開源MySQL類似，長於TP但AP能力較弱。由於PolarDB提供了最大單例項100TB的儲存能力，同時其事務處理能力遠超使用者自建MySQL。因此PolarDB使用者傾向於在單例項上儲存更多的資料，同時會在這些資料上執行一些複雜聚合查詢。藉助於PolarDB一寫多讀的架構，使用者可以增加只讀的RO節點以運行復雜只讀查詢，從而避免分析型查詢對TP負載的干擾。

1 MySQL的架構在AP場景的缺陷

MySQL的實現架構在執行復雜查詢時效能差有多個方面的原因，對比專用的OLAP系統，其效能瓶頸體現多個方面：

MySQL的SQL執行引擎基於流式迭代器模型（Volcano Iterator）實現， 這個架構在工程實現上依賴大量深層次的函式巢狀及虛擬函式呼叫，在處理海量資料時，這種架構會影響現代CPU流水線的pipline效率，導致CPU Cache效率低下。同時Iterator執行模型也無法充分發揮現代CPU提供的SIMD指令來做執行加速。

執行引擎只能序列執行，無法發揮現代多核CPU的並行話能力。官方從MySQL 8。0開始，在一些count（*）等基本查詢上增加並行執行的能力，但是複雜SQL的並行執行能力構建依然任重道遠。

MySQL最常用的儲存引擎都是按行儲存，在按列進行海量資料分析時，按行從磁碟讀取資料存在非常大的IO頻寬浪費。其次行式儲存格式在處理大量資料時大量複製不必要的列資料，對記憶體讀寫效率也存在衝擊。

2 PolarDB 並行查詢突破CPU瓶頸

PolarDB團隊開發的並行查詢框架（Parallel Query）， 可以在當查詢資料量到達一定閾值時，自動啟動並行執行，在儲存層將資料分片到不同的執行緒上，多個執行緒平行計算，將結果流水線彙總到匯流排程，最後匯流排程做些簡單歸併返回給使用者，提高查詢效率。

並行查詢的加入使得PolarDB突破了單核執行效能的限制，利用多核CPU的並行處理能力，在PolarDB上部分SQL查詢耗時成指數級下降。

3 Why We Need Column-Store

並行執行框架突破了CPU擴充套件能力的限制，帶來了顯著的效能提升。然而受限於行式儲存及行式執行器的效率限制，單核執行效能存在天花板，其峰值效能依然與專用的OLAP系統存在差距。要更進一步的提升PolarDB MySQL的分析效能，我們需要引入列式儲存：

在分析場景經常需要訪問某個列的大量記錄，而列存按列拆分儲存的方式會避免讀取不需要的列。其次列存由於把相同屬性的列連續儲存，其壓縮效率也遠超行存，通常可以達到10倍以上。最後列存中大塊儲存的結構，結合MIN/MAX等粗糙索引資訊可以實現大範圍的資料過濾。所有這些行為都極大的提升了IO的效率。在現今儲存計算分離的架構下，減少透過網路讀取的資料量可以對查詢處理的響應時間帶來立竿見影的提升。

列式儲存同樣能提高CPU在處理資料時的執行效率，首先列存的緊湊排列方式可提升CPU訪問記憶體效率，減少L1/L2 Cache miss導致的執行停頓。其次在列式儲存上可以使用應用SIMD技術進一步提升單核吞吐能力，而這是現代高效能分析執行引擎的通用技術路線（Oracle/SQL Server/ClickHouse）。

三 PolarDB In-Memory Column Index

PolarDB In-Memory Column Index功能為PolarDB帶來列式儲存以及記憶體計算能力，讓使用者可以在一套PolarDB資料庫上同時執行TP和AP型混合負載，在保證現有PolarDB優異的OLTP效能的同時，大幅提升PolarDB在大資料量上運行復雜查詢的效能。

In-Memory Column Index使用行列混合儲存技術，同時結合了PolarDB基於共享儲存一寫多讀的架構特徵，其包含如下幾個關鍵的技術創新點：

在PolarDB的儲存引擎（InnoDB）上新增對列式索引（Columnar Index）的支援，使用者可以選擇透過DDL將一張表的全部列或者部分列建立為列索引，列索引採用列壓縮儲存，其儲存空間消耗會遠小於行存格式。預設列索引會全部常駐記憶體以實現最大化分析效能，但是當記憶體不夠時也支援將其持久化到共享儲存上。

在PolarDB的SQL執行器層，我們重寫了一套面向列存的執行器引擎框架（Column-oriented）， 該執行器框架充分利用列式儲存的優勢，如以4096行的一個Batch為單位訪問儲存層的資料，使用SIMD指令提升CPU單核心處理資料的吞吐，所有關鍵運算元均支援並行執行。在列式儲存上，新的執行器對比MySQL原有的行存執行器性有幾個數量級的效能提升。

支援行列混合執行的最佳化器框架，該最佳化器框架會根據下發的SQL是否能在列索引上執行覆蓋查詢，並且其所依賴的的函式及運算元能被列式執行器所支援來決定是否啟動列式執行。最佳化器會同時對行存執行計劃和列存執行計劃做代價估算，並選中代價交代的執行計劃。

使用者可以使用PolarDB叢集中的一個RO節點作為分析型節點，在該RO節點上配置生成列存索引，複雜查詢執行在列存索引上並使用所有可用CPU的計算能力，在獲得最大執行效能的同時不影響該叢集上的TP型負載的可用記憶體和CPU資源。

幾個關鍵關鍵技術結合使得PolarDB成為了一個真正的HTAP資料庫系統，其在大資料量上運行復雜查詢的效能可以與Oracle/SQL Server等業界最頂尖的商用資料庫系統處在同一水平。

四 In-Memory Column Index的技術架構

1 行列混合的最佳化器

PolarDB原生有一套面向行存的最佳化器元件，在引擎層增加對列存功能支援之後，此部分需要進行功能增強，最佳化器需要能夠判斷一個查詢應該被排程到行存執行還是列存執行。我們透過一套白名單機制和執行代價計算框架來完成此項任務。系統保證對支援的SQL進行性加速，同時相容執行不支援的SQL。

如何實現100%的MySQL相容性

我們透過一套白名單機制來實現相容性目標。使用白名單機制是基於如下幾點考量。第一點考慮到系統可用資源（主要是記憶體）的限制，一般不會在所有的表的所有上都建立列索引，當一個查詢語句需要使用到列不在列存中存在時，其不能在列存上執行。第二點，基於效能的的考量，我們完全重寫了一套面向列存的SQL執行引擎，包括其中所有的物理執行運算元和表示式計算，其所覆蓋的場景相對MySQL原生行存能夠支援的範圍有欠缺。當下發的SQL中包含一些IMCI執行引擎不能支援的運算元片段或者列型別時，需要能能夠識別攔截並切換回行存執行。

查詢計劃轉換

Plan轉換的目的是將MySQL的原生邏輯執行計劃表示方式AST轉換為IMCI的Logical Plan。在生成IMCI的Logical Plan之後，會經過一輪Optimize過程，生成Physical Plan。Plan轉換的方法簡單直接，只需要遍歷這個執行計劃樹，將 mysql 最佳化後的 AST 轉換成IMCI 以 relation operator 位節點的樹狀結構即可，是一個比較直接的翻譯過程。不過在這個過程中，也會做一部分額外的事情，如進行型別的隱式轉換，以相容MySQL靈活的型別系統。

兼顧行列混合執行的最佳化器

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

在PolarDB中除了有原生MySQL的行存序列執行，還有能夠發揮多核計算能力的基於行存的Paralle Query功能。因此實際最佳化器會在1）行存序列執行，2）行存Paralle Query 3）IMCI 三個選項之中選擇。在目前的迭代階段，最佳化器按如下的流程操作：

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

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

3。如果IMCI無法執行此SQL，則PolarDB會嘗試編譯出一個Parallel Query的執行計劃並執行。如果無法生成PQ的執行計劃，則說明IMCI和PQ均無法支援此SQL，fallback回行存執行。

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

2 面向列式儲存的執行引擎

IMCI執行引擎是一套面向列存最佳化，並完全獨立於現有MySQL行式執行器的一個實現，重寫執行器的目的是為了消除現有行存執行引擎在執行分析型SQL時效率低兩個關鍵瓶頸點：按行訪問導致的虛擬函式訪問開銷以及無法並行執行。

支援BATCH並行的運算元

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

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

在IMCI的執行引擎中，每個Operator也使用迭代器函式來訪問資料，但不同的是每次呼叫迭代器會返回一批的資料，而不是一行，可以認為這是一個支援batch處理的火山模型。

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

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

SIMD向量化計算加速

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

傳統MySQL的表示式計算體系以一行為一個單位的逐行運算，一般稱其為迭代器模型實現。由於迭代器對整張表進行了抽象，整個表示式實現為一個樹形結構，其實現程式碼易於理解，整個處理的過程非常清晰。

但這種抽象會同時帶來效能上的損耗，因為在迭代器進行迭代的過程中，每一行資料的獲取都會引發多層的函式呼叫，同時逐行地獲取資料會帶來過多的 I/O，對快取也不友好。MySQL採用樹形迭代器模型，是受到儲存引擎訪問方法的限制，這導致其很難對複雜的邏輯計算進行最佳化。

在列存格式下，由於每一列的資料都單獨順序儲存，涉及到某一個特定列上的表示式計算過程都可以批次進行。對每一個計算表示式，其輸入和輸出都以Batch為單位，在Batch的處理模式下，計算過程可以使用SIMD指令進行加速。新表示式系統有兩項關鍵最佳化：

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

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

3 支援行列混合儲存的儲存引擎

事務型應用和分析型應用對儲存引擎有著截然不同的要求，前者要求索引可以精確定位到每一行並支援高效的增刪改，而後者則需要支援高效批次掃描處理，這兩個場景對儲存引擎的設計要求完全不同，有時甚至是矛盾的。

因此設計一個一體化的儲存引擎能同時服務OLTP型和OLAP型負載非常具有挑戰性。目前市場上HTAP儲存引擎做的比較好的只有幾家有幾十年研發積累的大廠，如Oracle （In-Memory Column Store）/Sql Server（In Memory Column index）/DB2（BLU）等。如TiDB等只能透過將多副本叢集中的一個副本調整為列存來支援HTAP需求。

一體化的HTAP儲存引擎一般使用行列混合的儲存方案，即引擎中同時存在行存和列存，行存服務於TP，列存服務於AP。相比於部署獨立一套OLTP資料庫 加一套OLAP資料庫來滿足業務需求，單一HTAP引擎具有如下的優勢：

行存資料和列存資料具有實時一致性，能滿足很多苛刻的業務需求，所有資料寫入即可見於分析型查詢。

更低的成本，使用者可以非常方便的指定哪些列甚至一張表哪個範圍的儲存為列存格式用於分析。全量資料繼續以行存儲存。

管理運維方便，使用者無需關注資料在兩套系統之間同步及資料一致性問題。

PolarDB 採用了和Oracle/Sql Server等商用資料庫類似的行列混合儲存技術，我們稱之為In-Memory Column Index：

建表時可以指定部分表或者列為列存格式，或者對已有的表可以使用Alter table語句為其增加列存屬性，分析型查詢會自動使用列存格式來進行查詢加速。

列存資料預設壓縮格式儲存在磁碟上，並可以使用In-Memory Columbia Store Area來做快取加速並加速查詢，傳統的行格式依然儲存在BufferPool中供OLTP性負載使用。

所有事務的增刪改操作都會實時反應到列存儲存上，保證事務級別的資料一致性。

實現一個行列混合的儲存引擎技術上非常困難，但是在InnoDB這樣一個成熟的面向OLTP負載最佳化的儲存引擎中增加列存支援，又面臨不同的情況：

滿足OLTP業務的需求是第一優先的，因此增加列存支援不能對TP效能太大影響。這要求我們維護列存必須足夠輕量，必要時需要犧牲AP效能保TP效能。

列存的設計無需考慮事務併發對資料的修改， 資料的unique check等問題，這些問題在行存系統中已經被解決，而這些問題對ClickHouse等單獨的列存引擎是非常難以處理的。

由於有一個久經考驗的行存系統的存在，列存系統出現任何問題，都可以切換回行存系統響應查詢請求。

上述條件可謂有利有弊，這也影響了對PolarDB整個行列混合儲存的方案設計。

表現為Index的列存

在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和Seconary Index都實現為一個B+Tree。而列索引在定義上是一個Index，但其實是一個虛擬的索引，用於捕獲對該索引覆蓋列的增刪改操作。

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

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

列存資料組織

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

列索引中記錄按RowGroup進行組織，每個RowGroup中不同的列會各自打包形成DataPack。

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

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

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

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

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

全量及增量行轉列

行轉列操作在兩種情況下會發生，第一種情況是使用DDL語句對部分列建立列索引（一般是業務對一個已有的表有新增分析型需求），此時需要掃描全表資料以建立列索引。另一種情況是在事務操作過程中對於涉及到的列實時行專列。

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

在一個表上建立列索引之後，所有的更新事務將會同步更新行存和列存資料，以保證二者的事務一致性。下圖演示了在IMCI功能關閉和開啟之間的差異性。在未開啟IMCI功能時，事務對所有行的更新都會先加鎖，然後再對資料頁進行修改，在事務提交之前會對所有加鎖的記錄一次性方所。在開啟IMCI功能之後，事務系統會建立一個列存更新快取，在所有資料頁被修改的同時，會記錄所涉及到的列存的修改操作，在事務提交結束前，該更新快取會應用到列存系統。

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

列索引粗糙索引

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

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

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

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

行列混合儲存下的TP和AP資源隔離

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

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

第二種方式，RW支援OLTP型負載，並啟動一個AP型RO開啟行列混合儲存以支援查詢，此種部署模式下CPU資源可以實現100%隔離，同時該AP型RO節點上的記憶體可以100%分配給列存儲存和執行器。但是由於使用的相同的共享儲存，因此在IO上會相互產生一定影響，對於這個問題我們在未來會支援將列存資料寫入到外部儲存如OSS等，實現IO的資源隔離，同時提升AP型RO上的IO吞吐速率。

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

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

五 PolarDB IMCI的OLAP效能

為了驗證IMCI技術的效果， 我們對PolarDB MySQL IMCI的進行了TPC-H場景的測試。同時在相同的場景下將其與原生MySQL的行存執行引擎以及當前OLAP引擎單機效能最強的ClickHouse進行了對比。測試引數簡要介紹如下：

資料量TPC-H 100GB， 22條Query

CPU Intel（R） Xeon（R） CPU E5-2682 2 socket

記憶體 512G， 啟動後資料都灌進記憶體。

1 PolarDB IMCI VS MySQL序列

在TPC-H場景下，所有22條Query ，IMCI處理延時相對比原生MySQL都有數十倍到數百倍不等的加速效果。其中Q6的的效果將近400倍。體現出了IMCI的巨大優勢。

2 PolarDB IMCI VS ClickHouse

而在對比當前社群最火熱的分析型資料庫ClickHouse時， IMCI在TPC-H場景下的效能也與其基本在同一水平。部分SQL的處理延時各有優劣。使用者完全可以使用IMCI替代ClickHouse使用，同時其資料管理也更加方便。

FutureWork

IMCI是PolarDB邁向資料分析市場的第一步，它迭代腳步不會停止，接下里我們會在如下幾個方向進一步研究和探索，給客戶帶來更好的使用體驗：

自動化的索引推薦系統，目前列存的建立和刪除需要使用者手動指定，這增加了DBA的工作量，目前我們正在研究引入自動化推薦技術，根據使用者的SQL請求特徵，自動建立列存索引，降低維護負擔。

單獨的列存表以及OSS儲存，目前IMCI只是一個索引，對純分析型場景，去除行存可以更進一步的降低儲存大小，而IMCI執行器支援讀寫OSS物件儲存能將儲存成本降到最低。

行列混合執行，即一個SQl的執行計劃部分片段在行存執行，部分片段在列存執行。以獲得最大化的執行加速效果。

中國計算機學會 × 高德地圖 釋出“POI名稱生成”賽題，誠邀全球英才組隊參加