テーブル圧縮の内部：辞書・RLE・デルタ・ビットパッキング

なぜ列指向は「軽量符号化」を使うのか

列指向ストレージでは、同じカラムの値が連続して並びます。同型・同分布の値が隣り合うため圧縮がよく効く――ここまでは直感的ですが、列指向が使うのは gzip のような汎用圧縮 だけ ではありません。主役は 軽量符号化（lightweight encoding） と呼ばれる一群で、辞書符号化・ランレングス・フレーム・オブ・リファレンス・ビットパッキングがそれにあたります。

軽量符号化を使う理由は2つです。第一に、これらは型のそろった整数列を生むため、汎用圧縮の前段として並べると最終的な圧縮率が上がります。第二に、そして本質的なのは、復号せずに圧縮表現のまま述語評価ができる ことです。汎用圧縮は一度すべて解凍しないと中身を触れませんが、辞書IDの等値比較やビットパック値の範囲判定は、符号化されたバイト列の上で直接行えます。これが後述するベクトル化スキャンとの整合性を生みます。

辞書符号化：値を整数IDに置き換える

辞書符号化（dictionary encoding） は、カラムの相異なる値を集めて辞書を作り、各値を辞書内の位置を指す小さな整数IDへ置き換える手法です。低カーディナリティ（取りうる値の種類が少ない）カラムで威力を発揮します。

元の status 列:
  [paid, paid, pending, paid, canceled, pending, paid]

辞書: paid=0, pending=1, canceled=2   （3種類 → 2ビットで足りる）

ID 列:
  [0, 0, 1, 0, 2, 1, 0]   （各値はわずか2ビット）

status のような区分値は文字列で持てば1値あたり数バイトですが、3種類なら ceil(log2(3)) = 2 ビットで表せます。ID列はさらにビットパッキングで詰められ、辞書本体は1回だけ持てば済みます。

辞書符号化の真価は述語評価にあります。status = 'paid' は、スキャン前に一度だけ辞書を引いて paid のIDが 0 だと分かれば、あとはID列に対する 整数の等値比較 に化けます。文字列比較を整数比較へ落とせるため、CPU効率が大きく上がります。

RLE：連続する同値をカウントに畳む

RLE（Run-Length Encoding, ランレングス符号化） は、同じ値が連続する「ラン（run）」を (値, 連続回数) の組に畳む手法です。

元: [A, A, A, A, B, B, C, C, C]
RLE: [(A,4), (B,2), (C,3)]   ← 9値が3組に

RLEが効くのは、同値が物理的に連続している場合だけです。そのため列指向ではカラムを ソートしてから RLEを掛けるのが定石で、低カーディナリティかつソート済みのカラム（ソートキーやその近傍カラム）で圧縮率が跳ね上がります。辞書符号化と組み合わせ、辞書ID列にRLEを掛ける「RLE on dictionary」も一般的です。

RLEもまた復号なしで処理できます。たとえば集計では、ラン (A,4) を見たら値Aを4回足す代わりに A×4 と一度で計算でき、ラン単位で処理が進みます。COUNT や SUM がランの個数・幅に比例した計算量に縮むのは、スキャンとの整合性の好例です。

FOR とデルタ：値域そのものを縮める

整数列の符号化では、値を詰める前に 値域を縮める 前処理が効きます。代表が フレーム・オブ・リファレンス（FOR: Frame of Reference） と デルタ符号化（delta encoding） です。

• FOR: ブロック内の最小値を基準（リファレンス）として引き、各値を「最小値からの差」で持つ。値域が [1000000, 1000050] のブロックなら、最小値 1000000 を1回だけ記録し、各値を [0..50] の小さな数に変換できる。差は最大50なので6ビットで足りる。
• デルタ符号化: 隣り合う値の差分を持つ。id やタイムスタンプのように単調増加・連番に近い列では、差分が小さな一定値付近に集中するため、差分列の値域が極端に狭くなる。

元の id 列（連番に近い）:
  [1000, 1001, 1003, 1004, 1006]
デルタ列（先頭は基準値、以降は差分）:
  [1000, +1, +2, +1, +2]   ← 差分はどれも小さい → 数ビットで詰まる

FORもデルタも、それ自体は値を縮めません。値域を狭めて、次段のビットパッキングが効くお膳立てをする のが役割です。デルタのデルタ（second-order delta）まで取ると、等間隔タイムスタンプのような列はほぼ一定値の列になり、極限まで縮みます。

ビットパッキング：必要なビット数だけに詰める

ビットパッキング（bit-packing） は、ブロック内の最大値を表すのに必要な最小ビット数 b を求め、すべての値を b ビット幅に詰めて連続配置する手法です。

値域が [0..50] のブロック → 最大50は6ビットで表せる（2^6=64 > 50）
各値を64ビットや32ビットではなく 6ビット に詰める
  → 32ビット格納比で約 5.3倍 の削減

必要ビット数 b は b = ceil(log2(最大値 + 1)) で決まります。FORやデルタで最大値を小さくしておくほど b が縮むため、FOR/デルタ → ビットパッキング はほぼ一体で使われます。辞書符号化が生むID列も値域が [0..辞書サイズ-1] に収まるため、ID列のビットパッキングも自然な組み合わせです。

ビットパッキングはバイト境界をまたいでビットを詰めるため、素朴に1値ずつ取り出すとシフトとマスクが多くなります。そこで実装は、32値・128値といった固定個数をまとめて1つのSIMDレジスタ群へ展開する アンパック（unpacking） ルーチンを使い、分岐レスでまとめて復元します。PFOR（Patched Frame of Reference）系では、大多数を小さい b で詰め、はみ出す少数の外れ値だけを例外リストに退避することで、外れ値1つで b 全体が膨らむのを防ぎます。

ベクトル化スキャンとの整合性

これらの符号化が単なる容量削減で終わらないのは、ベクトル化実行と噛み合うからです。ベクトル化スキャンは、1行ずつ next() を呼ぶのではなく、カラムの一塊（典型的には1024〜数千値のバッチ）をまとめて処理し、SIMDとCPUキャッシュを活かします。軽量符号化はこのバッチ処理に三重に貢献します。

• 復号せずに比較できる: 辞書述語はID列への整数等値・範囲比較、FOR述語は「基準値を引いた定数」との比較に変換できる。文字列比較や復号を挟まないため、比較カーネルがそのままSIMD命令列に乗る。
• アンパックがSIMD化できる: ビットパック列の復元は、固定幅のシフト・マスクをベクトル幅ぶん並列に行えるため、バッチ単位で分岐レスにアンパックできる。
• メタデータで丸ごと枝刈りできる: ブロックごとに最小値・最大値（ゾーンマップ）を持てば、述語の範囲と交差しないブロックは復号もアンパックもせずに丸ごと飛ばせる。FORの基準値はこの最小値をそのまま流用できる。

符号化はカラムの分布で選ぶ

ここまでの符号化は万能ではなく、カラムの分布に合っていなければ膨張します。RLEはソートされていない列で逆効果になり、辞書は高カーディナリティ列では辞書自体が肥大化し、デルタはランダムな整数列では差分がかえって大きくなります。

そのため 列指向の分析エンジンは、カラム全体に1つの符号化を固定せず、ブロック（行グループ）ごとにサンプリングして最適な符号化を自動選択 する設計を採ることが多いです。あるブロックは辞書＋RLE、別のブロックはFOR＋ビットパッキング、といった具合に切り替えます。Parquet や ORC のような列指向ファイルは、こうした符号化を最内層に適用し、その上から Snappy や Zstandard のような汎用圧縮を重ねる二段構えで、軽量符号化の「述語評価しやすさ」と汎用圧縮の「最終圧縮率」を両立させています。

まとめ