幾張圖看懂列式存儲
從Dremel和Impala的學習引申出了SQL查詢的并行執行問題，于是借此機會深入學習一下關系資料庫以及關系代數的并行計算。
Speedup和Scaleup
Speedup指用兩倍的硬體換來一半的執行時間。
Scaleup指兩倍的硬體換來同等時間内執行兩倍的任務。
但往往事情不是那麼簡單，兩倍的硬體也會帶來其他問題：
更多CPU帶來的長啟動時間和通信開銷，
以及并行計算帶來的資料傾斜問題
多處理器架構
共享記憶體：任意CPU都能通路任意的記憶體(全局共享)和磁盤。
優點是簡單，
缺點是擴充性差，可用性低。
共享磁盤：任意CPU都能通路任何的磁盤，但是隻能通路自己的主存。
優點是可用性和擴充性比較好，
缺點是實作複雜以及潛在的性能問題。
不共享：任意CPU都隻能通路自己的主存和磁盤。
優點也是擴充性和可用性，
缺點是實作複雜以及複雜均衡。
混合型：系統整體上是shared nothing架構，但結點内部可能是其他架構。
這樣就混合了多種架構的優點。
資料分區
資料分區的目的就是：讓資料庫能夠并行地讀寫資料，最大程度地挖掘I/O的潛力。
常見的分區算法有：round-robin、範圍索引、哈希。
關系運算并行化
關系代數自身的屬性允許關系操作的并行化。
并行查詢處理主要分為四步：
翻譯：将關系代數表達式翻譯成查詢樹。
優化：重排join順序，并選擇不同join算法來最小化執行開銷。
并行：将查詢樹轉換成實體操作樹，并加載到處理器。
執行：并行運作最終的執行計劃。
首先将一條SQL語句翻譯成查詢樹。
然後根據表大小、索引等情況，重新排列join順序，并選擇合适的算法。
關于join算法，常見的有以下幾種：
Nested Loop join：思路很簡單，相當于兩層循環周遊，外層是驅動表，傳回滿足關聯條件的行。
适用于驅動表小(經過條件過濾後)，而被驅動表上join字段有索引的情況。在兩表都很大時效率很差。
Sort-merge join：思路也很簡單，就是按join字段排序，然後進行歸并排序。
當join字段存在重複值時，相當于每個重複值形成了一個分區。Join字段是否排序和重複值的多少決定了sort-merge的效率。
适用于兩表都很大的情況，尤其當join字段上存在聚集索引時(相當于已經排好序了)，效率很高。算法主要消耗在磁盤上。
Hash join：類似于存在重複值情況時的sort-merge，隻不過是人為的使用哈希函數進行分區。
思路是掃描小表建立哈希表(build階段，小表也叫build表)，然後逐行掃描大表進行比較(probe階段，大表也叫probe表)。
适用于兩表都很大又沒有索引的情況，限制是隻适用于等值連接配接。算法主要消耗在CPU上。
此外，對于子查詢還有semi join和anti join等算法。
最後将查詢樹變成實體操作樹，也就是真正的執行計劃。
然後根據叢集的資源情況，排程到合适的結點上進行并行計算。
五大存儲模型
昨天跟一同僚讨論Sybase是不是關系型資料庫，同僚說Sybase是列式存儲，應該屬于NoSQL，我一直的記憶Sybase是關系型資料庫，後來專門去查了資料，才發現同僚所說的Sybase IO是列式存儲;而我說的是Sybase SQL Server，是關系型資料庫。網上看到這篇文章，算是對幾種資料庫模型補補課。
資料庫市場需要細分，行式資料庫不再滿足所有的需求，而有很多需求需要通過記憶體資料庫和列式資料庫解決，列式資料庫在資料分析、海量存儲、BI這三個領域有自己獨到。
定義：關系模型使用記錄（行或者元祖）進行存儲，記錄存儲在表中，表由架構界定。
表中的每個列都有名稱和類型，表中的所有記錄都要符合表的定義。
SQL是專門的查詢語言，提供相應的文法查找符合條件的記錄，如表聯接（Join）。
表聯接可以基于表之間的關系在多表之間查詢記錄。
存儲格式：行式資料庫把一行中的資料值串在一起存儲起來，然後再存儲下一行的資料，以此類推。
例如以下的一個表：
EmpId
Lastname
Firstname
Salary
1
Smith
Joe
40000
2
Jones
Mary
50000
3
Johnson
Cathy
44000
特點:
據以行相關的存儲體系架構進行空間配置設定，
主要适合與小批量的資料處理，
常用于聯機事務型資料處理。
不能滿足後面三個需求：
對資料庫高并發讀寫要求，
對海量資料的高效率存儲和通路需求，
對資料庫高可擴充性和高可用性。
一句話不适合分布式、高并發和海量。
定義：什麼是列式資料庫?列式資料庫是以列相關存儲架構進行資料存儲的資料庫。
列式存儲以流的方式在列中存儲所有的資料，
主要适合與批量資料處理和即席查詢。
存儲格式 ：
列式資料庫把一列中的資料值串在一起存儲起來，然後再存儲下一列的資料，以此類推。
特點：
包括查詢快，由于查詢需要讀取的blocks少；
資料壓縮比高，正因為同一類型的列存儲在一起。
Load快。
簡化資料模組化的複雜性。
但是插入更新慢，不太适合資料老是變化，它是按列存儲的。
這時候你就知道它适做DSS（決策支援系統），BI的優秀選擇，資料集市，資料倉庫，它不适合OLTP。
Examples are Sybase IQ, C-Store, Vertica, VectorWise,MonetDB, ParAccel, and Infobright.
即Key-Value存儲，簡稱KV存儲。
它是NoSQL存儲的一種方式。
它的資料按照鍵值對的形式進行組織，索引和存儲。
KV存儲非常适合不涉及過多資料關系、業務關系的業務資料，同時能有效減少讀寫磁盤的次數，比SQL資料庫存儲擁有更好的讀寫性能。
典型例子 Sorted String Table即SSTable。
其實STL 庫中map和hash_map, JAVA中hash_table, hash_map就是鍵值存儲。
但是他們值隻支援記憶體操作，
而且map的查詢效率太低，
關鍵是他們隻是簡單的資料結構，
不能實作較大規模存儲和分布式,
而且資料的修改效率比較低。
而SSTalbe就解決了這些問題。
鍵值存儲實際是分布式表格系統的一種。
分布式key-value 系統有cassandra, hbase, bigtable etc
注：其實Hbase也屬于列式存儲
文檔存儲支援對結構化資料的通路，不同于關系模型的是，文檔存儲沒有強制的架構。
事實上，文檔存儲以封包鍵值對的方式進行存儲。
在這種情況下，應用對要檢索的封包采取一些約定，
或者利用存儲引擎的能力将不同的文檔劃分成不同的集合，以管理資料。
與關系模型不同的是，文檔存儲模型支援嵌套結構。
例如，文檔存儲模型支援XML和JSON文檔，字段的“值”又可以嵌套存儲其它文檔。
文檔存儲模型也支援數組和列值鍵。
與鍵值存儲不同的是，文檔存儲關心文檔的内部結構。
這使得存儲引擎可以直接支援二級索引，進而允許對任意字段進行高效查詢。
支援文檔嵌套存儲的能力，使得查詢語言具有搜尋嵌套對象的能力，XQuery就是一個例子。MongoDB通過支援在查詢中指定JSON字段路徑實作類似的功能。
MongoDB 對SQL 和ACID 支援的比較全面的資料庫了。不過， 比較多的還是介紹日志的采集和存儲，小檔案的分布式存儲，類似網際網路微網誌應用的資料存儲等方面的内容。
圖形資料庫存儲頂點和邊的資訊，有的支援添加注釋。
圖形資料庫可用于對事物模組化，如社交圖譜、真實世界的各種對象。IMDB（Internet MovieDatabase）站點的内容就組成了一幅複雜的圖像，演員與電影彼此交織在一起。
圖形資料庫的查詢語言一般用于查找圖形中斷點的路徑，或端點之間路徑的屬性。Neo4j是一個典型的圖形資料庫。