最近看到一篇很好資料，里面三言兩語(yǔ)配上幾個(gè)圖就把列式存儲(chǔ)(Column-based Storage)講明白了，牛??！最喜歡的就是這種淺顯易懂就把背景知識(shí)講得明明白白，而不是長(zhǎng)篇大論的講概念。
1 為什么要按列存儲(chǔ)
列式存儲(chǔ)(Columnar or column-based)是相對(duì)于傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的行式存儲(chǔ)(Row-basedstorage)來(lái)說(shuō)的。簡(jiǎn)單來(lái)說(shuō)兩者的區(qū)別就是如何組織表(翻譯不好，直接抄原文了)：
? Row-based storage stores atable in a sequence of rows.
? Column-based storage storesa table in a sequence of columns.
下面來(lái)看一個(gè)例子：

image.png

從上圖可以很清楚地看到，行式存儲(chǔ)下一張表的數(shù)據(jù)都是放在一起的，但列式存儲(chǔ)下都被分開(kāi)保存了。所以它們就有了如下這些優(yōu)缺點(diǎn)：

注：關(guān)系型數(shù)據(jù)庫(kù)理論回顧 - 選擇(Selection)和投影(Projection)

選擇(Selection) 選擇是單目運(yùn)算，其運(yùn)算對(duì)象是一個(gè)表。該運(yùn)算按給定的條件，從表中選出滿足條件的行形成一個(gè)新表作為運(yùn)算結(jié)果。 選擇運(yùn)算的記號(hào)為 σF(R)。 其中σ是選擇運(yùn)算符，下標(biāo)F是一個(gè)條件表達(dá)式，R是被操作的表。 投影(Projection) 投影也是單目運(yùn)算，該運(yùn)算從表中選出指定的屬性值組成一個(gè)新表，記為：ΠA(R)。 其中A是屬性名（即列名）表，R是表名。 連接(JOIN) 把兩個(gè)表中的行按著給定的條件拼接而形成的新表。 執(zhí)行順序：自然連接–>選取–>投影

2補(bǔ)充：數(shù)據(jù)壓縮
剛才其實(shí)跳過(guò)了資料里提到的另一種技術(shù)：通過(guò)字典表壓縮數(shù)據(jù)。為了方面后面的講解，這部分也順帶提一下了。
下面中才是那張表本來(lái)的樣子。經(jīng)過(guò)字典表進(jìn)行數(shù)據(jù)壓縮后，表中的字符串才都變成數(shù)字了。正因?yàn)槊總€(gè)字符串在字典表里只出現(xiàn)一次了，所以達(dá)到了壓縮的目的(有點(diǎn)像規(guī)范化和非規(guī)范化Normalize和Denomalize)

3查詢執(zhí)行性能
下面就是最牛的圖了，通過(guò)一條查詢的執(zhí)行過(guò)程說(shuō)明列式存儲(chǔ)(以及數(shù)據(jù)壓縮)的優(yōu)點(diǎn)：

關(guān)鍵步驟如下：

1.去字典表里找到字符串對(duì)應(yīng)數(shù)字(只進(jìn)行一次字符串比較)。

2.用數(shù)字去列表里匹配，匹配上的位置設(shè)為1。

3.把不同列的匹配結(jié)果進(jìn)行位運(yùn)算得到符合所有條件的記錄下標(biāo)。

4.使用這個(gè)下標(biāo)組裝出最終的結(jié)果集。

從Dremel和Impala的學(xué)習(xí)引申出了SQL查詢的并行執(zhí)行問(wèn)題，于是借此機(jī)會(huì)深入學(xué)習(xí)一下關(guān)系數(shù)據(jù)庫(kù)以及關(guān)系代數(shù)的并行計(jì)算。
Speedup和Scaleup
Speedup指用兩倍的硬件換來(lái)一半的執(zhí)行時(shí)間。Scaleup指兩倍的硬件換來(lái)同等時(shí)間內(nèi)執(zhí)行兩倍的任務(wù)。但往往事情不是那么簡(jiǎn)單，兩倍的硬件也會(huì)帶來(lái)其他問(wèn)題：更多CPU帶來(lái)的長(zhǎng)啟動(dòng)時(shí)間和通信開(kāi)銷，以及并行計(jì)算帶來(lái)的數(shù)據(jù)傾斜問(wèn)題。

多處理器架構(gòu)
共享內(nèi)存：任意CPU都能訪問(wèn)任意的內(nèi)存(全局共享)和磁盤(pán)。優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是擴(kuò)展性差，可用性低。

共享磁盤(pán)：任意CPU都能訪問(wèn)任何的磁盤(pán)，但是只能訪問(wèn)自己的主存。優(yōu)點(diǎn)是可用性和擴(kuò)展性比較好，缺點(diǎn)是實(shí)現(xiàn)復(fù)雜以及潛在的性能問(wèn)題。

不共享：任意CPU都只能訪問(wèn)自己的主存和磁盤(pán)。優(yōu)點(diǎn)也是擴(kuò)展性和可用性，缺點(diǎn)是實(shí)現(xiàn)復(fù)雜以及復(fù)雜均衡。

混合型：系統(tǒng)整體上是shared nothing架構(gòu)，但結(jié)點(diǎn)內(nèi)部可能是其他架構(gòu)。這樣就混合了多種架構(gòu)的優(yōu)點(diǎn)。

數(shù)據(jù)分區(qū)
數(shù)據(jù)分區(qū)的目的就是：讓數(shù)據(jù)庫(kù)能夠并行地讀寫(xiě)數(shù)據(jù)，最大程度地挖掘I/O的潛力。常見(jiàn)的分區(qū)算法有：round-robin、范圍索引、哈希。

關(guān)系運(yùn)算并行化
關(guān)系代數(shù)自身的屬性允許關(guān)系操作的并行化。

并行查詢處理主要分為四步：
??翻譯：將關(guān)系代數(shù)表達(dá)式翻譯成查詢樹(shù)。
??優(yōu)化：重排join順序，并選擇不同join算法來(lái)最小化執(zhí)行開(kāi)銷。
??并行：將查詢樹(shù)轉(zhuǎn)換成物理操作樹(shù)，并加載到處理器。
??執(zhí)行：并行運(yùn)行最終的執(zhí)行計(jì)劃。
首先將一條SQL語(yǔ)句翻譯成查詢樹(shù)。

然后根據(jù)表大小、索引等情況，重新排列join順序，并選擇合適的算法。

關(guān)于join算法，常見(jiàn)的有以下幾種：
??Nested Loop join：思路很簡(jiǎn)單，相當(dāng)于兩層循環(huán)遍歷，外層是驅(qū)動(dòng)表，返回滿足關(guān)聯(lián)條件的行。適用于驅(qū)動(dòng)表小(經(jīng)過(guò)條件過(guò)濾后)，而被驅(qū)動(dòng)表上join字段有索引的情況。在兩表都很大時(shí)效率很差。

for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)

??Sort-merge join：思路也很簡(jiǎn)單，就是按join字段排序，然后進(jìn)行歸并排序。當(dāng)join字段存在重復(fù)值時(shí)，相當(dāng)于每個(gè)重復(fù)值形成了一個(gè)分區(qū)。Join字段是否排序和重復(fù)值的多少?zèng)Q定了sort-merge的效率。適用于兩表都很大的情況，尤其當(dāng)join字段上存在聚集索引時(shí)(相當(dāng)于已經(jīng)排好序了)，效率很高。算法主要消耗在磁盤(pán)上。
??Hash join：類似于存在重復(fù)值情況時(shí)的sort-merge，只不過(guò)是人為的使用哈希函數(shù)進(jìn)行分區(qū)。思路是掃描小表建立哈希表(build階段，小表也叫build表)，然后逐行掃描大表進(jìn)行比較(probe階段，大表也叫probe表)。適用于兩表都很大又沒(méi)有索引的情況，限制是只適用于等值連接。算法主要消耗在CPU上。

此外，對(duì)于子查詢還有semi join和anti join等算法。
最后將查詢樹(shù)變成物理操作樹(shù)，也就是真正的執(zhí)行計(jì)劃。然后根據(jù)集群的資源情況，調(diào)度到合適的結(jié)點(diǎn)上進(jìn)行并行計(jì)算。

參考資料

1 Parallel Query Processing

五大存儲(chǔ)模型

昨天跟一同事討論Sybase是不是關(guān)系型數(shù)據(jù)庫(kù)，同事說(shuō)Sybase是列式存儲(chǔ)，應(yīng)該屬于NoSQL，我一直的記憶Sybase是關(guān)系型數(shù)據(jù)庫(kù)，后來(lái)專門(mén)去查了資料，才發(fā)現(xiàn)同事所說(shuō)的Sybase IO是列式存儲(chǔ);而我說(shuō)的是Sybase SQL Server，是關(guān)系型數(shù)據(jù)庫(kù)。網(wǎng)上看到這篇文章，算是對(duì)幾種數(shù)據(jù)庫(kù)模型補(bǔ)補(bǔ)課。
數(shù)據(jù)庫(kù)市場(chǎng)需要細(xì)分，行式數(shù)據(jù)庫(kù)不再滿足所有的需求，而有很多需求需要通過(guò)本內(nèi)存數(shù)據(jù)庫(kù)和列式數(shù)據(jù)庫(kù)解決，列式數(shù)據(jù)庫(kù)在數(shù)據(jù)分析、海量存儲(chǔ)、BI這三個(gè)領(lǐng)域有自己獨(dú)到。

1. 關(guān)系型數(shù)據(jù)庫(kù)(行式數(shù)據(jù)庫(kù)) MySQL Sybase Oracle

定義：關(guān)系模型使用記錄（行或者元祖）進(jìn)行存儲(chǔ)，記錄存儲(chǔ)在表中，表由架構(gòu)界定。表中的每個(gè)列都有名稱和類型，表中的所有記錄都要符合表的定義。SQL是專門(mén)的查詢語(yǔ)言，提供相應(yīng)的語(yǔ)法查找符合條件的記錄，如表聯(lián)接（Join）。表聯(lián)接可以基于表之間的關(guān)系在多表之間查詢記錄。
存儲(chǔ)格式：行式數(shù)據(jù)庫(kù)把一行中的數(shù)據(jù)值串在一起存儲(chǔ)起來(lái)，然后再存儲(chǔ)下一行的數(shù)據(jù)，以此類推。
例如以下的一個(gè)表：
| EmpId | Lastname | Firstname | Salary |
| 1 | Smith | Joe | 40000 |
| 2 | Jones | Mary | 50000 |
| 3 | Johnson | Cathy | 44000 |

<pre style="box-sizing: border-box; font-family: "Courier New", monospace; font-size: 12px; white-space: pre-wrap; display: block; padding: 0px; margin: 0px 0px 1em; line-height: 1.5em; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background: rgb(247, 247, 247); border: 1px solid rgb(204, 204, 204); border-radius: 4px; width: 667.25px; overflow:

auto;">1,Smith,Joe,40000;2,Jones,Mary,50000;3,Johnson,Cathy,44000;</pre>




特點(diǎn)：據(jù)以行相關(guān)的存儲(chǔ)體系架構(gòu)進(jìn)行空間分配，主要適合與小批量的數(shù)據(jù)處理，常用于聯(lián)機(jī)事務(wù)型數(shù)據(jù)處理。不能滿足后面三個(gè)需求：對(duì)數(shù)據(jù)庫(kù)高并發(fā)讀寫(xiě)要求，對(duì)海量數(shù)據(jù)的高效率存儲(chǔ)和訪問(wèn)需求，對(duì)數(shù)據(jù)庫(kù)高可擴(kuò)展性和高可用性。 一句話不適合分布式、高并發(fā)和海量。

2. 列式存儲(chǔ) Sybase IQ, C-Store, Vertica，Hbase

定義：什么是列式數(shù)據(jù)庫(kù)?列式數(shù)據(jù)庫(kù)是以列相關(guān)存儲(chǔ)架構(gòu)進(jìn)行數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)庫(kù)。列式存儲(chǔ)以流的方式在列中存儲(chǔ)所有的數(shù)據(jù)，主要適合與批量數(shù)據(jù)處理和即席查詢。
存儲(chǔ)格式 ：
列式數(shù)據(jù)庫(kù)把一列中的數(shù)據(jù)值串在一起存儲(chǔ)起來(lái)，然后再存儲(chǔ)下一列的數(shù)據(jù)，以此類推。

<pre style="box-sizing: border-box; font-family: "Courier New", monospace; font-size: 12px; white-space: pre-wrap; display: block; padding: 0px; margin: 0px 0px 1em; line-height: 1.5em; color: rgb(51, 51, 51); word-break: break-all; word-wrap: break-word; background: rgb(247, 247, 247); border: 1px solid rgb(204, 204, 204); border-radius: 4px; width: 667.25px; overflow: auto;">1,2,3;Smith,Jones,Johnson;Joe,Mary,Cathy;40000,50000,44000;</pre>

特點(diǎn)：包括查詢快，由于查詢需要讀取的blocks少；數(shù)據(jù)壓縮比高，正因?yàn)橥活愋偷牧写鎯?chǔ)在一起。Load快。 簡(jiǎn)化數(shù)據(jù)建模的復(fù)雜性。但是插入更新慢，不太適合數(shù)據(jù)老是變化，它是按列存儲(chǔ)的。這時(shí)候你就知道它適做DSS（決策支持系統(tǒng)），BI的優(yōu)秀選擇，數(shù)據(jù)集市，數(shù)據(jù)倉(cāng)庫(kù)，它不適合OLTP。
Examples are Sybase IQ, C-Store, Vertica, VectorWise,MonetDB, ParAccel, and Infobright.

3. 鍵值存儲(chǔ) Cassandra, Hbase, Bigtable

即Key-Value存儲(chǔ)，簡(jiǎn)稱KV存儲(chǔ)。它是NoSQL存儲(chǔ)的一種方式。它的數(shù)據(jù)按照鍵值對(duì)的形式進(jìn)行組織，索引和存儲(chǔ)。KV存儲(chǔ)非常適合不涉及過(guò)多數(shù)據(jù)關(guān)系業(yè)務(wù)關(guān)系的業(yè)務(wù)數(shù)據(jù)，同時(shí)能有效減少讀寫(xiě)磁盤(pán)的次數(shù)，比SQL數(shù)據(jù)庫(kù)存儲(chǔ)擁有更好的讀寫(xiě)性能。
典型例子 Sorted String Table即SSTable。其實(shí)STL 庫(kù)中map和hash_map, JAVA中hash_table, hash_map就是鍵值存儲(chǔ)。 但是他們值只支持內(nèi)存操作，而且map的查詢效率太低，關(guān)鍵是他們只是簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，不能實(shí)現(xiàn)較大規(guī)模存儲(chǔ)和分布式,而且數(shù)據(jù)的修改效率比較低。 而SSTalbe就解決了這些問(wèn)題。

鍵值存儲(chǔ)實(shí)際是分布式表格系統(tǒng)的一種。
分布式key-value 系統(tǒng)有cassandra, hbase, bigtable etc
注：其實(shí)Hbase也屬于列式存儲(chǔ)

4. 文檔存儲(chǔ)

文檔存儲(chǔ)支持對(duì)結(jié)構(gòu)化數(shù)據(jù)的訪問(wèn)，不同于關(guān)系模型的是，文檔存儲(chǔ)沒(méi)有強(qiáng)制的架構(gòu)。
事實(shí)上，文檔存儲(chǔ)以封包鍵值對(duì)的方式進(jìn)行存儲(chǔ)。在這種情況下，應(yīng)用對(duì)要檢索的封包采取一些約定，或者利用存儲(chǔ)引擎的能力將不同的文檔劃分成不同的集合，以管理數(shù)據(jù)。
與關(guān)系模型不同的是，文檔存儲(chǔ)模型支持嵌套結(jié)構(gòu)。例如，文檔存儲(chǔ)模型支持XML和JSON文檔，字段的“值”又可以嵌套存儲(chǔ)其它文檔。文檔存儲(chǔ)模型也支持?jǐn)?shù)組和列值鍵。
與鍵值存儲(chǔ)不同的是，文檔存儲(chǔ)關(guān)心文檔的內(nèi)部結(jié)構(gòu)。這使得存儲(chǔ)引擎可以直接支持二級(jí)索引，從而允許對(duì)任意字段進(jìn)行高效查詢。支持文檔嵌套存儲(chǔ)的能力，使得查詢語(yǔ)言具有搜索嵌套對(duì)象的能力，XQuery就是一個(gè)例子。MongoDB通過(guò)支持在查詢中指定JSON字段路徑實(shí)現(xiàn)類似的功能。

MongoDB 對(duì)SQL 和ACID 支持的比較全面的數(shù)據(jù)庫(kù)了。不過(guò)， 比較多的還是介紹日志的采集和存儲(chǔ)，小文件的分布式存儲(chǔ)，類似互聯(lián)網(wǎng)微博應(yīng)用的數(shù)據(jù)存儲(chǔ)等方面的內(nèi)容。

5.圖形數(shù)據(jù)庫(kù)

圖形數(shù)據(jù)庫(kù)存儲(chǔ)頂點(diǎn)和邊的信息，有的支持添加注釋。
圖形數(shù)據(jù)庫(kù)可用于對(duì)事物建模，如社交圖譜、真實(shí)世界的各種對(duì)象。IMDB（Internet MovieDatabase）站點(diǎn)的內(nèi)容就組成了一幅復(fù)雜的圖像，演員與電影彼此交織在一起。
圖形數(shù)據(jù)庫(kù)的查詢語(yǔ)言一般用于查找圖形中斷點(diǎn)的路徑，或端點(diǎn)之間路徑的屬性。Neo4j是一個(gè)典型的圖形數(shù)據(jù)庫(kù)。