# 機能設計書 35-Star-Tree インデックス

## 概要

本ドキュメントは、OpenSearchのStar-Treeインデックス機能の設計を記述する。Star-Treeインデックスは事前集計データを保持する複合インデックスであり、集計クエリを高速に処理するための機能である。

### 本機能の処理概要

Star-Treeインデックスは、インデックス時にディメンション（次元）とメトリクスの組み合わせに対する集計値を事前計算し、ツリー構造で保持する機能である。検索時にStar-Treeを活用することで、全ドキュメントをスキャンすることなく集計結果を高速に取得できる。

**業務上の目的・背景**：大規模データセットに対する集計クエリ（特にSum、Count、Min、Max、Avg等のメトリクス集計）のレスポンスタイムを大幅に短縮するニーズに対応する。OLAP（Online Analytical Processing）的なワークロードに適した事前集計アプローチを提供する。

**機能の利用シーン**：インデックス設定でStar-Tree複合インデックスを定義し、ディメンション（グループ化軸）とメトリクス（集計対象）を指定する。検索時、適用可能な集計クエリが自動的にStar-Treeを使用して高速処理される。

**主要な処理内容**：
1. インデックス設定でStar-Tree構成（ディメンション、メトリクス）を定義
2. ドキュメントインデックス時にStar-Treeノードを構築・更新
3. Luceneセグメントマージ時にStar-Treeデータを統合
4. 検索時にStarTreeQueryContextでStar-Tree利用可能性を判定
5. StarTreeFilterでディメンションフィルタを適用
6. StarTreeBucketCollector/StarTreePreComputeCollectorで事前集計値を収集
7. 通常の集計パスをバイパスして高速に結果を返却

**関連システム・外部連携**：Luceneのセグメント・DocValues。CompositeIndexReaderによるStar-Treeデータ読み取り。

**権限による制御**：インデックスの読み取り権限が必要。Star-Tree設定はインデックス作成時の管理者権限が必要。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 21 | 検索 | 補助機能 | Star-Treeを活用した高速集計処理 |

## 機能種別

計算処理（インデックス構築・集計最適化）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| composite_index.star_tree | Object | Yes | Star-Tree設定セクション | 有効な設定オブジェクト |
| ordered_dimensions | Array | Yes | ディメンション（次元）の定義配列 | サポートされるフィールド型 |
| metrics | Array | Yes | メトリクス定義配列 | サポートされるメトリクスタイプ |
| metrics[].field | String | Yes | メトリクス対象フィールド | 数値型フィールド |
| metrics[].stats | String[] | Yes | 集計タイプ（sum, count, min, max, avg等） | サポートされるMetricStat |
| max_leaf_docs | Integer | No | Star-Treeリーフノードの最大ドキュメント数 | 正の整数 |
| build_mode | String | No | Star-Tree構築モード | ON_HEAP等 |

### 入力データソース

インデックス設定（mappings内のcomposite_index定義）。ドキュメントのフィールド値。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Star-Treeセグメントデータ | Binary | Luceneセグメント内のStar-Treeバイナリデータ |
| Star-Treeメタデータ | Binary | ディメンション構成・メトリクス情報 |
| 事前集計メトリクス値 | Numeric | 各ノードの集計済みメトリクス値 |

### 出力先

Luceneセグメントファイル内にStar-Treeデータとして格納。検索時は集計レスポンスに反映。

## 処理フロー

### 処理シーケンス

```
1. インデックス設定でStar-Tree定義
   └─ CompositeIndexValidatorで設定を検証
2. ドキュメントインデックス時
   └─ Star-TreeBuilderがディメンション・メトリクス値を収集
3. セグメントフラッシュ時
   └─ StarTreeWriterでStar-Treeをシリアライズ
4. 検索クエリ受信時
   └─ StarTreeQueryHelper.isStarTreeSupported()で利用可能性判定
5. Star-Tree読み取り
   └─ CompositeIndexReaderからStarTreeValuesを取得
6. ディメンションフィルタ適用
   └─ StarTreeFilterでマッチするノードを絞り込み
7. メトリクス値収集
   └─ StarTreeBucketCollectorで事前集計値を収集
8. 結果返却
   └─ 通常の集計パスをバイパスして高速返却
```

### フローチャート

```mermaid
flowchart TD
    A[検索クエリ受信] --> B{Star-Tree利用可能?}
    B -->|No| C[通常の集計パス]
    B -->|Yes| D[StarTreeQueryContext構築]
    D --> E[CompositeIndexFieldInfo取得]
    E --> F[StarTreeValues読み取り]
    F --> G[StarTreeFilter適用]
    G --> H[マッチノード走査]
    H --> I[事前集計メトリクス値収集]
    I --> J[InternalAggregation構築]
    J --> K[結果返却]
    C --> K
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-35-01 | Star-Tree対応判定 | aggregationsが存在し、CompositeIndexが存在し、post_filterがない場合にStar-Tree使用可能 | 検索クエリ |
| BR-35-02 | ディメンション型制約 | ディメンションはNumeric、Ordinal、UnsignedLong、DateTimeタイプのみ | Star-Tree定義 |
| BR-35-03 | メトリクス型制約 | メトリクスはsum、count、min、max、avg（sumとcountの組合せ）のみ | Star-Tree定義 |
| BR-35-04 | FixedLengthNode | Star-Treeノードは固定長形式で格納 | セグメント内 |
| BR-35-05 | DimensionFilter | ExactMatch、RangeMatch、MatchAll、MatchNoneの4種類 | 検索フィルタ |

### 計算ロジック

- Star-Treeノードはディメンション値の組み合わせごとにメトリクスの事前集計値を保持
- "*"（スター）ノードは特定ディメンション値を集約した集計値を保持
- 検索時はディメンションフィルタにマッチするノードのメトリクス値を収集して返却

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

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

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| Star-Tree構築 | Luceneセグメント | WRITE | セグメントフラッシュ時にStar-Treeデータを書き込み |
| Star-Tree検索 | Luceneセグメント | READ | Star-Treeデータから事前集計値を読み取り |

### テーブル別操作詳細

#### Luceneセグメント（Star-Treeデータ）

| 操作 | 項目 | 更新値・取得条件 | 備考 |
|-----|------|-----------------|------|
| WRITE | Star-Treeノード | ディメンション値とメトリクス事前集計値 | セグメントフラッシュ・マージ時 |
| READ | Star-Treeメトリクス | ディメンションフィルタ条件 | 検索集計時 |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| 400 | illegal_argument_exception | 不正なStar-Tree設定 | 有効なディメンション・メトリクスを指定 |
| 400 | mapper_parsing_exception | サポートされないフィールド型 | サポート対象のフィールド型を使用 |

### リトライ仕様

インデックス構築はドキュメント単位でリトライ可能。検索は読み取り専用のためリトライ可能。

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

Star-Tree構築はLuceneセグメントのフラッシュ・マージに統合されており、セグメントレベルのアトミック性が保証される。

## パフォーマンス要件

- Star-Tree検索は全ドキュメントスキャンを回避し、O(log N)〜O(1)の計算量で集計結果を取得
- インデックスサイズはStar-Treeデータ分だけ増加（ディメンションのカーディナリティに依存）
- インデックス速度はStar-Tree構築のオーバーヘッドにより低下

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

- Star-Tree設定はインデックス管理者権限が必要
- 検索時はインデックス読み取り権限に従う

## 備考

- Star-Treeインデックスは実験的機能（@opensearch.experimental）
- CompositeIndexFieldInfoでStar-Treeのメタ情報を保持
- ディメンションフィルタにはExactMatchDimFilter、RangeMatchDimFilter等がある

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | StarTreeMetadata.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/meta/StarTreeMetadata.java` | Star-Treeのメタデータ構造 |
| 1-2 | Metric.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/Metric.java` | メトリクス定義 |
| 1-3 | DimensionType.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/DimensionType.java` | ディメンション型定義 |
| 1-4 | FixedLengthStarTreeNode.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/node/FixedLengthStarTreeNode.java` | Star-Treeノードの固定長バイナリ形式 |

**読解のコツ**: Star-Treeは階層的ツリー構造であり、各ディメンションレベルでノードが分岐する。"*"（スター）ノードは特定ディメンション値を集約した特殊ノード。

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | StarTreeQueryHelper.java | `server/src/main/java/org/opensearch/search/startree/StarTreeQueryHelper.java` | Star-Tree検索のヘルパー。isStarTreeSupported()が利用可能性判定 |
| 2-2 | StarTreeQueryContext.java | `server/src/main/java/org/opensearch/search/startree/StarTreeQueryContext.java` | Star-Treeクエリコンテキスト |

**主要処理フロー**:
- **53-54行目**: isStarTreeSupported()：aggregationsがnullでない、compositeIndexが存在、parsedPostFilterがnullであることを確認
- **57-59行目**: getSupportedStarTree()：StarTreeQueryContextからCompositeIndexFieldInfoを取得
- **62-68行目**: getStarTreeValues()：LeafReaderContextからStarTreeValuesを取得

#### Step 3: ディメンションフィルタを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | DimensionFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/DimensionFilter.java` | ディメンションフィルタ基底 |
| 3-2 | ExactMatchDimFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/ExactMatchDimFilter.java` | 完全一致フィルタ |
| 3-3 | RangeMatchDimFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/RangeMatchDimFilter.java` | 範囲一致フィルタ |
| 3-4 | StarTreeFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/StarTreeFilter.java` | Star-Treeフィルタ実行 |

#### Step 4: Star-Treeデータの書き込みを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | StarTreeWriter.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/StarTreeWriter.java` | Star-Treeデータのシリアライズ |
| 4-2 | StarTreeDataWriter.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/data/StarTreeDataWriter.java` | Star-Treeデータの書き込み |
| 4-3 | StarTreeMetadataWriter.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/meta/StarTreeMetadataWriter.java` | メタデータ書き込み |

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

```
[インデックス時]
DocumentWriter
    +-- StarTreeBuilder.build()
          +-- StarTreeWriter.writeStarTree()
                +-- StarTreeDataWriter.writeData()
                +-- StarTreeMetadataWriter.writeMeta()

[検索時]
SearchService.executeQueryPhase()
    +-- StarTreeQueryHelper.isStarTreeSupported()
    +-- StarTreeQueryHelper.getSupportedStarTree()
    +-- AggregationPhase
          +-- StarTreeQueryHelper.getStarTreeValues()
          |     +-- CompositeIndexReader.getCompositeIndexValues()
          +-- StarTreeFilter.getStarTreeResult()
          +-- StarTreeBucketCollector / StarTreePreComputeCollector
                +-- SortedNumericStarTreeValuesIterator
```

### データフロー図

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

[インデックス時]
ドキュメント         +--> ディメンション値抽出
(フィールド値)       +--> メトリクス値計算
                     +--> Star-Treeノード構築        +--> Luceneセグメント
                     +--> FixedLengthNode書き込み          (Star-Treeデータ)

[検索時]
集計クエリ           +--> Star-Tree利用可能性判定
                     +--> StarTreeValues読み取り
                     +--> DimensionFilter適用
Star-Treeデータ      +--> マッチノードの                +--> 検索レスポンス
                     |     メトリクス値収集                   (集計結果)
                     +--> InternalAggregation構築
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| StarTreeQueryHelper.java | `server/src/main/java/org/opensearch/search/startree/StarTreeQueryHelper.java` | ソース | 検索時のStar-Treeヘルパー |
| StarTreeQueryContext.java | `server/src/main/java/org/opensearch/search/startree/StarTreeQueryContext.java` | ソース | クエリコンテキスト |
| StarTreeFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/StarTreeFilter.java` | ソース | フィルタ実行 |
| DimensionFilter.java | `server/src/main/java/org/opensearch/search/startree/filter/DimensionFilter.java` | ソース | ディメンションフィルタ基底 |
| StarTreeMetadata.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/meta/StarTreeMetadata.java` | ソース | メタデータ |
| FixedLengthStarTreeNode.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/node/FixedLengthStarTreeNode.java` | ソース | ノード形式 |
| StarTreeWriter.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/startree/fileformats/StarTreeWriter.java` | ソース | データ書き込み |
| CompositeIndexConstants.java | `server/src/main/java/org/opensearch/index/compositeindex/CompositeIndexConstants.java` | ソース | 定数定義 |
| CompositeIndexValidator.java | `server/src/main/java/org/opensearch/index/compositeindex/CompositeIndexValidator.java` | ソース | 設定バリデーション |
| Metric.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/Metric.java` | ソース | メトリクス定義 |
| DimensionType.java | `server/src/main/java/org/opensearch/index/compositeindex/datacube/DimensionType.java` | ソース | ディメンション型 |
