開発環境ではサクサク動いていたのに、本番データが入った途端に画面が重くなる。Webアプリを作っていると、一度はこの状況にぶつかると思います。

原因の多くは、次の4つのどれかに当てはまります。

この記事では、それぞれを「ざっくりした意味」と「よくある例」だけに絞って説明します。厳密な定義は置いておいて、コードを見たときに「これは危ないかも」と気づけるところまでを目指します。

O記法は「データが増えたらどれくらい重くなるか」の目安

O記法（オーダー記法）は、データ量 n が増えたときに処理量がどう増えるかを表す書き方です。

すごく雑に言うと「データが10倍になったら、処理は何倍になる？」の答えにあたります。Webアプリ開発ならこの感覚があれば十分で、数式を覚える必要はありません。

ここからは、速い順に7種類を見ていきます。

O(1)：データが増えても速さが変わらない

辞書（dict）のキー検索が代表例です。

users = {1: "Alice", 2: "Bob", 3: "Carol"}

name = users[2]  # 何件あっても一発で取れる

10件でも100万件でも、平均的にはほぼ1回で目的のデータにたどり着けます。キャッシュからの取得もこのタイプに入ります。

O(log n)：データが増えても少ししか重くならない

毎回、探す範囲を半分に絞り込むような処理がこれです。紙の辞書で単語を引くとき、真ん中あたりを開いて「前か後ろか」を判断していくのと同じ考え方です。

DBのINDEX（索引）を使った検索がこれに当たります。

CREATE INDEX idx_users_email ON users(email);

SELECT * FROM users WHERE email = 'test@example.com';

半分ずつ絞り込む二分探索なら、100万件あっても20回程度で見つかります。

O(n)：データ量に比例して重くなる

1件ずつ順番に調べる処理です。

for user in users:
    if user.id == target_id:
        return user

1,000件なら最大1,000回、100万件なら最大100万回チェックすることになります。DBでINDEXが効かず、テーブルを頭から全部読む Seq Scan（シーケンシャルスキャン。PostgreSQLでの呼び名で、MySQLではフルテーブルスキャンと呼びます）も同じイメージで考えて大丈夫です。

O(n log n)：ソートでよく出てくる

並べ替えの処理はだいたいこれです。

users.sort(key=lambda u: u.name)

データを細かく分けてから、並べながらまとめ直していきます。まとめ直す段数が log n 段、1段ごとに n 件を処理するので n log n になります。

SQLの ORDER BY も、INDEXが使えない場合はDBが内部でこのソート処理を行います。O(n) よりは重いものの、O(n²) と比べればずっと軽いので、普通に使う分には気にしすぎなくて大丈夫です。

O(n²)：二重ループは要注意

Webアプリで一番気をつけたいのがここです。

for user in users:
    for order in orders:
        if user.id == order.user_id:
            print(user.name, order.id)

正確には、ユーザー数 n × 注文数 m 回の比較になります。両方が同じくらいのペースで増えるなら n × n、つまり O(n²) と考えて構いません。ユーザーも注文も10倍になると、処理は100倍に膨らみます。

n = 100    →       10,000回
n = 1,000  →    1,000,000回
n = 10,000 →  100,000,000回

開発環境の数十件では気づかず、本番で一気に遅くなる典型パターンです。

多くの場合、dictを使えば O(n + m)、つまりデータ量に比例する形に書き換えられます。

from collections import defaultdict

orders_by_user = defaultdict(list)
for order in orders:
    orders_by_user[order.user_id].append(order)

for user in users:
    for order in orders_by_user[user.id]:  # O(1) で取り出せる
        print(user.name, order.id)

先に「ユーザーIDごとの注文リスト」を作っておけば、ユーザーごとに orders 全体をなめる必要がなくなります。

このコードも for が入れ子になっていますが、内側のループは「そのユーザーの注文だけ」を回すので、合計しても注文数ぶんしか回りません。for が2つ並んでいるかどうかではなく、内側で毎回全件を回しているかどうかを見るのがポイントです。

O(2^n) と O(n!) は存在だけ知っておけばOK

O(2^n) は、入力が1増えるたびに処理が掛け算で増えていくタイプです。工夫のない再帰で書いたフィボナッチ数が有名です。フィボナッチの場合、正確には1増えるごとに約1.6倍で、2^n はその上限の見積もりにあたります。

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # 同じ計算を何度も繰り返す

図のとおり、fib(5) を求めるだけで fib(2) を3回も計算し直しています。一度計算した結果を覚えておく（メモ化）と、この無駄が消えます。Pythonなら functools.lru_cache を付けるだけです。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # 各 n について1回だけ計算される

O(n!) は、すべての並び順を試すような処理を指します。たった10件で約363万通りになります。

どちらも、CRUD（登録・参照・更新・削除）が中心の普通のWebアプリではまず出てきません。組み合わせ探索や推薦のロジックを書くときに「データ数が小さいことが保証されているか」を確認する、くらいの意識で大丈夫です。

計算量の早見表

計算量	ざっくり言うと	よくある例
O(1)	件数に関係なく一瞬	dictのキー検索
O(log n)	件数が増えてもほぼ平気	DBのINDEX検索
O(n)	件数に比例	全件ループ、Seq Scan
O(n log n)	O(n)より少し重い	ソート、 `ORDER BY`
O(n²)	件数の2乗で増える	二重ループ
O(2^n) / O(n!)	爆発的に増える	全組み合わせ・全順列

メモリ使用量（空間計算量）もデータ量で増える

処理時間だけでなく、メモリの使い方も「データ量に比例して増えるか」で考えます。

users = list(User.objects.all())  # 全件をメモリに載せる

数件なら問題ありませんが、数百万件あるとサーバーのメモリを使い切ることがあります。一覧画面ならページネーション（1ページ20件ずつのように分けて取得する仕組み）を入れます。Djangoなら、図の右側のように [:20] でスライスすると、SQLの LIMIT 20 になってDBから20件だけ取ってきます。絞り込みはPython側でやらず、SQLの WHERE に任せます。この2つが基本の対策です。

N+1問題は「SQLを何回投げているか」の問題

ここからはDBの話です。N+1問題は、ここまで数えてきた「アプリの中の処理回数」ではなく「DBに投げるSQLの回数」に注目します。

たとえるなら、スーパーへの買い物です。100品買うのに、1品ごとに家とスーパーを往復する人はいませんよね。買い物リストを作って1回でまとめて買うはずです。N+1問題は、プログラムがこの「1品ずつ往復」をしてしまっている状態です。

どんなコードで起きるか

Djangoでよくある例を見てみます。ユーザー一覧を取ってきて、それぞれのプロフィール名を表示するだけのコードです。

users = User.objects.all()

for user in users:
    print(user.profile.name)

一見なんの問題もなさそうですが、Djangoは裏で次のようなSQLを発行しています。

SELECT * FROM users;                        -- ユーザー一覧を取る（1回）
SELECT * FROM profiles WHERE user_id = 1;   -- 1人目のプロフィール
SELECT * FROM profiles WHERE user_id = 2;   -- 2人目のプロフィール
SELECT * FROM profiles WHERE user_id = 3;   -- 3人目のプロフィール
-- ...ユーザーの人数ぶん続く

ユーザーが100人いると、一覧の1回と、プロフィールの100回で合計101回。ユーザー数を N とすると「N + 1回」になるので、N+1問題と呼ばれています。

なぜこうなるのか

Djangoは、最初の User.objects.all() の時点ではユーザーのデータしか取ってきません。プロフィールは、ループの中で user.profile に触れた瞬間に「まだ持っていないので取りに行こう」とSQLを1本投げます。これを遅延読み込みと呼びます。

コードにSQLが1行も書かれていないので、気づきにくいのが厄介なところです。

まとめて取ってくれば解決する

対策は「最初にまとめて取ってくるよう、Djangoに伝えておく」ことです。関連の種類によって、使うメソッドが2つあります。

関連の種類	例	使うメソッド	SQLの回数
相手が1つ（1対1、多対1）	ユーザー → プロフィール	`select_related()`	1回
相手が複数（1対多、多対多）	ユーザー → 注文	`prefetch_related()`	2回

プロフィールのように相手が1つなら、 select_related() を使います。JOIN（テーブル結合）で、ユーザーとプロフィールを1回のSQLでまとめて取ってきます。

users = User.objects.select_related("profile")

for user in users:
    print(user.profile.name)  # ここではSQLが発行されない

注文のように相手が複数なら、 prefetch_related() を使います。ユーザー一覧を取ったあと、全員分の注文を WHERE user_id IN (1, 2, 3, ...) のような1本のSQLでまとめて取ってきます。

users = User.objects.prefetch_related("order_set")

for user in users:
    for order in user.order_set.all():  # ここではSQLが発行されない
        print(order.id)

どちらも、ループの中身は書き換えずに済みます。変えるのは最初の1行だけです。ただし prefetch_related() の場合、ループの中で user.order_set.filter(...) のように条件を付けると、まとめて取っておいたデータが使われず、またSQLが発行されてしまいます。ループの中では .all() で取り出すようにしてください。

自分のコードで起きているか確かめたいときは、django-debug-toolbar を入れると、画面ごとに発行されたSQLの本数と中身を一覧で見られます。似たSQLが人数ぶん並んでいたら、N+1を疑ってください。

O(n) との違い

最後に、O(n) との違いを整理しておきます。

	数えているもの	1回あたりの重さ
O(n)	アプリの中で何回処理するか	メモリ上の処理なので軽い
N+1	DBに何回SQLを投げているか	通信の往復があるので重い

N+1では、ループの回数自体は O(n) のままでも、1回ごとにDBとの往復が入ります。そのため、件数が少ないうちから目に見えて遅くなりやすいのです。

INDEXは本の索引と同じ

INDEXがないと、DBは目的の行を探すために全件を順番に調べます（Seq Scan）。本の索引を使わず、1ページ目から目当ての単語を探すようなものです。

CREATE INDEX idx_users_email ON users(email);

INDEXを貼ると、先ほどの O(log n) で探せるようになります。 WHERE 、 JOIN 、 ORDER BY でよく使うカラムが候補です。

ただし、INDEXは多ければいいわけではありません。 INSERT / UPDATE / DELETE のたびにDBがINDEXも更新するので、書き込みが遅くなります。よく検索するカラムに絞って貼りましょう。

INDEXが効いているかは、PostgreSQLなら EXPLAIN ANALYZE で確認できます。

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'test@example.com';

EXPLAIN ANALYZE はクエリを実際に実行して時間を測ります。 UPDATE や DELETE に付けるとデータが本当に書き換わるので、トランザクションの中で実行して最後に ROLLBACK するか、実行計画を見るだけなら ANALYZE を外した EXPLAIN を使ってください。

結果に Index Scan 、 Index Only Scan 、 Bitmap Index Scan のどれかが出ていればINDEXが使われています。大きなテーブルで Seq Scan と出ていたら、INDEXが足りていない可能性があります。とはいえ、データが少ないときはDBがあえてSeq Scanを選ぶこともあるので、出たら即アウトというわけではありません。

I/Oはループ1回より圧倒的に重い

I/O（入出力）は、DB・外部API・ファイルなど、プログラムの外とやり取りする処理のことです。

メモリ上で100回ループするより、DBに100回アクセスするほうがずっと遅くなります。DBへのアクセスは毎回、ネットワークを通ってDBに届き、DBがSQLを解析してデータを探し、結果をまたネットワークで返します。この往復のコストが、メモリ上の処理とは桁違いに大きいのです。

実際の時間の目安で比べると、100回くり返したときにメモリ上の処理は一瞬で終わりますが、DBアクセスは約0.1秒、外部APIの呼び出しは約10秒かかります。

これでも差が実感しにくいので、図の下段ではすべてを同じ倍率で引き延ばしています。メモリ上の処理1回を「1秒」とすると、DBへのアクセスは約3時間、外部APIの呼び出しは約12日に相当します（実際の時間は環境によって大きく変わるので、あくまで目安です）。ループの中にI/Oが1つ入るだけで、ループ全体の重さがまるで変わってしまいます。

なので、ループの中で外部APIを呼ぶコードは特に注意が必要です。

for user in users:
    call_external_api(user)  # ユーザー数ぶん通信が発生する

APIが一括リクエストに対応していれば、そちらを使うのが基本です。

コードレビューで見るポイント

最後に、ここまでの内容を実際のコードに当てはめてみます。

users = User.objects.all()

for user in users:
    orders = Order.objects.filter(user_id=user.id)

    for order in orders:
        process(order)

一番の問題は、ループの中で Order を検索していることです。ユーザーが1,000人いれば、SQLが1 + 1,000回発行される N+1 になっています。 User.objects.all() で全件を取っているので、ユーザーが増えるほどメモリと時間も食います。

一方で、for が入れ子になっていること自体は問題ではありません。内側のループはそのユーザーの注文だけを回すので、全体でも注文数ぶんしか回りません。O(n²) の節で見たとおり、内側で毎回全件を回していなければ O(n²) にはなりません。

N+1 は prefetch_related() で解消できます。

users = User.objects.prefetch_related("order_set")

for user in users:
    for order in user.order_set.all():  # ここでは追加のSQLが発行されない
        process(order)

これでSQLは2回になります。ユーザー数がかなり多いなら、ページネーションや絞り込みも組み合わせましょう。

レビューのときは、次のチェックリストを上から見ていくと漏れにくくなります。

□ 全件取得や、大量データの一括読み込みをしていないか
□ ループの中が重くないか（内側で毎回全件を回す、SQLや外部APIを呼ぶ）
□ WHERE / JOIN / ORDER BY のカラムにINDEXがあるか
□ データが10倍・100倍になっても耐えられるか

特に最後の「10倍・100倍になったら？」を想像する癖をつけるだけでも、本番で慌てる回数はかなり減るはずです。気になる箇所が見つかったら、 EXPLAIN ANALYZE やログで実際の時間を測って確かめてみてください。