クエリコンパイル実行とデータ中心コード生成

解釈をやめて「クエリ専用プログラム」に変える

Volcano モデルは演算子をイテレータにして1行ずつ next() を呼びますが、大量集計では実データ演算1回の周囲を仮想関数呼び出し・型分岐・式インタプリタの固定費が何重にも取り囲み、CPU 命令の大半が「行を計算する」のではなく「行を運ぶ」ために費やされます。クエリコンパイル実行はこの解釈の層そのものを消す方式です。受け取ったプランを汎用エンジンで解釈するのではなく、そのクエリだけを実行する専用の機械語を生成して走らせます。本稿は HyPer（Neumann 2011）が確立した**データ中心コード生成（data-centric code generation）**の内部動作を、produce/consume モデルと分岐削減の観点から正確に追います。

オペレータ中心 vs データ中心

素朴なコード生成は「演算子ごとにループを書く」オペレータ中心になりがちです。Scan のループ、Filter のループ、Aggregate のループを順に並べ、各段が中間結果を配列へ書き出して次段が読む。これは Volcano の関数呼び出しを消すだけで、**段ごとのマテリアライズ（メモリ書き出し）**が残り、タプルがメモリとレジスタを往復し続けます。

HyPer の着想はここを逆転させます。中心に置くのは演算子ではなく**データ（タプル）**で、原則は「1つのタプルは、メモリへ書き戻す必要が生じるまで、できるだけ多くの演算子をレジスタ上で通り抜けさせる」です。タプルがどこまで CPU レジスタに留まれるかが性能を決めるため、コードはタプルの流れを軸に編成されます。

パイプライン境界（pipeline breaker）

どこまでレジスタ上で進めるかを決めるのがパイプライン境界です。ある演算子が入力タプルを一度ためてからでないと出力できないとき、そこでパイプラインが切れます。これを pipeline breaker と呼びます。

• pipeline breaker でない演算子: Filter、射影、式評価などは、タプルを受け取ったその場で次へ渡せる。レジスタ上の流れを止めない。
• pipeline breaker である演算子: ハッシュ結合の build 側（ハッシュ表を作り切る）、Aggregate（全グループを集計し切る）、ソートなどは、入力を全部受け取るまで結果を出せない。ここで一旦メモリ（ハッシュ表・集計表・実体化バッファ）へ書く必要が生じる。

プランは pipeline breaker を境に複数のパイプラインへ分割されます。1つのパイプラインは「ソースから始まり、breaker でメモリへ実体化して終わる」直線で、この1パイプラインが1つの融合ループへコンパイルされます。breaker は前のパイプラインの出口（書き込み先）であると同時に、次のパイプラインの入口（走査元）になります。

# 例: SELECT sum(amount) FROM orders JOIN cust ON ...
#     WHERE orders.status='paid' GROUP BY cust.region
#
# パイプライン1: cust を走査して結合ハッシュ表を build（breaker=HashJoin.build）
# パイプライン2: orders を走査 → Filter → 結合 probe → 集計表へ加算（breaker=Aggregate）
# パイプライン3: 集計表を走査して結果を出力

produce / consume モデル

このパイプライン融合を機械的に生成する枠組みが、各演算子に与える2つのメソッド produce() と consume() です。これはコードを生成するための再帰であって、実行時に呼ばれる関数ではない点に注意します（コード生成は1回、生成コードがクエリ実行時に走る）。

• produce(): 「あなたの結果タプルを生成するコードを出力せよ」という依頼。演算子は自分のループ枠組みを書き、入力が必要なら子へ produce() を再帰委譲する。
• consume(tuple, source): 「いま手元に1タプルが届いた。あなたの処理を施して親へ渡すコードを出力せよ」という通知。子が生成した1タプルに対する処理を、親側のコードとして埋め込む。

生成は親の produce() から始まり、子へ produce() が下りていき、最下段のソース（Scan）がループ枠を書きます。ソースは「1行得たらどうするか」を親へ問うため consume() を上向きに呼び返し、各演算子の consume() が自分の処理を1タプル分のコードとして連ねます。結果として、フィルタや結合 probe や集計加算が1つのループ本体の中に縦に積層されます。

# probe 側パイプラインに対する produce/consume が織りなす生成コード（概念）
for row in scan(orders):              # Scan.produce がループ枠を出力
    if row.status == 'paid':          # Filter.consume が条件をインライン
        h = hash(row.cust_id)
        if match = probe(htable, h, row.cust_id):   # HashJoin.consume が probe をインライン
            g = group_slot(aggtable, match.region)   # Aggregate.consume が…
            g.sum += row.amount                      #   集計表へ直接加算（ここが breaker）

scan から aggtable への加算まで、演算子境界をまたぐ関数呼び出しは1つも残りません。row のフィールドはレジスタに載ったまま Filter・Join・Aggregate を通過し、メモリに触れるのはソース読み出しとハッシュ表アクセス、breaker への書き込みだけになります。Volcano の next() 連鎖が、breaker 間の素直な for ループへ畳み込まれた形です。

なぜ分岐とメモリ往復が消えるのか

データ中心コード生成が速い理由は、削れる要素を分解すると明快です。

• 仮想関数呼び出しの除去: Volcano は演算子の型が実行時に決まるため next() がインライン化できない間接分岐になります。コンパイル実行はクエリのプラン形状をコンパイル時に確定させるため、演算子の処理が直接コードとして展開され、間接呼び出しそのものが消えます。間接分岐が減れば分岐予測ミスとパイプラインストールも減ります。
• 式インタプリタの除去: status='paid' のような述語を、汎用の式評価木をたどって解釈するのではなく、比較1命令へ直接コンパイルします。式ツリーの走査分岐がまるごと消えます。
• マテリアライズの最小化: breaker と breaker の間は中間結果をメモリへ書きません。タプルがレジスタに留まるため、メモリ帯域とロード/ストア命令、キャッシュミスが大幅に減ります。
• 死コードの消去と特殊化: 参照しない列、定数畳み込み、固定された結合キー型などが、コンパイラの最適化（LLVM の -O パス）で消去・特殊化されます。汎用エンジンでは「あらゆる場合」に備える分岐が、このクエリでは不要なら削れます。

つまり Volcano が「実データ演算の周囲を間接分岐で囲む」のに対し、生成コードは間接分岐を直接コードに、解釈を機械語に置き換えるため、CPU 命令がほぼ実データ処理だけになります。Neumann の報告では、解釈型に対して命令数・実行時間とも大きく削減されました。

LLVM でネイティブコードを生成する

HyPer は生成対象に **LLVM IR（中間表現）**を選びました。アセンブリを直書きするのではなく、移植性のある IR を吐き、LLVM の最適化器と JIT バックエンドにレジスタ割り当て・命令選択・対象 CPU 向け最適化を任せます。これにより、複雑な制御フロー（ハッシュ表の衝突処理など）は手書きの C++ ヘルパー関数を呼び、ホットなタプル処理ループだけを IR で生成する、という分担が可能になります。生成した IR と既存のランタイム関数を LLVM 上でリンクし、JIT で機械語にします。

コンパイル費用を回収する：適応的実行

この代償への現実的な答えが適応的実行（adaptive execution）です。HyPer 系の後続実装は、同じ生成ロジックから複数の実行手段を用意し、クエリの規模に応じて切り替えます。

• 即時開始: まず軽量なバイトコード VM か非最適化 JIT ですぐ走り始める。コンパイルの待ちをゼロにする。
• 並行最適化と差し替え: 実行を続けながら裏で LLVM 最適化版をコンパイルし、出来上がったら実行中のパイプラインを最適化コードへ差し替える（モーフィング）。長く回るクエリだけが最適化費用を負担する。
• コードキャッシュ: プリペアドステートメントなど形が同じクエリの生成コードを再利用し、コンパイルを1回に償却する。

これにより、「短いクエリはコンパイルせず即実行、長いクエリはコンパイルして全力」という費用対効果に応じた使い分けが自動化されます。

ベクトル化との関係

ベクトル化実行も解釈オーバーヘッドを断ちますが、断ち方が違います。

両者は排他ではありません。コンパイルしたコードの内側をベクトル単位で処理するハイブリッド（生成ループがバッチを回す）も実用化され、コンパイルの命令削減とベクトル化の SIMD・メモリ局所性を同時に取りに行きます。設計の主眼は列指向ストレージや列圧縮と組み合わせ、走査から集計までを CPU 効率の限界に近づけることにあります。

まとめ