列指向DBMSにおけるデータ圧縮手法の論文を読みました

この記事の趣旨

"Integrating Compression and Execution in Column-Oriented Database Systems"という2006年に発表されたそれまで行指向DBMSで培われてきた圧縮方法による、検索高速化手法を列指向DBMSに適用・評価した論文を読んで行きます。

Daniel J. Abadi, Samuel R. Madden, Miguel C. Ferreira

Daniel J. Abadi、Samuel R. Madden、Miguel C. Ferreiraのグループ。それぞれDBMSやデータ分析に関連する手法やパフォーマンスについて研究している。

2006年ごろの研究ということもありC-storeデータベースの研究が少なかった時期の論文。既に検索パフォーマンスに寄与することがしられていたR-storeデータベースの圧縮手法を、C-storeへ応用や評価を行なった。

提案手法は以下の圧縮技術の組み合わせからなる。

Null圧縮
Nullや0、空白を削除しどこに存在したかのみを記録する圧縮方法
辞書エンコーディング
頻出するパターンをより短い文字列に起き変える圧縮手法
Run Lengthエンコーディング
どの文字がどこで何回出現したのかを記録する圧縮方式
ビットベクターエンコーディング
カテゴリカルなデータに有効なエンコーディングで、それぞれのカテゴリに属するかどうかをバイナリで表現する圧縮方法
Lempel-Zivエンコーディング
 GZIPでも使用されている圧縮方式。データの非重複ブロックを解析して既存のデータは対応するブロックへのポインタに、それ以外のみを新規に追加する。

提案手法は圧縮方式が増えてもアクセスパターンをシンプルに留めるためにアクセス方法をAPIとして隠蔽した。そのため異なるエンコーディングも同一のAPIで保存でき、同一のAPIでも取得できる。

当然ながら一つのエンコーディングで全てのデータに対応することは難しく、論文では使用すべき圧縮スキームの選び方を以下のようにまとめている。

C-storeにおける古典的な圧縮手法がまとまった論文だった。近代DWHを利用する側では意識することが少ない部分だったためあたらしい知識も多かった。