レイトマテリアライゼーションとベクトル化実行の内部

列値を「いつ組み立てるか」が効く

列指向ストレージはカラムごとに値を連続配置します。ここでクエリを実行するとき、ディスク上のバラバラなカラムを、いつ1行のタプルへ組み立て直す（実体化＝materializeする）かが性能を大きく左右します。早く組み立てる early materialization と、できるだけ遅らせる late materialization の選択は、無駄な列値の読み出し・復号・コピーをどれだけ省けるかに直結します。本稿は late materialization と、それを支えるベクトル化実行の内部を解説します。

early materialization：走査直後にタプルを組む

素直な実装は、走査した時点で必要カラムの値を集めて行タプルを作り、以降の演算子（フィルタ・結合・集計）に1行ずつ流します。これが early materialization です。

# early materialization：先にタプルを組んでから処理
scan(orders) -> rows of (id, status, amount, region)
filter(status == 'paid') -> 残った行のタプル
aggregate(sum(amount) by region)

利点は単純さで、行が組み上がっているため後段は通常の行指向演算子をそのまま使えます。しかし問題は、フィルタで落ちる行の列値まで先に組み立ててしまう点です。status == 'paid' が全体の数%しか通さない場合でも、amount や region を全行ぶん読み・復号・コピーしてからフィルタにかけることになり、捨てる行のために費やした作業が無駄になります。列指向は「必要な列だけ読む」ことが強みなのに、early materialization は「必要かどうか決まる前に読む」ため、その強みを削ぎます。

late materialization：position list で処理を進める

late materialization は逆に、値そのものを組み立てず、行の位置情報だけで処理を進めます。中核となるのが position list（行ID列、あるいは選択ベクトル）です。フィルタは値の配列を返すのではなく、条件を満たした行の位置の集合を返します。

# late materialization：まず位置だけを絞り込む
status 列をスキャン -> 'paid' を満たす position list = [3, 7, 8, 15, ...]
# この時点で amount/region はまだ一切読んでいない
# 集計に必要な amount だけを position list で引く
amount[3], amount[7], amount[8], ... を取り出して sum

ポイントは、status 列だけを先に評価して位置を絞り、amount や region は生き残った位置の値だけを最後に取り出すことです。脱落する行の amount・region は読み出しも復号も発生しません。選択率（フィルタを通る割合）が低いほど、触らずに済む列値が増え、I/O とコピーが減ります。position list には、行IDの配列のほか、各行が生存かを 0/1 で持つビットマップ／選択ベクトルの形式があり、選択率に応じて使い分けられます。

なぜ速いのか：触らない列・行を最大化する

late materialization が効くのは、実体化の対象を「最後まで生き残った行 × 実際に出力／集計に要る列」に絞れるからです。効きどころを整理します。

• 不要な列読み出しの回避: 出力にも述語にも使われない列は最後まで読まない。フィルタで落ちる行の列値は復号すらしない。
• 圧縮表現のまま処理できる: 軽量符号化された列は、辞書IDやビットパック表現のまま述語評価でき、生き残った位置だけを最後に復号すればよい。早期に行へ展開しないぶん復号回数が減る。
• コピーとメモリ帯域の節約: タプルへ詰め替えるコピーが減り、CPU とメモリ間の帯域を節約できる。中間結果が「値の配列」ではなく「位置の集合」なので軽い。
• キャッシュ効率: 1カラムを連続走査する形が保たれるため、プリフェッチが効き、述語評価のカーネルが命令キャッシュに収まりやすい。

代償もあります。最終的に値を引くとき、position list が飛び飛びだとランダムアクセス（ギャザー）になり、連続走査より遅くなり得ます。そのため、選択率が高く（多くの行が生き残る）ギャザーする値そのものが多くなるケースや、列値を何度も参照するケースでは early materialization のほうが有利なこともあります。実エンジンはこの境界を選択率の見積もりで判断し、両者をプラン中で混在させます。

結合での late materialization

late materialization が特に効くのが結合です。結合キーだけで先にマッチング位置を求め、マッチした行ペアの位置（行ID）だけを中間結果として持ち、出力に必要な非キー列はマッチ確定後に position list で引きます。多くの行が結合で脱落する場合、脱落行の非キー列をまったく読まずに済みます。

# 結合をキー位置で先に解き、値は後から引く
build:  R.key 列から ハッシュ表（key -> R側の行ID）
probe:  S.key を引いてマッチした (R行ID, S行ID) のペア列を得る
# ここまで R/S の非キー列は未読
output: 必要な列だけを R行ID / S行ID で取り出して実体化

ベクトル化実行との噛み合わせ

late materialization は「何を実体化しないか」の戦略で、どう CPU を回すかは実行モデルの問題です。両者を結ぶのがベクトル化実行です。ベクトル化は1値ずつではなく、1024程度のカラムバッチを1回の呼び出しで処理し、固定費（仮想関数呼び出し・型分岐）をバッチサイズで償却します。

ここで position list と選択ベクトルは、ちょうどベクトル化カーネルの入出力として実装されます。フィルタカーネルはバッチを受け取り、生き残った位置を選択ベクトルとして返します。後段のカーネルは選択ベクトルを見て生存行だけを処理し、これが late materialization の「位置で処理を進める」を SIMD レベルで体現します。

# ベクトル化フィルタ：バッチを処理し選択ベクトルを返す
filter_eq(sel_out[], col[], value, n=1024):
  k = 0
  for i in 0..n:                 # 内側は同型配列の単純反復 → SIMD 化可能
      if col[i] == value: sel_out[k++] = i
  return k                       # 生存件数

# 後段は選択ベクトルで生存行だけを処理
sum_with_sel(sum, col[], sel[], k):
  for j in 0..k: sum += col[sel[j]]   # 位置で値を引いて集計

• SIMD への適合: 述語評価は同型配列の一括比較になり、1命令で複数値を比較する SIMD に載る。選択ベクトル生成も SIMD 圧縮命令で高速化できる。
• 分岐の追い出し: 生存判定がバッチ単位の選択ベクトルに集約されるため、後段カーネルの内側ループから条件分岐を減らせる。
• 遅延と償却の両立: late materialization が触る値を減らし、ベクトル化が触る値あたりの固定費を薄める。削減と効率化が直交して効く。

early と late の比較

まとめ