前言
233醬工作中開始接觸Presto等大數(shù)據(jù)分析場景下的內(nèi)容欠肾，列式存儲屬于OLAP中重要的一環(huán)。這周主要花時間搜索閱讀網(wǎng)上的相關(guān)資料钳宪，發(fā)現(xiàn)一眾大數(shù)據(jù)、數(shù)據(jù)庫開發(fā)等大佬們的總結(jié)文章，如知乎專欄：「分布式數(shù)據(jù)系統(tǒng)小菜」畸陡、「數(shù)據(jù)庫內(nèi)核」、「Presto」虽填、「尬聊數(shù)據(jù)庫」...這對我這種想要入門的小白是很好的讀物丁恭。本篇文章是我主要基于上述專欄中的一些資料的筆記總結(jié)，因?yàn)槟芰τ邢拚眨茈y跳脫于本文參考資料的總結(jié)牲览。希望本篇文章能對和我一樣的小白起到科普作用，想要了解更多的小伙伴請移步以上專欄恶守。另外第献，對OLAP/Presto等感興趣的小伙伴也歡迎和233醬多多交流，一起學(xué)習(xí)進(jìn)步兔港，求抱大腿庸毫，hhh~~
什么是OLAP
OLAP（Online analytical processing）指聯(lián)機(jī)分析處理。從字面意思上我們可以看出有「分析」二字衫樊，如：統(tǒng)計飒赃，報表，聚合類操作科侈。你說Mysql不也是能做嗎载佳？OLAP還有一側(cè)重點(diǎn)，指大數(shù)據(jù)量的在線分析臀栈，如PB級蔫慧，TB級以上。
下表是對OLTP和OLAP的簡單總結(jié)挂脑。
我們也可以通過兩者的benchmark直觀感受下評判性能的不同側(cè)重點(diǎn)藕漱。
對于OLTP來說欲侮，有sysbench和tpcc測試套件。sysbench的lua腳本中的sql語句如下：
SELECT c FROM sbtest10 WHERE id=4352
SELECT c FROM sbtest10 WHERE id BETWEEN 5046 AND 5046+99 ORDER BY c
對于OLAP來說肋联，有tpch和tpcds 2種威蕉。tpcds的 sql語句舉例如下：
SELECT
"c_last_name"
, "c_first_name"
, "ca_city"
, "bought_city"
, "ss_ticket_number"
, "extended_price"
, "extended_tax"
, "list_price"
FROM
(
SELECT
"ss_ticket_number"
, "ss_customer_sk"
, "ca_city" "bought_city"
, "sum"("ss_ext_sales_price") "extended_price"
, "sum"("ss_ext_list_price") "list_price"
, "sum"("ss_ext_tax") "extended_tax"
FROM
${database}.${schema}.store_sales
, ${database}.${schema}.date_dim
, ${database}.${schema}.store
, ${database}.${schema}.household_demographics
, ${database}.${schema}.customer_address
WHERE ("store_sales"."ss_sold_date_sk" = "date_dim"."d_date_sk")
AND ("store_sales"."ss_store_sk" = "store"."s_store_sk")
AND ("store_sales"."ss_hdemo_sk" = "household_demographics"."hd_demo_sk")
AND ("store_sales"."ss_addr_sk" = "customer_address"."ca_address_sk")
AND ("date_dim"."d_dom" BETWEEN 1 AND 2)
AND (("household_demographics"."hd_dep_count" = 4)
OR ("household_demographics"."hd_vehicle_count" = 3))
AND ("date_dim"."d_year" IN (1999 , (1999 + 1) , (1999 + 2)))
AND ("store"."s_city" IN ('Midway' , 'Fairview'))
GROUP BY "ss_ticket_number", "ss_customer_sk", "ss_addr_sk", "ca_city"
) dn
, ${database}.${schema}.customer
, ${database}.${schema}.customer_address current_addr
WHERE ("ss_customer_sk" = "c_customer_sk")
AND ("customer"."c_current_addr_sk" = "current_addr"."ca_address_sk")
AND ("current_addr"."ca_city" <> "bought_city")
ORDER BY "c_last_name" ASC, "ss_ticket_number" ASC
LIMIT 100
顯然，tpcds的查詢復(fù)雜度相比oltp高非常多橄仍。
為什么行式存儲不適用于OLAP領(lǐng)域
行式存儲是指數(shù)據(jù)的存儲是以行為單位韧涨，一行的數(shù)據(jù)在物理block上緊挨在一起存儲。
好處：操作一行的數(shù)據(jù)方便侮繁。
（雖然聽起來像一句廢話：）
我們以行存代表Mysql為例虑粥，Innodb的聚簇索引（B+樹）示意圖如下：
其中Intern Page上存儲的是索引數(shù)據(jù)，Leaf Page上存儲的完整的行數(shù)據(jù)宪哩。
行存能保證數(shù)據(jù)的修改是原地更新的娩贷，對讀取行數(shù)據(jù)友好，易于隨機(jī)IO锁孟。IO的單位通常是以頁為單位（如16KB）彬祖，也可以通過內(nèi)存緩存/SSD等方式優(yōu)化IO。
缺點(diǎn)：對于分析類sql品抽，通常只需要關(guān)聯(lián)一行中的幾個列數(shù)據(jù)储笑，行存會導(dǎo)致讀取大量無關(guān)的列數(shù)據(jù)，IO浪費(fèi)圆恤，CPU緩存失效...
為什么列式存儲適用于OLAP領(lǐng)域
列式存儲是指數(shù)據(jù)的存儲是以列為單位突倍，一列的數(shù)據(jù)在物理block上緊挨在一起存儲。
顯然盆昙，如果我們查詢：
select count(*) from table where name = '233'羽历；
只需要從中按需讀取name一列進(jìn)行分析總數(shù)就可以了，看樣子節(jié)省了不少I/O弱左。但列式存儲只有這一個必殺技嗎窄陡？
Column-Stores vs. Row-Stores: How Different Are TheyReally?一文中在行式存儲中模擬了列式范式設(shè)計：
通過將表結(jié)構(gòu)垂直拆分以及全列建索引炕淮，就可以在查詢時拆火，只查詢部分列對應(yīng)的數(shù)據(jù)，從而加快分析速度涂圆。
最終實(shí)驗(yàn)得出：在行式存儲上就算以column-oriented方式來設(shè)計數(shù)據(jù)的物理結(jié)構(gòu)们镜，面對分析型場景還是無法與列式存儲抗衡。對于分析型場景润歉，列式存儲在本質(zhì)上優(yōu)于行式存儲模狭。
其中關(guān)鍵的幾大殺器是：編碼壓縮（compression）、向量化查詢處理（vectorized query processing）踩衩、隱式連接（invisible join）嚼鹉、延遲物化（late materialization）等贩汉。壓縮帶來的性能提升要看真實(shí)數(shù)據(jù)，最多時有一個數(shù)量級之多锚赤，延遲物化提高3倍匹舞，塊迭代和隱式連接提升約1.5倍。而這些技術(shù)的應(yīng)用线脚，需要從存儲層到計算層的全面支持才行赐稽，顯然，目前主流的行式存儲并不具備這樣的條件浑侥。
下面我將簡單介紹下這些技術(shù)姊舵。
編碼壓縮
列式存儲的數(shù)據(jù)屬于同一種類型，如數(shù)值類型寓落，字符串類型等括丁。相似度很高，試用合適的編碼壓縮可減少數(shù)據(jù)的存儲空間伶选，進(jìn)而減少IO提高讀取性能躏将。
C-Store中針對數(shù)值類型的數(shù)據(jù)是否排序、區(qū)分度（Number of Distince Values）排列組合出4種情況考蕾，并給出了一些編碼方案祸憋。
- 有序且區(qū)分度不多
可以使用一系列三元組(v,f,n)對列數(shù)據(jù)編碼，表示值 v 從第 f 行出現(xiàn)肖卧，一共有 n 個（即 f 到 f+n?1 行）蚯窥。如：數(shù)值 2 出現(xiàn)在 10-15行，則編碼為 (2,10,6)塞帐。
- 無序且區(qū)分度不多
可以使用位圖構(gòu)造每個列取值出現(xiàn)的行位置拦赠，如：一列的數(shù)據(jù)為0,0,1,1,1,0,0,2,2，
則編碼為 (0, 110001100)葵姥、(1, 001110000) 和 (2,000000011)
同時對稀疏的位圖可進(jìn)一步進(jìn)行行程編碼（Run Length Encoding荷鼠，RLE)壓縮數(shù)據(jù)。
- 有序且區(qū)分度多
這時候可以使用等差數(shù)列（每個數(shù)值表示為前一個數(shù)值加上一個變化量）來減小數(shù)據(jù)的存儲榔幸。如：對于一列數(shù)據(jù) 1,4,7,7,8,12允乐，
可以表示為序列 1,3,3,0,1,4。
- 無序且區(qū)分度多
這種情況數(shù)據(jù)的規(guī)律性不強(qiáng)削咆，沒有很好的編碼方式牍疏。
其他場景的編碼還有varint、字符串字典編碼（Dictionary Encoding）等拨齐，這些輕量級的編碼技術(shù)僅需要多付出一些CPU鳞陨，就可以節(jié)省不小的IO。
對于復(fù)雜類型瞻惋，嵌套類型的可以使用Google Dremel提出Striping/Assembly算法（開源Parquet）厦滤，使用Definition Level+Repetition Level做編解碼援岩。一些數(shù)值類型有時也可以嘗試大一統(tǒng)的用bitshuffle做轉(zhuǎn)換，配合壓縮效果也不錯掏导，例如KUDU和百度Palo（Doris）中有應(yīng)用窄俏。
同時，對于有些壓縮/編碼算法碘菜，比如RLE算法凹蜈，針對壓縮后的數(shù)據(jù)無需解壓就可以直接做謂詞下推，加快計算速度忍啸。如：AAAAABBCCCDDDDA --> A5B2C3D4A1仰坦，如果要以where col = 'C'過濾數(shù)據(jù)，平均計算復(fù)雜度等于總行數(shù)/列的基數(shù)计雌，列基越大過濾越快（當(dāng)然副作用是結(jié)果集很大）悄晃；另外，如果輸出的列數(shù)據(jù)是排過序的凿滤，那where col = 'C'過濾數(shù)據(jù)的計算復(fù)雜度降為log(總行數(shù)/列的基數(shù))妈橄，速度更快。
在編碼基礎(chǔ)上翁脆，還可以進(jìn)行傳統(tǒng)的壓縮眷蚓，如snappy等支持流式處理、吞吐量高的壓縮算法反番。
向量化執(zhí)行
向量化是指一個CPU指令可以同時處理多條數(shù)據(jù)沙热，如下圖:
當(dāng)把v1和v2數(shù)組中的數(shù)據(jù)分別加載到寄存器XMM0和XMM1中時，可以通過一條指令就完成兩個數(shù)組的和vec_res計算罢缸。
這需要CPU對向量化指令的支持篙贸，如SSE2, AVX等。
在軟件層面上枫疆，向量化代碼的書寫方式體現(xiàn)在：先準(zhǔn)備好待處理的批量數(shù)據(jù)爵川，然后在對批量數(shù)據(jù)在一個for循環(huán)內(nèi)做簡單操作。
對于一個實(shí)現(xiàn)兩個 int 相加的 expression：
沒有向量化的代碼書寫方式：
class ExpressionIntAdd extends Expression {
Datum eval(Row input) {
int left = input.getInt(leftIndex);
int right = input.getInt(rightIndex);
return new Datum(left+right);
}
}
向量化后的代碼書寫方式：
class VectorExpressionIntAdd extends VectorExpression {
int[] eval(int[] left, int[] right) {
int[] ret = new int[input.length];
for(int i = 0; i < input.length; i++) {
ret[i] = new Datum(left[i] + right[i]);
}
return ret;
}
}
對比向量化之前的版本息楔，向量化之后的版本不再是每次只處理一條數(shù)據(jù)寝贡，而是每次能處理一批數(shù)據(jù)，而且這種向量化的計算模式在計算過程中也具有更好的數(shù)據(jù)局部性钞螟。這樣可以讓計算更多的停留在函數(shù)內(nèi)兔甘，而不是頻繁的交互切換，提高了CPU的流水線并行度鳞滨，而且還可以使用SIMD指令，例如AVX指令集來實(shí)現(xiàn)數(shù)據(jù)并行處理蟆淀。
向量化執(zhí)行引擎以列存為前提拯啦，每次從磁盤上讀取一批列澡匪，這些列以數(shù)組形式組織。每次operator（如實(shí)際執(zhí)行中的scan掃表算子褒链，agg聚合算子）的next操作都通過for循環(huán)處理列數(shù)組唁情。這么做可以大幅減少next的調(diào)用次數(shù)。相應(yīng)的CPU的利用率得到了提高甫匹，另外數(shù)據(jù)被組織在一起甸鸟。可以進(jìn)一步利用CPU硬件的特性兵迅，如SIMD抢韭，將所有數(shù)據(jù)加載到CPU的緩存當(dāng)中去，提高緩存命中率恍箭，提升效率刻恭。在列存儲與向量化執(zhí)行引擎的雙重優(yōu)化下，查詢執(zhí)行的速度會有一個非常巨大的飛躍扯夭。但是向量化也會帶來額外的開銷鳍贾，就是物化中間結(jié)果（materlization），以犧牲物化的開銷換取更高的計算性能交洗。
延遲物化
物化指的是在SQL的執(zhí)行過程中骑科，獲得最終數(shù)據(jù)的所處執(zhí)行時機(jī)。如：
select R.b from R where R.a=X and R.d=Y
延遲物化是指只有在算出過濾條件所對應(yīng)的準(zhǔn)確記錄時构拳，才去取記錄所對應(yīng)的結(jié)果值b.
對于OLAP場景纵散，延遲物化的好處有：
很多聚合與選擇計算，壓根不需要整行數(shù)據(jù)隐圾，過早物化會浪費(fèi)嚴(yán)重伍掀；
很多列是壓縮過的，過早物化會導(dǎo)致提前解壓縮暇藏，但很多操作可以直接下推到壓縮數(shù)據(jù)上的蜜笤；
面向真正需要的列做計算，CPU的cache效率很高（100%）盐碱，而行存因?yàn)榉潜匾姓加昧薱ache line中的空間把兔，cache效率顯然不高；
針對定長的列做塊迭代處理瓮顽，可以當(dāng)成一個數(shù)組來操作县好，可以利用CPU的很多優(yōu)勢（SIMD加速、cache line適配暖混、CPU pipeline等）缕贡；相反，行存中列類型往往不一樣，長度也不一樣晾咪，還有大量不定長字段收擦，難以加速。
隱式連接
對于多表Join谍倦，傳統(tǒng)的做法一般是找到過濾性最強(qiáng)的維度表來關(guān)聯(lián)事實(shí)表并過濾塞赂，然后再與其他維度表一一關(guān)聯(lián)，得到最終的結(jié)果昼蛀。
而隱式連接主要分三個步驟：
對于SQL：
SELECT c.nation, s.nation, d.year,
sum(lo.revenue) as revenue
FROM customer AS c, lineorder AS lo,
supplier AS s, dwdate AS d
WHERE lo.custkey = c.custkey
AND lo.suppkey = s.suppkey
AND lo.orderdate = d.datekey
AND c.region = 'ASIA'
AND s.region = 'ASIA'
AND d.year >= 1992 and d.year <= 1997
GROUP BY c.nation, s.nation, d.year
ORDER BY d.year asc, revenue desc;
1.下推相關(guān)條件到各個維度表宴猾，提煉出被事實(shí)表關(guān)聯(lián)的主鍵列表（也就是事實(shí)表的外鍵），并構(gòu)建對應(yīng)的hash table（key是外鍵值叼旋，value是外鍵在維度表中的position）仇哆；
2.對多個事實(shí)表以外鍵關(guān)聯(lián)維度表的列進(jìn)行探測，查找對應(yīng)的hash table送淆，過濾出多個position list（與被關(guān)聯(lián)的列相關(guān)）税产，然后對多個position list求交集（比如bitmap的AND計算等），得到一個最終的position list偷崩；
3.基于前面的position list辟拷，最終從事實(shí)表中找到需要投影的其他列，而通過hash table從維度表找到需要投影的其他列阐斜，hash table中的value是維度表中的position衫冻，所以可以快速定位維度表的其他列。
這里的“隱式”是指谒出，沒有通過傳統(tǒng)的join方式（兩兩表迭代隅俘，生成兩個表聯(lián)合在一起的寬行數(shù)據(jù)，再做過濾）來實(shí)現(xiàn)join笤喳，而是通過維持不同列的相同行之間的position對應(yīng)關(guān)系來完成多個表join为居。與倒排索引很類似。
除此之外杀狡，動態(tài)代碼生成蒙畴、塊IO（相比page IO,一次讀取的數(shù)據(jù)量更大）,針對塊建立的稀疏索引（因?yàn)閴K較大，索引量小呜象，可盡可能將索引數(shù)據(jù)加載到內(nèi)存）膳凝，倒排索引，Join索引等都可加速基于列式存儲的SQL執(zhí)行效率恭陡。
但是僅僅將數(shù)據(jù)按照列式存儲就可以解決所有問題了嗎蹬音？
列式存儲本質(zhì)上方便的是列式數(shù)據(jù)的讀取，但當(dāng)SQL的查詢結(jié)果是需要行相關(guān)的數(shù)據(jù)時休玩，如何兼顧列式存儲重構(gòu)出行的數(shù)據(jù)著淆，這和列式存儲的存儲格式和索引結(jié)構(gòu)有很大關(guān)系劫狠。
存儲格式和索引結(jié)構(gòu)
典型的列式存儲數(shù)據(jù)庫系統(tǒng)有Microsoft SQL Server、C-Store (2005) / Vertica牧抽、Dremel嘉熊、Apache Kudu遥赚、MonetDB等扬舒。文末的參考資料中分別對其存儲結(jié)果有一些介紹。這里我列舉一下Apache ORC文件格式幫助對列式的存儲格式和索引結(jié)構(gòu)有所了解凫佛。
Apache ORC的分區(qū)索引結(jié)構(gòu)如下：
ORC將數(shù)據(jù)結(jié)構(gòu)分成以下 3 個層級讲坎，在每個層級上都有索引信息來加速查詢。
File Level：即一個 ORC 文件愧薛，F(xiàn)ooter 中保存了數(shù)據(jù)的 meta 信息晨炕，還有文件數(shù)據(jù)的索引信息，例如各列數(shù)據(jù)的最大最小值（范圍）毫炉、NULL 值分布瓮栗、布隆過濾器等，這些信息可用來快速確定該文件是否包含要查詢的數(shù)據(jù)瞄勾。每個 ORC 文件中包含多個 Stripe费奸。
Stripe Level 對應(yīng)原表的一個范圍分區(qū)，里面包含該分區(qū)內(nèi)各列的值进陡。每個 Stripe 也有自己的一個索引放在 footer 里愿阐，和 file-level 索引類似。
Row-Group Level ：一列中的每 10000 行數(shù)據(jù)構(gòu)成一個 row-group趾疚，每個 row-group 擁有自己的 row-level 索引缨历，信息同上。
ORC 里的 Stripe 就像傳統(tǒng)數(shù)據(jù)庫的頁糙麦，它是 ORC 文件批量讀寫的基本單位辛孵。
其中Row-Group的概念方便對行數(shù)據(jù)的重新整合。數(shù)據(jù)分區(qū)赡磅、分區(qū)內(nèi)索引魄缚、行列混合等這些思想都可見于分布式存儲系統(tǒng)中。
后記
本文簡要總結(jié)了列式存儲的好處仆邓，Apache ORC的存儲格式等鲜滩。旨在幫助你我對OLAP場景下的列式存儲有一個初步認(rèn)識。更深一步的話題：如列式存儲到底是如何實(shí)現(xiàn)的节值，CRUD過程是如何的徙硅，涉及的分布式存儲問題又是如何解決的...開頭的一些專欄和文末參考資料中有一些闡述。因?yàn)?33醬離數(shù)據(jù)庫開發(fā)還很遠(yuǎn)搞疗，就不進(jìn)一步尬聊了嗓蘑。须肆。
文中有不懂的地方歡迎和233醬交流，一起進(jìn)步桩皿。后面233醬也打算分享更多OLAP相關(guān)的知識豌汇，如Presto。不是這種總結(jié)筆記的方式泄隔。期待與你再次相遇～
參考資料：
[1].https://zhuanlan.zhihu.com/p/144926830
[2].https://zhuanlan.zhihu.com/p/35622907
[3].https://zhuanlan.zhihu.com/p/54484592
[4].https://zhuanlan.zhihu.com/p/100933389
[5].https://www.bilibili.com/video/BV1Bt411v7ST
[6].https://www.the-paper-trail.org/post/2013-01-30-columnar-storage/
