論文連結： http://www.cs.umd.edu/~abadi/papers/abadi-sigmod08.pdf
概述
該文發表在 2008 年的 SIGMOD 會議上。從論文标題可以看出，論文主要内容不是陳述一種新的技術、架構，而是偏向議論、驗證。其主要目的在于闡述清楚在 OLAP 下為什麼列式存儲Column-Store優于行式存儲Row-Store。
在 OLAP 場景下，基準測試的結論都是列式存儲比行式存儲快一個數量級。而大家普遍了解的原因是
column-stores are more I/O efficient for read-only queries since they only have to read from disk (or from memory) those attributes accessed by a query.
對于隻讀查詢，列式存儲的 I/O 效率更高，因為它們隻需要從磁盤（或記憶體）中讀取查詢所需要的那些字段。
從這個了解出發，大家想到即使是行式存儲，也可以通過一些優化手段達到列式存儲的性能，包括：
- 垂直分表Vertically Partitioning
- 全列索引Indexing Every Column
簡介
作者認為當年面向列的系統性能測試方面過于“傳統”——仍然以面向行的系統資料結構的設計思路來設計性能測試方案。雖然看出了列式存儲的潛力，但沒有回答本質問題：
Are these performance gains due to something fundamental about the way column-oriented DBMSs are internally architected, or would such gains also be possible in a conventional system that used a more column-oriented physical design?
列式存儲帶來的性能提升是由于它内部架構的基本原理導緻的，還是采用更加面向列式實體設計的傳統系統中也有可能實作這些性能提升？
為了驗證這個問題，作者采用了垂直分表、索引查詢Index-only Plans、物化視圖Materialized Views三種設計範式來實作更加面向列式實體設計的行式系統：
- 垂直分表，将表結構拆分為二進制組的形式，來實作對于一個查詢，隻需要通路特定列的目标；
- 索引查詢，為每個表建立一組索引，以確定可以覆寫所有查詢中所需要的列，保證查詢過程中直接從索引中提取字段的值；
- 物化視圖，針對所有查詢做物化視圖，以擷取最佳的查詢性能。
經過模拟實驗，作者得出結論，即使在面向行的系統中應用了面向列的思路來設計存儲範式，在分析場景下，性能仍然無法與面向列的系統抗衡。
在得到上述結論後，作者又抛出下一個問題：
Which of the many column-database specific optimizations proposed in the literature are most responsible for the significant performance advantage of column-stores over row-stores on warehouse workloads?
在數倉場景下，究竟是哪些優化手段讓面向列的系統性能優于面向行的系統性能？
論文直接給出結論，面向列的系統中優化主要有：
- 延遲物化Late Materialization
- 塊周遊Block Iteration
- 壓縮Compression
- 隐式連接配接Invisible Joins（本文創新優化點）
到這裡，作者提出了第三個問題：
However, because each of these techniques was described in a separate research paper, no work has analyzed exactly which of these gains are most significant.
定量來看，這幾種優化手段分别可以為面向列的系統提升多少性能呢？
接下來的工作中，作者逐個移除 C-Store 資料庫中的上述優化手段來進行測試，最終發現：
- 壓縮帶來的性能提升要看具體的資料，最多時可以提升一個數量級
- 延遲物化可以提升 3 倍
- 塊周遊和隐式連接配接可以提升約 1.5 倍
面向行的執行
垂直分表
垂直分表将表結構拆分成二進制組，通過某種機制再将所有字段組合成之前的資料。第一反應可能需要在表中增加一個主鍵字段Primary Key，但是主鍵字段可能會比較大，并且很多時候主鍵是複合主鍵，是以通常需要向每個表添加一個整數 “position” 列。但是查詢中如果需要多個列，就得基于 position 列做額外的 join 操作。如果為了加速 join 再引入索引，則又會增加存儲和 I/O 的開銷，很難有優勢。
索引查詢
垂直分表會引入兩個新問題：
- 它需要在每一列上增加一個 position 字段用來還原之前的記錄，這會浪費大量的磁盤空間和磁盤帶寬；
- 大多數行式存儲在每個元組上會存儲一個大的頭部資料，這又進一步浪費了磁盤空間。
索引查詢可以避免上述問題。為了不發生回表查詢，勢必要将 query 中任意條件的字段，都通過對應字段的索引來過濾出各種主鍵清單，然後做合并計算。如果某些字段對應的條件無法被其索引快速過濾資料的話，就會導緻索引的全掃描，且這樣的掃描可能會有多次。最終造成多個索引掃描，合并主鍵列的速度還不如一趟掃描原始表資料并過濾的速度。另外，大量備援的元資訊和頭資訊也會造成巨大的性能損失。是以，整體的存儲、I/O 開銷都很大。
物化視圖
完全根據預定義的 SQL 來生成确定的物化視圖，且其中不會關聯多餘的列。顯然這種方式查詢性能很好（插入性能差），I/O 效率高，但這種方法又隻能應付極其有限的場景。
面向列的執行
壓縮
壓縮，就是将相似度很高、資訊熵很低的資料放在一起，用更小的空間表達相同的資訊量。列存的資料往往類型相同，相同的特征更多，更容易被壓縮，是以列存系統的壓縮優化比行存系統更加有效。
壓縮優化帶來的優勢有：
- 壓縮後的資料量更小，可以減少硬碟存儲空間，同時硬碟的資料量變少在讀取時就可以減少 I/O 壓力；
- 有些時候解壓縮的過程可以省略掉，進而直接對壓縮後的資料進行操作。比如使用 Run-Length 編碼方式進行壓縮的資料，就可以直接進行某些運算。
Run-Length 壓縮：對于原始序列為 1, 1, 2, 2, 3, 3, 3 的資料，壓縮後表達為 $1 \times 2$, $2 \times 2$, $3 \times 3$。當我們要對這一列進行 sum 或者 count 運算時，原始資料可以直接轉換為 $sum(1 \times 2 + 2 \times 2 + 3 \times 3) $ 和 $ count(2 + 2 + 3)$，不僅不需要解壓縮，而且還提高了計算效率。
另外，壓縮優化最好可以配合
sort
使用，如果資料是經過排序的，則更容易找到相鄰資料的同質化特征，獲得更好的壓縮效果。
延遲物化
物化Materialization 是指為了把底層面向列的存儲格式跟要求的行式格式對上，需要在查詢的某個階段轉換一下。
了解物化的概念後，延遲物化就很好了解了，意思就是把物化的時機盡量地拖延到整個查詢聲明的後期。延遲物化意味着在查詢執行的前一段時間内，查詢執行的模型不是關系代數，而是基于 Column 的。
例如下面的查詢：
select name
from person
where id > 10
and age > 20 一般的做法是從檔案系統讀出三列的資料，馬上物化成一行行的 person 資料，然後應用兩個過濾條件：$id > 10$ 和 $age > 20$，過濾完了之後從資料裡面抽出 name 字段，作為最後的結果，大緻的轉換過程如下圖：
而延遲物化的做法則會先不拼出行式資料，直接在 Column 資料上分别應用兩個過濾條件，進而得到兩個滿足過濾條件的 bitmap，然後再把兩個 bitmap 做位與的操作得到同時滿足兩個條件的所有的 bitmap，因為最後使用者需要的隻是
name
字段而已，是以下一步我們拿着這些
position
對
name
字段的資料進行過濾就得到了最終的結果。如下圖：
延遲物化有四個方面的好處：
- 關系代數裡面的
selection
aggregation
- 如果資料是被壓縮過的，物化的過程就必須對資料進行解壓，這會影響壓縮帶來的好處；
- 列式的記憶體組織形式對 CPU Cache 非常友好，進而提高計算效率，相反行式的組織形式因為非必要的列占用了 Cache Line 的空間，Cache 效率低；
- 塊周遊的優化手段對 Column 類型的資料效果更好，因為資料以 Column 形式儲存在一起，資料是定長的可能性更大，而如果 Row 形式儲存在一起資料是定長的可能性非常小（因為你一行資料裡面隻要有一個是非定長的，比如 VARCHAR，那麼整行資料都是非定長的）。
塊周遊
行存模型中，每一個算子在處理資料的時候，都要先疊代一條資料，然後通過定義的接口從資料中擷取到某個字段的值，然後再對值進行操作。這個流程使得每處理一條資料就得額外調用一兩次用來擷取資料的函數（一般稱為火山模型）。
而在列式存儲中，每一次塊疊代都可以擷取到多條資料，并且當需要對某一列操作時，可以将一整塊列的值傳遞給處理函數。同時不需要額外調用函數擷取值，并且如果列是等寬的，可以直接作為數組來疊代。
使用上述方法時，可以充分利用 CPU 的很多優勢（SIMD加速、cache line适配、CPU pipeline等）。
隐式連接配接
最後本文提出了一個具有創新性的性能優化措施：隐式連接配接。隐式連接配接針對的場景是數倉裡面的星型模型Star Schema， 如果使用者查詢符合下面的模式就可以應用隐式連接配接：
針對這個模型，我們給出一個
Join
的場景，例如以下的 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; 按照 Selectivity 依次 Join
這種方式很簡單，就是按照謂詞的選擇性來依次執行 join。
例如，
c.region = 'ASIA'
的選擇性很強，則首先使用這個條件過濾
customer
表，然後使用
customer
表去
Join
LineOrder
表，是以
customer
表中的
nation
字段就被增加到了
customer-order
表中。依次類推，去完成
supplier
date
表的
Join
。
這種方式的缺點為：一開始就開始做
Join
，後續無法享受上面提到的延遲物化的好處。
傳統延遲物化的 Join
這個方式可以規避一開始做
Join
的行為，具體方法為：
- 用
c.region = 'ASIA'
custom
custom key
custom
- 用 1 中獲得的
custom key
orderline
- 周遊 2 中獲得的位置清單，提取
suppplier key
order date
revenue
custom key
custom
c.nation
-
supplier
date
Join
這種方式的缺點為：在 3 中提取
c.nation
的操作為随機通路，會産生較大的開銷。
隐式連接配接
隐式連接配接是本文新提出的一種方法，用于上文中提到的星型模型的
Join
場景。它優化了傳統延遲物化
Join
的缺點，盡可能減少随機讀取的資料，進而提高性能。具體的執行步驟為：
- 在每個次元表上應用對應的過濾條件，得到每個次元表Dimension Table滿足條件的記錄的 key，同時這個
key
- 周遊事實表的各個外鍵列，使用 1 中得到的
key
bitmap
bitmap
AND
bitmap
- 利用 2 中得到的
bitmap
相比于延遲物化，隐式連接配接可以減少 I/O 的随機通路，但僅是這樣，無法大幅度提升性能。論文認為在很多元度表内符合過濾條件的資料往往是連續的，這樣就可以把
Lookup Join
變成範圍查詢。如果次元表的資料不連續，可以通過
Dictionary Encoding
方式，重新按序編碼。
Dictionary Encoding Ref doc: https://docs.kinetica.com/7.1/concepts/dictionary_encoding/
總結
讀這篇論文最大的收獲是首先明确了是哪些因素促使列式存儲對 OLAP 性能可以大幅提升——壓縮、延遲物化、塊周遊、隐式連接配接。
論文三位作者系統系統解答了列式存儲與行式存儲的差別，通過實驗告訴我們，列式存儲是因為其内部架構而具有更好的性能，而不是理所當然的理由——更少的 I/O。不僅僅限于内部架構，查詢引擎層的各種優化也同樣是列式存儲性能提升的關鍵。