黃峰，Kyligence?公司高級研發工程師，目前主要負責?Kyligence?企業級產品的開發以及維護工作。

對?OLAP?場景的查詢而言，單個查詢往往需要在存儲端掃描大量數據，再在內存中進行一些統計分析后，才能輸出所需要的統計結果。因此，如果不能像以?Kylin?為代表的?MOLAP?引擎采用預計算的方式來避免數據的實時掃描，對于基于磁盤存儲的數倉而言，存儲端無疑會因為掃描大量數據造成磁盤吞吐的瓶頸。

既然如此，是否存在別的選擇，可以少從存儲端加載數據呢？列存數據庫正是通過采取合適的數據組織結構，來減小查詢加載的數據量，最終提高查詢效率。

大數據圈的各位對列式存儲一定不陌生，快速浮現你腦海里的想必是?ORCFile，Parquet?等，但其實這些只是數據格式，并不能直接和列存數據庫劃等號。

列存格式?=?列存數據庫

列存數據庫?[1]?更像是基于列存格式，設計的一套完整的數據庫解決方案，而這套解決方案不僅需要考慮數據格式，更要考慮以下因素：

由于考慮成本效率的因素，計算機中的存儲常被設計成多級存儲的結構，所以數據不單在磁盤上有特定的存儲格式，在內存中，甚至?L1，L2，L3?緩存中同樣有其獨特的布局方式。考慮到存儲端復雜的情況，如何結合?OLAP?場景的?workload，從而針對不同的硬件特點設計數據布局，是列存數據庫在存儲端需要考慮的核心問題;

有了在不同存儲層的數據存儲布局之后，數據如何在不同存儲層之間流動，比如，如何從磁盤加載數據到內存，什么時候進行加載，這些都是存取方法?[2]?(Access?Method)所涉及的內容;

數據結構配上合適的算法才能橫行江湖，計算和數據組織方式往往緊密耦合，彰顯團結的力量。如何結合列存的特點設計一個高效的執行引擎，為?Join，Sort，Groupby?等關系算子提供一種更為高效的算法，都是列存數據庫需要考慮的問題。

由此可見，為了追求極致的性能，底層存儲的變化往往會引發?存取方法、?執行引擎、?關系算子算法實現等多方面的一系列適配性的變化，真可謂環環相扣，好不緊張。下面，我們就依次從這幾個方面介紹其所涉及內容。

01

存儲格式

可曾記得把列存的思想引入大數據的先驅者——?RCFile?[3]?，它的基本思想是將數據水平切分成一個個行組，在每個行組內除了元數據和行組切分標識以外，數據部分按列來進行連續存儲。

這樣操作的原因在于?OLAP?的查詢雖然一般都會掃描大量行，但只會涉及少量列，通過這樣的列存布局方式，能夠有效避免無關列的加載，從而達到減小磁盤吞吐的目的。

但似乎先驅者的下場往往不那么盡如人意，RCFile?也沒有擺脫這個魔咒。相較傳統數倉中的列存而言，RCFile?還是太過粗糙，要學就學全套呀!

Hive?的開發者們總結了?RCFile?的經驗教訓，指出其核心問題?[4]?在于：

對數據類型不感知，從而無法對具體類型做編碼優化，限制了列存的存儲高效性;

沒有索引輔助過濾數據(如：謂詞下推)，造成數據讀取效率低下。

站在前人的肩膀上，后續的?ORCFile，Parquet?都開啟了進化之旅，一方面加入一些?Min、Max、Count?等?輕量級統計索引來加速查詢;另一方面，針對不同場景，采用?RLE，Bitcode，Dictionary?Code?等編碼方式進行存儲優化，比如?RLE，針對的就是取值范圍不大，重復度高的數據，假設有一列數據是?AAABBBB，RLE?就會直接采用?A3B4?來表達(其中“3”和“4”代表前一個值出現的次數)。

自此以后，列存格式的風吹遍了整個大數據生態圈，CarbonData?采用多維排序的方式優化數據的列式布局;Druid?在列存之上，通過對維度列進行?Dictionary?編碼加?Bitmap?索引的方式加速了數據的篩選和聚合......

當然，存儲格式并不是只需關心存儲查詢的效率問題，將其應用到實際中所需要考慮的問題同樣重要。比如，2019?年?4?月，Databricks?公司重磅開源?Delta?Lake，給數據添加了?ACID?特性，支持數據的并發讀寫，Hudi?和?Iceberg?也不甘落后，存儲的故事又拉開了一張大幕，世界就是這樣精彩!

02

存取方式

數據存在磁盤上的數據布局叫做存儲格式，而存取方式則包括：

數據是怎么從磁盤讀到內存的？(例如?MySQL?加載數據的時候，是通過全表掃描，還是通過索引掃描)

數據在內存的布局是怎樣的？

數據又是怎么寫回磁盤的？

等一系列過程。

這里我們以數據從磁盤加載到內存的過程為例，來探討列式存儲能夠給存取過程帶來哪些優勢。由于數據最終輸出時是以行為單位，所以在將列存數據讀入內存時，直接定位到要掃描的列，然后按順序重構一行行數據并交由執行引擎處理，就顯得尤為自然，但我們不如想的更深入一步：

內存中的數據表是不是也可以是列式的？

數據是不是可以懶加載(延遲物化)？

對于問題一，Presto、ClickHouse?等實踐者通過在內存中使用列存布局，不僅優化了存儲效率，也使得向量化計算加速分析查詢變為可能;

對于延遲物化?[5]?的問題，核心就在于?數據是否能等到真正需要它們的時候再加載，例如對于以下查詢：

selectb?fromR?wherea?=X?andd?=Y

是直接如上圖左側所示，將查詢涉及到的?a、b、d?列全部加載到內存里構成一行一行數據，然后進行過濾(Filter)和映射(Project);

還是如上圖右側所示，選擇盡量延遲加載，先分別對?a、d?列進行單獨加載過濾，決定要輸出的行(圖中的?01?向量)，再把對應行的?b?列加載輸出，最后再構建成行數據輸出？

這兩者的?Tradeoff?在于，雖然延遲加載能夠減少數據的加載量，但需要維護原始數據的位置，這樣才能找到對應行的其他列的值，然而如果篩選條件(R.a?=?X?and?R.d?=?Y?)不能大量過濾數據，延遲加載反而低效。對于這種情況，就需要根據一些統計信息選擇合適的加載算法，來最大限度的提高效率。

03

執行引擎與關系算子

說完了存儲端的故事，讓我們轉戰計算端，嘮一嘮執行引擎和關系算子與列存之間又有怎樣的故事。

執行引擎

首先，來了解一下執行引擎的在?SQL?查詢過程中發揮了什么樣的作用。

熟悉?SQL?查詢引擎的同學應該都清楚，一條?SQL?會經過詞法語法解析、語義校驗、邏輯執行計劃生成優化等一系列步驟，生成最后的物理執行計劃，例如，對于如下?SQL：

select*fromR?wherea?=1

其物理執行計劃如下圖所示：

執行引擎所做的事情就包括，定義?TableScan，Filter?等一系列關系算子(Operator)的實現框架，從而可以組合使用多個關系算子，構建它們之間的數據依賴關系(也就是執行計劃)，最終實現不同?SQL?的功能。

最經典的執行引擎實現非?Volcano?[6]?莫屬了。它把每一個算子抽象成數據的迭代器(Iterator)，分別由?Open，Next，Close?構成。其中?Open?做一些初始化的工作，比如?TableScan?如何實現打開對應的表文件;Next?按照特定算子的功能邏輯處理數據，增量式得到輸出;Close?清理資源。如下的偽代碼就是?TableScan?的一個實現：

publicclassTableScanimplementIterator{?voidopen{?tableFile.open;?}?Row?next{?if(?(row?=?tableFile.nextRow)?!=?EOF){?returnrow;?}?returnEOF;?}?voidclose{?tableFile.close;?}?}

Volcano?的優點在于處理邏輯清晰，每個算子只需關心自己的處理邏輯即可，耦合性低。不過它的缺點也很明顯，過多虛函數的調用，導致大量?CPU?cache?miss，從而影響?CPU?執行效率。

在數據庫誕生之初，數據庫先賢們奮戰在彌補磁盤和?CPU?速度巨大的鴻溝上，CPU?的浪費顯得微不足道。然而，在數據庫新時代，摩爾定律的失效使得單核性能提升日漸趨緩，OLAP?的發展導致將大量數據加載到內存進行計算，瓶頸慢慢從存儲端向?CPU?端傾斜，榨干?CPU?每一滴性能的企圖就變得越發強烈，于是?CodeGen，向量化執行?[7]?等方法應運而生，它們從不同的方向入手來優化?CPU?的利用率，能夠極大的提高執行效率。?向量化執行正是利用列式存儲的優勢，可以一次性對整列數據進行批量處理，減少?CPU?的消耗。

關系算子

有了執行引擎奠定的框架，關系算子只需要一個蘿卜一個坑，逐一實現即可，然而算法的世界是層出不窮，千變萬化的，比如對于?Join?大家最熟悉的算法就有?BroadcastJoin，LookupJoin，SortJoin?等等，?而列存又會給?Join?算法帶來什么樣的優化空間呢？

對于?Join?而言，運算的核心在于兩表中?Joinkey?的匹配上，而對于其他列數據匹配上了就復制，匹配不上就丟棄。那么結合延遲物化的思想，是否可以等到匹配完成后再加載其他列數據，從而減小不必要的數據加載。

舉個例子，對于如下?SQL：

SELECTemp.age,?dept.name?FROMemp,?dept?WHEREemp.dept_id?=dept.id

我們先抽出?emp?表的?dept_id?和?dept?表的?id?列數據，進行匹配，并輸出匹配結果對應原表的位置信息，如下圖所示：

其中等于號的左邊為?dept_id?和?id?列的數據，等于號的右邊為匹配結果對應原表的位置信息，比如第一行?1，2?代表?dept_id?列的第一個值?42?和?id?列的第?2?個值?42，Join?的結果。

然后根據輸出的位置信息，就可以從原始數據中抽取?age，name?列的數據得到?Join?最后的結果。當然該算法能夠產生明顯優化效果的前提是?Join?的結果相較于原始數據比較小，這樣才能夠有效避免加載過多數據。另外由于上圖輸出結果的第二列是無序的，如果回表查必然造成大量隨機?IO，為了解決這個問題，Jive?Join?[8]?采用了對其進行排序之后再查詢，即將隨機?IO?轉化為順序?IO?的方法進行優化。

04

總結

綜上，我們從大數據存儲格式的變遷;存取方式中?Early?Materialization?和?Late?Materialization?的權衡取舍;執行框架向優化?CPU?的方向邁進;關系算子結合存儲進行優化等幾個方面對列存數據庫進行了講解。

實際上，列存數據庫不只是存儲格式的問題，底層存儲的變化往往牽一發而動全身，如何適應性的修改計算引擎、存取方式等來達到更高更快的性能，并適應不同的?workload?或者硬件發展的趨勢，都是列存數據庫要關心的問題。

參考文獻：

[1]?The?Design?and?Implementation?of?Modern?Column-oriented?Database?Systems.

[2]?Design?Tradeoffs?of?Data?Access?Methods.

[3]?RCFile:?A?Fast?and?Space-efficient?Data?Placement?Structure?in?MapReduce-based?Warehouse?Systems.

[4]?Major?Technical?Advancements?in?Apache?Hive.

[5]?Materialization?Strategies?in?a?Column-oriented?DBMS.

[6]?Encapsulation?of?Parallelism?in?the?Volcano?Query?Processing?System.

[7]?Vectorization?vs.?Compilation?in?Query?Execution.

[8]?Fast?Joins?Using?Join?Indices.

最后，小編給您推薦，如果您不想讓您的文檔被其他人查看，您可以使用金山毒霸“文件夾加密”，讓文檔更加安全。