プッシュ型パイプライン実行

# プッシュ型パイプライン実行 ## 定義プッシュ型パイプライン実行とは、クエリ実行プランを「パイプライン」という単位に分解し、各スレッドがソースから取得した行データチャンクを演算子列に沿って下流(親演算子)へ押し出しながら処理する実行モデルである。1本のパイプラインは**ソース**(行を取得・分割)・**演算子群**(FILTER・PROJECTION等、行を変換または破棄)・**シンク**(全入力を消費してから結果を出す)の3セグメントからなる。ソースとシンクだけが並列性を意識し、演算子自身は並列性を意識しなくてよい。HASH_GROUP_BYやHASH_JOINのBUILD側のような「シンク」演算子は全入力行を読み切るまで結果を生成できないため、パイプラインの終端(パイプラインブレーカー)にしか置けない。シンクはSink(スレッドローカル状態への取り込み)→Combine(ローカル状態のグローバル状態への統合)→Finalize(単一スレッドによるグローバル状態の後処理、次パイプラインへの引き渡し)という3フェーズで動作する。非自明なSQLクエリの実行プランは複数パイプラインの継ぎ合わせで組み立てられ、パイプライン間には有向の依存関係(`❶ < ❷`、パイプライン❶がfinalizeしてから❷が読める)が生じる(Source: [[@2026__DiDi__Query Execution Plans and Pipelining]])。各パイプラインの実行は、スレッドごとに走る「パイプライン駆動ループ」が担う。ループはソースから次のデータチャンクを取得し(枯渇したら終了)、パイプライン順に演算子を適用し(演算子がチャンクをサイズ0まで縮小したら次チャンクからやり直し)、非空チャンクがシンクまで到達したらシンクに回収させる。ドライバは小さすぎるチャンクの伝播オーバーヘッドを避けるための行キャッシュや、TABLE_SCANの出力を複数の消費者に分岐させるといった最適化も行える(Source: [[@2026__DiDi__Query Execution Plans and Pipelining]])。 ## 横断的知見 - **1992年のパイプライン並列化・パーティション並列化の分類が、演算子レベルの具体実装として2026年のDuckDB講義に受け継がれている**: [[並列データベース]]がまとめるDeWitt/Gray(1992)の「パイプライン並列化(演算子連鎖による並列)」「パーティション並列化(データ分割による複製演算子の同時実行)」という2分類のうち、本概念が扱うDuckDBの実装は両方を同時に体現する。パイプライン内の演算子連鎖自体がパイプライン並列化に相当し、各スレッドが独立にパイプラインインスタンスを走らせる(ソースが行を分割し各スレッドが担当分を処理する)点がパーティション並列化に相当する。1992年に抽象化された2形態が、34年後の実装ではひとつの「パイプライン」概念の中に統合されている点が興味深い(Source: [[@2026__DiDi__Query Execution Plans and Pipelining]], [[並列データベース]])。 - **独立パイプラインの並列実行は理論上のレイテンシ削減効果があるが、DuckDBの設計判断はDeWitt/Grayが指摘した「歪み(skew)」問題を実務的に回避する方向を選ぶ**: DiDi #06は独立パイプライン(`❶∥❷`)の並列実行について「パイプライン間で作業量が大きく異なりうる」「キャッシュ局所性を損なう」という理由で懐疑的な立場を示し、「1本のパイプラインへより多くのコアを投入する方が有利」と結論する。これは[[並列データベース]]がまとめるDeWitt/Grayの3脅威(startup/interference/skew)のうちskew(データ・作業量の歪み)を、複雑な負荷分散ロジックの実装ではなく設計上の選択(独立パイプライン並列化を積極採用しない)によって回避する事例である(Source: [[@2026__DiDi__Query Execution Plans and Pipelining]], [[並列データベース]])。 ## 未解決の問い - HASH_JOINのBUILD側で「小さい方の入力を選ぶ」という判断(p.09)は、どの段階(バインダ/オプティマイザ/実行時)で・どのような統計情報に基づいて行われるか。 - パイプライン駆動ループが行う「行キャッシュ」(FILTER/PROBEが少数の結果しか返さない場合の最適化)の具体的な閾値・実装詳細は何か。 - morsel-driven parallelism(HyPerで提案された類似の実行モデル)とDuckDBのパイプライン駆動ループはどの程度設計が近いか。DiDi講義の他回で言及があれば追記する。 ## 関連 - ソース: [[@2026__DiDi__Query Execution Plans and Pipelining]] - 概念: [[クエリ実行プラン]] / [[並列データベース]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] ## 出典 - [[@2026__DiDi__Query Execution Plans and Pipelining]](パイプライン・シンク・パイプラインブレーカー・パイプライン駆動ループを解説する一次ソース)