データベースの実行計画を最適化する！統計情報とヒストグラムの活用法

## 目次
- [1. ヒストグラムとは？](#1-ヒストグラムとは)
- [2. 統計情報のヒストグラムとは？](#2-統計情報のヒストグラムとは)
- [3. 統計情報のヒストグラムの種類](#3-統計情報のヒストグラムの種類)
- [4. RDBMSごとのヒストグラム仕様の比較](#4-rdbmsごとのヒストグラム仕様の比較)
- [5. 各ヒストグラムの活用例（クエリ最適化）](#5-各ヒストグラムの活用例クエリ最適化)
- [6. 検証の準備：ヒストグラムの確認方法](#6-検証の準備ヒストグラムの確認方法)
- [7. 検証：ヒストグラムによるクエリ最適化の影響](#7-検証ヒストグラムによるクエリ最適化の影響)
- [8. まとめ](#8-まとめ)

---

## 1. ヒストグラムとは？

**ヒストグラム（Histogram）** とは、**データの分布を視覚的に表す棒グラフ** の一種です。  
データのばらつきや集中度、偏りを直感的に把握するために利用されます。  

### 🔹 ヒストグラムの特徴
- **X軸**：データの範囲（**ビン / Bin**）  
- **Y軸**：各範囲（ビン）に属するデータの個数（頻度）

ヒストグラムは、データの分布を視覚的に確認するために使われ、統計解析や機械学習、データベースの最適化など幅広い分野で活用されます。

---

### 🔹 ヒストグラムの用途
ヒストグラムを用いることで、以下のような情報を得ることができます。

- **データの分布（正規分布 / 偏りの有無）**
- **外れ値（異常値）の検出**
- **中央値・平均値の確認**
- **データのばらつき具合**
- **頻度が高い値の特定**




---

### 🔹 ヒストグラムの具体例
例えば、**試験の点数分布** をヒストグラムで表すと、次のような特徴がわかります。

- **平均点付近にデータが集中しているか？**
- **特定の範囲（ビン）に極端な偏りがあるか？**
- **分布が一山（正規分布）か、二山（バイモーダル分布）か？**

---

### 🔹 ヒストグラムと棒グラフの違い
| **項目** | **ヒストグラム** | **棒グラフ** |
|----------|----------------|-------------|
| **目的** | データの分布を表現 | カテゴリごとの比較 |
| **X軸** | 連続値の範囲（ビン） | 離散的なカテゴリ（例：商品A, 商品B） |
| **棒の間隔** | **なし（連続）** | **あり（カテゴリ間に隙間）** |

- **ヒストグラムは「連続値」のデータの分布を可視化するためのグラフ**
- **棒グラフは「カテゴリごとの数値」を比較するためのグラフ**


### 🔹 棒グラフ（イメージ）
![スクリーンショット 2025-03-16 21.36.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/bb6c3942-e936-4195-8749-1e1b537f8f6b.png)

### 🔹 ヒストグラム（イメージ）
![スクリーンショット 2025-03-16 21.36.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/92d7a324-722b-4dea-9e7d-25a5ae156671.png)


---

## 2. 統計情報のヒストグラムとは？

データベース管理システム（RDBMS）では、クエリの最適な実行計画を作成するために **「統計情報（Statistics）」** を保持しています。  
その統計情報の一つが **ヒストグラム（Histogram）** です。  

### 🔹 統計情報のヒストグラムの役割
**データベースのヒストグラム** は、各カラムのデータ分布を記録し、クエリ最適化に活用されます。  
これにより、**WHERE 句のフィルタリングやインデックスの有無に応じた最適なスキャン方法を選択** できます。

### 🔹 具体的な活用例
- **クエリ実行時、WHERE 句の条件がどの程度のデータを取得するのかを推定**
- **インデックスを使うべきか、フルスキャン（Seq Scan）が適切かを判断**
- **結合（JOIN）の際に、どちらのテーブルを先にスキャンすべきかを決定**

---

### 🔹 ヒストグラムを利用したクエリ最適化の流れ
1. **クエリ実行時にオプティマイザが統計情報を参照**
2. **WHERE 句の条件にマッチするデータの割合（選択率）を推定**
3. **適切なスキャン方法（Index Scan / Seq Scan / Bitmap Index Scanなど）を選択**
4. **最適な結合アルゴリズムを決定（Nested Loop / Hash Join など）**
5. **実行計画を決定し、クエリを実行**

---

### 🔹 ヒストグラムが適切に機能しない場合の影響
**統計情報（ヒストグラム）が不正確、もしくは更新されていない場合、以下のような問題が発生します。**

- **不要なインデックススキャンが発生し、クエリの実行が遅くなる**
- **Seq Scan（フルスキャン）が選ばれ、不要なレコードを大量に読み込む**
- **結合順序が最適化されず、処理時間が増加**
- **データ分布の変化に適応できず、オプティマイザの推定精度が低下**

これらの問題を防ぐため、定期的に **`ANALYZE`** を実行し、統計情報を更新することが推奨されます。

```sql
ANALYZE table_name; -- PostgreSQL / MySQL
DBMS_STATS.GATHER_TABLE_STATS('schema_name', 'table_name'); -- Oracle
UPDATE STATISTICS table_name; -- SQL Server
```


### 🔹 統計情報のヒストグラム（イメージ）
![スクリーンショット 2025-03-16 21.43.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/dfb39d82-c69f-4b4a-a045-44c116f2aa48.png)




---

## 3. 統計情報のヒストグラムの種類


データベースが統計情報として保持するヒストグラムには、以下の3つの主要な種類があります。

- **等間隔ヒストグラム（Equal-Width Histogram）**
- **等深度ヒストグラム（Equal-Height Histogram）**
- **ハイブリッドヒストグラム（Hybrid Histogram）**

それぞれの特性を理解することで、クエリ最適化にどのように影響するのかを把握できます。

---

### 🔹 1. 等間隔ヒストグラム（Equal-Width Histogram）
**特徴**
- データの範囲を **均等な幅（ビン）** に区切る
- **各ビンの幅は一定** だが、ビンごとのデータ数は異なる
- **データが均等に分布している場合に適している**

**メリット**
- 計算コストが低く、実装がシンプル
- 一般的な数値データ（時間、金額など）に適用しやすい

**デメリット**
- **データの偏りを考慮できない**
- 極端に偏ったデータがあると、特定のビンにデータが集中してしまう

---

### 🔹 2. 等深度ヒストグラム（Equal-Height Histogram）
**特徴**
- **各ビンのデータ数を均等にする** ように範囲を決定
- データの偏りを考慮して、ビンの幅を可変に調整
- **分布が偏っているデータに適している**

**メリット**
- データの偏りがあっても、各ビンに均等なデータ量を割り当てるため、選択率（選択性）の推定精度が向上する
- WHERE 句の **フィルタリング精度が向上し、最適な実行計画が選ばれやすい**

**デメリット**
- ビンの境界値が均等でないため、計算コストが上がる
- 極端にデータが偏っている場合、特定の値が適切に扱われないことがある

---

### 🔹 3. ハイブリッドヒストグラム（Hybrid Histogram）
**特徴**
- **等深度ヒストグラム + MCV（Most Common Values）**
- **高頻度の値（MCV）を個別のビンとして保持** し、それ以外を等深度ヒストグラムで管理
- Oracle や PostgreSQL などで採用されている

**メリット**
- **データの偏りが大きい場合に最も精度が高い**
- **特定の値が多く出現する（例：カテゴリデータ）場合に最適**
- クエリオプティマイザが、頻出値とそれ以外のデータを区別できる

**デメリット**
- 統計情報の管理が複雑になる
- 更新のたびに MCV の再計算が必要

---


### 🔹 4. 等間隔ヒストグラム　のイメージ
![スクリーンショット 2025-03-17 21.14.27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/516cd99b-8414-4507-9b55-5f0db6a163fd.png)

---
### 🔹 5. 等深度ヒストグラム　のイメージ
![スクリーンショット 2025-03-17 21.14.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/b7c1abbb-6b81-4851-b3c7-06813d084e23.png)

---

### 🔹 6. ハイブリッドヒストグラム（イメージはPostgreSQLの等深度＋MCV）
![スクリーンショット 2025-03-17 21.14.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3880450/a4c93c8f-06f4-48cb-888d-6f68001e97d9.png)

PostgreSQL では、**等深度ヒストグラム（Equal-Height Histogram）** と **MCV（Most Common Values）** を組み合わせた **ハイブリッドヒストグラム** を採用しています。  
これにより、**データの偏りを考慮しつつ、頻出値（高頻度の値）を個別に管理** することで、クエリの最適化精度を向上させています。

---

### 🔹 ハイブリッドヒストグラムの仕組み
-  **「高頻度の値」は個別のビンに分ける（MCVの考え方）**  
　→ **特定の値（例：31）は個別のビンとして扱い、その他の値は統合**  
-  **「その他の値」は等深度で分割**  
　→ **データ数を均等にするように、範囲ごとにグループ化**  
-  **ビンの幅は可変！データの偏りに応じて調整される**  
　→ **等間隔ではなく、データの分布によって区切りが変わる**  
-  **ヒストグラム＋MCVのハイブリッド手法！**  
　→ **ヒストグラムの精度を上げるため、頻出値を個別に記録する仕組み！**  
✅ **データの偏りを考慮し、実行計画をより最適化！**  

---

### 🔹 なぜハイブリッドヒストグラムが必要か？
従来の **等間隔ヒストグラム** や **等深度ヒストグラム** には、それぞれ以下の問題点があります。

| **ヒストグラムの種類** | **問題点** |
|------------------|------------|
| **等間隔ヒストグラム** | 偏りのあるデータに対応できず、特定のビンにデータが集中する |
| **等深度ヒストグラム** | 頻出値の影響を無視し、正確な選択率を推定できない |
| **ハイブリッドヒストグラム** | 頻出値（MCV）を個別に管理し、残りを等深度で分割することで精度向上 |

✅ **ハイブリッドヒストグラムでは、「よく出る値」を個別に管理し、それ以外を等深度で分割することで、より正確な推定が可能！**

---

## 4. RDBMSごとのヒストグラム仕様の比較
| RDBMS        | 等間隔 | 等深度 | その他 |
|-------------|--------|--------|----------------|
| **Oracle**  | ❌ なし | ✅ あり | ハイブリッド（等深度 + MCV） |
| **PostgreSQL** | ❌ なし | ✅ あり | ハイブリッド（等深度 + MCV）|
| **MySQL**    | ❌ なし | ✅ あり | シングルトンヒストグラム |

---

## 5. 各ヒストグラムの活用例（クエリ最適化）


### 🔹 なぜヒストグラムが必要なのか？
SQL の実行計画を決定する **クエリオプティマイザ** は、テーブルのデータ分布を考慮して最適なスキャン方法を選択する。  
しかし、**データ分布が均一ではない** 場合、**単純な統計情報だけでは適切な実行計画を立てられません。**  
→ **そこでヒストグラムを活用し、データの分布を詳細に把握することで、より正確な実行計画を選択できます。**

---

## 🔹 各ヒストグラムの活用例

### **📌 1. 等間隔ヒストグラム（Equal-Width Histogram）**
**適用シナリオ**:  
- **データが均等に分布している場合に有効**（例：時間、シーケンシャルID）  
- **範囲検索（BETWEEN、>、<）が頻繁に行われる** クエリに適している  
**クエリ最適化の例**
```sql
SELECT * FROM sales WHERE sale_date BETWEEN '2024-01-01' AND '2024-06-30';
```
➡ データが均一に分布しているため、等間隔ヒストグラムを使って範囲検索の選択率を正確に予測できます。

---

### 📌 2. 等深度ヒストグラム（Equal-Height Histogram）

#### **適用シナリオ**
- **データの分布が偏っている場合に有効**（例：売上データ、ユーザーアクセス数）
- **カラムの値ごとにデータの偏りが大きい場合**

#### **クエリ最適化の例**
```sql
SELECT * FROM sales WHERE customer_id = 100000;
```
➡ データが偏っていると、単純な統計情報では対応しきれない可能性がある
➡ 等深度ヒストグラムを使用すると、頻出する customer_id = 100000 の選択率をより正確に把握でき、最適なインデックススキャンを選択可能！

---
### 📌 3. ハイブリッドヒストグラム（等深度 + MCV）

#### **適用シナリオ**
- **特定の値が極端に多い（最頻値：MCV）**
- **データの偏りが大きく、特定の値がクエリ頻度の大部分を占める場合**

#### **クエリ最適化の例**
```sql
SELECT * FROM orders WHERE order_status = 'shipped';
```
➡ 「shipped」が全データの 50% を占める場合、MCV を使ってこの値を個別に管理
➡ 「その他の値」は等深度ヒストグラムで管理し、データ分布を考慮した最適なスキャン方法を選択可能！

---

## 6. 検証の準備：ヒストグラムの確認方法


### 📌 なぜヒストグラムを確認するのか？
SQL の実行計画を適切に評価するためには、**PostgreSQL が持つ統計情報（ヒストグラム）がどのように構成されているかを確認することが重要** である。  
ヒストグラムの確認方法を知ることで、**クエリオプティマイザが適切な実行計画を選択しているかを検証できる！**

---

### 検証環境

| 項目             | 内容                                   |
| ---------------- | -------------------------------------- |
| **データベース** | PostgreSQL                             |
| **テストデータ** | 400万件のデータ                        |
| **検証対象**     | `pg_stats` の MCV & ヒストグラムの影響 |
| **スキャン方法の確認** | `EXPLAIN ANALYZE` を使用             |


---
### テーブル構造 & データの分布

| カラム名 | データの分布                   | 検証の目的                                         | `pg_stats` 情報 |
| -------- | ------------------------------ | -------------------------------------------------- | --------------- |
| **COL_A** | 一意なデータ (1〜400万)        | 主キー検索で Index Scan になるか？                 | MCVなし / ヒストグラムあり |
| **COL_B** | 100,000 が 40% を占める        | MCV の影響で Seq Scan になるか？                   | MCVあり / ヒストグラムあり |
| **COL_C** | 10,000(50%) & 90,000(50%)      | 2種類の場合、MCVの影響はどうか？                   | MCVあり / ヒストグラムなし |
| **COL_D** | A〜J の10種類(均等)           | カテゴリデータ(10種類)で MCVの影響はどうか？       | MCVあり / ヒストグラムなし |

---

### `pg_stats` のデータ

| カラム名 | `n_distinct` | `most_common_vals`（MCV） | `histogram_bounds` | `correlation` |
| -------- | ------------ | ------------------------ | ------------------- | ------------- |
| **COL_A** | -1<br>（ユニーク） | NULL | {112, 38992…} (多いため略) | 0.83 |
| **COL_B** | 31,803 | {100,000}<br>（39.95%） | {10,005, 10,899…} (多いため略) | -0.65 |
| **COL_C** | 2 | {10,000, 90,000}<br>（約50%ずつ） | NULL | 1.0 |
| **COL_D** | 10 | {E, G, B, F, H, C, A, I, J, D}<br>（約10%ずつ） | NULL | 0.108 |

**各カラムの補足**

- **`n_distinct`**：ユニークな値の数
- **`most_common_vals`（MCV）**：よく出る値リスト（NULLはMCVを使用しない）
- **`histogram_bounds`**：等深度ヒストグラムの境界（NULLは等深度を使用しない）
- **`correlation`**：カラム値の並びと物理順の相関
  - 1 に近い：Index Scan 向き
  - -1に近い：逆 Index Scan 向き
  - 0 に近い：Full Scan の可能性

**用語解説**

- **「物理順」**：ディスク上のデータの並び（実際の保存順）
- **「カラム値の順序」**：カラムの値を大小順に並べた場合の論理的な概念（物理順とは関係なし）

---

### 検証用のクエリ

| クエリ | 意味 |
| ------ | ---- |
| `SELECT * FROM A WHERE COL_A = 100000;` | 主キー検索で Index Scan になるか？ |
| `SELECT * FROM A WHERE COL_B = 100000;` | MCV の影響で Seq Scan になるか？ |
| `SELECT * FROM A WHERE COL_B = 50000;` | 低頻度値で Index Scan になるか？ |
| `SELECT * FROM A WHERE COL_C = 10000;` | 二つの山がある分布(バイモーダル分布)はスキャンに影響するか？ |
| `SELECT * FROM A WHERE COL_C = 90000;` | 同上 |
| `SELECT * FROM A WHERE COL_D = 'A';` | 10種類のデータ（カテゴリ）で Bitmap Index Scan になるか？ |


---

## 7. 検証：ヒストグラムによるクエリ最適化の影響

### 📌 検証結果

| クエリ | スキャン方法 |
|--------|------------|
| `SELECT * FROM A WHERE COL_A = 100000;` | **Index Scan** |
| `SELECT * FROM A WHERE COL_B = 100000;` | **Seq Scan** |
| `SELECT * FROM A WHERE COL_B = 50000;` | **Index Scan** |
| `SELECT * FROM A WHERE COL_C = 10000;` | **Index Scan** |
| `SELECT * FROM A WHERE COL_C = 90000;` | **Index Scan** |
| `SELECT * FROM A WHERE COL_D = 'A';` | **Bitmap Index Scan** |

---

### ✅ 結果からの考察

#### **COL_A = 100000 は Index Scan**
- **`COL_A` は一意なデータ（1〜400万）であり、プライマリキーが設定されているため、Index Scan が最適**
- **`pg_stats` の `n_distinct = -1`（ユニーク値）であり、MCV は不要**
- **`histogram_bounds` が存在し、等深度ヒストグラムが有効**
- **correlation = 0.83 と高いため、物理順とカラム値の順序が概ね一致 → Index Scan に適したデータ配置**
- **このようなユニークキーの検索では、Index Scan がほぼ常に選択される**


#### **COL_B = 100000 が Seq Scan になった理由**
- **データの 40% を取得するため、Index Scan より Seq Scan の方が効率的**
- **correlation = 0 に近いため、Index Scan ではランダムアクセスが発生し、Seq Scan の方が適切と判断された可能性が高い**
- **もし correlation = 1.0 または -1.0 に近ければ、Index Scan が選ばれた可能性がある**

#### **COL_B = 50000 は Index Scan になった理由**
- **MCV に登録されていないため、PostgreSQL はヒストグラムを参照**
- **低頻度値なので Index Scan を選択**


#### **COL_C = 10000 / 90000 は Index Scan**
- **MCV によって両方の値が登録されていたため、適切に Index Scan が選ばれた**
- **対象行数は多いが correlation = 1.0（物理順とカラム値が一致）なので、インデックススキャンが効率的**

#### **COL_D = 'A' は Bitmap Index Scan**
- **COL_B と同様に、correlation の影響で Index Scan は非効率**
- **correlation = 0.108（ほぼ順番バラバラ）で、Index Scan よりも Bitmap Index Scan の方が適切**
- **カテゴリ型データ（10種類の値）で特定の値を取得する場合、Bitmap Index Scan によって効率的に処理された**

---

### 📌 ヒストグラムとスキャン方式の関係

✅ **MCV に登録された値 → 適切に Seq Scan or Index Scan を選択**  
✅ **correlation = 1.0 に近い場合 → Index Scan が効率的**  
✅ **correlation = 0 に近い場合 → Seq Scan or Bitmap Index Scan が選ばれる**  

- **correlation = 0 に近い場合、Seq Scan が最適になることがある！**  
- **Seq Scan は、連続的なデータ読み込みによりキャッシュ効率が高く、Index Scan のランダム I/O (O(N)) よりも速くなる場合がある！**  
- **Index Scan はインデックスを参照しつつランダムアクセスが発生 → 取得対象が多いと I/O コスト増**  
- **Seq Scan はディスクを連続的に読み込み、I/O が最適化されるため、高速に処理できる**
---

## 8. まとめ


### 📌 今回の検証のポイント

✅ **ヒストグラムの有無によってクエリのスキャン方式が変わる！**  
✅ **MCV（Most Common Values）が適切に機能すれば、最適なスキャン方法が選択される！**  
✅ **correlation（カラム値の順序と物理順の相関）がスキャン方式に大きく影響！**  

---

### 🔹 **ヒストグラムの影響まとめ**

| カラム | スキャン方式 | 主な要因 |
|--------|------------|-------------------------|
| **COL_A** | Index Scan | 主キー検索（ユニーク値） |
| **COL_B = 100000** | Seq Scan | MCV に登録され、取得件数が多いため |
| **COL_B = 50000** | Index Scan | MCV に登録されておらず、低頻度値 |
| **COL_C** | Index Scan | MCV による適切な選択、correlation = 1.0 |
| **COL_D** | Bitmap Index Scan | correlation が低く、10種類のデータ |

---

### 🔹 **ヒストグラムとクエリ最適化のポイント**
✅ **MCV の影響**
- 高頻度な値は MCV に登録され、適切なスキャン方法が選択される
- **MCV に登録されると、特定の値のカーディナリティ推定が向上**

✅ **等深度ヒストグラムの影響**
- 等深度ヒストグラムが有効な場合、カラム値の分布に応じて適切な推定が可能
- MCV に登録されなかった値の選択率を補正

✅ **correlation の影響**
- **1.0 に近い場合**：物理順とカラム順が一致し、Index Scan が効率的
- **0 に近い場合**：ランダムアクセスが多くなり、Seq Scan や Bitmap Index Scan が選ばれる
- **-1 に近い場合**：逆順インデックススキャンが有効になるケースも

---

### 📌 **学びと実践**
💡 **統計情報を確認し、適切なヒストグラムを活用することで、SQL の最適化が可能！**  
💡 **ANALYZE を適宜実行し、最新の統計情報を維持することが重要！**  
💡 **クエリのパフォーマンスが想定と異なる場合、`pg_stats` でヒストグラムや MCV の影響をチェックする！**  

---