# 機能設計書 16-WHERE句最適化

## 概要

本ドキュメントは、SQLiteにおけるWHERE句の解析・最適化機能について記述する。WHERE句最適化は、クエリの検索条件を解析し、利用可能なインデックスを選択して最適なVDBEコードを生成するクエリオプティマイザの中核機能である。

### 本機能の処理概要

**業務上の目的・背景**：データベースクエリの性能は、WHERE句の評価方法に大きく依存する。WHERE句最適化は、テーブルスキャンを避け、適切なインデックスを選択することで、検索時間を数桁のオーダーで短縮できる。この機能は、開発者がSQL文を書くだけで自動的に最適な実行計画を選択し、高性能なデータベースアクセスを実現する。

**機能の利用シーン**：
- SELECT文のWHERE句評価
- UPDATE/DELETEの対象行特定
- JOINの結合条件評価
- サブクエリの実行最適化

**主要な処理内容**：
1. WHERE句の項（term）への分解
2. 各項の解析と最適化情報の抽出
3. 利用可能なインデックスの列挙
4. コスト見積もりに基づく最適なスキャン方法の選択
5. 複合インデックスの活用判断
6. ORクエリの最適化（OR-by-union）
7. VDBEコードの生成

**関連システム・外部連携**：VDBEバイトコードエンジン、B-Treeストレージエンジン、統計情報（sqlite_stat1）

**権限による制御**：特になし（内部処理）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 直接的な画面関連なし（内部最適化処理） |

## 機能種別

クエリ最適化 / 実行計画生成

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pParse | Parse* | Yes | パース状態 | - |
| pTabList | SrcList* | Yes | FROM句のテーブルリスト | - |
| pWhere | Expr* | No | WHERE句の式木 | - |
| pOrderBy | ExprList* | No | ORDER BY句 | - |
| pResultSet | ExprList* | No | SELECT結果列 | - |
| wctrlFlags | u16 | Yes | 制御フラグ | - |

### 入力データソース

- SQL文解析結果（式木）
- テーブルスキーマ（インデックス情報）
- 統計情報（sqlite_stat1）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | WhereInfo* | 最適化情報構造体 |
| pWInfo->nRowOut | LogEst | 推定出力行数 |
| pWInfo->eDistinct | int | DISTINCT処理方法 |
| pWInfo->nOBSat | int | ORDER BY充足項数 |

### 出力先

- VDBEプログラム（バイトコード）
- WhereInfo構造体

## 処理フロー

### 処理シーケンス

```
1. WhereInfo構造体の割り当て
   └─ メモリ確保と初期化

2. テーブルマスクの作成
   └─ 各テーブルにビットマスク割り当て

3. WHERE句の項分解
   └─ sqlite3WhereClauseInit()
   └─ sqlite3WhereSplit()でANDで分割

4. 各項の解析
   └─ sqlite3WhereExprAnalyze()で最適化情報抽出
   └─ インデックス使用可能性の判定

5. OUTER JOIN制約の処理
   └─ ON句の制約をWHERE句に統合

6. インデックス候補の列挙
   └─ whereLoopAddBtree()でB-Treeインデックス
   └─ whereLoopAddVirtual()で仮想テーブル

7. 最適経路の選択
   └─ wherePathSolver()で動的計画法
   └─ コスト最小の実行計画を選択

8. VDBEコード生成
   └─ sqlite3WhereCodeBegin()でループ開始コード
   └─ 呼び出し元で本体処理
   └─ sqlite3WhereEnd()でループ終了コード
```

### フローチャート

```mermaid
flowchart TD
    A[WHERE句最適化開始] --> B[WhereInfo割り当て]
    B --> C[テーブルマスク作成]
    C --> D[WHERE句分解]
    D --> E[各項の解析]
    E --> F{仮想テーブル?}
    F -->|Yes| G[xBestIndex呼び出し]
    F -->|No| H[B-Treeインデックス列挙]
    G --> I[WhereLoop作成]
    H --> I
    I --> J[最適経路選択]
    J --> K[VDBEコード生成]
    K --> L[WhereInfo返却]
    L --> Z[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-16-01 | 全列参照時フルスキャン | SELECT *でインデックスより安価な場合はテーブルスキャン | カバリングインデックスなし |
| BR-16-02 | インデックス選択 | コスト最小のインデックスを選択 | 複数インデックス存在時 |
| BR-16-03 | 複合インデックス優先 | より多くの条件をカバーする複合インデックスを優先 | 常時 |
| BR-16-04 | ROWID優先 | 等価条件でROWIDが使用可能な場合は最優先 | ROWID条件時 |
| BR-16-05 | OR最適化 | OR条件は可能な場合インデックス和で処理 | インデックス使用可能時 |
| BR-16-06 | LIKE最適化 | LIKE 'prefix%'はインデックス範囲スキャンに変換 | ESCAPE指定なし |

### 計算ロジック

**コスト見積もり**:
- フルスキャン: テーブル行数 * 行取得コスト
- インデックススキャン: 推定行数 * (インデックス検索コスト + 行取得コスト)
- カバリングインデックス: 推定行数 * インデックス検索コスト

**行数推定（LogEst）**:
- 対数スケールで行数を表現（実際の行数の10を底とする対数の10倍）
- sqlite_stat1の統計情報を使用
- 統計情報がない場合はデフォルト推定値

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象 | 操作種別 | 概要 |
|-----|-----|---------|------|
| 統計参照 | sqlite_stat1 | SELECT | インデックス統計の取得 |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| SQLITE_NOMEM | メモリ不足 | WhereInfo割り当て失敗 | メモリ確保 |
| SQLITE_ERROR | 仮想テーブルエラー | xBestIndex失敗 | 仮想テーブル実装確認 |

### リトライ仕様

WHERE句最適化はクエリ実行前の単発処理であり、リトライ機構はない。

## トランザクション仕様

WHERE句最適化はコンパイル時処理であり、トランザクションとは独立。

## パフォーマンス要件

- 最適化処理時間はテーブル数・インデックス数に依存
- 通常は数ミリ秒以内で完了
- 複雑なクエリ（多テーブルJOIN）では最適経路探索に時間を要する可能性

## セキュリティ考慮事項

- 特になし（内部処理）

## 備考

- EXPLAINコマンドで生成された実行計画を確認可能
- EXPLAIN QUERY PLANでより人間可読な形式で表示
- ANALYZE文で統計情報を更新し、より正確な最適化が可能

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | whereInt.h | `src/whereInt.h` | WhereInfo, WhereClause, WhereTerm, WhereLoop構造体 |
| 1-2 | sqliteInt.h | `src/sqliteInt.h` | Expr, ExprList構造体 |

**読解のコツ**:
- WhereInfo: WHERE句処理全体の状態を保持
- WhereClause: WHERE句の項のコレクション
- WhereTerm: 個々の条件項（a=5, b>10など）
- WhereLoop: 1つのテーブルへのアクセス方法を表現

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | where.c | `src/where.c` | sqlite3WhereBegin()が主要エントリーポイント |

**主要処理フロー**:
1. WhereInfo構造体の割り当てと初期化
2. sqlite3WhereClauseInit()でWhereClause初期化
3. sqlite3WhereSplit()でWHERE句をANDで分割
4. sqlite3WhereExprAnalyze()で各項を解析
5. whereLoopAddAll()でアクセス方法を列挙
6. wherePathSolver()で最適経路を選択
7. VDBEコード生成

#### Step 3: 式解析を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | whereexpr.c | `src/whereexpr.c` | sqlite3WhereExprAnalyze()で式解析 |

**主要処理**:
- 比較演算子の解析（=, <, >, <=, >=, IN, LIKE等）
- インデックス使用可能性の判定
- 複合条件の分解

#### Step 4: コード生成を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | wherecode.c | `src/wherecode.c` | sqlite3WhereCodeBegin(), sqlite3WhereEnd() |

### プログラム呼び出し階層図

```
sqlite3WhereBegin() [where.c]
    │
    ├─ sqlite3WhereClauseInit() [whereexpr.c]
    │
    ├─ sqlite3WhereSplit() [whereexpr.c]
    │      └─ WHERE句をANDで分割
    │
    ├─ sqlite3WhereExprAnalyze() [whereexpr.c]
    │      ├─ exprAnalyze() - 個々の項を解析
    │      └─ exprAnalyzeOrTerm() - OR項の解析
    │
    ├─ whereLoopAddAll() [where.c]
    │      ├─ whereLoopAddBtree() - B-Treeインデックス
    │      │      └─ whereLoopAddBtreeIndex()
    │      └─ whereLoopAddVirtual() - 仮想テーブル
    │             └─ xBestIndex()呼び出し
    │
    ├─ wherePathSolver() [where.c]
    │      └─ 動的計画法で最適経路選択
    │
    └─ sqlite3WhereCodeBegin() [wherecode.c]
           └─ VDBEコード生成

sqlite3WhereEnd() [wherecode.c]
    └─ ループ終了コード生成
```

### データフロー図

```
[入力]                       [処理]                      [出力]

WHERE句式木 ───────▶ sqlite3WhereSplit()
                              │
                              ▼
                      WhereTerm配列
                              │
                              ▼
            ┌─────────────────┼─────────────────┐
            ▼                 ▼                 ▼
       項解析          インデックス列挙      統計情報参照
    (whereexpr.c)       (whereLoop*)       (sqlite_stat1)
            │                 │                 │
            └─────────────────┼─────────────────┘
                              ▼
                    wherePathSolver()
                              │
                              ▼
                    最適実行計画 ───────▶ VDBEコード
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| where.c | `src/where.c` | ソース | WHERE句最適化メイン処理、sqlite3WhereBegin() |
| whereexpr.c | `src/whereexpr.c` | ソース | 式解析、sqlite3WhereExprAnalyze() |
| wherecode.c | `src/wherecode.c` | ソース | VDBEコード生成 |
| whereInt.h | `src/whereInt.h` | ヘッダー | 内部データ構造定義 |
| analyze.c | `src/analyze.c` | ソース | 統計情報管理 |
| vdbe.c | `src/vdbe.c` | ソース | 生成されたコードの実行 |
