# Vectorized Query Execution ## 概要 DuckDB開発者 Torsten Grust(Universität Tübingen)による講義シリーズ「Design and Implementation of DuckDB Internals(DiDi)」第7回のスライド。DuckDBのクエリエンジンが処理するデータ単位(vector・data chunk・morsel)の定義から始め、ベクトルの物理表現(FLAT/CONSTANT/DICTIONARY/SEQUENCE)、演算子ごとの「super-specific」なC++コードとunified representation+テンプレートによる組み合わせ爆発の回避、DuckDB 1.4実ソースコードでの比較式評価のトレース、コンパイラによるtight loopの生成(ループ展開・SIMD化・`__restrict__`)、そしてCPUパイプライン・分岐予測とその誤予測ペナルティまでを一貫して扱う回である([[.raw/slides/DiDi-07/DiDi-07.pdf]])。 ## 主要メッセージ - DuckDBのクエリエンジンは、テーブルの列を2048要素の**ベクトル**に分割し、複数列のベクトルをまとめた**data chunk**を演算子間で受け渡す。スレッドは60個のdata chunk(=122,880行)からなる**morsel**単位で並列に入力を消費する(p.02)。 - data chunkはCPUのL2キャッシュに収まる大きさに設計されており、「列全体を渡す(中間結果がRAMにしか収まらず高レイテンシ)」でも「単一行を渡す(演算子間の文脈切り替えが頻発する)」でもない中間点として選ばれている(p.03)。 - 論理的に単一種類の値2048個であるベクトルは、物理的にはFLAT(そのまま格納)・CONSTANT(定数+長さ)・DICTIONARY(辞書+選択ベクトル)・SEQUENCE(base+inc)のいずれかで圧縮表現され、構造体・リストなどの複雑な値は「構造体のベクトル」「リストのシェイプ+全データを結合した1本のベクトル」として再帰的に表現される(p.04, p.07)。 - 任意のベクトルは**選択ベクトル**(値の並び替え・フィルタ結果を指すインデックス列)と**validity mask**(NULL表現用のビット列)を伴う。両者はソート・フィルタ後の値コピーを避けるために使われる(p.05)。 - 二項演算の実装は「演算の種類×値の型×左右オペランドの物理表現」の組み合わせに応じて枝分かれする決定木の葉ごとに専用コードを書く「super-specific code」で最速になりうるが、この方式をすべての組み合わせに適用するとC++コード量が組み合わせ爆発するため、DuckDBは(1) l/rをunified representation(data vector + selection vector)へ変換してから汎用ループで処理する、(2) C++テンプレートでDBMSコンパイル時にコードを生成する、の2段構えで対応する(p.08-10)。 - `SELECT i = 42 FROM generate_series(1, 100) AS _(i)`(i: SEQUENCE、42: CONSTANT)を例に、DuckDB 1.4の実ソースコード(`execute_comparison.cpp`・`comparison_operators.cpp`・`binary_executor.hpp`)を`ExpressionExecutor::Execute`から`ExecuteGenericLoop`まで追跡し、SEQUENCE=CONSTANTという組み合わせには専用コード節が存在せず、両ベクトルをUnifiedVectorFormatへ変換してから汎用ループで処理していることを示す(p.11-16)。`ldata`/`rdata`はプレーンなC++配列で、`const ... *__restrict`修飾により両配列が重ならないことをコンパイラへ伝えて最適化を促す(p.16)。 - 生成コードの性能は手作業のループ展開(4要素ずつ独立に計算しCPUの並列実行を促す、p.19)と、コンパイラによる自動的なループ展開+SIMD化(`-funroll-loops`・`-fvectorize`)の両方に依存する。`__restrict__`修飾がないとコンパイラはベクトル重複を疑い、実行時チェック付きの非ベクトル化版へフォールバックするコードを生成する(p.20, p.22)。SIMD化された core loop は128bit(SSE、4×32bit)幅のレジスタ2本を使い、1イテレーションで16要素を処理する(p.23)。 - 予測可能な前方/後方スキャンではCPUが自動的に非同期プリフェッチを発行できるが、ジャンプや不規則なスキップを伴うアクセスパターンでは`prefetcht1`等の**ソフトウェアプリフェッチ命令**をDBMSコード側で明示的に挿入する必要がある(p.24)。 - FILTER演算子の核心は入力ベクトルの各要素に対する条件分岐であり、条件分岐(および`for`ループ)は5段パイプラインの命令フェッチ・デコード段を乱す**分岐**を生む。分岐が誤予測されるとパイプラインフラッシュ(≈15サイクルのペナルティ)と命令キャッシュミスが起こりうるため、DuckDBのタイトループはbranch-less実装、または分岐予測ヒューリスティック(後方分岐=ループは taken 予測、前方分岐は not taken 予測)に沿う分岐配置を志向する(p.25-29)。 ## 視覚的に重要な図表 **p.02 DuckDB用語の再確認(table・vector・data chunk・morsel)** ![[_attachments/DiDi-07/page-004.png]] テーブルの列(一部は特定の演算子で未使用)が2048要素のベクトルに分割され、複数列のベクトルをまとめたdata chunkが水平スライスを構成し、60個のdata chunk(122,880行)がスレッド1つが消費するmorselになるという階層図。 **p.04 ベクトルの物理表現(FLAT/CONSTANT/DICTIONARY/SEQUENCE)** ![[_attachments/DiDi-07/page-006.png]] 論理的には同一の値列でも、物理的にはFLAT(そのまま)・CONSTANT(定数+長さ)・DICTIONARY(辞書配列+選択インデックス)・SEQUENCE(base+増分)のいずれかで圧縮表現されうることを示す対比図。 **p.10 選択ベクトル/validity maskを含む専用コードとunified representationの折衷** ![[_attachments/DiDi-07/page-012.png]] 前スライドの決定木コードは選択ベクトル・validity maskを扱っていないことを明示し、それを含めた「本当に」super-specificなコード片の例を示したうえで、DuckDBがunified representationへの変換(汎用ループでの処理)とC++テンプレートによるコンパイル時コード生成の2手法でコード量を制御していることを示す。脚注では、Umbraのようにクエリ変換時にC++/IR/機械語を生成・コンパイルする別方式のDBMSにも言及する。 **p.23 SIMD化されたcore loop(アセンブリ)** ![[_attachments/DiDi-07/page-025.png]] `col1`/`col2`減算処理を、128bit幅の`movdqu`/`psubd`命令2系統(4要素×2)でループ展開しつつSIMD化したx86-64アセンブリ。1イテレーションで16要素(2048/16=128イテレーション)を処理し、`res[]`と`col1[]`/`col2[]`が重ならないことを前提とする。 **p.27 分岐が取られた場合のパイプラインフラッシュ** ![[_attachments/DiDi-07/page-029.png]] 条件分岐命令`#i`の分岐結果がID(instruction decode)段の末尾で確定する一方、後続命令`#i+1`は既にIF(instruction fetch)段まで進んでいるため、分岐が取られると`#i+1`をパイプラインから除去(flush)し、ジャンプ先`#j`を新たにフェッチし直す必要があることを示す図。 ## 概念・実体への接続 - [[DuckDB]] — 本スライドの題材となる組み込み分析データベース本体。DiDi講義シリーズの教材。 - [[Torsten Grust]] / [[Universität Tübingen]] — 講師と所属。 - [[SIMDベクトル処理]] — p.21-23の128bit SIMD命令によるdata-parallelismは、既存概念ページが扱うSIMD拡張命令セット(SSE等)の具体的なDBMS内適用例として接続する。 - [[分岐予測]] — p.26-29の分岐取得時のパイプラインフラッシュ・分岐予測ヒューリスティック(後方分岐=taken)は既存概念ページの記述と整合する具体的なDBMSコンテキストの事例。 - [[パイプライン処理]] — p.26の5段パイプライン図(IF/ID/EX/MEM/WB)は既存概念ページの一般的なパイプライン説明のDBMS文脈での再確認。 - [[列指向OLAPデータベース]] — DuckDBのベクトル化クエリエンジンが支える列指向OLAPアーキテクチャの実装内部。 ## 限界・不確実点 - タイトルスライド(p.01)には発表日として "April 7, 2026" と明記されているが、DuckDB公式コースページ(`https://duckdb.org/library/design-and-implementation-of-duckdb-internals/`)のメタデータでは `article:published_time`/`article:modified_time` がともに `2026-03-19` である。これは既存の同シリーズ各回ソースページ(DiDi-01〜05)と同一の食い違いであり、`date_published` はスライド記載の2026-04-07を優先し `confidence: medium` とした。なお、DiDi-01〜06すべてが同一の "April 7, 2026" というタイトル日付を持つ可能性が高く、各回固有の実施日ではなくコース資料テンプレートの固定表記である疑いが強い。 - 個別スライドPDFの直接URL(`https://blobs.duckdb.org/slides/DiDi-07.pdf` のような形式)はDiDi-02で確認済みの命名パターンからの類推であり、本セッションではネットワークアクセス制限により実際に取得・確認できていない。`url:` にはコース一覧ページのURLを暫定的に設定した。 - p.01・p.03(ファイル名 `page-001.png`・`page-003.png`)は無地の白紙ページで、章区切り・製本用の意図的な空白と判断した。目視で内容の欠落がないことを確認済み。 - p.09(複雑な値のベクトル表現、STRUCT/LIST)は本文の主要メッセージには含めていないが、構造は視覚的に確認済み(構造体は列ごとのベクトルに分解、リストはshape(offset,len)ペアと全データを結合した1本のベクトルに分解、NULLは□で表現)。 - p.10脚注のUmbraへの言及は名称と概要(query translation timeでC++/IR/機械語を生成・コンパイルする方式)のみで、Umbra自体の詳細はスライド上に無く未収集。 - 音源・動画・transcriptは提供されておらず、口頭説明・質疑は反映していない。