xVelocityとSQL Server における列ストア インデックスの実装
SQL Server データベース エンジンの列指向オブジェクトである列ストア インデックス (※1) は SQL Server 2012 で初めて導入されました。
列ストア インデックスはマイクロソフトのメモリ最適化データ管理テクノロジである xVelocity (※2) を使用したメモリ最適化列ストア インデックスで、最新の圧縮アルゴリズムだけでなく、xVelocity により導入された「Batch Mode処理」と呼ばれるベクトルに基づく新しいクエリ実行テクノロジが、列ストア インデックスと組み合わされることで、クエリ処理が劇的に高速化されます。xVelocity は PowerPivot for Excel 2010、PowerPivot for SharePoint 2010 と共に SQL Server 2008 R2 で初めて導入されたテクノロジー(当時の呼称は VertiPaq)で、現在では SQL Server Analysis Services 表形式モードでも採用されています。
※2 SQL Server 2012 での xVelocity
xVelocity メモリ最適化列ストアインデックスにおけるデータ圧縮
行ストアデータが列ストア圧縮されるまでの大まかな流れを下図に示します。
フェーズⅠ：データの読込・分割
ヒープ、クラスター化インデックス等の行ストアのデータは行グループ単位(1行グループ当たりの最大行数は 1,048,576 行)に分割され、さらに列セグメントに分割されます。
フェーズⅡ：Encoding(符号化)
各列セグメントのデータを符号化して整数ベクトルへ変換します。整数ベクトル化することで復号化せずに直接集計処理できるようにします。列のデータ型やカーディナリティから符号化の方法を以下の２つから選択します。
辞書ベースの符号化(Dictionary Encoding)
- 値を整数値で表現するために定性的な属性をDictionary に抽出します。
- 文字列型やカーディナリティの低い数値型に適しています
値ベースの符号化(Value Encoding)
- Numericの場合、最も小さい正の指数を選択(指数ベースの符号化)し、基数ベースの符号化を行います
- Integerの場合、最も小さい負の指数を選択(指数ベースの符号化)し、基数ベースの符号化を行います
フェーズⅢ：Compression(圧縮)
さらに列セグメントを以下の２つから圧縮アルゴリズムを選択して圧縮を実行します。整数ベクトルのまま圧縮することで復号化せずに直接集計処理をすることができます。
Bit Packing 圧縮
- ビット演算処理を施して、より少ないビット数でデータを表現する圧縮方式です。
Run Length Encoding 圧縮
(値, 繰り返し回数) のペアで値を格納する圧縮方式です。連続する値が多い場合、非常に高い圧縮率を実現できます。
