# Query Execution Plans and Pipelining(DiDi #06) ## 概要 [[Torsten Grust]]([[Universität Tübingen]])による講義シリーズ「Design and Implementation of DuckDB Internals」(DiDi)第6回のスライド。全17ページ(実質14コンテンツページ)で、[[DuckDB]]がSQLをどのような実行プラン(演算子の木構造データフロー)に変換し、その実行プランをどうパイプラインへ分解して全CPUコアを使い中間結果を素材化せずに並列実行するかを扱う。前半で自明に並列な演算子(FILTER・PROJECTION)とパイプラインブレーカーとなるシンク演算子(HASH_GROUP_BY)を対比し、後半でTPC-Hクエリを題材に複数パイプラインの組み立て・パイプライン依存関係・パイプライン内の並列性(ソース/演算子/シンク)・パイプライン駆動ループの疑似コードを解説する。 ## 主要メッセージ - 冒頭の問い(p.03、TPC-H Q2の複雑な実行プラン図を示した上で)は「中間結果を素材化せず全CPUコアを均等に並列動作させるには、データフローをどう組織すればよいか」であり、本スライド全体の主題になる。 - FILTER・PROJECTIONのような演算子はスレッドローカルに行を処理でき、演算子実装自体は並列性を意識する必要がない(p.04)。これらは「パイプライン」という単位に組み立てられ、各スレッドが自分のパイプラインインスタンスを走らせる(p.05)。 - HASH_GROUP_BYのような演算子(DB用語でシンク)は全入力を読み切るまで結果を出せないため、パイプラインの終端(パイプラインブレーカー)にしか置けない。シンクはSink→Combine→Finalizeの3フェーズで、スレッドローカル状態からグローバル状態への統合と単一スレッドによる後処理を経る(p.06-07)。 - 複雑なSQLクエリの実行プランは複数パイプラインの継ぎ合わせで組み立てられ、パイプライン間には有向の依存関係が生じる。独立パイプラインは並列実行でレイテンシ削減が見込めるが、実装コストとキャッシュ局所性低下の観点から「1本のパイプラインに多くのコアを投入する方が有利」だとスライドは示唆する(p.10)。 - 1本のパイプラインはソース・演算子群・シンクの3セグメントで構成され、並列性を担うのはソースとシンクだけである。パイプライン実行はスレッドごとの駆動ループ(pipeline driver)が担い、ソース枯渇または演算子が空チャンクを返したことを検知して制御を分岐する(p.11-14)。 ## 視覚的に重要な図表 **p.01 タイトルスライド** ![[_attachments/DiDi-06/page-002.png]] 講義シリーズ「Design and Implementation of DuckDB Internals」第6回、テーマは「Query Execution Plans and Pipelining」。日付は2026年4月7日、発表者は[[Torsten Grust]]([[Universität Tübingen]])。 **p.03 TPC-H Q2の複雑な実行プラン** ![[_attachments/DiDi-06/page-004.png]] QUERYを根に、TOP_N・PROJECTION・FILTER・LEFT_DELIM_JOIN・複数のHASH_JOIN・HASH_GROUP_BY・複数のTABLE_SCANが木構造をなす。相関サブクエリに由来するLEFT_DELIM_JOIN/DELIM_SCANが登場し、脚注1(p.02)が述べる「相関サブクエリやCTEはDAG形状の実行プランを生む」ことを実例として示す。 **p.09 TPC-H由来クエリQ₁の実行プランとパイプライン割当** ![[_attachments/DiDi-06/page-012.png]] QUERY-PROJECTION-HASH_GROUP_BY(シンク、❸)-PROJECTION-PROBE|BUILD(HASH_JOIN)-TABLE_SCAN/FILTER-TABLE_SCANという木に、演算子ごとにパイプライン番号❶❷❸を付与し、パイプラインブレーカーを太線(╂)で示す。パイプライン依存は❶<❷<❸。HASH_JOINはPROBE側とBUILD側で異なるパイプラインに属し、DuckDBはBUILD側に小さい方の入力を選ぶ。 **p.11 パイプラインの3セグメント(ソース・演算子・シンク)** ![[_attachments/DiDi-06/page-014.png]] 1本のパイプラインを「Source → Operators → Sink」の3セグメントとして図示し、ソースとシンクだけが並列性を意識する(演算子は意識不要)ことを示す。ソースの例としてCOLUMN_DATA_SCAN・RANGE・TABLE_SCAN・CTE_SCAN・READ_CSV・PARQUET_SCANを挙げ、HASH_GROUP_BYのようにシンクかつソースを兼ねる演算子があることも注記する。 **p.14 DuckDBのパイプライン駆動ループ疑似コード** ![[_attachments/DiDi-06/page-017.png]] 各スレッドが走らせるコアループの疑似コード。ソースから次のデータチャンクを取得し(枯渇ならFINISHED)、パイプライン順に演算子を適用し(空チャンクなら次チャンクからやり直し)、非空チャンクがシンクまで到達したらシンクに回収させる。脚注4によりDuckDB GitHub issue 1583をもとにモデル化されたとある。 ## 概念・実体への接続 - [[クエリ実行プラン]] — SQLからの木構造(まれにDAG)物理演算子プラン、2048行データチャンク、TABLE_SCAN/PROJECTION/FILTER/HASH_GROUP_BYの役割分担を集約。 - [[プッシュ型パイプライン実行]] — パイプライン(ソース・演算子・シンク)、パイプラインブレーカー、Sink/Combine/Finalizeの3フェーズ、パイプライン依存関係、パイプライン駆動ループを集約。 - [[並列データベース]] — DeWitt/Gray(1992)のパイプライン並列化・パーティション並列化の分類に、DuckDBの具体的な演算子レベル実装を対応させる横断的知見を追加。 - [[DuckDB]] — 本スライドが内部実装を解説する対象システム。 - [[Torsten Grust]] / [[Universität Tübingen]] — 講義シリーズの講師・所属機関。 ## 限界・不確実点 - 公式ページ(https://duckdb.org/library/design-and-implementation-of-duckdb-internals/)のJekyll SEOメタデータでは`datePublished`/`dateModified`がともに`2026-03-19`とされているが、これはコースページ全体(全チャプター一覧)の日付である可能性が高い。本スライドのタイトルページには「April 7, 2026」と明記されており、既存の[[@2026__DiDi__The ART of Indexing|DiDi #05]]と**同一の日付**が使われている。第5回・第6回が同日に開講された可能性もあるが、テンプレートの日付欄が更新されないまま複数回のスライドに転記されている可能性も残る(DiDi #05の限界・不確実点で既に同種の懸念を記録済み)。出典優先度(スライド > 公式ページ)に従いスライド記載の2026-04-07を`date_published`として採用し、確度は`medium`とした。 - PDF抽出テキストでは、`❶`❷`❸`等の丸数字タグや`⭘`等の記号、パイプライン図中の罫線・矢印が文字化けする(例: `fgfhigjh khfhjkhjlghm`は「pipeline dependencies」の文字化けと推定)。本ページの記述はすべて画像を正として作成した。 - p.03の`#020`、p.09の`#021`、p.12の`#022`という右上のクリップボード風アイコン付き番号は、DiDi #04・#05にも見られた社内的な図版IDと見られ、文脈上の意味は不明。 - p.09脚注3のTPC-H制約(`o_orderstatus`と`l_linestatus`の整合性)はTPC-H仕様書§4.2.3を参照するとあるが、本ページでは仕様書原文までは裏取りしていない。 - 音源・動画・transcriptは提供されておらず、口頭説明は反映していない。