最近看到一篇很好資料，里面三言兩語配上幾個(gè)圖就把列式存儲(chǔ)(Column-based Storage)講明白了，牛?。∽钕矚g的就是這種淺顯易懂就把背景知識講得明明白白，而不是長篇大論的講概念。

1 為什么要按列存儲(chǔ)

列式存儲(chǔ)(Columnar or column-based)是相對于傳統(tǒng)關(guān)系型數(shù)據(jù)庫的行式存儲(chǔ)(Row-basedstorage)來說的。簡單來說兩者的區(qū)別就是如何組織表(翻譯不好，直接抄原文了)：

? Row-based storage stores atable in a sequence of rows.

? Column-based storage storesa table in a sequence of columns.

下面來看一個(gè)例子：

image.png

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

image.png

image.png

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

選擇(Selection)

選擇是單目運(yùn)算，其運(yùn)算對象是一個(gè)表。該運(yùn)算按給定的條件，從表中選出滿足條件的行形成一個(gè)新表作為運(yùn)算結(jié)果。 
選擇運(yùn)算的記號為 σF(R)。 
其中σ是選擇運(yùn)算符，下標(biāo)F是一個(gè)條件表達(dá)式，R是被操作的表。

投影(Projection)

投影也是單目運(yùn)算，該運(yùn)算從表中選出指定的屬性值組成一個(gè)新表，記為：ΠA(R)。 
其中A是屬性名（即列名）表，R是表名。

連接(JOIN)

把兩個(gè)表中的行按著給定的條件拼接而形成的新表。 
執(zhí)行順序：自然連接–>選取–>投影

image.png

2補(bǔ)充：數(shù)據(jù)壓縮

剛才其實(shí)跳過了資料里提到的另一種技術(shù)：通過字典表壓縮數(shù)據(jù)。為了方面后面的講解，這部分也順帶提一下了。

下面中才是那張表本來的樣子。經(jīng)過字典表進(jìn)行數(shù)據(jù)壓縮后，表中的字符串才都變成數(shù)字了。正因?yàn)槊總€(gè)字符串在字典表里只出現(xiàn)一次了，所以達(dá)到了壓縮的目的(有點(diǎn)像規(guī)范化和非規(guī)范化Normalize和Denomalize)

image.png

3查詢執(zhí)行性能

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

image.png

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

1. 去字典表里找到字符串對應(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í)行問題，于是借此機(jī)會(huì)深入學(xué)習(xí)一下關(guān)系數(shù)據(jù)庫以及關(guān)系代數(shù)的并行計(jì)算。

Speedup和Scaleup

Speedup指用兩倍的硬件換來一半的執(zhí)行時(shí)間。Scaleup指兩倍的硬件換來同等時(shí)間內(nèi)執(zhí)行兩倍的任務(wù)。但往往事情不是那么簡單，兩倍的硬件也會(huì)帶來其他問題：更多CPU帶來的長啟動(dòng)時(shí)間和通信開銷，以及并行計(jì)算帶來的數(shù)據(jù)傾斜問題。

image.png

多處理器架構(gòu)

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

image.png

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

image.png

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

image.png

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

image.png

數(shù)據(jù)分區(qū)

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

image.png

關(guān)系運(yùn)算并行化

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

image.png

并行查詢處理主要分為四步：

? 翻譯：將關(guān)系代數(shù)表達(dá)式翻譯成查詢樹。

? 優(yōu)化：重排join順序，并選擇不同join算法來最小化執(zhí)行開銷。

? 并行：將查詢樹轉(zhuǎn)換成物理操作樹，并加載到處理器。

? 執(zhí)行：并行運(yùn)行最終的執(zhí)行計(jì)劃。

首先將一條SQL語句翻譯成查詢樹。

image.png

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

image.png

關(guān)于join算法，常見的有以下幾種：

? Nested Loop join：思路很簡單，相當(dāng)于兩層循環(huán)遍歷，外層是驅(qū)動(dòng)表，返回滿足關(guān)聯(lián)條件的行。適用于驅(qū)動(dòng)表小(經(jīng)過條件過濾后)，而被驅(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：思路也很簡單，就是按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)排好序了)，效率很高。算法主要消耗在磁盤上。

? Hash join：類似于存在重復(fù)值情況時(shí)的sort-merge，只不過是人為的使用哈希函數(shù)進(jìn)行分區(qū)。思路是掃描小表建立哈希表(build階段，小表也叫build表)，然后逐行掃描大表進(jìn)行比較(probe階段，大表也叫probe表)。適用于兩表都很大又沒有索引的情況，限制是只適用于等值連接。算法主要消耗在CPU上。

image.png

此外，對于子查詢還有semi join和anti join等算法。

最后將查詢樹變成物理操作樹，也就是真正的執(zhí)行計(jì)劃。然后根據(jù)集群的資源情況，調(diào)度到合適的結(jié)點(diǎn)上進(jìn)行并行計(jì)算。

image.png

參考資料

1 Parallel Query Processing

五大存儲(chǔ)模型

昨天跟一同事討論Sybase是不是關(guān)系型數(shù)據(jù)庫，同事說Sybase是列式存儲(chǔ)，應(yīng)該屬于NoSQL，我一直的記憶Sybase是關(guān)系型數(shù)據(jù)庫，后來專門去查了資料，才發(fā)現(xiàn)同事所說的Sybase IO是列式存儲(chǔ);而我說的是Sybase SQL Server，是關(guān)系型數(shù)據(jù)庫。網(wǎng)上看到這篇文章，算是對幾種數(shù)據(jù)庫模型補(bǔ)補(bǔ)課。

數(shù)據(jù)庫市場需要細(xì)分，行式數(shù)據(jù)庫不再滿足所有的需求，而有很多需求需要通過本內(nèi)存數(shù)據(jù)庫和列式數(shù)據(jù)庫解決，列式數(shù)據(jù)庫在數(shù)據(jù)分析、海量存儲(chǔ)、BI這三個(gè)領(lǐng)域有自己獨(dú)到。

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

定義：關(guān)系模型使用記錄（行或者元祖）進(jìn)行存儲(chǔ)，記錄存儲(chǔ)在表中，表由架構(gòu)界定。表中的每個(gè)列都有名稱和類型，表中的所有記錄都要符合表的定義。SQL是專門的查詢語言，提供相應(yīng)的語法查找符合條件的記錄，如表聯(lián)接（Join）。表聯(lián)接可以基于表之間的關(guān)系在多表之間查詢記錄。

存儲(chǔ)格式：行式數(shù)據(jù)庫把一行中的數(shù)據(jù)值串在一起存儲(chǔ)起來，然后再存儲(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è)需求：對數(shù)據(jù)庫高并發(fā)讀寫要求，對海量數(shù)據(jù)的高效率存儲(chǔ)和訪問需求，對數(shù)據(jù)庫高可擴(kuò)展性和高可用性。 一句話不適合分布式、高并發(fā)和海量。

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

定義：什么是列式數(shù)據(jù)庫?列式數(shù)據(jù)庫是以列相關(guān)存儲(chǔ)架構(gòu)進(jìn)行數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)庫。列式存儲(chǔ)以流的方式在列中存儲(chǔ)所有的數(shù)據(jù)，主要適合與批量數(shù)據(jù)處理和即席查詢。

存儲(chǔ)格式 ：

列式數(shù)據(jù)庫把一列中的數(shù)據(jù)值串在一起存儲(chǔ)起來，然后再存儲(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快。 簡化數(shù)據(jù)建模的復(fù)雜性。但是插入更新慢，不太適合數(shù)據(jù)老是變化，它是按列存儲(chǔ)的。這時(shí)候你就知道它適做DSS（決策支持系統(tǒng)），BI的優(yōu)秀選擇，數(shù)據(jù)集市，數(shù)據(jù)倉庫，它不適合OLTP。

Examples are Sybase IQ, C-Store, Vertica, VectorWise,MonetDB, ParAccel, and Infobright.

具體請參考如下地址:http://en.wikipedia.org/wiki/Column-oriented_DBMS.

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

即Key-Value存儲(chǔ)，簡稱KV存儲(chǔ)。它是NoSQL存儲(chǔ)的一種方式。它的數(shù)據(jù)按照鍵值對的形式進(jìn)行組織，索引和存儲(chǔ)。KV存儲(chǔ)非常適合不涉及過多數(shù)據(jù)關(guān)系業(yè)務(wù)關(guān)系的業(yè)務(wù)數(shù)據(jù)，同時(shí)能有效減少讀寫磁盤的次數(shù)，比SQL數(shù)據(jù)庫存儲(chǔ)擁有更好的讀寫性能。

典型例子 Sorted String Table即SSTable。其實(shí)STL 庫中map和hash_map, JAVA中hash_table, hash_map就是鍵值存儲(chǔ)。 但是他們值只支持內(nèi)存操作，而且map的查詢效率太低，關(guān)鍵是他們只是簡單的數(shù)據(jù)結(jié)構(gòu)，不能實(shí)現(xiàn)較大規(guī)模存儲(chǔ)和分布式,而且數(shù)據(jù)的修改效率比較低。 而SSTalbe就解決了這些問題。

鍵值存儲(chǔ)實(shí)際是分布式表格系統(tǒng)的一種。

分布式key-value 系統(tǒng)有cassandra, hbase, bigtable etc

注：其實(shí)Hbase也屬于列式存儲(chǔ)

4. 文檔存儲(chǔ)

文檔存儲(chǔ)支持對結(jié)構(gòu)化數(shù)據(jù)的訪問，不同于關(guān)系模型的是，文檔存儲(chǔ)沒有強(qiáng)制的架構(gòu)。

事實(shí)上，文檔存儲(chǔ)以封包鍵值對的方式進(jìn)行存儲(chǔ)。在這種情況下，應(yīng)用對要檢索的封包采取一些約定，或者利用存儲(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ìn)行高效查詢。支持文檔嵌套存儲(chǔ)的能力，使得查詢語言具有搜索嵌套對象的能力，XQuery就是一個(gè)例子。MongoDB通過支持在查詢中指定JSON字段路徑實(shí)現(xiàn)類似的功能。

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

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

圖形數(shù)據(jù)庫存儲(chǔ)頂點(diǎn)和邊的信息，有的支持添加注釋。

圖形數(shù)據(jù)庫可用于對事物建模，如社交圖譜、真實(shí)世界的各種對象。IMDB（Internet MovieDatabase）站點(diǎn)的內(nèi)容就組成了一幅復(fù)雜的圖像，演員與電影彼此交織在一起。

圖形數(shù)據(jù)庫的查詢語言一般用于查找圖形中斷點(diǎn)的路徑，或端點(diǎn)之間路徑的屬性。Neo4j是一個(gè)典型的圖形數(shù)據(jù)庫。