Pythonで実装して理解する RDBパフォーマンスチューニング入門 ─ フルスキャンとインデックスの仕組み

株式会社ブレインパッドプロダクトユニットでRtoaster GenAIの開発をしている依田です。
今回はRDB（リレーショナルデータベース）のパフォーマンスチューニングの基礎として、インデックスの仕組みと、カーディナリティ（値のバリエーションの多さ）がクエリ性能に与える影響について解説します。

はじめに

データベースを触り始めてしばらくすると、こんな経験をすることがあります。

「なんかこのクエリ、遅くない？」
「インデックス貼ればいいって聞いたけど……どこに貼るの？」
「インデックス貼ったのになんで速くならないんだ！」

インデックスは、正しく理解すれば強力な武器になります。しかし「なんとなく貼ればいい」という理解のままだと、効果がなかったり、むしろ状況が悪化したりすることもあります。

この記事では、以下のことをPythonの実装を通じて直感的に理解することを目指します。

• テーブルフルスキャン（全件検索）がなぜ遅いのか
• B-treeインデックスの構造と、なぜ検索が速いのか
• カーディナリティが低いと、インデックスがあっても遅くなる理由

対象読者

この記事は以下の方を対象としています。

• SQLを学び始めた駆け出しエンジニア
• インデックスという言葉は知っているが、仕組みがよくわからない方
• 「インデックスを貼れ」と言われたことはあるが、なぜかを説明できない方
• データベースの仕組みを体系的に学びたい方

前提知識

この記事を理解するには、計算量オーダー（ビッグ・オー記法）の基礎知識が必要です。以下の記事で解説していますので、不安な方は先にお読みください。

特に以下の内容を理解していることが前提となります。

• 線形探索：$O(n)$
• 二分探索：$O(\log n)$

Pythonコードについて

本記事のPythonコードは以下の方針で書いています。

• 外部ライブラリは使用しない（標準ライブラリのみ）
• 型アノテーションを必ず明記する（list[int] や str など）
• RDBMSの実際の実装を忠実に再現するものではなく、概念を理解するためのシミュレーションです

本記事は初学者向けのため一部表現を平易にしています。実際のRDBMSの実装は、ここで説明する内容よりも複雑で最適化されています。

それでは、RDBのパフォーマンスチューニングの世界へ一緒に踏み出しましょう。

テーブルフルスキャン - 先頭から全件チェックする

インデックスのないテーブルからレコードを検索するとき、RDBはテーブルフルスキャン（Full Table Scan）を行います。読んで字のごとく、テーブルの先頭から末尾まで全件チェックする方法です。

これは、計算量オーダーの記事で紹介した線形探索そのものです。

テーブル: users（10万件）

id	name	birthday	prefecture
1	田中 太郎	1990-04-01	東京都
2	佐藤 花子	1985-07-15	大阪府
3	鈴木 次郎	1990-04-01	北海道
...	...	...	...
100000	山田 一郎	1995-11-30	東京都

WHERE birthday = '1990-04-01' を探す場合、同じ誕生日の人が何人いるかわからないため、先頭から全件確認が必要になります。

Pythonで実装するフルスキャン

Pythonで表を辞書（dict）のリスト（list）として表現し、フルスキャンを実装してみましょう。

./full_scan.py

def full_table_scan(
    table: list[dict[str, str | int]],
    column: str,
    value: str | int
) -> list[dict[str, str | int]]:
    """
    テーブルフルスキャン：先頭から全件チェックして条件に一致するレコードを返す。
    計算量：O(n)
    """
    results: list[dict[str, str | int]] = []
    for record in table:          # 先頭から1件ずつ確認
        if record[column] == value:
            results.append(record)
    return results

試しに動かしてみましょう。

./full_scan.py

# テーブルを作成（簡略化のため5件）
users: list[dict[str, str | int]] = [
    {"id": 1, "name": "田中 太郎", "birthday": "1990-04-01", "prefecture": "東京都"},
    {"id": 2, "name": "佐藤 花子", "birthday": "1985-07-15", "prefecture": "大阪府"},
    {"id": 3, "name": "鈴木 次郎", "birthday": "1990-04-01", "prefecture": "北海道"},  # 田中と同じ誕生日
    {"id": 4, "name": "高橋 三郎", "birthday": "1992-12-24", "prefecture": "東京都"},
    {"id": 5, "name": "伊藤 四郎", "birthday": "1988-03-08", "prefecture": "福岡県"},
]

# birthday = "1990-04-01" を検索（田中・鈴木の2件が一致）
result: list[dict[str, str | int]] = full_table_scan(users, "birthday", "1990-04-01")
print(result)
# → [{"id": 1, "name": "田中 太郎", ...}, {"id": 3, "name": "鈴木 次郎", ...}]

件数が5件なら一瞬で終わります。しかし100万件のテーブルに対して同じことをすると、最悪100万回のチェックが必要です。

何件チェックしているか数えてみる

フルスキャンがどれほどのチェックをしているか、カウンターを追加して確認してみましょう。

./full_scan.py

def full_table_scan_with_count(
    table: list[dict[str, str | int]],
    column: str,
    value: str | int
) -> tuple[list[dict[str, str | int]], int]:
    """
    フルスキャン（チェック回数付き）。
    戻り値: (検索結果のリスト, チェック回数)
    """
    results: list[dict[str, str | int]] = []
    check_count: int = 0

    for record in table:
        check_count += 1          # チェック回数をカウント
        if record[column] == value:
            results.append(record)

    return results, check_count

./full_scan.py

import datetime
import random

# 10万件のテーブルを生成（誕生日はランダムに割り当て）
start_date: datetime.date = datetime.date(1980, 1, 1)
date_range: int = 365 * 40  # 1980〜2019年の40年分

large_table: list[dict[str, str | int]] = []
for i in range(1, 100_001):
    delta: int = random.randint(0, date_range - 1)
    birthday: str = (start_date + datetime.timedelta(days=delta)).isoformat()
    large_table.append({"id": i, "name": f"ユーザー{i}", "birthday": birthday})

# birthday = "1990-04-01" を検索
results, count = full_table_scan_with_count(large_table, "birthday", "1990-04-01")
print(f"チェック回数: {count:,}回")   # → チェック回数: 100,000回
print(f"検索結果: {len(results)}件")  # → 検索結果: 約7件（ランダム生成のため変動あり）

同じ誕生日の人が何人いるかは事前にわからないため、フルスキャンは末尾まで全件チェックします¹。

インデックス - 高速検索の仕組み

本の巻末にある「索引」を思い出してください。「データベース」という言葉を調べたいとき、本の最初から全ページをめくる人はいません。索引で「データベース → 42ページ」と確認してから、42ページを直接開きます。

データベースのインデックスも同じ発想です。あらかじめ検索キーと行の場所を対応づけておき、全件チェックせずに目的のレコードへたどり着ける仕組みです。

B-treeの構造

RDBで最もよく使われるインデックスがB-treeインデックス（Balanced Tree）です。「Balanced（バランスの取れた）」という名前の通り、木構造²の高さが偏らないよう自動的に調整されます。

B-treeの主な特徴は以下の通りです。

• 1ノードに複数のキーを格納できる（多分木）: 1ノードに $n$ 個のキーがあれば子ノードは $n+1$ 個になります
• すべての葉が同じ深さ: どのキーを探しても、常に同じステップ数で到達できます
• 自動バランス調整: データの挿入・削除に伴い、ノードの分割・統合によって高さが均等に保たれます

RDBMSでは1ノードが1ディスクページ（通常数KB〜数十KB）に対応しており、1ノードに数百〜数千のキーを格納します。分岐数 $m$ が非常に大きいため $\log_m n$ で検索でき、数百万件のデータでも木の高さが数段に収まります。

内部ノードには複数のキー値（区切り値） が格納されており、キーの範囲に応じて対応する子ノードへ降りていきます。葉ノードはテーブルの行へのポインタ（レコードの格納位置）を持ちます。

B-treeでの検索プロセス

例として、birthday = '1990-04-01' を探してみましょう。

1. 根ノード [1988-03-08 | 1992-12-24] を確認
   "1990-04-01" は "1988-03-08" 以上かつ "1992-12-24" 未満なので、中央の葉ノードへ
2. 葉ノード [1988-03-08 | 1990-04-01] を確認
   "1990-04-01" が見つかった！田中 太郎・鈴木 次郎のポインタを取得

2ステップで見つかりました。フルスキャンなら最悪7ステップ（全件チェック）必要なところを、木の高さ分（この例では2段）だけで済みます。1ノードに複数のキーを持つ多分木のため、同じ7件でも二分木より浅い階層で到達できます。

Pythonで実装する簡易版インデックス

実際のB-treeは実装が複雑なため、ここでは 「ソート済み配列への二分探索」 を実装します。これはB-treeとは別のデータ構造ですが、$\log_2 n$ での検索という性質を体験するためのシミュレーションです。実際のB-treeは $\log_m n$（$m$ は数百〜数千）なので、この実装よりもさらに浅い階層で検索できます。

以下の実装はB-treeではなく、ソート済み配列＋二分探索による簡易シミュレーションです。B-treeの概念（多分木・自動バランス調整）を再現したものではありません。

./simple_index.py

class SortedArrayIndex:
    """
    ソート済み配列＋二分探索による簡易インデックスのシミュレーション。
    実際のB-treeとは異なり、(キー値, 行番号) のリストをソートして二分探索する。
    計算量はO(log n)で、インデックス検索の本質を体験できる。
    """

    def __init__(self) -> None:
        # インデックスエントリのリスト: (キー値, 行番号) のタプル
        self.entries: list[tuple[str, int]] = []
        self.is_built: bool = False

    def build(self, table: list[dict[str, str | int]], column: str) -> None:
        """
        テーブルからインデックスを構築する。
        (キー値, 行番号) のリストを作り、キー値でソートする。
        """
        self.entries = [
            (str(record[column]), row_num)
            for row_num, record in enumerate(table)
        ]
        self.entries.sort(key=lambda entry: entry[0])  # キー値でソート
        self.is_built = True

    def search(self, value: str) -> list[int]:
        """
        二分探索でキー値に一致する行番号のリストを返す。
        計算量：O(log n)
        """
        if not self.is_built:
            raise RuntimeError("インデックスがまだ構築されていません")

        row_numbers: list[int] = []
        left: int = 0
        right: int = len(self.entries) - 1

        # 二分探索で最初の一致位置を探す
        first_match: int = -1
        while left <= right:
            mid: int = (left + right) // 2
            mid_key: str = self.entries[mid][0]

            if mid_key == value:
                first_match = mid
                right = mid - 1        # さらに左を探して最初の一致を確定
            elif mid_key < value:
                left = mid + 1
            else:
                right = mid - 1

        if first_match == -1:
            return []                  # 一致なし

        # 一致するエントリをすべて収集
        idx: int = first_match
        while idx < len(self.entries) and self.entries[idx][0] == value:
            row_numbers.append(self.entries[idx][1])
            idx += 1

        return row_numbers

実際に使ってみましょう。

./simple_index.py

# テーブルを作成
users: list[dict[str, str | int]] = [
    {"id": 1, "name": "田中 太郎", "birthday": "1990-04-01", "prefecture": "東京都"},
    {"id": 2, "name": "佐藤 花子", "birthday": "1985-07-15", "prefecture": "大阪府"},
    {"id": 3, "name": "鈴木 次郎", "birthday": "1990-04-01", "prefecture": "北海道"},
    {"id": 4, "name": "高橋 三郎", "birthday": "1992-12-24", "prefecture": "東京都"},
    {"id": 5, "name": "伊藤 四郎", "birthday": "1988-03-08", "prefecture": "福岡県"},
]

# birthday列にインデックスを構築（ソート済み配列として内部管理）
index: SortedArrayIndex = SortedArrayIndex()
index.build(users, "birthday")

# インデックスを使って birthday = "1990-04-01" を検索（田中・鈴木の2件）
row_numbers: list[int] = index.search("1990-04-01")
for row_num in row_numbers:
    print(f"行番号={row_num}, レコード: {users[row_num]}")
# → 行番号=0, レコード: {'id': 1, 'name': '田中 太郎', 'birthday': '1990-04-01', ...}
# → 行番号=2, レコード: {'id': 3, 'name': '鈴木 次郎', 'birthday': '1990-04-01', ...}

インデックスによる検索高速化を数値で確認する

フルスキャンとインデックス検索のチェック回数を比較してみましょう。

./comparison.py

import math

def count_btree_steps(n: int) -> int:
    """
    n件のデータに対するインデックス検索のステップ数（概算）を返す。
    ソート済み配列への二分探索を想定しており、log₂(n) に比例する。
    実際のB-treeは分岐数 m が数百〜数千のため、さらに少ないステップで到達できる。
    """
    if n <= 1:
        return 1
    return math.ceil(math.log2(n))

./comparison.py

# データ件数ごとの比較
data_sizes: list[int] = [1_000, 10_000, 100_000, 1_000_000]

print(f"{'件数':>10} | {'フルスキャン':>12} | {'B-tree':>8} | {'差（倍）':>8}")
print("-" * 50)

for n in data_sizes:
    full_scan_steps: int = n
    btree_steps: int = count_btree_steps(n)
    ratio: float = full_scan_steps / btree_steps
    print(f"{n:>10,} | {full_scan_steps:>12,} | {btree_steps:>8} | {ratio:>8,.0f}倍")

件数	フルスキャン	インデックス	差（倍）
1,000	1,000	10	100倍
10,000	10,000	14	714倍
100,000	100,000	17	5,882倍
1,000,000	1,000,000	20	50,000倍

データが100万件になると、フルスキャンは最悪100万回のチェックが必要ですが、実装したインデックスならたったの20回で済みます。実際のB-treeインデックスは、さらに少ない回数のチェックで済みます。

インデックスが効く条件

ここで重要なことをおさえておきましょう。インデックスが効果を発揮するのは、検索結果が全体のごく一部の場合です。(部分的に使うだけでなく、全体を走査する使い方もありますが、後のセクションで説明します)

• WHERE birthday = '1990-04-01' → 全体の約0.03%（約274件）→ インデックスが大幅に有利
• WHERE gender = 'M' → 全体の約55%（55万件）→ インデックスの効果は？

gender のような列でのフィルタリングは、次のセクションで詳しく解説します。

後の説明のため、 gender には多少偏りがある前提としています。

では、どれくらい絞り込めればインデックスは有効なのでしょうか？ その答えを左右するのが「カーディナリティ」です。

カーディナリティ - インデックスが裏目に出るケース

カーディナリティ（Cardinality）とは、ある列に含まれる値の種類の数のことです。

100万件の users テーブルで考えると、列ごとにカーディナリティは大きく異なります。

• id 列：1, 2, 3, … 1,000,000（100万種類）→ 高カーディナリティ
• prefecture 列：東京都, 大阪府, … 北海道（47種類）→ 中程度のカーディナリティ
• gender 列：M, F（2種類）→ 低カーディナリティ

カーディナリティは、インデックスの効果に大きく影響します。

なぜ低カーディナリティだとインデックスが遅くなるのか

100万件の users テーブルで、gender = 'M' を検索するケースで考えてみましょう。

インデックスを使って gender = 'M' を検索するとき

1. B-treeインデックスで 'M' の位置を特定
   $O(\log n)$ で高速
2. インデックスエントリを順に走査して 'M' の行番号をすべて収集
   gender = 'M' は実データに偏りがあり全体の約55%、つまり55万エントリを走査
3. 収集した行番号を使って、テーブルの行を1件ずつ取得
   55万行の取得が発生

ここが落とし穴です。「インデックス＝速い」と思っていると、ここで必ずつまずきます。インデックス経由ではステップ2（55万エントリ）＋ステップ3（55万行）＝合計110万件超の処理が必要になります。テーブルを先頭から順番に全件スキャンするだけなら100万件の処理で済むため、インデックスを使うほうがむしろ処理量が多いという逆転現象が起きるのです。

Pythonでカーディナリティの影響を確認する

インデックスを使った場合と使わない場合で、何件のデータへのアクセスが必要かを計算してみましょう。

./cardinality.py

def estimate_index_cost(
    total_rows: int,
    matching_rows: int
) -> dict[str, int | float]:
    """
    インデックス検索のコスト（処理件数）を推定する。

    Args:
        total_rows: テーブルの総行数
        matching_rows: 検索条件に一致する行数

    Returns:
        各方式のコスト推定値
    """
    import math

    # B-treeで最初の一致位置を見つけるコスト
    btree_traversal: int = math.ceil(math.log2(total_rows))

    # インデックスエントリのスキャンコスト（一致件数分）
    index_scan_cost: int = matching_rows

    # テーブル行の取得コスト（一致件数分）
    table_fetch_cost: int = matching_rows

    # インデックス経由の合計コスト
    index_total_cost: int = btree_traversal + index_scan_cost + table_fetch_cost

    # フルスキャンのコスト（全件を順次読み込み）
    full_scan_cost: int = total_rows

    return {
        "全行数": total_rows,
        "一致行数": matching_rows,
        "一致率(%)": round(matching_rows / total_rows * 100, 1),
        "インデックス経由コスト": index_total_cost,
        "フルスキャンコスト": full_scan_cost,
        "インデックスが有利か": index_total_cost < full_scan_cost,
    }

./cardinality.py

total: int = 1_000_000  # 100万件のテーブル

# カーディナリティ別に比較
scenarios: list[tuple[str, int]] = [
    ("id（1件一致）",                  1),
    ("birthday 特定日（約274件）",   274),   # 100万人 ÷ 365日 ≈ 274人
    ("prefecture 東京都（30%）",  300_000),
    ("gender M（55%）",           550_000),   # 実データには偏りがあり約55%と仮定
]

for label, matching in scenarios:
    cost: dict[str, int | float] = estimate_index_cost(total, matching)
    is_index_better: str = "◎ インデックスが有利" if cost["インデックスが有利か"] else "✕ フルスキャンが有利"
    print(
        f"[{label}] "
        f"一致率={cost['一致率(%)']:>5}% | "
        f"インデックスコスト={cost['インデックス経由コスト']:>10,} | "
        f"フルスキャンコスト={cost['フルスキャンコスト']:>10,} | "
        f"{is_index_better}"
    )
# [id（1件一致）]                 一致率=  0.0% | インデックスコスト=        22 | フルスキャンコスト= 1,000,000 | ◎ インデックスが有利
# [birthday 特定日（約274件）]    一致率=  0.0% | インデックスコスト=       568 | フルスキャンコスト= 1,000,000 | ◎ インデックスが有利
# [prefecture 東京都（30%）]      一致率= 30.0% | インデックスコスト=   600,020 | フルスキャンコスト= 1,000,000 | ◎ インデックスが有利
# [gender M（55%）]               一致率= 55.0% | インデックスコスト= 1,100,020 | フルスキャンコスト= 1,000,000 | ✕ フルスキャンが有利

一致件数が増えるほどインデックス経由のコストも増え、一致率が約50%を超えるとフルスキャンの方が処理量が少なくなることが確認できます。

インデックスフルスキャンとは

少し発展的な内容ですが、カーディナリティの話と合わせて知っておきたいのがインデックスフルスキャン（Index Full Scan）です。

通常のインデックス検索（インデックスレンジスキャン）は、B-treeをたどって目的の値の範囲だけを読みます。一方、インデックスフルスキャンはインデックスを先頭から末尾まで全件走査する方法です。

インデックスフルスキャンは全エントリを走査した上でテーブルのデータにもアクセスするため、一致するデータが多いほど処理量はインデックスレンジスキャンより増えます。一方、インデックスはテーブル本体より小さいため、「全件読む」場合でもテーブルフルスキャンより有利になるケースがあります。

採用されるケース1：ORDER BY を伴うソート

SELECT birthday FROM users ORDER BY birthday;

• テーブルフルスキャンの場合：全件読み込み後に birthday でソート処理が必要
• インデックスフルスキャンの場合：インデックスはすでに birthday 順に並んでいるため、ソート処理が不要。birthday 列のみを取得する場合はテーブル本体へのアクセスも省略できる

ソート処理のコストを節約できるため、オプティマイザがインデックスフルスキャンを選ぶことがあります。

採用されるケース2：ORDER BY なしの集計クエリ

SELECT COUNT(*) FROM users;
SELECT MAX(birthday) FROM users;

COUNT(*) はインデックスのエントリ数を数えるだけでよく、MAX(birthday) はインデックスの末尾を1件読むだけで済みます。いずれもテーブル本体へのアクセスが不要なため、テーブルフルスキャンより処理量が少なくなり、インデックスフルスキャンが選ばれます。

インデックスフルスキャンで性能が悪化するケース

ケース1の例と比べて、取得する列を birthday から * に変えただけで状況が一変します。

-- birthday 列のみを取得（テーブルアクセス不要 → インデックスフルスキャンが有利）
SELECT birthday FROM users ORDER BY birthday;

-- すべての列を取得（テーブルアクセスが全行分必要 → インデックスフルスキャンが不利）
SELECT * FROM users ORDER BY birthday;

SELECT * の場合、インデックスに格納されていない name・gender・prefecture を取得するためにテーブル本体へのアクセスが全行分必要になります。その結果、処理は次のようになります。

方式	処理内容	処理量
インデックスフルスキャン	インデックス全件走査 ＋ テーブル行を全行取得	2N
テーブルフルスキャン	テーブル全件読み込み ＋ ソート処理	N ＋ ソート

インデックスフルスキャンのコストが 2N になるのに対し、テーブルフルスキャン＋ソートの合計コストが 2N を下回る場合、テーブルフルスキャンの方が速いという逆転が起きます。

ここでは説明のため「1行＝1コスト」として単純化しています。
実際のコスト計算には以下の要因が絡みます。

• ページ単位のI/O：DBはレコードを1件ずつでなく、ページ（例：8KB）単位でディスクを読み込む
• ランダムI/O vs シーケンシャルI/O：インデックスフルスキャン後のテーブルアクセスはランダムI/Oが発生しやすく、テーブルフルスキャンの連続読み込み（シーケンシャルI/O）より遅くなりやすい
• バッファキャッシュ：頻繁にアクセスされるページはメモリ上にキャッシュされており、ディスクI/Oが発生しない場合もある

そのため、単純な 2N vs N の比較にはなりません。

テーブルフルスキャンが選ばれるケース

一方、低カーディナリティの列（例：gender）に対して WHERE gender = 'M' と条件検索する場合は話が異なります。インデックスのエントリを大量にスキャン（約55%）した上でテーブル行の取得も必要になり、テーブルフルスキャンよりコストが高くなります。

RDBMSのクエリオプティマイザ³は、このコストを計算した上で、「インデックスより全件スキャンの方が速い」と判断したとき、インデックスが存在していても使わない選択をすることがあります。

./cardinality.py

def simulate_optimizer_decision(
    total_rows: int,
    matching_rows: int,
) -> str:
    """
    クエリオプティマイザの判断を簡易シミュレートする。
    インデックスとフルスキャンのコストを比較し、選択する方式を返す。
    """
    import math

    btree_traversal: int = math.ceil(math.log2(total_rows))
    # インデックスエントリのスキャン + テーブル行の取得
    index_cost: int = btree_traversal + matching_rows * 2
    full_scan_cost: int = total_rows

    if index_cost < full_scan_cost:
        return f"インデックス使用（コスト比: {index_cost:,} vs {full_scan_cost:,}）"
    else:
        return f"フルスキャン採用（コスト比: {index_cost:,} vs {full_scan_cost:,}）"

./cardinality.py

total: int = 1_000_000

# 一致率別のオプティマイザ判断
match_ratios: list[float] = [0.001, 0.01, 0.10, 0.30, 0.49, 0.50]

print(f"{'一致率':>6} | オプティマイザの判断")
print("-" * 70)

for ratio in match_ratios:
    matching: int = int(total * ratio)
    decision: str = simulate_optimizer_decision(total, matching)
    print(f"{ratio*100:>5.1f}% | {decision}")
#  一致率 | オプティマイザの判断
# ----------------------------------------------------------------------
#   0.1% | インデックス使用（コスト比:     2,020 vs 1,000,000）
#   1.0% | インデックス使用（コスト比:    20,020 vs 1,000,000）
#  10.0% | インデックス使用（コスト比:   200,020 vs 1,000,000）
#  30.0% | インデックス使用（コスト比:   600,020 vs 1,000,000）
#  49.0% | インデックス使用（コスト比:   980,020 vs 1,000,000）
#  50.0% | フルスキャン採用（コスト比: 1,000,020 vs 1,000,000）

上記のシミュレーションは概念理解のために簡略化しています。実際の閾値は以下の要因によって変動します。（一例）

• テーブルサイズとインデックスサイズ：小テーブルはインデックスより全件スキャンの方が速い場合がある
• バッファキャッシュの状況：テーブルがメモリ上にキャッシュされているとシーケンシャルスキャンが高速になる

そのため、実務では必ず EXPLAIN コマンドで実際の実行計画を確認することが重要です。

このシミュレーションでは一致率が約50%でオプティマイザの判断が切り替わります。実際のRDBMSでは固定の閾値は存在せず、コストベースで動的に判断されます。一致率が高くなるほどフルスキャンが選ばれやすく、Oracle の公式ドキュメントでは「従業員の80%がマネージャーの場合、フルテーブルスキャンを選ぶ可能性がある」という例示があります⁴。

まとめ

本記事を通じて、以下のことを学びました。

項目	内容
フルテーブルスキャン	先頭から全件チェック。計算量 $O(n)$ で件数に比例して遅くなる
B-treeインデックス	バランスの取れた木構造。計算量 $O(\log n)$ で高速に目的のレコードへたどり着ける
インデックスが有効な場面	高カーディナリティ（id、email など）の列、一致率が低い検索条件
インデックスが逆効果な場面	低カーディナリティ（gender など）の列、一致率が高い検索条件
クエリオプティマイザ	コストを自動計算し、インデックスとフルスキャンを適切に選択する

「インデックスがあれば速い」というわけではなく、「使い方とデータ分布による」という点が重要です。

実際のパフォーマンスチューニングで使えるチェックリスト

1. EXPLAIN / EXPLAIN ANALYZE でクエリ実行計画を確認する

   • Seq Scan（フルスキャン）か Index Scan か確認する
   • 想定外のフルスキャンが発生していないか確認する
   • EXPLAIN ANALYZE は実際にクエリを実行し、actual time や rows を出力するため、推定と実際のズレも把握できる（UPDATE / DELETE では BEGIN; EXPLAIN ANALYZE ...; ROLLBACK; でデータを変えずに確認できる）

2. インデックスを貼る前にカーディナリティを確認する

   • SELECT COUNT(DISTINCT column) FROM table; で種類数を確認する
   • 種類数が少ない列へのインデックスは効果が薄いことを念頭に置く

3. 複合インデックスを検討する

   • gender（低カーディナリティ）+ prefecture（中カーディナリティ）など、組み合わせることで絞り込み効果が高まる場合がある

4. カバリングインデックスを活用する

   • SELECT する列がすべてインデックスに含まれている場合、テーブルへのアクセスを省略できる（テーブル行をフェッチするステップ3が不要になる）
   • クエリのボトルネックになっている場合は、インデックス設計を見直す選択肢として知っておくとよい

データベースのパフォーマンスチューニングは奥が深いですが、今回学んだ「フルスキャン vs インデックス」「カーディナリティ」という基礎をおさえておくと、多くの問題の原因と対策が見えてくるはずです。

1. フルスキャンは一致するレコードを見つけても、まだ他に一致するレコードが存在する可能性があるため、最後まで全件チェックを続けます。誕生日が同じ人が何人いるかを事前に知る手段がないからです。 ↩

2. 木構造（tree structure）：データをノード（節）と枝の形で表したデータ構造。根（root）から葉（leaf）に向かって枝分かれしていく。 ↩

3. クエリオプティマイザ（Query Optimizer）：SQLクエリを実行する前に、最もコストが低い実行計画を自動的に選択するRDBMSの内部機能。インデックスの利用有無も自動的に判断する。 ↩

4. 公式ドキュメントに固定の閾値の記載はありません。Oracle Database 19c のクエリオプティマイザ概念に80%の例示があります。PostgreSQL では random_page_cost（デフォルト4.0）と seq_page_cost（デフォルト1.0）のコスト比をもとに動的に判断します（PostgreSQL 公式ドキュメント参照）。 ↩