Published on

DRFのインデックスについて(PodDairy)

Authors
  • Name
    Twitter

結論

REST APIのエンドポイントでは、IDを利用してリソースを指定するよう設計するのが一般的。理解のため、インデックスについて深掘る。これは開発者側で日記内容を分析する際の検索時に考慮したほうがいいかもしれない。

  • 結論、B-Treeインデックスを使うと、検索対象が含まれる範囲を素早く絞り込める（なおこれがデフォルトなので考えなくていい）。絞り込む範囲だけを探索するので、非常に効率的。
  • B-Treeは「効率よくデータを検索するために設計されたデータ構造」。目次（インデックス）は階層的に整理されているため、部分的に探索するだけで目的のデータに辿り着ける。
  • 基本的にフルテーブルスキャンはないが、文字列検索する際に、%john%といった部分一致で検索しようとすると、文字列の先頭部分が固定されていないため、データベースはインデックス（B-Treeなど）を使えず、フルテーブルスキャンが発生する。
  • フルテキスト検索（Full-Text Search）という文字列データ（通常は大量のテキスト）の中で効率的に部分一致や高度な検索を行う仕組みがある。
    • フルテキストインデックスという特別なデータ構造を使い、テキストのどの部分に特定の単語やフレーズが含まれているかを効率的に検索可能。尚、Djangoでは、CharFieldに対し、SearchVectorを使えばできるらしい
    • 通常の検索用とでは不要のはず
    • フルテキストインデックスはテキストをトークン化して管理するため、データの挿入や更新時のコストが高く、高頻度の更新がある場合、パフォーマンスが低下する可能性あり。
    • 記事タイトルや本文内での部分一致検索、ECサイトの商品検索、ドキュメント検索システム、などで使用。頻繁なデータ更新が必要な場合や単純なIDやキー検索では不要。
    • 検索対象がテキストデータ（ブログ記事、商品説明、ドキュメントなど）,複雑な検索条件が必要（部分一致、AND/OR条件など）,検索がシステムの中心的な役割

インデックスを設定すると検索や結合時のパフォーマンスが向上する理由

インデックスは、データの「検索用の目次」のような役割を果たす。目次を使うことで、必要なデータの位置を効率的に見つけられるため、パフォーマンスが向上。

例え: 本の目次を使う場合と使わない場合

  • 目次なし（インデックスなし）: 本の中から「Python」という単語を探すために、1ページずつすべてのページを順番にチェックする。
  • 目次あり（インデックスあり）: 目次を使って「Python」の項目がp.50にあることを確認し、すぐに該当ページを開く。

実際のデータベースでの動き

  • インデックスなし:
    データベースは、テーブル内の全行を順番にスキャンして検索（フルテーブルスキャン）。
  • インデックスあり:
    データベースは、インデックス（目次）を参照して必要な行を特定。テーブル全体をスキャンせずに済む。
# 非効率な方法
episodes = Episode.objects.all()
for episode in episodes:
    podcast = Podcast.objects.get(id=episode.podcast_id)  # 毎回クエリが発行される
    print(f"Episode: {episode.title}, Podcast: {podcast.title}")
  • N+1問題が発生します（Episodeの件数Nに応じてN回の追加クエリが発行される）。
  • データベースへのアクセス回数が多くなり、パフォーマンスが低下。
# 効率的な方法 リレーションとselect_relatedの活用
episodes = Episode.objects.select_related('podcast').all()
for episode in episodes:
    print(f"Episode: {episode.title}, Podcast: {episode.podcast.title}")
  • select_relatedを使うことで、EpisodeとPodcastを1回の結合クエリで取得。
  • データベースへのアクセス回数が1回に削減。

Djangoでのインデックスについて

Djangoは外部キーや一意制約に自動的にインデックスを作成

  • 外部キー: 外部キーを設定すると、そのカラムにインデックスが自動的に作成される。
  • 一意制約: ユニーク制約を設定すると、自動的にインデックスが作成される。

開発者が気にする必要がある場合

  1. カスタムインデックスが必要なケース
    特定のクエリ（例えば、WHERE条件が複雑で頻繁に使われる）が遅い場合、カスタムインデックスを作成する必要がある。
    class MyModel(models.Model):
    my_field = models.CharField(max_length=255)

    class Meta:
        indexes = [
            models.Index(fields=['my_field'], name='my_field_idx')
        ]
  2. 大量データの場合
    インデックスが多すぎると、データ挿入や更新が遅くなる場合がある（インデックスの更新が必要なため）。

1. 作成されるデータベース構造（PostgreSQLの例）

Djangoが上記のモデルをデータベースに適用すると、以下のSQLが実行される。

CREATE TABLE app_user (
    id SERIAL PRIMARY KEY,
    username VARCHAR(100) NOT NULL UNIQUE,
    email VARCHAR(254) NOT NULL UNIQUE,
    created_at TIMESTAMP WITHOUT TIME ZONE NOT NULL
);

-- インデックス（ユニーク制約のために自動生成）
CREATE UNIQUE INDEX app_user_username_key ON app_user(username);
CREATE UNIQUE INDEX app_user_email_key ON app_user(email);

2. 自動的に作成されるインデックス

下記、PostgreSQLがユニーク制約（Unique Constraint）を実現するために自動的に作成するインデックスの名前。
データベースにデータを挿入または更新する際に、usernameやemailの値が一意であることを保証する。

  • app_user_username_key: username列に対するユニーク制約のインデックス。
  • app_user_email_key: email列に対するユニーク制約のインデックス。

これらのインデックスは、データベースに次のような効果をもたらす：

  • ユニーク性の検証（usernameやemailの重複を防ぐ）。
  • クエリ（検索）パフォーマンスの向上：
    SELECT * FROM app_user WHERE username = 'example_username';
  • データベースはapp_user_username_keyインデックスを利用して、usernameにjohn_doeがすでに存在するかをチェック
  • usernameがすでに存在する場合、エラーを発生

3. ユニーク制約を持たないフィールドとの比較

例えば、以下のフィールドにはインデックスが作成されない。

class Post(models.Model):
    title = models.CharField(max_length=200)  # デフォルトではユニーク制約なし
    content = models.TextField()

これに対応するSQL：

CREATE TABLE app_post (
    id SERIAL PRIMARY KEY,
    title VARCHAR(200) NOT NULL,
    content TEXT NOT NULL
);

-- インデックスは自動的には作成されない

この場合、titleフィールドに対する検索やフィルタリングが発生すると、テーブル全体をスキャン（フルテーブルスキャン）する可能性がある。

4. ユニーク制約を持つ場合のクエリの高速化効果

インデックスがない場合、次のようなクエリは全行をスキャンする（フルテーブルスキャン）。

SELECT * FROM app_user WHERE username = 'example_username';

インデックスがある場合、データベースはインデックスを使って素早く該当行を見つける。

  • フルテーブルスキャン: 全行を逐一チェック → 時間がかかる。
  • インデックススキャン: インデックスを利用して該当する行を特定 → 時間短縮。

**データベースはどの行に該当するデータがあるかを事前に把握していないため、すべての行を順番に確認する必要がある。**本の目次がないと、特定のトピックがどのページにあるか分からないのと同じ。

勉強

DjangoでのID生成について

Djangoでは特別な設定をしない限り、各モデルにプライマリキー（ID）が自動的に追加される。

  • プライマリキーはデフォルトでidという名前の整数型フィールドで、自動インクリメントされる仕組みになっている。
  • 開発者がidをカスタマイズしない限り、自動生成されるので意識せず使える

木構造とハッシュ構造について

データベースで一般的なインデックス構造

  • 木構造（B-Tree）:

    • 多くのデータベース（PostgreSQLやMySQLなど）でデフォルトのインデックス構造。
    • データを階層的に管理するため、大量データでも高速な検索、挿入、削除が可能。
    • 範囲検索（BETWEENや>, <など）にも適している。
    • Djangoでunique=Trueや外部キーを指定すると、このB-Treeが自動的に作成される。

  • ハッシュ構造:

    • キーと値のペアでデータを管理するシンプルな構造。
    • 一致検索（=）は高速だが、範囲検索やソートには適さない。
    • PostgreSQLなどでは、特定のカラムの用途に応じて明示的に指定して使用。

Djangoとデータベースでの違い

  • Djangoではインデックスの詳細（B-TreeかHashか）を指定しない限り、データベースのデフォルト（多くの場合B-Tree）が使用される。

自分のデータベースでインデックスの構造や仕組みを理解する方法

1. PostgreSQLでのインデックス確認

  • インデックスの種類を確認するコマンド:

    \d tablename;  -- テーブル構造を確認

    出力例：

                                    Table "public.app_user"
 Column    |          Type          | Collation | Nullable | Default
-----------+------------------------+-----------+----------+---------
 id        | integer                |           | not null | nextval('app_user_id_seq'::regclass)
 username  | character varying(100) |           | not null |
Indexes:
    "app_user_pkey" PRIMARY KEY, btree (id)
    "app_user_username_key" UNIQUE, btree (username)

  • インデックスの詳細を確認するコマンド:

    SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'app_user';

    出力例：

     indexname                | indexdef
--------------------------+--------------------------------------------
 app_user_pkey            | CREATE UNIQUE INDEX app_user_pkey ON app_user USING btree (id)
 app_user_username_key    | CREATE UNIQUE INDEX app_user_username_key ON app_user USING btree (username)

2. インデックスの種類を調査する

  • B-Treeインデックスの特性を試す:
    • 範囲検索（BETWEENや>）を含むクエリを実行してパフォーマンスを測定。
  • Hashインデックスを作成して比較:
    CREATE INDEX username_hash_idx ON app_user USING hash (username);

3. 実行計画を確認する

クエリがインデックスを利用しているか確認するには、実行計画（EXPLAIN）を使う。

  • クエリの実行計画を見る:

    EXPLAIN SELECT * FROM app_user WHERE username = 'john_doe';

  • 出力例（インデックスを利用している場合）：

    Index Scan using app_user_username_key on app_user  (cost=0.13..8.15 rows=1 width=72)

  • 出力例（フルテーブルスキャンの場合）：

    Seq Scan on app_user  (cost=0.00..35.50 rows=5 width=72)

Djangoで木構造やインデックスを調べる方法

DjangoではQuerySetの実行SQLを確認することで、インデックスの利用を確認。

  1. デバッグログでSQLを確認:

    from django.db import connection

# 実行されるSQLを確認
User.objects.filter(username='john_doe')
print(connection.queries)

  2. explain()を使う（Django Debug Toolbarでも可能）:

    qs = User.objects.filter(username='john_doe')
print(qs.explain())

出力例（インデックスが使用されている場合）：

Seq Scan on app_user  (cost=0.00..8.15 rows=1 width=72)

部分一致が効率的でないケース

部分一致では、特に文字列検索でインデックスが効率的に使えないケースがある。
クエリ例:

コードをコピーする
SELECT * FROM users WHERE username LIKE '%john%';

動作:

  1. 条件'%john%'は、文字列のどこかにjohnが含まれているかを確認する必要がある。
  2. インデックス（例えばB-Tree）はデフォルトで「先頭から順に比較」する仕組みのため、%で始まる条件ではインデックスが無効になる。
  3. データベースはインデックスを使わず、全行をスキャンして確認する

範囲検索ができるケース

クエリ例:

コードをコピーする
SELECT * FROM users WHERE username LIKE 'john%';

動作:

  1. 条件'john%'は、「johnで始まる文字列」を検索。
  2. B-Treeインデックスが「先頭から順に比較」できるため、効率的に検索可能。

まとめ

  1. なぜ全行を確認する必要があるのか？

    • インデックスがない場合、データベースはデータがどこにあるかを知らないため、すべての行を順番に確認する（フルテーブルスキャン）。

  2. 木構造とハッシュ構造の違い

    • B-Treeは範囲検索やソートが高速。
    • Hashは一致検索が高速だが、範囲検索は非対応。

  3. DBの仕組みを理解する方法

    • PostgreSQLでインデックスの詳細を確認。
    • 実行計画（EXPLAIN）を調べ、インデックスの使用を確認。

  4. Djangoのデフォルト

    • 通常はB-Treeが利用される。
    • 必要に応じてインデックスやクエリを調整することで、パフォーマンスを最適化できる。

具体的な動作: B-Treeでの探索手順

例として、次のようなusernameインデックスを持つデータをB-Treeで管理している：

[alice, bob, carol, john_doe, zara]

B-Treeでは以下のようにデータが階層構造で保存される：

        carol
       /     \
    bob       john_doe
   /  \       /      \
 alice   carol  john_doe  zara

この構造を利用してjohn_doeを探す手順は下記。

手順: username = 'john_doe'を探す

  1. ルートノード（トップの階層）からスタート

    • 最初にcarolを確認。
    • 'john_doe' > 'carol'なので、右のノードに進む。

  2. 次のノード（2階層目）を確認

    • 次にjohn_doeを確認。
    • 一致するため、検索終了。

探索の効率性

  • データを1行ずつ確認せず、B-Treeの階層を順に探索します。
  • 探索にかかるコストはO(log n)（データ量が増えても、処理量の増加は緩やか）。

具体的な順番: B-Treeの探索アルゴリズム

1. 探索範囲の絞り込み

  • ルートノードから比較を行い、次に進むべきノードを決定する。
  • 各ノードは次の情報を持っています：
    • キー（検索対象の値）
    • 左側の子ノードへのポインタ
    • 右側の子ノードへのポインタ

2. 再帰的な比較

  • ルートノードを基準に、子ノードをたどっていく。
  • 各ノードで次の条件を確認します：
    • 検索対象が現在のノードのキーと一致 → 検索成功。
    • 検索対象がキーより小さい → 左側のノードへ移動。
    • 検索対象がキーより大きい → 右側のノードへ移動。

3. 終了条件

  • ノードが見つかった場合 → 検索成功。
  • 子ノードが存在しない場合 → 検索失敗。

まとめ

  1. B-Treeでの探索はフルテーブルスキャンを行わない理由:

    • 階層構造により、特定の範囲に絞り込む仕組みがある。
    • 一度にすべてのデータを見る必要がなく、探索コストがO(log n)。

  2. ID指定とusername指定の違い:

    • どちらもインデックスがあれば効率的に検索できる。
    • インデックスがない場合はフルテーブルスキャンになる。

  3. フルテーブルスキャンの発生タイミング:

    • インデックスがない場合。
    • 特定の操作（範囲検索ができない部分一致など）。
Discuss on Twitter • View on GitHub