行式儲存與 OLAP

OLTP 與 OLAP 的分歧

第 1 章區分過兩種負載：OLTP 以主鍵存取少數列的全部欄位並頻繁更新；OLAP 掃描上億列但只碰少數欄位，做聚合，幾乎只讀。 用列式（row-oriented，NSM）儲存跑 OLAP 有三個根本問題：

1. I/O 浪費： 只需要一欄，卻得讀入整筆 tuple（可能 50 欄）。

2. 壓縮不佳：一頁內混雜各種型別與值域，通用壓縮器找不到規律。

3. CPU 低效：tuple-at-a-time 的 Volcano 每筆都要解讀欄位位移、虛擬函數呼叫，分支多、快取差（第 5 章）。

列式與行式

DSM（Decomposition Storage Model）把每個欄位獨立存放；同一列的各欄位值靠相同的位置（position / row id）關聯， 或者（較少見）每個值帶一個明確的 tuple id。好處對應上面三個問題：只讀需要的欄、同型別連續資料壓縮率高、 整欄緊湊的陣列正適合向量化與 SIMD。代價是：tuple 重建（查詢需要多欄時要把各欄依位置拼回）與單列更新昂貴（要改 \(n\) 個區段）。

Abadi 等人（SIGMOD 2008）的實驗證明：把行式系統「假裝」成列式（垂直切表、每欄一個索引）仍慢一個數量級—— 關鍵不只是儲存格式，而是整個執行引擎為欄位設計：壓縮、延遲物化、block iteration（向量化）與 invisible join。

壓縮編碼

行式系統偏好輕量級（lightweight）編碼：解碼極快、甚至不必解碼就能運算，再視情況疊一層 LZ4/Zstd。

典型壓縮比：事實表 5–10 倍（Parquet + Zstd 常見），且因為解碼便宜、讀取 I/O 大減，壓縮同時提升速度而非拖慢。 選擇編碼通常由系統自動依取樣統計決定（DuckDB、Parquet writer 都會為每個 column chunk 選擇）。

排序、zone map 與跳塊

把資料依常用過濾欄位排序（ClickHouse 的 、Redshift 的 sort key、C-Store 的 projection）有雙重效果： 排序欄的 RLE 效果極佳，且每個區塊的最小／最大值（zone map / min-max 統計）可以在不讀資料的情況下判斷整塊是否可能符合條件—— block skipping。範圍查詢 在排序欄上只需讀少數區塊。 PostgreSQL 的 BRIN 索引（第 3 章）就是 heap 上的 zone map。更進一步可以為一個表維護多種排序的副本（C-Store/Vertica 的 projections），以空間換查詢。

執行引擎

• 向量化（第 5 章）：運算子一次處理一個欄位的 1k–4k 個值；過濾結果以selection vector（通過者的位置陣列）或位元圖傳遞，不複製資料。

• SIMD：AVX2/AVX-512 一條指令比較 8–16 個 32 位元整數；字典碼、bit-packed 整數都能直接餵給 SIMD； 編譯器對簡單緊湊迴圈能自動向量化，關鍵路徑常用 intrinsics 手寫。

• 延遲物化（late materialization）：盡量只傳遞位置與必要欄位，到最後輸出（或 join 真正需要時）才取其他欄位—— 過濾選擇率低時省下絕大多數的重建工作。對照早期物化（一開始就拼成 tuple，然後跑行式引擎）。

• Morsel-driven 平行（Leis et al. 2014）：把輸入切成小塊（morsel，約 10 萬筆）由工作執行緒動態取用，NUMA-aware，負載均衡；DuckDB、HyPer/Umbra 採用。

• 聚合與 join：雜湊聚合在欄位陣列上以分區（radix partitioning）提高快取局部性；星型 join 用 invisible join／bloom filter 先在事實表過濾，再查維度表。

Parquet、PAX 與 Arrow

純 DSM 把每欄放成一個檔案，讀一列要開 \(n\) 個檔；Ailamaki 等人（2001）的 PAX（Partition Attributes Across）折衷： 頁內（或區塊內）按欄位分組存放，一個區塊仍包含同一批列的所有欄位。Apache Parquet 正是這個思路：

讀取器先讀 footer，依查詢需要的欄位與統計只取相關的 column chunk 與 page（projection + predicate pushdown）， 這是雲端物件儲存（S3）上以 HTTP range request 讀資料湖的基礎。ORC 結構類似（stripe / stream）。 Apache Arrow 則是記憶體中的標準欄位格式（含 validity bitmap、offset buffers），讓 Pandas、DuckDB、Spark、Polars 之間零複製交換資料； Parquet 是磁碟格式、Arrow 是記憶體格式，兩者常搭配。Iceberg、Delta Lake、Hudi 等「表格式」在 Parquet 檔之上加入 manifest、快照與 ACID 提交協定，構成 lakehouse。

寫入與 HTAP

行式儲存對單列插入／更新不友善（要改每個欄位區段、且區塊通常不可變）。通用解法是 delta store + merge：

• 新寫入先進一個小的列式或記憶體結構（Vertica 的 WOS、SAP HANA 的 delta、ClickHouse 的新 part），查詢同時掃描主儲存與 delta 並合併。

• 背景定期把 delta 排序、壓縮、合併進主儲存（本質上就是 LSM 的 compaction——ClickHouse MergeTree 的名稱即由此而來）。

• 刪除與更新以刪除位元圖（deletion vector）或 tombstone 標記，merge 時實際移除（Iceberg/Delta 的 deletion vectors 亦同）。

HTAP（混合負載）系統通常維持雙格式：列式主副本服務 OLTP，透過複寫產生行式副本服務 OLAP（TiDB 的 TiFlash、Oracle Database In-Memory、SingleStore、AlloyDB 的 columnar engine）。

系統速覽