Storage Models & Compression
Database Workloads
資料庫可以依據查詢複雜度以及讀寫比例來進行分類 :
- OLTP (Online Transaction Processing) : 一些簡單的讀寫操作，且通常只包含一小部分的資料
- OLAP (Online Analytical Processing) : 一些複雜的查詢，且有大量的資料聚合
- HTAP (Hybrid Transaction/Analytical Processing) : 同時支持 OLTP 和 OLAP
Storage Models
relational model 並沒有強調同一個 tuple 的所有屬 性都要被儲存在同一個 page 中，在不同的應用場景下，我們可以有不一樣的做法。
常見的儲存模型有以下幾種 :
- N-ary Storage Model (NSM) (row store)
- Decomposition Storage Model (DSM) (column store)
- Hybrid Storage Model (PAX)
N-ary Storage Model (NSM)
如同我們之前所學的一樣，NSM 會將一個 tuple 的屬性在 page 中連續儲存，這種儲存方式較為適合 OLTP 的應用場景。
如圖所示，一般的 OLTP 應用場景中，我們會有大量的查詢，我們可以直接透過 index 之後返還所有資料。
但對於 OLAP 應用場景，即使我們只需要一個 tuple 的部分屬性，我們也需要讀取整個 page。
總結來說，NSM 的優缺點如下 :
- 優點
- 快速的 insert、update、delete
- 適合需要所有屬性的查詢
- 適合使用 index 的查詢
- 缺點
- 不適合需要 table 中大量 tuple 或是一部分屬性的查詢
- 記憶體使用效率較低 (需要讀取整個 page)
- 不適合進行壓縮
Decomposition Storage Model (DSM)
DSM 會將所有 tuple 的同一個屬性儲存在一起，這種儲存方式較為適合 OLAP 的應用場景。
透過這種方式，我們就可以減少不必要的 I/O，只讀取我們需要的部分屬性，但這樣也會造成新的問題，例如要如何存取同一個 tuple 的不同屬性，通常這個問題有兩種解決方式 :
- Fixed-length Offsets : 每個屬性都是固定長度，透過 offset 來存取 (常見)
- Embedded Tuple Ids : 在每個屬性前都加上 tuple id，透過 tuple id 來存取
對 fixed-length offsets 來說，padding 會造成空間浪費， 因此我們可以考慮使用 dictionary compression。
總結來說，DSM 的優缺點如下 :
- 優點
- 減少 OLAP 查詢的 I/O
- 記憶體使用效率較高
- 適合進行壓縮
- 缺點
- insert、update、delete 較慢
Partition Attributes Across (PAX)
PAX 是一種混合式的儲存模型，目標是將 column store 的優點 (處理速度) 和 row store 的優點 (空間) 結合在一起。
這種儲存方式會先將 tuple 分成幾個 group，在每個 group 中，資料會以 column store 的方式儲存，同時在 global header 中儲存每個 tuple 的 offset，且每個 group 也都有自己的 header 來儲存 metadata。
Compression
由於 disk I/O 是資料庫中最耗時的操作，因此壓縮被廣泛的使用在 disk-oriented 的資料庫中，特別是在一些 read-only 的 OLAP 應用場景下，可以幫助我們提升 I/O 的效率。
在 DBMS 中，我們希望壓縮之後可以達到以下幾個目標 :
- 產生 fixed-length 的值
- 只有當需要的時候才解壓縮
- 無損壓縮
針對壓縮的粒度，大致分為以下幾種 :
- Block-level : 壓縮同一個表的部分 tuple
- Tuple-level : 壓縮整個 tuple (NSM only)
- Attribute-level : 壓縮一個 tuple 內的單一溢出 (overflow) 屬性，如 blob
- Column-level : 壓縮多個 tuple 儲存的一個或多個屬性 (DSM only)
Naive Compression (Block-level)
大多數的 DBMS 都會使用一般的壓縮算法，如 gzip、snappy、lz4、Zstd 等，主要考量的點是壓縮率和壓縮 / 解壓縮速度。
一個有名的壓縮例子是 MySQL 的 InnoDB，InnoDB 會將 page 壓縮成 1、2、4、8 KB (其中之一) 再傳送到 buffer pool 中，如果我們需要寫入資料，InnoDB 會將資料寫入到 mod log 中而不需要解壓縮，但如果我們需要讀取資料，InnoDB 會將全部解壓。
這個方法的缺點在於，如果我們需要修改，我們需要解壓縮資料，這限制了壓縮的範圍，使得我們必須要資料分成較小的 block 來進行壓縮。 另一個問題是壓縮不會考慮資料的結構，也不會知道 query plan 如何訪問資料，因此 DBMS 不會知道要怎麼延遲解壓縮。
Columnar Compression (Column-level)
在理想請況下，我們希望可以在讀資料的時候不需要對整個 page 解壓縮，因此我們可以對查詢的 query 進行一些轉換。
Run-Length Encoding (RLE)
我們可以將一樣的值壓縮成三元組 (value, offset, length)。
也可以排序來減少空間。
Bit-Packing Encoding
如果整數的值小於給定類型的值的位數，我們可以將整數壓縮成較小的位數。
Mostly Encoding
當大部分的值的位數小於最大的大小時，我們可以對大部分的值進行壓縮。
Bitmap Encoding
對於每個不同的值，我們可以建立一個 bitmap 來表示是否有這個值，不適合用在高 cardinality 的 column。
Delta Encoding
紀錄差的值，適合用在有序的 column。
Dictionary Compression
最常見的壓縮方式，將常見的值轉換成一個較小且固定長度的值，並且維護一個 dictionary 來對應原本的值，由於需要加解碼，因此無法使用 hash function 來對應原本的值，除此之外，還需要注意順序來確保使用壓縮和未壓縮的結果是一樣的 (如排序、範圍查詢等等)。
有三種方式可以用來儲存 dictionary :
- Array
- 一個陣列儲存長度和字串，另一個陣列儲存 offset
- update、delete 較慢
- Hash Table
- 速度較快
- 無法支持 range query
- B+ Tree
- 比 hash table 慢，且需要消耗記憶體
- 支持 range query
