又是一篇來自 Hyper 的文章。Hyper 是一個 In-memory 的通用資料庫，同時支援 OLTP 和 OLAP 查詢（也就是現在熱門的 HTAP）。

本文是 Hyper 為 HTAP 設計的一種檔案格式，名叫 Data Blocks，它不僅能同時支援 OLTP、OLAP 查詢，還支援壓縮，並且對它的訪問可以用向量化和 JIT 編譯執行加速。

Data Blocks

Data Block 是一個由很多資料行組成的不可變的 Chunk 或者說 Row Group，一旦一組資料被打包成 Data Block 就不能再修改了，除了可以用 delete flag 實現刪除，update 只能先標記刪除再 insert 新的資料。但也正式因為不可變的特性，使得我們可以讓 Data Block 內部資料按列排列，並應用一些壓縮機制。

下圖a中，truncated、single value、keys/dictionary 分別是三種壓縮機制，之後再展開說。

Data Block 的另一個特性是 PSMA，它能在 range scan 時進一步縮小要 scan 的範圍，達到類似索引的效果。這是 Data Block 的一大貢獻，下面開始講它。

PSMA

先說什麼是 SMA：Small Materialized Aggregates，其實就是 ORC\Parquet 中都支援的 Row Group 區域性統計資訊，比如最常用的 min/max。透過這個 min/max 就可以對 SARG（可下推到 TableScan 的那些 predicates）做預過濾。比如 SARG = { x<10 }，而當前一個 Row Group 的 min = 11，那麼顯然不會有交集，可以直接跳過這個 Row Group。

PSMA = Positional SMA，是對 SMA 的一個擴充套件。SMA 讓我們可以過濾掉整個 Data Block（不scan或scan所有），而 PSMA 讓我們可以在 Data Block 內 scan 一個區間，忽略區間以外的資料。

PSMA 的設計很巧妙，以 int32 整數列為例，int32 由 4 byte 組成，所以 PSMA 包含 n_bytes * 2^8 = 4 * 256 = 1024 個 entry，每個 entry 都是一個 range：［ start， end ）

先說說 PSMA 的使用：假設給定一個等於 v 的等值查詢，那麼如何算出要 scan 的 range 呢？計算 delta = v - min，拿 delta 的 most significant byte 加上 256 * delta 的 byte 數量，即等於要拿的區間的下標。看個例子：

對於 v = 7， delte = 7 - 2 = 5，5 這個數字只有 1 個 byte（其他位為0），並且這個 byte = 5，所以對應 5 + 256*0 = 5 這個下標的 range

對於 v = 998， delta = 998 -2 = 996 = 0x03E4，這個數字有 2 個 byte，最高位為 0x03，所以對應 0x03 + 256*1 = 259 這個下標的 range

不難發現，對於 0~255 這些 delta，每個值獨享 range；而更高的 delta 就得共享 range了，比如 delta = 0x0300 ~ 0x03FF，都是共享 0x03 + 256*1 = 259 這個下標的 range。為何這樣設計呢？如果這個 attribute 的值比較集中，那麼 0～255 的“獨享”讓準確性較高；如果 attribute 的值比較分散，那麼“共享”同一個 range 的值其實也不會太多。

有了 PSMA，我們在 range scan 時能夠進一步縮減要 scan 的區間——如果運氣好，甚至可以做到點查的效能（range 長度為 1）。即使運氣不好，最差也不會比掃描整個 Data Block 更差。

那 PSMA 怎麼構建呢？只需掃一遍這個列的資料，並用掃到的值更新對應的 range 的 max 即可，這個過程代價非常小。

壓縮

從 PSMA 中可以看出，我們需要有能力對資料進行隨機定址：從指定某一位置開始/結束讀取。所以可選的壓縮方法很有限：

dictionary

：經典的字典壓縮，把所有取值做成（有序）字典，然後儲存值的編號即可，對於重複值較多的場景很有用

truncated

：對於整數，可以讓所有值減掉 min，有時候就能用更少的 byte 數儲存

single-value

：一個特例，整個列只有一個值（比如NULL）

看似都是很無腦的方法，但是論文中說相比 uncompressed 有高達 5 倍的壓縮率！

查詢執行

這塊比較簡單，沒有細看。大致就是下圖：

無論是壓縮還是未壓縮的 Chunk，都可以走 vectorized scan 高效過濾掉無用資料。最後仍然轉成 tuple 進去 HyPer 原有的 JIT 執行引擎。