会社情報
採用情報
お問い合わせ
Article

Database Indexing戦略でクエリを100倍高速化

高田晃太郎
Database Indexing戦略でクエリを100倍高速化

**全表走査は O(n)、B-Tree 検索は O(log n)**¹。理論だけ見れば、1億行のテーブルで必要な比較回数は約1億対27と桁違いです¹。現実のRDBでも、キャッシュ・I/O・CPUを含む実行コストはこの差に強く引きずられます²。公開ベンチや実測報告では、適切な索引によりクエリが1〜数桁短縮される事例が珍しくありません²⁵⁷。編集観点では、単に「貼る」ではなく、ワークロード別の戦略を設計し、計測で確かめ、運用で維持することが鍵になります。この記事では、B-Treeを軸に部分・複合・カバリング・BRIN・GINといった手法を、実行計画とコードで具体化しながら、こうした大幅な高速化（条件次第では二桁〜三桁短縮も）を現実的な選択肢にする道筋を示します²⁵⁷。

なぜインデックスで「100倍」のような大幅短縮が起きるのか

高速化の根源は計算量の差とI/O削減にあります。B-Tree（高さが抑えられた平衡木）¹は選択性の高い述語で強く効き、少数行へのランダムアクセスを作り出します。ページキャッシュに乗ればCPUのみで処理され、乗らなくてもディスクI/Oは桁違いに減ります²。加えて、カバリングインデックスやIndex Only Scan（インデックスだけで必要列を満たし、テーブル本体へのアクセスを省く）が成立すると、テーブルヒープへの追加アクセスが消えます³⁇。これらの条件が重なると、p95（95パーセンタイルのレイテンシ）は数百msから数msまで落ちるケースが公開事例で報告されています²。実際の改善幅はデータ分布・統計・キャッシュ・I/O帯域などの前提で変動する点は押さえましょう。

ただし魔法ではありません。インデックスは書き込みコストを増やし、メモリを消費し、統計の劣化や断片化で効き目が落ちます。戦略は常にトレードオフの最適化です。以降は設計パターンを順に掘り下げ、最後に測定と運用で定着させます。

EXPLAINで体感するオーダーの差

まずはPostgreSQLで実測の感触を掴みます。以下は1億行のeventsテーブルから特定ユーザーの最近のアクティビティを引く想定です。

-- 前提（サンプル）：events(user_id int, created_at timestamptz, payload jsonb)
EXPLAIN (ANALYZE, BUFFERS)
SELECT user_id, created_at
FROM events
WHERE user_id = 12345
ORDER BY created_at DESC
LIMIT 50;

インデックスなしでは、実行計画はSeq Scan（全表走査）に寄り、数千万〜1億行を舐めるため数百ms〜数秒が見えます²。複合インデックスを適切な順序で作ると計画はIndex Scanに替わり、ヒープフェッチが最小化されます³⁇。

CREATE INDEX CONCURRENTLY idx_events_user_created
  ON events(user_id, created_at DESC);

EXPLAIN (ANALYZE, BUFFERS)
SELECT user_id, created_at
FROM events
WHERE user_id = 12345
ORDER BY created_at DESC
LIMIT 50;

一例として、公開ベンチや実測の報告では、p95が数百msから数ms台に短縮される（二桁以上の短縮が得られる）ケースが見られます²。LIMITとの相性が良く、インデックスがORDER BYを満たせる場合は先頭ページをなめるだけで答えが出るためです¹⁵。実際の改善幅はデータ分布・統計・キャッシュ・I/O帯域で変動します。

実戦で効くインデックス設計パターン

現場で使う頻度が高く、再現性があるパターンを、効果のメカニズムとともに示します。ポイントは、述語（どの行を選ぶか）、結合、並び替え、取得列の四つの観点を常に同時に見ることです。ここでの「選択性」は、条件に一致する行の割合の低さを指します。低いほど効果が出ます。

複合インデックスの列順は「フィルタ強→順序→カバー」

複合インデックスでは、選択性の高いフィルタ列を先頭に置き、その次にORDER BYに現れる列、最後に取得頻度の高い列をINCLUDEや末尾列として配置します。PostgreSQLであればINCLUDE句を使うと、検索キーに含めたくない列も物理的にインデックスに同梱できます。これがIndex Only Scanを呼び込み、ヒープアクセスを消します³⁇。

-- カバリングの例（PostgreSQL 11+）
CREATE INDEX CONCURRENTLY idx_orders_user_status_created
  ON orders(user_id, status, created_at DESC)
  INCLUDE (total_amount);

-- よくあるクエリ
EXPLAIN (ANALYZE, BUFFERS)
SELECT total_amount, created_at
FROM orders
WHERE user_id = $1 AND status = 'PAID'
ORDER BY created_at DESC
LIMIT 20;

MySQL/InnoDBでは、主キーを物理順序に組み込むクラスタ化インデックスの特性上、二次インデックス経由でも主キーアクセスが発生します⁸。よってカバリング（必要列をすべてインデックス側に含める）を成立させる設計が特に効きます⁷。キー長やページ分割による肥大化には注意します。

部分インデックスで集合を絞る

多くのSaaSでは、実際に検索対象になるのは「生きている」データです。論理削除やステータスで分母を強く絞れるなら、部分インデックスで小さく速い構造を作れます⁴。

-- ACTIVE だけに貼る（サイズと更新コストを削減）
CREATE INDEX CONCURRENTLY idx_sessions_active_user
  ON sessions(user_id)
  WHERE deleted_at IS NULL AND status = 'ACTIVE';

EXPLAIN (ANALYZE)
SELECT *
FROM sessions
WHERE user_id = $1 AND deleted_at IS NULL AND status = 'ACTIVE';

条件とクエリの述語を厳密に一致させることが成功の条件です。一致しないとプランナは部分インデックスを選びません⁴。

BRINで巨大な時系列を軽量に絞り込む

append-onlyなログやメトリクスでは、BRIN（ページ範囲ごとの最小/最大などのメタデータで粗く絞るインデックス）が強い味方です。ページ範囲のメタデータでヒット範囲を粗く絞り込み、I/Oを劇的に削ります。インデックスサイズはB-Treeの数百分の一に収まりやすく、取り回しも軽量です⁵。範囲の相関が高いほど効果が出やすく、物理配置やVACUUMの影響も受けます¹⁴。

-- 時間で強く相関する巨大テーブル向け
CREATE INDEX CONCURRENTLY idx_events_brin_created
  ON events USING BRIN (created_at) WITH (pages_per_range = 128);

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*)
FROM events
WHERE created_at > now() - interval '15 minutes';

GINでJSONB・全文検索を実用速度に

半構造化データの検索は、適切なGIN（キー/値やトークンの存在を高速化するインデックス）を使えば実用域に入ります。キー存在、パス一致、全文の語彙検索などで、インデックスなしでは秒単位の探索がミリ秒に収まります⁶。更新頻度が高いテーブルではGINの更新コストが気になるため、トリガや非同期のマテビューで更新バッチ化する設計も検討します¹³。

-- JSONBのキー/値検索
CREATE INDEX CONCURRENTLY idx_profiles_gin_prefs
  ON profiles USING GIN (preferences jsonb_path_ops);

EXPLAIN (ANALYZE)
SELECT id
FROM profiles
WHERE preferences @> '{"lang": "ja", "news": true}';

-- 全文検索
ALTER TABLE articles ADD COLUMN tsv tsvector;
CREATE INDEX CONCURRENTLY idx_articles_gin_tsv ON articles USING GIN (tsv);
UPDATE articles SET tsv = to_tsvector('simple', title || ' ' || body);

EXPLAIN (ANALYZE)
SELECT id FROM articles WHERE tsv @@ plainto_tsquery('vector index');

結合キーと外部キーは迷わず索引化

JOINの片側が外部キーなら、その外部キー列にインデックスを用意すると結合順序の選択肢が広がり、ネステッドループが生きる場面で顕著に効きます。参照整合性の検証も速くなります。

-- 親: customers(id PK), 子: orders(customer_id FK)
CREATE INDEX CONCURRENTLY idx_orders_customer ON orders(customer_id);

EXPLAIN (ANALYZE)
SELECT c.id, o.id, o.total_amount
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.segment = 'enterprise' AND o.created_at > now() - interval '30 days';

測定と運用: 速さを維持するための指標

インデックスは作って終わりではなく、計測と保守で効き目を維持することが重要です。ここでは、EXPLAIN/統計/監視の三点で回し方を固めます。

EXPLAIN (ANALYZE, BUFFERS) を標準装備に

計画と実行の差分を可視化し、論理読取りと物理I/Oを定量化します。PostgreSQLではtrack_io_timingを有効にしてI/O時間を観測します¹⁰。Index Only Scanが成立しているか、ヒープフェッチが消えているか、再検討の余地が一目で分かります³。

-- サンプル：I/O時間も観測
SET track_io_timing = on;
EXPLAIN (ANALYZE, BUFFERS)
SELECT ... -- 対象クエリ

統計の鮮度と選択性の把握

プランナは統計に依存します。ANALYZEの自動実行任せで足りない場合、対象テーブルの統計ターゲットを引き上げます。n_distinctやmost_common_valsで選択性を推定し、複合インデックスの列順を見直す判断材料にします¹¹。

-- 統計ターゲットの引き上げ（PostgreSQL）
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
VACUUM (ANALYZE) orders;

-- 選択性の確認
SELECT attname, n_distinct
FROM pg_stats
WHERE tablename = 'orders';

運用コストとROIの勘定

高速化はビジネス価値に接続してこそ意味があります。例えば、p95が大幅に下がり、QPSが同じでも待機が解消されるなら、同一インスタンスでピークを吸収できる可能性が高まります。CPU使用率やストレージIOPSが顕著に低下すれば、RDSのクラスやIOPSプロビジョニングを見直せる可能性もあります。一方で、書き込みのコストは増えます。更新QPSが高いワークロードでは、追加インデックスの維持コストにより書き込みスループットが低下する場合があるため、読み取りの改善幅との相殺で意思決定します²。

簡易ベンチマークの実装例（Python）

安全な負荷で相対比較を行い、前後の差を明文化します。例ではpsycopg2で準備済み文を使い、例外とタイムアウトを適切に処理します。

import os
import time
import statistics
import psycopg2
from psycopg2.extras import execute_values

DSN = os.getenv("PG_DSN", "dbname=app host=127.0.0.1 user=app password=secret")
QUERY = """
SELECT user_id, created_at
FROM events
WHERE user_id = %s
ORDER BY created_at DESC
LIMIT 50
"""

def run_once(conn, uid):
    with conn.cursor() as cur:
        cur.execute("SET statement_timeout = '1500ms'")
        start = time.perf_counter()
        cur.execute(QUERY, (uid,))
        _ = cur.fetchall()
        return (time.perf_counter() - start) * 1000

def main():
    latencies = []
    try:
        with psycopg2.connect(DSN) as conn:
            conn.autocommit = True
            for i in range(200):
                uid = 10000 + (i % 500)
                try:
                    lat = run_once(conn, uid)
                    latencies.append(lat)
                except psycopg2.OperationalError as e:
                    print(f"timeout or operational error: {e}")
            p50 = statistics.median(latencies)
            p95 = sorted(latencies)[int(len(latencies)*0.95)-1]
            print(f"runs={len(latencies)} p50={p50:.2f}ms p95={p95:.2f}ms")
    except psycopg2.Error as e:
        print(f"db error: {e}")

if __name__ == "__main__":
    main()

インデックス作成前後で同条件のベンチを回し、p95短縮幅と標準偏差の変化を記録します。カバリングが成立していれば分散も小さくなりやすい点が指標になります³⁇。

Goでもう一歩踏み込む（同時実行測定）

goroutineで同時実行時のスループットとテールレイテンシ（高位百分位の遅延）を観察します。

package main
import (
    "context"
    "database/sql"
    "fmt"
    "log"
    "math"
    "os"
    "sync"
    "time"
    _ "github.com/lib/pq"
)

func worker(db *sql.DB, n int, res chan float64, wg *sync.WaitGroup) {
    defer wg.Done()
    ctx, cancel := context.WithTimeout(context.Background(), 1500*time.Millisecond)
    defer cancel()
    for i := 0; i < n; i++ {
        uid := 10000 + (i % 500)
        start := time.Now()
        rows, err := db.QueryContext(ctx, `SELECT user_id, created_at FROM events WHERE user_id = $1 ORDER BY created_at DESC LIMIT 50`, uid)
        if err != nil { continue }
        for rows.Next() { var a int; var b time.Time; _ = rows.Scan(&a, &b) }
        rows.Close()
        res <- float64(time.Since(start).Microseconds()) / 1000.0
    }
}

func main() {
    dsn := os.Getenv("PG_DSN")
    if dsn == "" { dsn = "dbname=app host=127.0.0.1 user=app password=secret sslmode=disable" }
    db, err := sql.Open("postgres", dsn)
    if err != nil { log.Fatal(err) }
    db.SetMaxOpenConns(50)
    db.SetMaxIdleConns(50)

    runs := 200
    conc := 10
    res := make(chan float64, runs)
    var wg sync.WaitGroup
    start := time.Now()
    for i := 0; i < conc; i++ { wg.Add(1); go worker(db, runs/conc, res, &wg) }
    go func(){ wg.Wait(); close(res) }()

    vals := []float64{}
    for v := range res { vals = append(vals, v) }
    dur := time.Since(start)

    // p95計算
    var p95 float64
    if len(vals) > 0 { for i := 0; i < len(vals)-1; i++ { for j := i+1; j < len(vals); j++ { if vals[i] > vals[j] { vals[i], vals[j] = vals[j], vals[i] } } }
        idx := int(math.Ceil(float64(len(vals))*0.95)) - 1
        if idx < 0 { idx = 0 }
        p95 = vals[idx]
    }
    fmt.Printf("runs=%d conc=%d elapsed=%.2fs p95=%.2fms\n", runs, conc, dur.Seconds(), p95)
}

同時実行下でもp95が安定して短縮されるか、ヘッドルームがどれだけ増えたかを確認します。

メンテナンス: 断片化、統計、再構築

長期運用ではインデックスの断片化や膨張が効きを損ない、プラン誤選択の呼び水になります。PostgreSQLならREINDEX CONCURRENTLYでダウンタイムを抑えた再構築、FILLFACTORでページ分割の抑制、autovacuum設定の最適化が定石です¹²。MySQLでもANALYZE/OPTIMIZEの効果とコストを把握し、オンラインDDLを選びます。統計の更新や永続化設定（innodb_stats_persistent）の活用も検討します¹⁶。

-- 再構築（オンライン）
REINDEX INDEX CONCURRENTLY idx_orders_user_status_created;

-- 膨張の観察（簡易）
SELECT relname, pg_relation_size(indexrelid) AS bytes
FROM pg_stat_all_indexes
WHERE schemaname = 'public'
ORDER BY bytes DESC
LIMIT 20;

よくある落とし穴と回避策

過剰な索引は害になります。更新負荷が高いテーブルに類似の複合インデックスを並べると、書き込みスループットが目に見えて落ちます。クエリ群を棚卸しし、重複度の高いものへ統合し、INCLUDEや部分インデックスで必要最小限を実現します。もう一つは列順のミスマッチで、等価述語を後ろに置き、選択性の低い範囲指定を先頭にすると、インデックスの有効領域が痩せ、全表走査に落ちやすくなります。最後は誤った期待です。高カーディナリティのlike ‘%foo’や関数適用列は素直なB-Treeでは効きません。必要に応じて正規化や生成列＋関数インデックス、あるいは専用検索エンジンに引き渡す設計を選びます。

MySQLでのヒントと違い

InnoDBではクラスタ化インデックス（主キー順にデータ行が格納される構造）の影響で、二次インデックス経由でも主キーアクセスが発生します⁸。よってカバリングを成立させると強く効きます⁷。ANALYZE TABLEで統計を更新し、innodb_stats_persistentを活かし、降順ソートの最適化度合いの差（バージョン依存）にも注意します¹⁶。また、複合インデックスの先頭一致ルールは厳格に効くため、述語の並べ方と列順の整合性を崩さないことが重要です¹⁷。

MongoDBなどドキュメントDBの文脈

ドキュメントDBでも原理は同じです。選択性、カバリング、部分インデックスに相当するpartialFilterExpression、TTLや時系列コレクションの運用設計が鍵です。複合インデックスの順序はフィルタの選択性とソート要件で決め、hintやexplainでプランを検証します。書き込み負荷とのバランスはRDBと同様に評価します⁹。

実運用でのベンチマーク失敗例

本番キャッシュが温まった状態と検証環境のコールドキャッシュを混同すると、改善幅を誤認します。代表データのサンプリング、同一ワークロードの再現、主なクエリのパラメータ分布の再現が必要です。さらに、1回だけのEXPLAIN ANALYZEで判断せず、複数回の中央値とp95を必ず記録します。

まとめ: 戦略・実装・計測を一気通貫に

Indexingは点のチューニングではなく、ワークロードに適合した戦略設計、クエリと整合した実装、データ増加とともに劣化を検出して修復する運用の三位一体で初めて成果を産みます。複合・部分・カバリング・BRIN・GINを状況に応じて使い分け、EXPLAINとp95を指標に意思決定すれば、誇張に頼らずとも大幅な高速化を現実的に狙えます²⁵⁷。次の一手として、まずはトップNの遅いクエリに対して統計と実行計画を洗い、選択性と並び替え要件から列順を再設計してみてください。改善の確度が高いものから順に適用し、前後のp95とI/Oを数字で残す。それがチームの知見になり、次の案件での立ち上がりを加速します。

参考文献

  1. Dat Nguyen. Did you know time complexity of B-Tree is always O(log n)? https://www.linkedin.com/pulse/did-you-know-time-complexity-b-tree-always-olog-n-dat-nguyen-7yrvc
  2. Percona. Full Table Scan vs. Full Index Scan Performance. https://www.percona.com/blog/full-table-scan-vs-full-index-scan-performance
  3. PostgreSQL 16 Manual. Index-Only Scans. https://www.postgresql.org/docs/16/indexes-index-only-scans.html
  4. PostgreSQL 15 Manual. Partial Indexes. https://www.postgresql.org/docs/15/indexes-partial.html
  5. Crunchy Data. PostgreSQL BRIN indexes: Big data performance with minimal storage. https://www.crunchydata.com/blog/postgresql-brin-indexes-big-data-performance-with-minimal-storage
  6. Timescale. How to index JSON columns in PostgreSQL. https://www.timescale.com/learn/how-to-index-json-columns-in-postgresql
  7. Crunchy Data. Why covering indexes are incredibly helpful. https://www.crunchydata.com/blog/why-covering-indexes-are-incredibly-helpful
  8. MySQL 8.0 Reference Manual. InnoDB and Indexes: Clustered and Secondary Indexes. https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html
  9. MongoDB Manual. Partial Indexes with partialFilterExpression. https://www.mongodb.com/docs/manual/core/index-partial
  10. PostgreSQL 16 Manual. track_io_timing (Runtime Statistics). https://www.postgresql.org/docs/16/runtime-config-statistics.html#GUC-TRACK-IO-TIMING
  11. PostgreSQL 16 Manual. The View pg_stats. https://www.postgresql.org/docs/16/view-pg-stats.html
  12. PostgreSQL 16 Manual. REINDEX — rebuild indexes (CONCURRENTLY). https://www.postgresql.org/docs/16/sql-reindex.html
  13. PostgreSQL 16 Manual. GIN Indexes and fastupdate. https://www.postgresql.org/docs/16/gin-implementation.html
  14. PostgreSQL 16 Manual. BRIN Indexes and data correlation. https://www.postgresql.org/docs/16/brin.html
  15. PostgreSQL 16 Manual. Using Indexes with ORDER BY. https://www.postgresql.org/docs/16/using-explain.html#USING-EXPLAIN-ORDER-BY
  16. MySQL 8.0 Reference Manual. Persistent Optimizer Statistics (innodb_stats_persistent). https://dev.mysql.com/doc/refman/8.0/en/innodb-persistent-stats.html
  17. MySQL 8.0 Reference Manual. How MySQL Uses Indexes (Leftmost Prefix). https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html