# 機能設計書 18-VDBEソート処理

## 概要

本ドキュメントは、SQLiteにおけるVDBEソート処理機能について記述する。VdbeSorterは、ORDER BY句やCREATE INDEX文で必要となる大量データのソート処理を効率的に実行するためのコンポーネントである。

### 本機能の処理概要

**業務上の目的・背景**：データベースクエリではORDER BY句による結果のソートや、インデックス作成時のキーソートが必要となる。VdbeSorterは、メモリに収まらない大量データでも効率的にソートできるマルチスレッド対応の外部マージソートアルゴリズムを実装している。これにより、利用可能なメモリ量に関係なく、任意サイズのデータセットをソート可能。

**機能の利用シーン**：
- ORDER BY句を含むSELECT文の実行
- CREATE INDEX文でのインデックス構築
- DISTINCT処理での重複排除
- GROUP BY句での集約処理

**主要な処理内容**：
1. ソーターの初期化（sqlite3VdbeSorterInit）
2. レコードの追加（sqlite3VdbeSorterWrite）
3. メモリ閾値超過時のPMA（Packed Memory Array）作成
4. 全レコード追加後のリワインド（sqlite3VdbeSorterRewind）
5. ソート済みデータの順次取得（sqlite3VdbeSorterNext, sqlite3VdbeSorterRowkey）
6. ソーターの終了処理（sqlite3VdbeSorterClose, sqlite3VdbeSorterReset）

**関連システム・外部連携**：VDBEバイトコードエンジン、一時ファイルシステム

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

## 関連画面

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

## 機能種別

ソートアルゴリズム / 外部マージソート

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pCsr | VdbeCursor* | Yes | ソーターカーソル | - |
| pKey | Mem* | Yes | ソートキー+データ | - |

### 入力データソース

- VDBEレジスタ（Mem構造体）
- ORDER BY列のデータ

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | int | エラーコード |
| ソート済みレコード | Mem* | sqlite3VdbeSorterRowkey()で取得 |

### 出力先

- 呼び出し元VDBEプログラム
- 一時ファイル（大量データ時）

## 処理フロー

### 処理シーケンス

```
1. 初期化（sqlite3VdbeSorterInit）
   └─ VdbeSorter構造体の割り当て
   └─ メモリ閾値の設定

2. レコード追加ループ
   └─ sqlite3VdbeSorterWrite()で各レコード追加
   └─ メモリ閾値チェック

3. 閾値超過時のPMA書き出し
   └─ インメモリデータをソート
   └─ 一時ファイルにPMA形式で書き出し
   └─ メモリ解放

4. リワインド（sqlite3VdbeSorterRewind）
   └─ 残りのインメモリデータをソート
   └─ PMAが存在する場合はマージ準備
   └─ 読み取りカーソルの位置決め

5. 順次取得ループ
   └─ sqlite3VdbeSorterNext()で次レコードへ
   └─ sqlite3VdbeSorterRowkey()でデータ取得

6. 終了処理
   └─ sqlite3VdbeSorterClose()でリソース解放
```

### フローチャート

```mermaid
flowchart TD
    A[ソーター初期化] --> B[レコード追加]
    B --> C{メモリ閾値超過?}
    C -->|No| D[メモリリストに追加]
    D --> E{追加完了?}
    E -->|No| B
    C -->|Yes| F[インメモリソート]
    F --> G[PMAファイル書き出し]
    G --> H[メモリ解放]
    H --> B
    E -->|Yes| I[リワインド]
    I --> J{PMA存在?}
    J -->|No| K[インメモリソート]
    J -->|Yes| L[マージ準備]
    K --> M[読み取り開始]
    L --> M
    M --> N{Next}
    N -->|データあり| O[Rowkey取得]
    O --> N
    N -->|EOF| P[終了処理]
    P --> Z[完了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-18-01 | メモリ閾値 | page_size * cache_sizeがメモリ閾値 | 常時 |
| BR-18-02 | PMA最大サイズ | 512MiB（SQLITE_MAX_PMASZ） | 常時 |
| BR-18-03 | マルチスレッド | SQLITE_MAX_WORKER_THREADS > 0でマルチスレッド有効 | コンパイル時 |
| BR-18-04 | 増分マージ | SORTER_MAX_MERGE_COUNT未満のPMAは増分マージ | リワインド時 |
| BR-18-05 | 階層マージ | 多数のPMAは階層的にマージ | PMA数が多い場合 |

### 計算ロジック

**メモリ閾値**:
```
threshold = PRAGMA main.page_size * PRAGMA main.cache_size
```

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

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

| 操作 | 対象 | 操作種別 | 概要 |
|-----|-----|---------|------|
| 一時ファイル作成 | ファイルシステム | 作成 | PMA保存用 |
| 一時ファイル削除 | ファイルシステム | 削除 | ソーター終了時 |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| SQLITE_NOMEM | メモリ不足 | メモリ割り当て失敗 | メモリ確保 |
| SQLITE_IOERR | I/Oエラー | 一時ファイル操作失敗 | ディスク容量確認 |

### リトライ仕様

エラー発生時はソート処理全体が失敗。リトライはクエリレベルで実施。

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

ソート処理はトランザクションとは独立。一時ファイルはトランザクション外。

## パフォーマンス要件

- インメモリソート: O(n log n)
- 外部マージソート: O(n log n) ディスクI/O
- マルチスレッド時は並列化により高速化

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

- 一時ファイルは自動削除
- 機密データの一時ファイル残存リスクあり（必要に応じて暗号化検討）

## 備考

- PRAGMA threads=Nでワーカースレッド数を制御
- インメモリDBでも大量ソートは一時ファイルを使用

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | vdbesort.c | `src/vdbesort.c` | VdbeSorter, SorterList, SorterRecord, MergeEngine構造体 |

**読解のコツ**:
- VdbeSorter: ソーター全体の状態
- SorterList: インメモリのレコードリスト
- SorterRecord: 個々のソートレコード
- MergeEngine: PMAマージ処理用
- PmaReader: PMA読み取り用
- PmaWriter: PMA書き込み用

#### Step 2: インターフェースを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | vdbesort.c | `src/vdbesort.c` | 22-67行目のインターフェースコメント |

**主要API**:
1. **sqlite3VdbeSorterInit()**: 初期化
2. **sqlite3VdbeSorterWrite()**: レコード追加
3. **sqlite3VdbeSorterRewind()**: ソート実行と読み取り準備
4. **sqlite3VdbeSorterNext()**: 次レコードへ移動
5. **sqlite3VdbeSorterRowkey()**: 現在レコード取得
6. **sqlite3VdbeSorterCompare()**: 比較（UNIQUEチェック用）
7. **sqlite3VdbeSorterClose()**: 終了
8. **sqlite3VdbeSorterReset()**: リセット（再利用用）

#### Step 3: アルゴリズムを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | vdbesort.c | `src/vdbesort.c` | 69-137行目のアルゴリズム説明コメント |

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

```
sqlite3VdbeSorterInit() [vdbesort.c]
    └─ VdbeSorter構造体初期化

sqlite3VdbeSorterWrite() [vdbesort.c]
    │
    ├─ レコードをSorterListに追加
    │
    └─ (閾値超過時)
           ├─ vdbeSorterSort() - インメモリソート
           └─ vdbeSorterFlushPMA() - PMA書き出し

sqlite3VdbeSorterRewind() [vdbesort.c]
    │
    ├─ (インメモリのみ)
    │      └─ vdbeSorterSort()
    │
    └─ (PMAあり)
           ├─ 残りデータのPMA化
           └─ vdbeMergeEngineInit() - マージ準備

sqlite3VdbeSorterNext() [vdbesort.c]
    │
    ├─ (インメモリ)
    │      └─ 次レコードへポインタ移動
    │
    └─ (マージ中)
           └─ vdbeMergeEngineStep()

sqlite3VdbeSorterRowkey() [vdbesort.c]
    └─ 現在レコードのキーを返却

sqlite3VdbeSorterClose() [vdbesort.c]
    └─ リソース解放
```

### データフロー図

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

レコード ─────────▶ sqlite3VdbeSorterWrite()
                              │
                              ▼
                      SorterList (メモリ)
                              │
            ┌─────────────────┼─────────────────┐
            ▼                                   ▼
       (閾値以下)                          (閾値超過)
            │                                   │
            ▼                                   ▼
       メモリ保持                        vdbeSorterSort()
                                               │
                                               ▼
                                       PMAファイル書き出し

sqlite3VdbeSorterRewind()
            │
            ▼
    ┌───────┴───────┐
    ▼               ▼
インメモリ      マージエンジン
ソート          初期化
    │               │
    └───────┬───────┘
            ▼
     読み取り準備完了

sqlite3VdbeSorterNext() ───▶ 次レコード
sqlite3VdbeSorterRowkey() ─▶ レコードデータ
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| vdbesort.c | `src/vdbesort.c` | ソース | ソート処理メイン |
| vdbeInt.h | `src/vdbeInt.h` | ヘッダー | VdbeSorter構造体定義 |
| vdbe.c | `src/vdbe.c` | ソース | OP_SorterOpen, OP_SorterInsert等の実装 |
| pager.c | `src/pager.c` | ソース | 一時ファイル管理 |
