# Query Rewriting and Optimization(DiDi #08) ## 概要 [[Torsten Grust]]([[Universität Tübingen]])による講義シリーズ「Design and Implementation of DuckDB Internals」(DiDi)第8回のスライド。全36ページ(実質34コンテンツページ)で、[[DuckDB]]のクエリオプティマイザを扱う。前半でパスベースの最適化アーキテクチャと個々の最適化パス(式簡約・述語並べ替え・統計伝播・フィルタのプッシュダウン/プルアップ・動的join filterプッシュダウン・row groupプルーニング・遅延実体化・sum書き換え・IN句書き換え・window関数の自己結合化・CTEのインライン化/実体化・共通部分プランの共有)を紹介し、後半で結合順序最適化(結合実装の選択・結合木の探索空間・DPhyp動的計画法・build/probe側の選び方)と相関サブクエリのクエリ非相関化(DEPENDENT_JOINの段階的な除去)を、TPC-Hクエリを例に手順を追って解説する。 ## 主要メッセージ - SQLは宣言的で「how」を指定できないため、クエリオプティマイザは正準プラン→(等価性を保つ)プラン書き換え→物理プランという3段階でSQLの約束を実現する。正準プランではFROM節がCROSS_PRODUCTの左深木、WHERE節がFILTER、SELECT節がプラン根に近いPROJECTIONへ機械的に翻訳される(p.02-03)。 - 最適化パスは「特定のプラン側面の専門家」であり、事前に決められた順序で一度だけ実行される。予測可能な最適化コスト(パス全体で約1ms)を得る代わりに、fixpointまで反復しないためパス順序に起因する最適化の取りこぼしが起こり得る(p.04)。DuckDB v1.5は30以上のパスを実装する(p.06)。 - 結合の最適化は3つの独立した問題からなる。(1) 述語の形に応じた結合実装の選択(HASH_JOIN/NESTED_LOOP_JOIN/PIECEWISE_MERGE_JOIN/IE_JOIN)、(2) n-1個の二項結合からなる結合木の並び順の探索(DPhypによる動的計画法)、(3) 各結合でどちらの入力をbuild/probe側に置くか(build_side_probe_sideパス)(p.19-24)。 - 相関サブクエリはDEPENDENT_JOIN(⧑)としてプランに現れるが、DuckDBはこれを物理演算子として実装しない。Neumann & Kemperの系統的書き換え規則(π・Γ・σを経由してDEPENDENT_JOINを下流へ押し込む)により、最終的に通常のJOINへ置き換えるクエリ非相関化が必須の最適化として組み込まれている(p.25-33)。 ## 視覚的に重要な図表 **p.01 タイトルスライド** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-002.png]] 講義シリーズ「Design and Implementation of DuckDB Internals」第8回、テーマは「Query Rewriting and Optimization」。日付は2026年4月7日、発表者は[[Torsten Grust]]([[Universität Tübingen]])。 **p.06 DuckDB v1.5の最適化パス実行順序一覧** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-006.png]] `expression_rewriter`から`join_filter_pushdown`まで、番号付きで実行順に並んだ25個の主要パスとその専門分野(式簡約・CTEインライン化・sum書き換え・フィルタのpullup/pushdown・IN句書き換え・結合順序・列生存期間・遅延実体化・統計伝播等)を一覧できる表。 **p.10 フィルタのpullup/pushdown** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-010.png]] `t.a=s.b`で結合された2表に対し、`t.a<100`というFILTERを等値述語経由で`s.b<100`へ伝播(pullup)したのち、両方のFILTERをそれぞれの基底テーブルスキャン直前まで押し下げる(pushdown)3段階の変形を示す。 **p.20 結合述語に基づく結合実装の選択決定木** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-020.png]] 述語の有無→等値述語の有無→複雑述語(LIKE等)の有無→行数閾値、という順に分岐し、CROSS_PRODUCT/HASH_JOIN/NESTED_LOOP_JOIN/PIECEWISE_MERGE_JOIN/IE_JOINのいずれかへ振り分ける決定木。等値結合が典型的なSQLワークロードの主力(HASH_JOIN)である一方、不等式のみの部分木は別ロジック(nested_loop_join_threshold/merge_join_threshold)に従う。 **p.26 DEPENDENT_JOIN演算子と相関** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-026.png]] 初期プランにおける相関サブクエリの表現。左枝(外側クエリのプラン、行変数`o`の束縛を提供)の各行に対し右枝(ネストしたサブクエリのプラン、`o`への自由参照を含む)をネストループ的に評価する。DuckDBは物理演算子としてDEPENDENT_JOINを実装しないため、query decorrelationが必須となる。 **p.33 クエリ非相関化ステップ5: DEPENDENT_JOINの除去** ![[_attachments/DiDi-08-Query-Rewriting-Optimization/page-033.png]] TPC-H例題(各注文の最安lineitem行を求めるQ1)に対する非相関化の最終ステップ。書き換え規則「dがQに自由出現しなければ `D ⧑^d Q ≡ D ⋈ Q`」により、πを経由してσまで押し下げられたDEPENDENT_JOINが、パラメータ`d`に依存しなくなった時点で通常のJOINに置き換わる。 ## 概念・実体への接続 - [[クエリオプティマイザ]] — 正準プラン・最適化パスの逐次適用アーキテクチャ、DuckDB v1.5の30以上のパス一覧と個々のパス(expression_rewriter・reorder_filter・statistics_propagation・filter_pullup/pushdown・join_filter_pushdown・row_group_pruner・late_materialization・sum_rewriter・in_clause・window_self_join・cte_inlining・common_subplan)。 - [[結合順序最適化]] — 結合実装の選択決定木、結合木の探索空間(カタラン数)、DPhypによる動的計画法、build_side_probe_sideヒューリスティック。 - [[クエリ非相関化]] — DEPENDENT_JOIN演算子、Neumann & Kemperの系統的書き換え規則によるπ/Γ/σ越しの押し下げとJOINへの置換。 - [[DuckDB]] — `duckdb_optimizers()`テーブル関数、`PRAGMA disable_optimizer`/`enable_optimizer`、`SET disabled_optimizers`によるパス制御機構。 - [[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」と明記されており、既存のDiDi #01〜#05と同一の記載パターン(各回タイトルスライドが個別の日付を示すが同一値になりがちな点は要注意)である。出典優先度(スライド > 公式ページ)に従いスライド記載の2026-04-07を`date_published`として採用し、確度は`medium`とした。 - PDF抽出テキストにのみ現れる脚注番号・図版マーク(`#031`〜`#048`)はスライド上のアイコン(クリップボード風マーク)に紐づく社内的な図版IDと見られ、文脈上の意味は不明。DiDi #04・#05にも同種の番号が確認されている。 - p.05のパス一覧表で番号が飛んでいる箇所(10, 15, 24, 28, 29など)があるが、スライド上に注記はなく欠番の理由(廃止パス・非公開パス・単なる欠番)は不明。 - p.08の式コスト関数`cost(e :: τ)`で、テキストへのキャストにペナルティ200を課す設計思想の定量的根拠(なぜ200か)はスライド上で説明されていない。 - 音源・動画・transcriptは提供されておらず、口頭説明は反映していない。