クエリ実行モデル（Volcano とベクトル化）

同じプランでも「回し方」で速度が変わる

オプティマイザが選んだ物理プランは、結合方式や走査順を決めるだけで、実際にどう CPU を回すかまでは規定しません。同じプランでも、演算子を1行ずつ駆動するか、カラムの塊でまとめて駆動するか、専用コードへコンパイルして駆動するかで、消費 CPU 命令数は桁違いになります。本稿はこの実行モデルの3系統――Volcano、ベクトル化、コンパイル実行――を、CPU 効率の原理から比較します。

Volcano：行単位イテレータモデル

古典的な実行エンジンは、各物理演算子（Scan・Filter・HashJoin・Aggregate）を共通インタフェースを持つイテレータとして実装します。インタフェースは概念的に open() / next() / close() の3つで、next() を呼ぶと1行（タプル）を返します。これを Volcano（火山）モデル、または 反復子モデル / pull モデルと呼びます。

# 各演算子は next() を1回呼ぶと1行返す（pull 型）
Aggregate.next():
  while (row = child.next()) != EOF:   # 子に1行を要求
      accumulate(row)
  return result

Filter.next():
  while (row = child.next()) != EOF:   # さらに子へ要求
      if predicate(row): return row

プランは演算子の木で、最上位の演算子の next() を呼ぶと、要求が木を下へ連鎖し、最下段の Scan が1行を生んで上へ返します。1行が木を一周して初めて1タプルが完成する1行ずつのパイプラインです。利点は明快で、演算子が同じインタフェースに従うため任意の演算子を自由に組み合わせられ、中間結果を全部メモリに持たずに行を流せます。長くこの単純さが標準でした。

なぜ Volcano は CPU を遊ばせるのか

Volcano の弱点は I/O ではなく CPU 効率です。1タプルを進めるたびに、木の深さぶんだけ next() 呼び出しが発生します。演算子は実行時に型が決まるため、この呼び出しは多くが**仮想関数呼び出し（間接分岐）**で、インライン化できません。結果として、1値を足し算する実作業の周囲を、関数呼び出し・戻り・型分岐・述語評価のための間接ジャンプが何重にも取り囲みます。

• 解釈オーバーヘッドが支配的: 実データ演算1回に対し、next() 連鎖と式インタプリタの固定費が何倍も乗る。数億行の集計では、CPU 命令の大半が「行を運ぶ」ために費やされ、「行を計算する」命令が薄まる。
• 分岐予測の外れ: 演算子ごとの間接呼び出しは飛び先が一定せず、CPU の分岐予測が外れてパイプラインがストールしやすい。
• キャッシュ局所性の悪さ: 1行は複数カラムの値が混在した構造体で、合計したい1カラムの値はメモリ上に飛び飛び。命令キャッシュも演算子間を行き来して効きにくい。
• SIMD が使えない: 1値ずつ処理する形では、1命令で複数要素を扱う SIMD に載せられない。

つまり Volcano は、現代 CPU が得意とする「連続データの一括処理」と正反対の、1値ごとの細切れ処理を強いる構造です。OLTP のように1〜数行を触る処理では問題になりませんが、OLAPの大量集計では致命的になります。

ベクトル化実行：バッチで固定費を償却する

この解釈オーバーヘッドを断つ第一の方向が**ベクトル化実行（vectorized execution）**です。発想は単純で、next() が返す単位を1行ではなく、**型のそろったカラムの一塊（ベクトル / バッチ、典型的には1024〜数千値）**にします。MonetDB/X100 が原型で、DuckDB などが採用しています。

# Volcano（行単位）
add(out, a, b):
  return a + b          # 1値ごとに呼び出し・分岐

# ベクトル化（バッチ単位）
add_vec(out[], a[], b[], n=1024):
  for i in 0..n: out[i] = a[i] + b[i]   # 1呼び出しでバッチ全体を処理

next() の呼び出し回数が「行数」から「行数 ÷ バッチサイズ」へ激減するため、仮想関数呼び出しや型分岐などの固定費が 1 / バッチサイズ に薄まります。さらにループ内部は同型配列の単純な反復になり、3つの効果が生まれます。

• SIMD への適合: 連続した同型配列は、1命令で8値・16値を同時計算する SIMD 命令にコンパイラが載せやすい。
• 分岐の追い出し: 型分岐や演算子分岐がバッチループの外に出るため、内側ループの分岐が減り予測が当たりやすい。
• キャッシュ効率: カラム値の連続アクセスはプリフェッチが効き、型別カーネルは命令キャッシュにも収まりやすい。

ベクトル化は列指向ストレージと特に相性がよく、ディスク上の列をそのままバッチとして実行段へ流せます。ただし行指向ストレージでも、走査直後にカラム単位へ詰め替えればベクトル化の恩恵は受けられ、レイアウトと実行モデルは独立に選べます。

コンパイル実行（JIT）：解釈そのものを消す

第二の方向がコンパイル実行です。ベクトル化が「1回の呼び出しで多数の値を処理」して固定費を薄めるのに対し、コンパイル実行はクエリごとに専用のネイティブコードを生成し、解釈・仮想呼び出しそのものを消し去ります。HyPer が示した方式で、LLVM などでクエリ専用の機械語を生成して実行します。

鍵はパイプライン融合（演算子融合）です。Volcano では演算子境界ごとに next() を跨ぎますが、コンパイル実行ではマテリアライズが不要な一連の演算子を1つのタイトなループへ畳み込みます。

# 融合後に生成される擬似コード（Scan→Filter→Aggregate を1ループに）
sum = 0
for row in scan(orders):          # 演算子境界の関数呼び出しが消える
    if row.status == 'paid':      # Filter がインライン展開
        sum += row.amount         # Aggregate もインライン展開

演算子をまたぐ関数呼び出しが消え、1行が複数演算子をレジスタ上で通り抜けるため、CPU 命令はほぼ実データ処理だけになります。理論上、解釈型に対して命令数を大きく削れます。多くの実装は下位が上位へ行を送る push 型でコードを生成し、各タプルを CPU レジスタに載せたまま融合ループを流すことで、メモリへの中間書き出しを最小化します。

3モデルの比較

ベクトル化とコンパイルは「どちらが上」ではなくトレードオフです。ベクトル化は既製の型別カーネルを束ねるだけなので実装が比較的容易で、クエリ起動も速い。コンパイルは命令数の理論限界に最も近づけますが、コード生成器の実装負荷とコンパイル時間を伴います。両者を組み合わせ、コンパイルしたコードの中でベクトル単位に処理するハイブリッドも実用化されています。

まとめ