接續 Day 11

Column-Oriented Storage

想像一下如果你的 fact table 有上兆筆資料，資料大小是 PB，dimension table 通常比較小 (百萬筆)， 該如何儲存或查詢呢？今天就會來聊聊有什麼好方法可用。

fact table 可能會有上百個欄位，但在 data warehouse 做分析時不可能會全用到，差不多就一次撈個 5,6 個欄位做計算，我們用昨天那張 fact table 來舉例，

現在來試著計算 2013 年水果和糖果的每週銷售數量，我們可以用下面這個 SQL 來查，這個查詢裡我們在 fact_sales 裡只用到 date_key, product_sk, quantity 這 3 毎欄位，其他忽略：

SELECT
	dim_date.weekday, dim_product.category,
	SUM(fact_sales.quantity) AS quantity_sold 
FROM fact_sales
	JOIN dim_date ON fact_sales.date_key = dim_date.date_key
	JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk 
WHERE 
	dim_date.year = 2013 AND 
	dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY 
	dim_date.weekday, dim_product.category;

我們如何查詢更有效率？

在 relational 資料庫，資料會以 row-oriented 的方式儲存，所有的值是每一列接著每一列的儲存，在 doucment 資料庫也類似，每一整個 documnet 也是連續的儲存，存的方式很像 Day 8 裡的圖 3-1；

我們可以針對 fact_sales.date_key 和 fact_sales.product_sk 建立 index，可是最終資料庫還是得把整筆 row 載入到記憶體中，然後過濾我們的條件，留下我們要用的欄位，若 fact_table 有上百個欄位，這樣很花時間。

column-oriented 的概念很簡單，以 column 的方式來存資料，如果我們只要撈 3 個欄位，我只要去這 3 個檔案查就好了，就節省了 parse 其他不必要欄位的時間了，如下圖說明：

column-oriented 儲存引擎的重點是，每一個 column 檔案的 順序要一樣，所以如果你想查詢第 35 列的資料 (select * from fact_sales_table) ，就得去所有的 column 檔案裡找到第 35 個值然後組合。

特別介紹：Parquet

這是一個用在 document data model 中的 column storage 格式，支援大多數的 Hadoop 生態圈工具。

Column Compression (欄位壓縮)

壓縮的好處就是節省空間 (廢話)，回去看上圖 3-10，會發現有些 column 中有很多值重複了，這是個好訊號，代表我們可以做資料的壓縮，一個在 data warehouse 常用的有效技巧為 bitmap endcoding ，如下圖說明：

bitmap 就是針對每個去重複的值，如 product_sk = 29, 30, 31, 68, 69, 74 建立一個用 0, 1 識別的 map，1 代表該列 (row) 有值，首先 product_sk = 29 在該 bitmap 中的相同順序的位置上會填入 1 ，如紅色小箭頭，以此類推把所有的值都填完，

最後在做 run-length encoding，以淺藍色線的 product_sk = 69 舉例，encoding 完後的結果是 0, 4, 12, 2 ，表示一開始是沒有 0，接下來連續 4 個 1，再來 12 個 0，最後有 2 個 1 ，如此，就能達到效果非常好的壓縮。

column-oriented storage and column-families

Cassandra 和 HBase 的概念是 column families (來自 Bigtable)，這常和 column-oriented 搞混，column families 是隨著 row key 用 row 儲存所有的欄位，它無法做到 column compression。

Sort Order in Column Storage

對 column 做排序有幾個好處，第一是能依業務需求加快查詢速度，類似 index 的概念，如果我們常用 date_key 來計算業績、銷售數量等等，我們就可以選擇 date_key 為主要排序的 column，如此當我們想要撈上個月的資料時，就不需要用全部的 date_key 資料做過濾，能直接找到特定幾列的資料；

第二是壓縮成果會更好，一樣以 date_key 舉例，2013 年若有幾千萬筆銷售，因為有用 date_key 做排序，用上面的 bitmap 技法儲存資料時只要存幾 KB 就好了；壓縮有最大效果的就是首要排序的 column。

Writing to Column-Oriented Storage

前面提到的 Column-Oriented Storage, column compression 和 sort column 技法都是對查詢有幫助，但隨之也會讓寫入變的比較困難，例如你有主要排序欄位，你想寫一筆中間位置的資料進去，這代表你要重新產生所有的 column 檔案，

但有個好消息是，我們可以借用在 Day 介紹過的 LSM-Trees 中的 in-memory store 來解決，概念一樣在記憶體累積一定資料後在合併回 column 檔案裡去，這也是 Vertica 公司做的事，查詢時一樣要去 in-memory 跟 column 檔案 2 個地方查。

總結

Day 8 ~ Day 12 討論了各種不同的 data storage 跟 index 方式，書中其實有提到更多 index 的方法，值得去買來看看，我們公司的資料有百億筆了，慢慢的就會開始碰到很多資料問題，我想認識這些技巧越多，你就越知道怎麼去設計、優化數據密集的系統，明天開始就是介紹各種不同的 encoding 格式了。