プッシュ型 vs プル型実行モデルの比較

同じ木でも「駆動の向き」が二つある

オプティマイザが確定した物理プランは演算子の木です。ところが、その木を実際に動かすときの制御フローの向きには二つの選択肢があります。上位が下位へタプルを「要求する」pull 型と、下位が上位へタプルを「押し込む」push 型です。どちらも計算結果は同じで、変わるのは関数呼び出しの向き・パイプラインの組み方・生成されるコードの形です。本稿はこの軸を、パイプライン化・分岐予測・コード生成適性の観点で対比します。実行を1行ずつ回すかバッチで回すかという軸（Volcano／ベクトル化／コンパイル）とは直交した、別の設計次元である点に注意してください。

pull 型：上位が need で引き出す

pull 型では各演算子が open() / next() / close() を持つイテレータで、上位演算子が next() を呼ぶと下位が1タプルを返します。古典的な Volcano モデルがこれです。要求が木の上から下へ連鎖し、最下段の Scan が1行を生んで上へ返ります。

# pull 型：上位が next() を呼ぶ＝下位へ「要求」が降りる
Filter.next():
  while (row = child.next()) != EOF:   # 下位へ要求
      if predicate(row): return row    # 通過した1行だけ呼び出し元へ返す

制御の主体が上にある（需要駆動 / demand-driven）ことが pull 型の本質です。これは次のような「消費側の都合で生産を止めたい」状況を素直に表現できます。

• 早期停止: LIMIT 10 は上位が10回 next() を呼んだ時点で要求をやめれば、下位の走査も自然に止まります。停止条件が呼び出し元のループ内に閉じます。
• 片側選択駆動: Merge Join は「今キーが小さい方の子だけ進めたい」。pull なら進めたい子の next() だけを呼べばよく、制御が直感的です。
• 多消費先の調停: 上位が「どの子からいつ引くか」を握るため、合流系の演算子で進行を制御しやすい。

弱点も明確です。1タプル進めるたびに木の深さぶんの next() 呼び出しが連鎖し、演算子の型が実行時に決まるため多くが**仮想関数呼び出し（間接分岐）**になります。飛び先が一定せず分岐予測が外れやすく、解釈の固定費が実データ処理を薄めます。

push 型：下位が result を押し込む

push 型は向きを反転させます。各演算子は「自分の結果を上位へ渡す」produce と「下位から来た結果を受け取る」consume の対で表現され、下位が処理したタプルを上位の consume に押し込みます。

# push 型：下位が consume() を呼ぶ＝上位へ「結果」が昇る
Scan.produce():
  for row in table:
      parent.consume(row)              # 上位へ押し込む

Filter.consume(row):
  if predicate(row):
      parent.consume(row)              # 通過分だけさらに上へ

制御の主体が下にある（データ駆動 / data-driven）のが push 型です。重要なのは、隣り合う演算子の境界が「next() を跨ぐ関数呼び出し」ではなく、consume のコード片を続けて並べる連結になる点です。これがパイプライン融合と相性がよい理由です。

なぜ push はコード生成に向くのか

pull で生成コードを作ると、演算子境界ごとに next() 関数を跨ぐため、1タプルが境界を越えるたびに関数の呼び出し・戻り・状態の保存復元が要ります。push では consume を呼び出し先へインライン展開していくと、マテリアライズ不要な一連の演算子が1本のタイトなループに畳み込まれます。

# push をコンパイルすると Scan→Filter→Aggregate が1ループへ融合
sum = 0
for row in scan(orders):          # produce が外側ループを生成
    if row.status == 'paid':      # Filter.consume がインライン展開
        sum += row.amount         # Aggregate.consume がインライン展開

この形は、コンパイル実行で HyPer が示した「produce/consume で生成し、1タプルを CPU レジスタに載せたまま融合ループを流す」方式そのものです。利点が分岐予測にも効きます。

• 演算子境界の間接分岐が消える: 仮想 next() の連鎖がインライン化された直接コードになり、外れやすい間接分岐そのものが減ります。
• データ依存分岐がループ内に局在: 残る分岐は述語評価などデータ依存のものだけで、予測器が履歴を学習しやすい配置になります。
• 中間マテリアライズの削減: パイプライン内ではタプルがレジスタを通り抜けるため、メモリへの書き戻しが減ります。

逆に pull がコード生成に不利なのは、next() の「呼ばれたら1個返して中断、次にまた呼ばれたら続きから」というコルーチン的な中断・再開を生成コードで表現しづらいからです。早期停止の素直さと裏表の関係になっています。

系統と分岐：どこで pull から push へ寄ったか

制御フローの選択は実装系の世代と結びついています。年代と分岐を整理します。

• 1990年代（pull の時代）: Graefe の Volcano（1990年代前半に体系化）が反復子モデルを標準化。open/next/close の pull で、行指向・1行ずつのインタプリタ実行が長く主流でした。実装が単純で任意の演算子を組める汎用性が評価されました。
• 2000年代（バッチ化はするが pull のまま）: MonetDB/X100（2005）に代表されるベクトル化は、next() の単位を1行からカラムバッチへ広げて固定費を償却しました。ただし駆動の向きは pull のままで、push へ寄ったわけではありません。これが「pull/push」と「行/バッチ」が直交軸である証拠です。
• 2010年代（push＋コンパイル）: HyPer（Neumann, 2011）が produce/consume の push でクエリ専用ネイティブコードを生成する方式を示し、push がコード生成の事実上の標準になりました。以後、コンパイル系エンジンの多くが push を採用します。
• 現在（混在・適応）: 純粋にどちらか一方ではなく、breaker の前後でモデルを使い分ける、push で生成したコードの中をベクトル単位で回す、といったハイブリッドが実用化されています。

両者は優劣ではなくトレードオフです。pull は需要駆動・早期停止・選択的な進行制御を素直に書け、汎用性が高い。push はパイプライン融合と分岐の素直さでコード生成に最適で、OLAPの大量スキャンで CPU を埋め切れます。だからこそ、breaker を境に両モデルを併用する設計が現実解になります。

まとめ