黃峰，Kyligence?公司高級研發(fā)工程師，目前主要負責(zé)?Kyligence?企業(yè)級產(chǎn)品的開發(fā)以及維護工作。

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

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

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

列存格式?=?列存數(shù)據(jù)庫

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

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

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

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

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

01

存儲格式

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

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

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

Hive?的開發(fā)者們總結(jié)了?RCFile?的經(jīng)驗教訓(xùn)，指出其核心問題?[4]?在于：

對數(shù)據(jù)類型不感知，從而無法對具體類型做編碼優(yōu)化，限制了列存的存儲高效性;

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

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

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

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

02

存取方式

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

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

數(shù)據(jù)在內(nèi)存的布局是怎樣的？

數(shù)據(jù)又是怎么寫回磁盤的？

等一系列過程。

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

內(nèi)存中的數(shù)據(jù)表是不是也可以是列式的？

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

對于問題一，Presto、ClickHouse?等實踐者通過在內(nèi)存中使用列存布局，不僅優(yōu)化了存儲效率，也使得向量化計算加速分析查詢變?yōu)榭赡?

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

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

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

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

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

03

執(zhí)行引擎與關(guān)系算子

說完了存儲端的故事，讓我們轉(zhuǎn)戰(zhàn)計算端，嘮一嘮執(zhí)行引擎和關(guān)系算子與列存之間又有怎樣的故事。

執(zhí)行引擎

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

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

select*fromR?wherea?=1

其物理執(zhí)行計劃如下圖所示：

執(zhí)行引擎所做的事情就包括，定義?TableScan，F(xiàn)ilter?等一系列關(guān)系算子(Operator)的實現(xiàn)框架，從而可以組合使用多個關(guān)系算子，構(gòu)建它們之間的數(shù)據(jù)依賴關(guān)系(也就是執(zhí)行計劃)，最終實現(xiàn)不同?SQL?的功能。

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

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

Volcano?的優(yōu)點在于處理邏輯清晰，每個算子只需關(guān)心自己的處理邏輯即可，耦合性低。不過它的缺點也很明顯，過多虛函數(shù)的調(diào)用，導(dǎo)致大量?CPU?cache?miss，從而影響?CPU?執(zhí)行效率。

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

關(guān)系算子

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

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

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

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

我們先抽出?emp?表的?dept_id?和?dept?表的?id?列數(shù)據(jù)，進行匹配，并輸出匹配結(jié)果對應(yīng)原表的位置信息，如下圖所示：

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

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

04

總結(jié)

綜上，我們從大數(shù)據(jù)存儲格式的變遷;存取方式中?Early?Materialization?和?Late?Materialization?的權(quán)衡取舍;執(zhí)行框架向優(yōu)化?CPU?的方向邁進;關(guān)系算子結(jié)合存儲進行優(yōu)化等幾個方面對列存數(shù)據(jù)庫進行了講解。

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

參考文獻：

[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.

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