開発環境ではサクサク動いていたのに、本番データが入った途端に画面が重くなる。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 やログで実際の時間を測って確かめてみてください。