> [!abstract] 概要(Abstractの日本語訳) > SQLiteの絶大な人気は、控えめなプロセス内データ管理ソリューションへの需要があることを示している。しかし、分析ワークロードに向けて構築されたそのようなシステムはこれまで存在しない。我々はDuckDBを実演する。これは、別プロセスに組み込まれた状態で分析SQLクエリを実行するために設計された新しいデータ管理システムである。本デモンストレーションでは、組み込み分析シナリオにおける性能を示すため、DuckDBを他のデータ管理ソリューションと対決させる。DuckDBは寛容なライセンスの下でオープンソースソフトウェアとして提供されている。 ## 論文情報 - タイトル: DuckDB: an Embeddable Analytical Database - 著者: Mark Raasveldt・Hannes Mühleisen(いずれも[[CWI]]、Amsterdam) - 媒体: SIGMOD '19(2019 International Conference on Management of Data)、Demonstration track、4ページ - DOI: https://doi.org/10.1145/3299869.3320212 - コードURL: https://github.com/cwida/duckdb(論文中の脚注として記載) ## 概要 DuckDBは、SQLiteのようなプロセス内組み込みデータベースの需要が実証されている一方で、そのようなシステムが軒並みOLTP(トランザクション処理)向けに設計され分析(OLAP)ワークロードには不向きであるという課題意識から生まれた、組み込み型の分析用データベース管理システムである。SIGMOD '19のデモンストレーショントラックで発表され、TPC-Hベンチマークを用いてSQLite・MonetDBLite・HyPerと対決させる実演構成が提案されている。 ## 問題設定 入力はSQLクエリと、ホストプロセス内に配置されるデータ(TPC-Hのようなベンチマークテーブルを想定)。出力はクエリ結果であり、DuckDBはサーバプロセスやクライアントプロトコルを持たずC/C++ APIを通じて直接呼び出される点が前提となる。組み込み分析データ管理への需要は、インタラクティブデータ分析(RやPythonでのdplyr・Pandas等の利用)とエッジコンピューティング(帯域制限・プライバシー上の理由で中央集約せずエッジノード上でデータを分析したいニーズ)という一見無関係な2つのユースケースから生じており、両者はともに移植性と省リソース性を要求する点で共通している。 ## 提案手法 - **アーキテクチャ**: パーサ・論理プランナ(binder + プラン生成)・オプティマイザ・物理プランナ・実行エンジンという「教科書的」なコンポーネント分離に、トランザクションマネージャとストレージマネージャを直交コンポーネントとして組み合わせる構成を取る(Table 1)。DuckDBはクライアントプロトコルやサーバプロセスを持たず、C/C++ APIで直接アクセスされる。SQLite互換レイヤーによりSQLiteアプリケーションの再リンク/ライブラリオーバーロードでの移行も可能で、R(DBI)・Python(PEP 249)向けAPIも提供する。 - **アルゴリズム/手法の詳細**: - SQLパーサはPostgresのSQLパーサ(`libpg_query`)を可能な限り削ぎ落として利用し、パース結果はすぐにDuckDB独自のC++クラスによる構文木に変換してPostgresのデータ構造への依存を局所化する。 - 論理プランナはbinder(テーブル・カラム名/型の解決)とプラン生成器の2段構成。統計情報を各式木に伝播させ、オプティマイザでの利用と整数オーバーフロー防止のための型昇格に用いる。 - オプティマイザは動的計画法によるjoin順序最適化(複雑なjoinグラフには貪欲法へのフォールバックあり)、任意のサブクエリのflattening、共通部分式除去・定数畳み込み等の書き換え規則を実装する。 - 物理プランナは選択率推定に基づきインデックススキャンとベーステーブルスキャンを切り替えたり、join述語に応じてhash joinとmerge joinを切り替えたりする。 - 実行エンジンはVectorized Interpreted Execution(JITコンパイルではなくベクトル化解釈実行)を採用する。デフォルト最大1024要素のベクトルを単位とし、固定長型はネイティブ配列、可変長文字列は文字列ヒープへのポインタ配列として表現。NULLは別ビットベクトルで表現し、フィルタ時のデータシフトを避けるための選択ベクトル(selection vector)を持つ。「Vector Volcano」モデルでルートノードからチャンク単位でデータをpullする。 - 並行性制御はHyPerのシリアライザブルMVCC変種を実装し、データをin-placeで即時更新しつつ以前の状態をundoバッファに保持する。単純なOptimistic Concurrency Controlより選ばれた理由は、分析主用途でも並行書き込みが実運用でしばしば要求される機能だったため。 - 永続化には読み取り最適化されたDataBlocksストレージレイアウトを採用。論理テーブルをカラムのチャンクへ水平パーティションし、軽量圧縮でブロック化。各ブロックはカラムごとのmin/maxインデックスとカラムごとの軽量インデックスを持ち、クエリに無関係なブロックのスキャンを回避する。 - **実装上の工夫**: JITコンパイル方式(LLVM等)への依存を避けることで移植性を確保しつつ、ベクトル単位処理でキャッシュ局所性を活かす設計を選択している。 ## 新規性 論文の主張によれば、執筆時点(2019年)で分析用途に特化して設計された組み込みデータベースは存在しなかった。SQLiteは行指向・B-Tree実行エンジンでOLTPに特化しておりOLAP性能が乏しい。著者らの先行研究MonetDBLite(MonetDBから派生した組み込み分析システム)は実際の需要を実証したが、「purpose-built(非組み込み用に設計されたシステムを後付けで組み込み化)ではない」ことに起因する複数の課題が判明したため、DuckDBはゼロから組み込み分析用途向けに設計された。要件として、(1) OLTP性能を犠牲にしないOLAP効率、(2) プロセス内共有アドレス空間を活かした効率的なテーブル転送、(3) ホストプロセスを道連れにしないクラッシュ耐性とリソース枯渇時の安全な中断、(4) 外部ライブラリ依存や`exit()`呼び出し・プロセスグローバル状態変更の禁止を含む実践的な組み込み容易性・移植性、が挙げられている。 ## 実験設定 デモンストレーションは実測ベンチマークではなく対話的展示として構成される。物理設置として、画面・大型ダイヤル・4台の同一構成ベンチマークコンピュータをテーブル上に配置し、各コンピュータでSQLite・MonetDBLite・HyPer・DuckDBをそれぞれ1台ずつ稼働させる(Figure 2)。全システムにTPC-Hベンチマークテーブル(観客に馴染みのあるスキーマとして選定)を事前ロードし、Ethernet経由で5台目の管理コンピュータからクエリを設定して4台に反復実行させる。画面にはクエリ完了率(QpS)とメモリ使用量を含むリアルタイムメトリクスを表示し、ダイヤルで各クエリが読み込むデータ量を調整できる。 - **teaserシナリオ**: 事前設定されたクエリに対し、観客がダイヤルを操作してファクトテーブルの読み込みデータ量を増減させ、中間結果・結果セットサイズと画面上メトリクスへの即時影響を観察する。 - **drilldownシナリオ**: 観客自身が提案したクエリをベンチマークコンピュータに設定し(著者による恣意的なクエリ選定を排除)、同様にダイヤルでデータ量を増やしながら4システムへの影響をリアルタイムに比較する。 ## 実験結果 本論文はデモンストレーション提案であり定量的な実測数値表は含まれていないが、期待される定性的挙動として次を予測している: 小規模データセットでは4システムとも比較可能な挙動を示す一方、データ規模が増大するとDuckDB以外は機能し続けられなくなる。SQLiteは行指向実行モデルに起因して劣化し、MonetDBLiteはbulk processingモデル由来の過剰な中間結果の実体化に悩まされる。HyPerはクエリ処理自体は極めて高速だが、ソケットクライアントプロトコル経由での結果セット転送がDuckDBほど高速でないと予測されている(HyPerがサーバ/クライアント分離型であるのに対しDuckDBはプロセス内で直接結果を共有できるため)。また、執筆時点でDuckDBは全TPC-HクエリとTPC-DSクエリの大半(2クエリを除く全て)を実行でき、SQLiteのSQLロジックテストスイート(数百万クエリを含む)の大部分にも合格していると報告されている。 ## 考察 DuckDBの設計判断は一貫して「組み込み(embedded)」という制約から導かれている。JIT不採用は移植性優先の判断であり、DataBlocksストレージのmin/maxインデックスや軽量インデックスはスキャン範囲の絞り込みによる効率化を狙う。HyPerとの対比で示唆される点は、クエリ実行自体の速度だけでなく「結果セットをホストプロセスへどれだけ低コストで引き渡せるか」が組み込み分析データベースの性能を左右する独自の評価軸になるということである。この点は同じ著者らの先行研究([[Mark Raasveldt]]・[[Hannes Mühleisen]]、"Don't Hold My Data Hostage")のクライアントプロトコル批判とも一貫している。 ## 強み / 弱点・課題 - **Strengths**: 組み込み分析という明確に未充足だったニーズに対し、教科書的コンポーネント分離とベクトル化実行・DataBlocksストレージ・HyPer由来のシリアライザブルMVCCという実績ある要素技術を組み合わせて設計。SQLite互換レイヤーによる移行容易性。 - **Weaknesses/Limitations**: 論文自身が「4章 現状と次のステップ」で認める通り、執筆時点でDataBlocksストレージスキームは未完成、カーディナリティ推定は未実装、バッファマネージャも未実装。クエリ間並列性はサポートするがクエリ内並列性は未対応で、短時間/長時間クエリ間のリソース配分を行うwork-stealingスケジューラも将来課題として残されている。ハードウェア故障への耐性(チェックサムによる自己検証)も将来の方向性として述べられるにとどまり、本論文時点では未実装。デモンストレーション論文であるため定量的な性能比較データそのものは含まれていない。