為什么需要壓縮

在面向磁盤的數(shù)據(jù)庫(kù)，從磁盤中取數(shù)據(jù)是最大的性能瓶頸。
而在內(nèi)存數(shù)據(jù)庫(kù)中，在速度與壓縮率的取舍中總是會(huì)選速度，其壓縮的主要目的是為了減少內(nèi)存的需求和處理。（Compressing the database reduces DRAM requirements and processing 減少requirements顯而易見(jiàn)，reduce processing如何體現(xiàn)呢）

數(shù)據(jù)庫(kù)壓縮的目標(biāo)
壓縮后產(chǎn)生固定長(zhǎng)度的值；查詢時(shí)解壓盡可能放到后面；無(wú)損解壓縮

壓縮技術(shù)

數(shù)據(jù)特征，什么樣的數(shù)據(jù)是適合壓縮的
數(shù)據(jù)集在某些屬性值上有很高的偏斜分布（如Zipfian）；數(shù)據(jù)集在同一個(gè)元組中的屬性間有很強(qiáng)的相關(guān)性（Zip Code to City）。

有損/無(wú)損 壓縮
數(shù)據(jù)庫(kù)的壓縮必須是無(wú)損的；有損壓縮只能用在應(yīng)用級(jí)；讀比原來(lái)應(yīng)讀的數(shù)據(jù)少某種意義上說(shuō)和壓縮一樣（比如利用聚合信息）。

Data Skipping

近似查詢（有損） 在原來(lái)的整表的抽樣子集進(jìn)行查詢產(chǎn)生近似結(jié)果（適合有沒(méi)有的查詢）
Zone Map（無(wú)損）預(yù)先計(jì)算每個(gè)block的列的聚合信息，在DBMS進(jìn)行查詢的時(shí)候會(huì)檢查聚合信息判斷是否需要訪問(wèn)這個(gè)塊

Zone Map.png

壓縮的粒度

Block-level 壓縮同一個(gè)表中同一塊中的元組
Tuple-level 壓縮整個(gè)元組（行存儲(chǔ)NSM）
Attribute-level 壓縮一個(gè)元組中的一個(gè)屬性；壓縮一個(gè)元組中的多個(gè)屬性
Column-level 壓縮多個(gè)元組的同一個(gè)屬性（列存儲(chǔ)CSM）

Naive Compression
用通用壓縮算法，不考慮語(yǔ)義；只需要考慮計(jì)算開(kāi)銷和壓縮和解壓的速度。
數(shù)據(jù)在讀或者可能修改時(shí)需要先解壓；如果要連接的數(shù)據(jù)是以同樣的方式壓縮的，可能可以直接用壓縮數(shù)據(jù)進(jìn)行連接

OLAP 列壓縮

Null Suppression 對(duì)于連續(xù)的0或者連續(xù)的空（稀疏數(shù)據(jù)），描述有多少0或者數(shù)據(jù)在什么位置
run-length 游程編碼 壓縮一列中相同的數(shù)據(jù)到一個(gè)三元組<value, offset, length>

游程編碼.png

位圖編碼

Bitmap Encoding.png

壓縮的實(shí)現(xiàn)上有 通用壓縮（用標(biāo)準(zhǔn)壓縮算法，查詢時(shí)需要解壓縮，不適用于內(nèi)存數(shù)據(jù)庫(kù)）和Byte-aligned Bitmap Codes（用結(jié)構(gòu)化游程編碼壓縮），下面介紹一種BBC, Oracle BBC，但是已經(jīng)過(guò)時(shí)了。

BBC 例子.png

ORACLE BBC規(guī)則.jpg

BBC都不支持隨機(jī)訪問(wèn)

Delta Encoding
記錄的是同一列中彼此之間值的不同；在本表中或單獨(dú)的查找表中存一個(gè)基礎(chǔ)值，其他值存的都是和這個(gè)基礎(chǔ)值的差值（可以與RLE結(jié)合）

Delta Encoding.png

Incremental Encoding
記錄下一行和上一行的公共前綴，找出最長(zhǎng)的那個(gè)，然后進(jìn)行壓縮，記錄前綴長(zhǎng)度和自己獨(dú)占的。

Increamental Encoding.png

Dictionary Compression

字典壓縮，把出現(xiàn)頻率高的部分用更小的code代替，在DBSM中應(yīng)用最普遍；需要支持快速解壓縮；需要支持范圍查詢。

字典壓縮有幾個(gè)問(wèn)題，字典何時(shí)構(gòu)建；字典的規(guī)模（要覆蓋多大的范圍）；字典用什么數(shù)據(jù)結(jié)構(gòu)；字典用什么編碼模式？
構(gòu)建 通常有一次構(gòu)建和增量構(gòu)建。一次構(gòu)建就是在一個(gè)給定時(shí)間點(diǎn)上根據(jù)全部的元組來(lái)計(jì)算字典，對(duì)于新加入的元組用單獨(dú)的字典否則字典要用全部的元組重新計(jì)算；增量構(gòu)建就是把新元組和已經(jīng)存在的字典合并，可能需要對(duì)已經(jīng)存在的元組進(jìn)行重新編碼
字典規(guī)模 塊級(jí)-只包含一個(gè)表中子集；壓縮率低但是添加新元組簡(jiǎn)單；表級(jí)-為一整個(gè)表構(gòu)建一個(gè)字典，更高的壓縮率，更新貴；多表級(jí)-可以是覆蓋多個(gè)表或子表，可能對(duì)連接和集合操作有幫助。

多表級(jí).png

編碼/解碼 編碼上采取保序編碼編碼后的值和原來(lái)的值的順序保持一致。

Order-Preserving Encoding.png

字典的數(shù)據(jù)結(jié)構(gòu) 數(shù)組-一個(gè)變長(zhǎng)String數(shù)組，一個(gè)指針數(shù)組-更新貴，因?yàn)槭怯行虻?，所以涉及到?shù)組的后移問(wèn)題； 哈希表-快速且緊湊，但不支持范圍查詢和前綴(%)查詢；B+樹(shù)-比哈希表慢，更少的內(nèi)存，支持范圍查詢和前綴查詢。

OLTP的索引壓縮

OLTP不能用OLAP壓縮技術(shù)，因?yàn)镺LTP需要快速的隨機(jī)訪問(wèn)，動(dòng)態(tài)的解壓/壓縮熱元組對(duì)于一個(gè)事務(wù)的更新太慢了，然而索引會(huì)消耗大量的內(nèi)存。
Hybrid Indexes
一個(gè)邏輯索引分成兩個(gè)物理索引，數(shù)據(jù)會(huì)從一個(gè)stage遷移到另一個(gè)stage。
Dynamic Stage-存新數(shù)據(jù)，快速更新
Static Stage - 舊數(shù)據(jù)，可以壓縮，用來(lái)只讀
(講的并不很清楚，有機(jī)會(huì)會(huì)看論文Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes
)