SQLエンジンの構造分析

• SQLエンジンはデータベースの論理層であり、クライアントとストレージの間で動作する
• SQLエンジンの主要プロセスであるパース、バインディング、プラン簡素化、結合探索とコスト評価、実行、結果スプーリングについて詳細に説明
  • パースはSQLクエリを構造化された抽象構文木(AST)に変換
  • バインディングはASTのフィールドを現在のデータベースカタログのシンボルと対応付け
  • プラン簡素化はSQLの複雑な構文を簡素化された形式に正規化して実行速度を高める
  • 計画探索は結合、集約、ウィンドウ関数のさまざまな変形を探索して最適な実行計画を見つける
  • 実行と結果スプーリングは最終計画を実行可能な形式に変換し、結果をクライアントに返す

---

SQLエンジン概要

• SQLエンジンはクライアント要求とデータストレージの間にある論理的な仲介層である
• 主要段階
  • Parsing: クエリをAST(抽象構文木)に変換する
  • Binding: ASTの識別子をデータベースカタログのシンボルに結び付ける
  • Plan Simplification: さまざまなSQL構文を標準化されたプラン形式に簡素化する
  • Join Exploration & Costing: さまざまな結合順序を探索してコストを評価する
  • Execution: 最適な実行プランを使ってクエリを実行する
  • Spooling Results: 結果をクライアントに返す

パース(Parsing)

• パースは入力されたクエリをトークン化し、ASTに変換するプロセスである
• 右再帰パーサーは理解とデバッグが容易な一方で、スタックメモリを多く使用する
• 左再帰パーサー(Yaccベース)はメモリ効率が高いが、複雑なロジックが必要である
• Doltは左再帰パーサーを使用して高速なパースを支援している
• パースに成功するとAST構造はYacc規則と一致する

バインディング(Binding)

• バインディングはASTのフィールドをデータベースの実際のテーブル、カラムシンボルに接続するプロセスである
• 主要概念
  • テーブル定義: データのソースとして機能
  • カラム定義: テーブルソース内の特定カラムを参照
  • エイリアス(Alias): スカラー値をソースとしてもシンクとしても使用
  • スカラーサブクエリ: 親スコープを共有しながら名前バインディングを実行
• バインディングの結果としてsql.Node形式の実行プランノードを生成する

プラン簡素化(Plan Simplifications)

• さまざまなSQL表現を正規化された形式に変換し、実行最適化を支援するプロセスである
• 代表的な最適化
  • フィルタープッシュダウン(Filter Pushdown): 不要な行を削除
  • カラムプルーニング(Column Pruning): 不要なカラムを削除
• サブクエリデコリレーション(subquery decorrelation)のような変換を通じて結合プラン最適化も実行する

型強制変換(Type Coercion)

• 型強制変換は文脈に応じて式の型を自動変換するプロセスである
• WHERE、INSERTなど文脈によって型が変わることがある
• Doltは型変換をバインディング段階で段階的に処理している

結合探索(Plan Exploration)

• 結合探索はさまざまな結合順序を生成して検討するプロセスである
• 2つの探索戦略
  • トップダウン・バックトラッキング: 有効な結合順序のみを探索
  • ボトムアップ動的計画法(DP): すべての組み合わせを試して最適な結合順序を見つける
• Memo構造を使用して中間状態を効率的に管理する

関数従属性(Functional Dependencies)

• 5個以上のテーブルを結合するとコストが急増する可能性がある
• 主キー(PK)ベースの結合のように「1:1関係」を活用すると探索コストを削減できる
• LOOKUP_JOINを優先的に考慮して最適化する

中間表現の要約(IR Intermission)

• ここまで進めた3段階のIR要約
  • AST: トークン整理
  • スコープバインディング: カラム参照の検証
  • Memo: 結合探索とコスト評価のための表現

結合コスト評価(Join Costing)

• 結合コスト評価は、すべての可能なプランについて実行コストを推定するプロセスである
• コスト要素
  • 入力テーブルのサイズ
  • 結果テーブルのサイズ
  • 結合演算子の種類 (LOOKUP_JOIN, HASH_JOIN など)
• Doltは正確なテーブル統計(histogram)に基づいてコストを評価する

結合ヒント(Join Hints)

• ユーザーが提示したヒントに応じて結合戦略を優先適用しようと試みる
• 矛盾している、または不適切なヒントは無視される

実行(Execution)

• 最適プランを実際に実行可能な**イテレーター(Volcano Iterator)**構造に変換する
• 特徴
  • 非マテリアライズ(non-materializing)イテレーター: 即座に行を返す
  • マテリアライズ(materializing)イテレーター: すべての行を収集してから返す
• カラム参照は実行前にインデックスオフセットベースでマッピングされる

I/Oおよび結果スプーリング(IO/Spooling)

• 実行結果をMySQLプロトコル形式に変換してクライアントへ渡す
• キー・バリュー(KV)ストレージ層から直接結果を読み取って最適化する場合もある
• バッチ処理とバッファ再利用によって処理速度とメモリ効率を改善する

今後の計画(Future)

• Doltは基本的にローカルサーバーで**行ベース実行(row-based execution)**を使用している
• AST、スコープベースのバインディング、Memo構造による結合探索などの**3段階の中間表現(IR)**を活用して最適な実行計画の策定を支援している
• **結合順序探索(Join Search)と結合コスト評価(Join Costing)**を通じて最適な結合戦略を決定する
• 今後はIR統合とメモリ再利用最適化によって性能改善を計画している