基于Trevni行列混合的分布式嵌套存儲研究

文衛東，李 鴦，李文海

1.軟件工程國家重點實驗室，武漢 430072

2.武漢大學 計算機學院，武漢 430072

1 引言

伴隨互聯網相關技術的快速發展和分布式計算方法在數據密集型應用的逐步深入，越來越多的數據庫平臺在面對半結構化數據的查詢中引入存儲和計算并行化。近年來，相關并行化技術主要沿MapReduce[1]和MPP[2]（Massive Parallel Processing）兩個維度展開，二者顯著的不同在于數據庫算符與Map和Reduce兩個階段之間的轉換。其中，MPP更加側重于在不同計算階段之間盡量減少階段化的持久化操作，從而實現算符之間的管道工作（Pipelining）模式。一種折衷的方式[2-3]是將數據庫中無法管道化的操作分解成一個操作符超集（Super Cluster of Operators），從而實現超集內管道化執行，超集間持久化執行。這一方式使得數據庫查詢的負載較傳統基于MapReduce的開源實現（如Hive[4]）更多依賴底層存儲和數據組織方法。

為提高數據訪問效率，列存儲技術自20世紀末被逐步引入，其常見的存儲[5]和組合[6]方式先后得到較為深入的研究。列存提升數據庫應用的前提是查詢的局部性特征，即單個查詢在某個執行階段上往往僅訪問數據模式中的一個子模式。通過引入列存，已有數據庫應用中OLAP[7]（OnLine Analytical Processing）負載的可用性得到了保障。然而必須指出，OLAP的星型模式以減少數據冗余為目標，引入了代價高昂的連接操作。早在20世紀80年代[8-9]，就有研究指出這些連接操作可以通過嵌套建模方式予以優化，通過迭代遍歷嵌套記錄既保證數據的低冗余又通過線性掃描嵌套元組降低操作執行代價。該思想直到近年仍然受到學界的廣泛重視[10-11]，同時有大量的開源框架[12]在持續開發。

列存儲和嵌套模型的混合催生了大量極具現實意義和研究價值的問題[13-16]。而其中一個核心問題在于如何在保證列存數據局部性的同時降低其高昂的裝配（Assembly）代價。這里的裝配可以解釋為將分散于各列的數據單元進行封裝、形成滿足給定數據模式的各個記錄。傳統行存中的這一代價表現為連接被廣泛研究，而列存在去除連接后的代價主要集中于迭代遍歷單元以及依據模式構建元組上。后者的代價更加側重于這樣一個事實：當元組依據列存方式加載到內存后，列和列之間的同屬一個元組的單元在內存中不再連續，從而對其訪問在L1/L2緩存中的訪問效率也大大降低。此外，在嵌套模式下這一問題顯得更加突出：由于嵌套模式需要在不同層級之間維護一對多關聯關系，因而常用嵌套框架在跨層關聯時的表現不能讓人滿意[14]。

有鑒于此，本文研究并給出一個行列混合式存儲設計。該存儲方法的核心在于通過將經常聚集訪問的屬性列按照行的方式與其他列等同建模和組織，形成空間上局部的若干列組、進而保證數據交換的有效性和裝配的內存局部性。為該設計目標，研究深入分析了主流開源框架的模式和存儲構成，通過特殊設計union結構實現復雜類型的嵌入。研究設計并給出了一種特殊類型Group，并將該類型與普通列統一存儲。從而在當查詢僅涉及到若干屬于某列組的單元時以行方式反序列化（Deserialize）元組，提高了列存的裝配性能。

2 相關研究

近年來，面向嵌套列存的研究伴隨Dremel[10]在Web級數據上的逐步深入應用而被廣泛重視。該方法在數據庫領域曾得到深入研究，大量有關模式[8]、互操作[9]和存取方法[13]的優化成果先后被提出。

Dremel的核心特色在于通過引入定義層（Definition Level，DL）和重復層（Repetition Level，RL）的嵌套抽象，使得任意嵌套記錄的層級映射可以通過狀態機轉換方式在兩個層次的數組上得到。即連續的子層元組通過列上對應的重復層指示器得到層級，通過其定義層指示器得到單元是否為空值。該方法的優勢在于通用，但每個可為空（nonrequired）的嵌套列均需要進行轉換、降低了其裝配效率[14]。

Avro的列存核心組件Trevni[12]采用了層映射方法，即同一嵌套層次共享一個映射單元。該策略的優勢在于裝配復雜度較Dremel低，但逐一計數的方式使得該存儲格式僅支持迭代方式。同時，Trevni的變長字段采取單元塊內偏移與數據負載混合存放，進一步降低了列映射的效率。已有研究通過引入Dremel設計思想改寫Trevni，如Parquet等。如上述可知，引入Dremel需要對嵌套列的每行增加RL和DL，從而增加了逐列進行狀態轉換的代價。因而如何在保證列存優勢的同時減少裝配代價仍然是Trevni和Dremel研究中的一個開放問題。

已有研究在上層模式上側重平坦化（Flattening）[13]和共享優化設計[14]。平坦化研究分析并給出了避免上層高代價平坦化裝配操作的場景，與本文研究正交；而共享優化僅限于單個映射節點，難以適用于具有任意級聯層次的即席（ad-hoc）查詢[6，15-16]，如富含嵌套連接條件的關系子查詢[17]或對象模型下[18]面向嵌套模式的多選擇條件查詢。

3 行列混合存儲設計

本章給出嵌套模式列存架構樣例，分析模式構造與裝配的通用過程，進而研究提出列組物理結構。

3.1 通用嵌套行列混合模式

主流列存框架（如Trevni和Parquet等）將每個列存放于連續的物理塊中實現高效的按列提取。其中，Trevni的思路是同一個列的所有單元（unit）具有全局連續的偏移量，其表示為塊號和塊內偏移；而Parquet采用Dremel架構，基于定義層（Definition Level）表示某列的某個單元是否為空、基于復制層（Replication Level表示層級）。此外，Google的數據交換格式Protobuf也被廣為接受，其提供與JSON兼容的模式定義方法用于數據交換。Parquet與Trevni均采用計數原理完成不通層級之間的關聯。

圖1給出了Trevni和Parquet建立層級關聯的過程。該過程通過計數（Trevni采用圖1（a）所示方式）或復制層遍歷（Parquet如圖1（b）所示）對各個列獨立存儲的方式重建上下層之間的一對多關系。如果發生一個上層實體對下層的映射，可以根據行標或復制層計數進行裝配，模式的層級可以通過類似JSON的格式進行定義。該方法的潛在不足之處在于：當需要一對多重建嵌套記錄時，頻繁在列間進行計數和狀態切換會帶來大量的裝配開銷。為此，研究給出一種新的邏輯模式定義與物理存儲分離的行列組織策略，迭代定義嵌套模式如下。

圖1 嵌套元組用例和兩種典型列存框架組織示意圖

定義1（邏輯嵌套模式）任意一個嵌套模式可基于樹結構[13]遞歸定義如下。

該定義通過基本類型primary及集合類型array構造了兩類高層對象object和value，并在這兩類高層對象基礎上遞歸定義了對象類型record和group。其中，record類型可遞歸通過primary、array或group分組構成；group只能遞歸由array或primary構成。考慮到規范化嵌套模式均可通過一個模式根Troot表達成上述定義中的record類型[13]，通過對不同類型定義列映射，建立如下行列混合存儲約束。

定義2（行列混合存儲）任意獨立存儲的連續物理單元必須由primary和group兩種類型的同構實體或array類型的映射數組構成。

該定義通過約定可連續存儲的單元類型，為混合存儲構建了通用模式要素。這里任意模式根節點可以由多個列（集）的record構成，其中每個列可以由三種類型構成，三種類型數據實體按列連續存放（array的映射數組與primary等價處理）。下面給出一個典型的模式實例，其中record與group類型在“組”中取一種即可。當選定group類型時，其下屬三個域需要作為整體連續存放。

3.2 基于Trevni的列組構造

上述模式及其約束適用于主流嵌套列存框架，下面以Trevni為例對嵌套模式的列式存儲給出構造方法。在該存儲框架下，以支持嵌套的模式元數據為基礎，該框架為列存數據庫提供了兩層描述。通過特別構建列存映射數據塊形成不同層次的數據映射關系。模式中的每個葉子節點的數據連續保存于若干數據塊中，保證數據按列訪問的效率。在實現上，Trevni提供一組用于持久化基本類型的單列載入類ColumnFileReader，通過依次順序掃描維護在緩沖區InputBuffer中的單個列的所有實例，實現按列載入。能夠支持的基本類型有：長整形、布爾、整形、字符串、字節數組、浮點和定長類型等。

如圖2所示，Trevni的數據由一個文件頭和連續的列數據塊構成，其中文件頭的核心結構由版本號、基于JSON的模式信息和塊偏移量數組構成。每個數據塊原則上被設計為定長的數據塊，每個塊的實際長度被保存于文件頭的偏移量結構中，其中記錄每個塊的實際維護的單元（同屬于一個列的實例）數量。一個模式根節點下的子節點間關聯關系通過JSON格式的模式信息描述，模式特別對存在嵌套的字段構建一個容器，所有同屬于一個父親的孩子節點共享一個一對多的映射結構。圖2示意了這兩個核心結構與所面向的數據塊之間的關系。其中，JSON格式給出了一個具有兩層級聯（Cascading）的嵌套關系：作者（Authors，簡稱A，下同）節點包含三個屬性，即名（F）、姓（L）和聯系地址（C）。

圖2 行列混合存儲示意圖

上述模式及其約束中，record類型為嵌套結構，即一個父親下面可以有多個孩子節點，但是不經array解釋，每個孩子在一個父親實例下僅有一個實例；array為行迭代類型，即一個父親實例可以有多個孩子實例。二者可以結合，用以描述具有層次嵌套關系的復雜實體。例如，一個文獻若有多個作者，則通過在作者映射數組中保存該文獻的作者數量，最終裝配過程中根據作者數量確定該文獻的作者。這一方法的優勢在于當查詢需要少量的列時，裝配僅發生在這些列上，有利于減少IO代價和記錄寬度。然而，由于多個同屬于一個父親的列，如上例中A到F、L、C三個子節點，在封裝對象時需要依次訪問對象數組元素、增加了裝配代價。

上例給出文獻的一個模式定義，其中作者信息依次由array和group嵌入類型構成。原始Trevni給出的模式定義通過在group的位置定義record，從而使得頂層四個屬性和“作者”下屬三個屬性形成獨立的列，以構成物理存儲結構。通過引入例子中給出的group類型，將列組類型作為一種普通bytes類型與Trevni其他基礎類型采用相同的方法讀寫，并在裝配時根據每個group的變長實例的模式信息進行反序列化。這樣同一頂層實體的下屬被頻繁聚集訪問的屬性列能夠以一個整體對每個實例反序列化，從而有利于提高裝配效率。

3.3 級聯存儲結構

上述group構造的基本原理是通過聚集group節點的數據存儲和解析，從而在存儲階段以普通字節數組方式存取這些實體。而解析階段，依據該類型字段的讀寫對象、基于模式對字節數組進行反序列化。下面針對上述過程詳述存儲方法。

設計解析group類型的GenericGroupReader，該類與ColumnFileReader和InputBuffer的轉換功能同構，根據模式信息調用已讀入到內存的group類型對象的反序列化接口。GenericGroupReader除了能夠支持上述基本類型外，還提供對array和record的嵌套反序列化。實現對這三類復雜結構的嵌套調用，并對葉子節點的基本類型的實例進行嵌套定義。不同于record，group將下屬所有節點按照行方式在磁盤塊中以字節數組方式存儲，從而保證了應用中被連續訪問的字段能夠在空間上連續存放，從而可以保證反序列化和裝配的效率。

基于字節數組方式保存模式化group實例的塊分布如圖3所示。通過將圖2中的數據庫展開，可以看到采用group方式存儲的字段集與其他獨立存儲的字段之間在物理結構上的差別。由上述模式樣例可知這里的作者信息包括姓、名和聯系三個字段，與其他字段共同構成模式的頂層節點。

從圖中可以看到作者信息包含一個映射字段，用以維護文獻與作者之間的一對多映射。與該節點處于同一層次的關鍵字、修訂日期等字段采用列存儲（如上述模式定義所述），每個列分別占用連續的磁盤塊。其中，關鍵字信息也包含一個映射字段，用以描述一個文獻對多個關鍵字的約束。值得注意的是，這里的映射字段采用全局連續的偏移量進行記錄，以方便快速定位一個字段的實例。在圖中，文獻[1]的兩個作者“張，三，武漢”，“李，四，北京”被連續存放于塊2和塊3，當某查詢需要訪問這些作者信息的時候，該聚集存儲方法可以依次獲得同一作者的三個字段，從而有利于提高系統效率。對于其他列信息，查詢必須逐列序列化后再依據映射列的一對多關系分別裝配。

4 模式關聯方法

為進一步加速反序列化過程，設計了變長字段塊內聚集存儲策略，通過高效保存空值、偏移量和變長數據的字節數組，提高塊內數據訪問效率。

4.1 塊內聚集存儲

從圖3可知，對某屬性列（組），行列混合存儲面對三類對象存在不同的訪問方式，即葉子節點中基本類型的對象數組、葉子節點中group類型對象的字節數組和映射關系中的偏移量數組。可以通過塊偏移量描述符對各個塊進行定位，但在塊內數據進行反序列化的時候按照偏移量逐次確定列實例的邊界，使得查詢無法跳過無用的記錄。這在很多應用中無法保證對空值的高效處理。基于這一問題，研究給出了塊內數據的一種快速訪問方法。

圖3 組按行關聯與不同層次之間列關聯示意圖

如圖4所示，綜合考慮空值和變長字段，給出一個優化塊內數據組織方法將每個數據塊分割為三個區。其中，指示器（Indicator）區以1位指示一個實例是否為空；偏移量（Offsets）區存放該實例在塊內的開始地址；對于一個開始地址，數據區存放該實例的變長字節數組。默認地，如果字段在模式定義中未聲明為null，則該字段不能為空，存儲結構中不為該字段設置指示區。圖中給出了第3章模式的塊內數據形式。對于“摘要”字段，模式定義為可以為空，因而該字段的每個數據塊采用三個區域對數據進行組織。如果要訪問該塊中的第二個記錄（該記錄對應第二個“文獻”）的“摘要”，反序列化過程首先根據模式找到指示器的第二位得到該實例不為空。然后基于偏移量區域的第二個元素定位到內存中cache頁面的該實例起始位置，讀取該位置到下一個開始位置之前的字節數組。

圖4 塊內空值—位置—數據三級訪問結構

當需要跳過若干字段的時候，可以直接在塊內進行二分查找、基于塊內計數定位到需要跳轉的目的實例位置，完成對中間無用實例的跳過；當發現若干實例為空的時候，同樣可以根據指示位“0”決定是否忽略該實例。這對于特殊場景（如選擇下推[6，14]或空值字段[13]）中的數據裝配具有較強的現實意義。同時，對于通常應用中的記錄裝配，這些聚集存儲的指示位對每個實例僅占用一位的存儲空間，可以采用選擇下推操作提升訪問效率。

4.2 組裝流程設計

如前所述，列組中的數據在存儲時按照普通字節數組方式讀寫，在模式轉換過程中形成與復雜類型record同構的行存嵌套對象。對于一個從模式根節點開始的訪問請求，需要以深度優先方式（Breath first）依次訪問各層節點的列（組）數據塊，將其讀入內存中的各個封裝器中。然后對其中的一對多的節點進行組裝，形成嵌套記錄。

如圖5所示，深度優先算法的流程以模式的讀取和解析作為起始過程，在遍歷完一個模式的所有節點后結束一個層次的訪問，其中的遍歷模式可以是數據模型的一個任意子集。例如，在上一章給出的模式定義中，可以根據用戶的查詢請求查找所有包含關鍵字集合{“存儲”，“數據庫”}的論文題名和作者信息。這一查詢模式（Pattern）實際上排除了除關鍵字和題名以外的其他屬性，是數據模式的一個子集。僅需要依次遍歷一級節點“關鍵字”，“題名”和“作者”。其元組組裝過程如下：

首先，加載模式根的一級列中的葉子“題名”，根據其對象數組找到第一個記錄的“題名”對象。

然后遍歷“題名”的兄弟節點，根據“關鍵字”字段的第一個映射元素找到四個關鍵字對象，并根據作者的映射關系找到兩個作者的三個字段。這一映射過程可以參考圖3的映射字段，并在其偏移量2的基礎上在圖4所示的塊結構中找到對應的作者信息。兩個字段均包含一個映射數組，但根據模式給定的類型差異分別做如下處理：

（1）“作者”字段為group類型，其對象以字節數組存放，需要在裝配階段反序列化。

（2）“關鍵字”字段為基本類型string，其對象在裝配之前的讀取階段已經是string類型的字節數組了，因而僅需要進行一次類型轉換。

（3）各節點均無孩子節點后，一個記錄完成；所有記錄裝配后，程序完成讀取。

圖5 嵌套分組層級之間關聯流程圖

4.3 代價分析與MapReduce接口設計

上述按照group裝配的特點在于：當模式指定的字段為group類型時，根據映射數組可以一次順序地裝配一個記錄的所有字段。傳統列存方法下，因為反序列化階段是按列組織列實例的，因而需要輪轉根據映射關系裝配所有作者的三個子字段。

對于上述列組的組裝方式，當需要的字段信息一定時，一定范圍的低層對象的若干個列僅需要順序進行反序列化和一次掃描裝配；與之相反，Trevni需要針對每個列獨立反序列化成對象數組，需要輪轉依據映射數組進行裝配。假定一個包含c列的列組在第l層逐層具有ni:1的映射，則每個頂層記錄在Group方式下裝配該列的內存代價為：

這里Dj為反序列化和裝配某列的代價，D為反序列化一個映射數組中一個元素的代價。通用列存分離存儲模式下由于需要根據列組訪問，其代價為：

可以看到式（2）的內存操作多出了對每列進行數組映射的代價。進一步的，假定可以在頂層掃描過程中進行過濾，如在反序列化前根據前一個過濾器確定后一個對象是否需要進行反序列化和封裝，給定第一個頂層選擇率r，則式（1）縮減為：

在一個選擇過程中，通過度量每個列的裝配代價和掃描代價，從而得到下面的總代價：

其中Fj為在給定列（列為第 j層）上執行選擇的代價，且反序列化和選擇分別具有O(Nnc)和O(Nn)的時間復雜度。因為反序列化復雜度較高、其在式（2）中不會受益于選擇率，故式（3）描述的代價顯示出所提方法可線性減少下層嵌套列的反序列化代價。行列混合存儲合并了原本分離存放的列、不需要額外引入存儲空間，因而不會帶來額外的存儲開銷，且內存合并行組與列存分列存儲的時間復雜度相同。基于選擇率在不同層次之間進行選擇下推[5，14]將被作為后續的研究目標。

對于MapReduce下的列存數據庫存取，研究給出了相應的實現。基于對Hadoop HDFS的對象讀取類RecordReader進行重載，研究引入了上述帶有group類型的模式轉換實現和塊反序列化實現。其核心流程遵循RecordReader的約束，首先通過打開數據分片（Split）得到分布于HDFS中的數據塊，然后按照塊內進行數據分割。其中每個分割后的小塊用以容納某個列的連續實例的字節數組，其訪問方式與本地模式相同，文件的頭信息和模式在各個Map任務上保存一個副本。當一個Map任務執行Split的掃描的時候，基于HDFS的訪問原則，在本地數據塊上進行響應的封裝操作。這里需要說明的是，HDFS的數據塊默認值是128 MB、上限2 GB，這會使得大規模數據的查詢請求被劃分成很多小的Map任務，實驗可以看到這一條件的影響。

5 實驗驗證分析

實驗基于不同數據規模的TPCH基準進行。通過級聯Customer、Orders、Lineitem三個表形成三級嵌套模式COL，生成具有不同選擇列和不同選擇率的查詢條件進行測試和比較，以驗證所提基于group方法的優劣。特別的，比較過程中引入了原始的Trevni實現和一個基于Trevni的Deremel實現——Parquet。將在行存Avro和這兩類列存框架下進行綜合比較。最后給出了真實數據Pubmed，通過對不同框架執行時間比較，分析研究給出了技術的適用性實驗分析結果。

實驗環境中硬件由一個Dell 720服務器和一套集群系統分別對各類存儲框架在單節點和分布式環境下進行比較。其中，Dell 720服務器由2個Intel Xeon ES-2640 8核CPU構成，內存為320 GB，磁盤由180 MB/s的SCSI磁盤構成。單節點實驗均在軟件設計中采用單線程執行。集群由4節點構成，每個節點配備了24核AMD OperonTM1674CPU，內存128 GB，網絡由40 Gb/s的InfiniBand網絡連通。

實驗1變投影列實驗

通過在COL級聯表的路徑上分別選擇不同數量的列驗證存儲框架的IO和內存效率，其中列的選擇要求是級聯外建關鍵字至少被選中。此外，其他的列平均分布于不同的層次上。實驗分別選擇總共4、6、8、10個列作為投影列進行元組提取驗證，最終提取的元組以嵌套方式返回，以查詢的平均執行時間作為度量標準。

如圖6所示，不同列數對列存影響顯著。其中圖6（a）為磁盤IO環境下的執行時間，即每次查詢需要清空所有系統緩存區，保證數據讀取操作對磁盤的訪問。顯而易見，不管任何情況下Avro的行存結構需要讀取所有列，因而其IO時間相對穩定；而幾種列存框架僅需要訪問所需的列數據，因此其執行時間大致與列數呈線性關系。圖6（b）給出了裝配時間，即在查詢前先執行一次查詢，保證第二次的統計時間不包含IO時間（實驗內存遠大于數據規模）。從圖中可以看到上述結果依然成立，即三種列存框架的效率顯著優于行存框架Avro。此外，由于同一層次的選擇在Group中采用順序反序列化，因而其效率優于原始Trevni的實現，而Parquet需要對投影的每個嵌套列進行一次較為耗時的裝配，影響了其執行效率。

圖6 嵌套分組與其他方法在磁盤和內存中執行時間比較

此外，一個顯著的現象需要分析：磁盤環境下的執行時間僅比內存下略大。這是由于現有操作系統廣泛采用磁盤預取技術，這使得IO和反序列化并行執行。圖中的磁盤環境執行的同時內存中也并行執行反序列化，因而統計的時間可理解為IO時間；而沒有IO時（圖6（b）），統計時間等價為反序列化等內存操作的執行時間。

實驗2不同層次上的變選擇率實驗

分別在同層和嵌套層次下進行變選擇率實驗，驗證所提方法的優越性。

如圖7（a）所示，選擇在嵌套表的Lineitem層級上進行4列選擇，比較行存和三種列存方法。由于該層為嵌套表COL的核心負載，因而可以看到列存較行存節省了大約3/4的執行時間（列存僅需讀取Lineitem16列中的4列）；同時，Group在這種沒有映射的平坦掃描的查詢中優勢不明顯。而圖7（b）新增了三個層次中的另外兩列，總計構成對COL三個層級一共10列的掃描。從執行結果上看，Group因為較小的級聯組裝代價，執行時間比Trevni節省了約2/3；此外上一個實驗中Parquet的高代價分析在該實驗結果中再次得到驗證。

圖7 嵌套分組在不同模式下的執行時間比較

實驗3分布式環境效率比較

基于MapReduce對上述實驗1進行分布式效率比較。由于Trevni的數據轉換需要容納于內存，無法轉換160 GB的數據，因而實驗引入另一個分布式數據庫Asterix（DB）進行比較。對Group數據采用構建—歸并方式進行加載，并基于不同Map物理任務限制驗證不同任務數量下，4個節點配備時的平均執行時間。

圖8和圖9分別給出了不同并發度上的執行時間對比。從圖中可以看到Group方式的效率在分布式環境下較其競爭對手更優越，其執行時間較次優的Parquet節省了3/5。同時可以看到當訪問層次更深的時候Asterix的模式內置方式與Group方式相當。而伴隨并發度的提升，Avro行存模式和Group受到的影響不大，均保持了大致線性的加速比；Parquet的執行時間加速比其他幾種策略略低。這些都驗證了Group方式的優化在分布式環境下的有效性。

圖9 總數據量160 GB上16并發任務的執行時間

上述執行過程中，通過不斷增加節點數量對上述4個查詢的平均執行時間進行統計比較，如圖10所示。可以看到不同存儲架構和大數據平臺的執行時間大致隨節點數量增加而減少。其中研究給出的方法在不同規模下具有較好的可擴展性。

圖10 總數據量160 GB上變節點數量查詢平均執行時間

實驗4真實負載執行效率比較

最后通過在Medline網站下載真實的Pubmed數據，共計1 800萬嵌套記錄，模式包含107個節點，共計80 GB。不同框架在磁盤和內存中的執行時間如圖11所示。

圖中顯示非行存框架Parquet、Trevni和Group的執行結果基本與圖6給出的結果一致。該模式較為復雜（模式節點多且層次更深），其中選擇僅在很少的列上執行，因而相對于圖6，圖11中行存框架Avro的執行效率進一步顯著降低。此外，可以看到Group較之于其他框架仍具有顯著優勢。

圖11 嵌套分組與其他方法真實負載性能比較

6 結束語

提出一種行列混合式存儲方法，通過引入分組形成邏輯上完整但局部上獨立的列組物理單元。分析了現有單純行存儲和列存儲的優勢和潛在不足，并通過模式驅動設計行列混合物理存儲結構。基于Trevni對所提方法予以實現以降低列存到元組轉換過程中的開銷并保證數據交換的有效性。通過union對存儲結構進行優化，使得訪問能夠集中于有效的單元中。實驗基于10億條TPCH數據進行。結果表明所提方法較傳統行列存儲方法有顯著提升。