1. はじめに
高校までとは異なり、必修科目や選択必修といった一定程度制約はあるものの、大学では各々興味のある授業を選択して受講することができる。
この「学生」と「授業」の関係をデータベースで表すことを考える。一人の学生は複数の授業を選択することができる。また一つの授業には複数の学生が登録する。これは「多対多（Many-to-Many)」の関係となる。
このモデル構造を持つアプリケーションにおいて、全学生のリストとそれぞれの履修科目を一覧で表示しようとする際、N+1問題というものに直面する。
今回はこの N+1問題 について取り上げる。また、Python フレームワークの Django における解決策を用いた実測データをもとに、その改善効果について検証をする。
2. N+1問題の概要
ここでは、N+1問題について説明をする。はじめにで取り上げた「学生」と「授業」の多対多（Many-to-Many)モデルを例に用いる。
学生のリストをデータベースから取得し、それぞれの学生が履修している科目名を一覧表示する処理を考える。この際、プログラム内部では次のような順序でクエリが実行される。
- メインクエリ：全学生のデータを取得する（1回）
- サブクエリ：取得した学生一人に対して、その学生が履修している授業のデータを取得する（N回）
この結果、データベースに対して発行されるクエリの数は 1 + N 回となる。これが「N+1問題」と呼ばれるものである。この $N$ は線型的に増加するので、データ数が多くなればなるほど、アプリケーション全体の実行速度を低下させる。
N+1問題が発生すると、クエリの回数が増加するだけでなく、データベースとの通信回数も増加する。データベースとの通信は単なる計算処理よりもコストが高い。そのため、
\begin{align}
&\text{アプリケーション} \\
&\rightarrow
\text{データベースに問い合わせ} \\
&\rightarrow
\text{データベースが処理} \\
&\rightarrow
結果が返る
\end{align}
この往復が学生一人に対して毎回発生するため、処理時間が増加する。
3. 対策
N+1問題は、データ取得のたびにクエリが発行されることで、クエリ数が増加しパフォーマンスが低下する問題である。では、どのように対策をすればいいのだろうか。
結論としては、次の2つの対策法がある。
- JOINによる一括取得
- 事前取得（prefetch）
3.1. JOINによる一括取得
N+1問題の本質は、クエリがN回追加で発行されることにある。
これに対して、JOINを使用すると、複数のテーブルを結合して1回のクエリで必要なデータをまとめて取得できる。これにより、データベースとの通信回数を削減することで、N+1問題を解決するアプローチである。
必要なものをまとめて取得することで、処理時間を短縮することができる。
図書館で本を $N$ 冊借りるときに、一つずつ借りて家と図書館を往復するよりも、$N$ 冊まとめて一気に持っていき借りることで家と図書館との往復の回数が減って、全体の時間を節約する。
3.4. 事前取得（prefetch）
JOINによる一括取得は、1回のクエリでデータをまとめて取得する方法である。
一方で、事前取得（prefetch）は少し異なるアプローチをとる。
まず、必要なデータを「まとめて別々に取得」し、その後アプリケーション側で結合する。
先ほどの例であれば、
- 学生一覧を取得（1回）
- すべての履修情報をまとめて取得（1回）
このように、クエリ数を 1 + N → 2回 に削減することができる。
図書館の例で考えると、JOINは「必要な本をすべて1回でカウンターに持っていく」方法だった。
一方でprefetchは次のような動きになる：
- まず「借りたい人のリスト」を用意する
- 次に「その人たちが借りる本をまとめて別で探す」
- 最後に「誰がどの本を借りるかを整理する」
つまり、
- 行き来は少ない（往復は2回だけ）
- ただし、最後に自分で仕分けする必要がある
という違いがある。
JOINとprefetchの違いは次のようになる。
- JOIN：データベース側で結合する（1回のクエリ）
- prefetch：アプリケーション側で結合する（複数クエリ）
4. 実験
今回は Django を用いて、N+1問題が実際にどの程度発生するのかを計測する。
実験は次の2種類で行う。
- ForeignKey に対する計測
- ManyToManyField に対する計測
それぞれの実験では、関連データを取得する処理について、以下のパターンを比較する。
a. 通常取得：N回の追加クエリが発生する取得方法
b. select_related：SQLの JOIN を使用して関連データを取得する方法
c. prefetch_related：関連データを別クエリでまとめて取得する方法
ただし、ManyToManyField に対して select_related は使用できない。そのため、ManyToManyField の実験では、通常取得と prefetch_related の2パターンのみを計測する。
本実験では、Django のモデル定義や設定が必要となるが、データはすべてスクリプト内で生成している。
4.1. 実験準備
実験準備として、2種類の関係を用意する。
-
EventとGroupの ForeignKey（多対1）の関係
1.1.Eventは1つのGroupに所属する
1.2.Groupは複数のEventを持つことができる -
GroupとTagの ManyToManyField の関係
2.1. 1つのGroupには複数のTagを付けられる
2.2. 1つのTagも複数のGroupを付けられる
4.2. 計測
4.1. で定義した2種類の関係に対して、データ件数を変化させながら、それぞれの取得方法における実行時間とクエリ数を計測する。
計測するデータ件数は、10、100、1000件の3種類である。
計測に使用した Python コードは次の通り
import os
import django
import time
import pprint
os.environ.setdefault("DJANGO_SETTINGS_MODULE", "config.settings")
django.setup()
from django.db import connection, reset_queries
from apps.core.models import Event, Group, Tag
import matplotlib.pyplot as plt
# ------- セットアップ -------
def cleanup_data():
Event.objects.all().delete()
Group.objects.all().delete()
Tag.objects.all().delete()
def setup_fk_data(n):
cleanup_data()
group = Group.objects.create(name="Test Group", owner=None)
events = [
Event(
group=group,
name=f"Event {i}",
start_time="2024-01-01T10:00:00Z",
end_time="2024-01-01T12:00:00Z",
)
for i in range(n)
]
Event.objects.bulk_create(events)
print(f"Created {n} Event records.")
def setup_m2m_data(n):
cleanup_data()
tags = [
Tag(name=f"Tag {i}")
for i in range(5)
]
Tag.objects.bulk_create(tags)
tags = list(Tag.objects.all())
groups = [
Group(name=f"Group {i}", owner=None)
for i in range(n)
]
Group.objects.bulk_create(groups)
groups = list(Group.objects.all())
for group in groups:
group.tags.add(*tags[:3])
print(f"Created {n} Group records with tags.")
# ------- Visualization -------
def visualize_results(results, n, test_name):
labels = list(results.keys())
times = [results[label]["time"] for label in labels]
queries = [results[label]["queries"] for label in labels]
_, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
ax1.bar(labels, times, color=["#e74c3c", "#2ecc71", "#3498db"])
ax1.set_title(f"{test_name} Execution Time for N={n}")
ax1.set_ylabel("Seconds")
ax2.bar(labels, queries, color=["#e74c3c", "#2ecc71", "#3498db"])
ax2.set_title(f"{test_name} Query Count for N={n}")
ax2.set_ylabel("Count")
plt.tight_layout()
os.makedirs("qiita", exist_ok=True)
filename = f"qiita/{test_name.lower()}_n{n}_comparison.png"
plt.savefig(filename)
plt.close()
print(f"Saved graph: {filename}")
# ------- 測定関数デコレータ -------
def measure_time(func):
def timer(*args):
start = time.time()
func(*args)
end = time.time()
total_time = end - start
print(f"関数 {func.__name__} の実行時間: {total_time:.6f} 秒")
return total_time
return timer
def measure_query(label, func, results):
reset_queries()
time = func()
q_count = len(connection.queries)
results[label] = {
"time": time,
"queries": q_count,
}
def add_ratio(show_results, n, label, results):
base_time = results["N+1"]["time"]
base_queries = results["N+1"]["queries"]
time_ratio = (results[label]["time"] / base_time) * 100
query_ratio = (results[label]["queries"] / base_queries) * 100
show_results[n][label] = (
f"{time_ratio:.2f}%",
f"{query_ratio:.2f}%",
)
# ------- ForeignKey Access -------
@measure_time
def fk_n_plus_one():
events = Event.objects.all()
for event in events:
_ = event.group.name
@measure_time
def fk_select_related():
events = Event.objects.select_related("group").all()
for event in events:
_ = event.group.name
@measure_time
def fk_prefetch_related():
events = Event.objects.prefetch_related("group").all()
for event in events:
_ = event.group.name
# ------- ManyToMany Access -------
@measure_time
def m2m_n_plus_one():
groups = Group.objects.all()
for group in groups:
_ = list(group.tags.all())
@measure_time
def m2m_prefetch_related():
groups = Group.objects.prefetch_related("tags").all()
for group in groups:
_ = list(group.tags.all())
# ------- Tests -------
def foreign_key_test():
data_n = [10, 100, 1000]
show_results = {}
for n in data_n:
results = {}
show_results[n] = {
"N+1": {},
"select_related": {},
"prefetch_related": {},
}
# データセットの準備
setup_fk_data(n)
# N+1 クエリの測定
measure_query("N+1", fk_n_plus_one, results)
show_results[n]["N+1"] = (100.0, 100.0)
# select_related の測定
measure_query("select_related", fk_select_related, results)
add_ratio(show_results, n, "select_related", results)
# prefetch_related の測定
measure_query("prefetch_related", fk_prefetch_related, results)
add_ratio(show_results, n, "prefetch_related", results)
# 結果の可視化
visualize_results(results, n, "foreign_key")
# CLIへの結果表示
pprint.pprint(show_results)
# データのクリーンアップ
cleanup_data()
def many_to_many_test():
data_n = [10, 100, 1000]
show_results = {}
for n in data_n:
results = {}
show_results[n] = {
"N+1": {},
"prefetch_related": {},
}
# データセットの準備
setup_m2m_data(n)
# N+1 クエリの測定
measure_query("N+1", m2m_n_plus_one, results)
show_results[n]["N+1"] = (100.0, 100.0)
# prefetch_related の測定
measure_query("prefetch_related", m2m_prefetch_related, results)
add_ratio(show_results, n, "prefetch_related", results)
# 結果の可視化
visualize_results(results, n, "many_to_many")
# CLIへの結果表示
pprint.pprint(show_results)
# データのクリーンアップ
cleanup_data()
if __name__ == "__main__":
foreign_key_test()
many_to_many_test()
5. 実験結果
以下に実験結果を示す。
5.1. ForeignKeyに対する計測
5.1.1. N=10
5.1.2. N=100
5.1.3. N=1,000
5.2. ManyToManyFieldに対する計測
5.2.1. N=10
5.2.2. N=100
5.2.3. N=1,000
5.3. 結果まとめ
5.3.1. ForeignKey
クエリ数に注目すると、select_related は prefetch_related のおおよそ半分となっている。
これは理論値と一致している。
-
select_related：1回のクエリ -
prefetch_related：2回のクエリ
また、$N$ が大きくなるにつれてクエリ数比はそれぞれ
-
select_related：$\frac{1}{N+1}$ -
prefetch_related：$\frac{2}{N+1}$
に近づいており、理論通りの挙動を示していることが確認できる。
| N | 手法 | 実行時間 | 実行時間比 | クエリ数比 |
|---|---|---|---|---|
| $10$ | N+1 |
$3.51 \times 10^{-3}$ 秒 | $100.00$% | $100.00$% |
| $10$ | select_related |
$0.00 \times 10^{0}$ 秒 | $0.00$% | $9.09$% |
| $10$ | prefetch_related |
$2.10 \times 10^{-3}$ 秒 | $59.91$% | $18.18$% |
| $100$ | N+1 |
$3.16 \times 10^{-2}$ 秒 | $100.00$% | $100.00$% |
| $100$ | select_related |
$2.49 \times 10^{-3}$ 秒 | $7.88$% | $0.99$% |
| $100$ | prefetch_related |
$2.03 \times 10^{-3}$ 秒 | $6.44$% | $1.98$% |
| $1000$ | N+1 |
$2.83 \times 10^{-1}$ 秒 | $100.00$% | $100.00$% |
| $1000$ | select_related |
$1.92 \times 10^{-2}$ 秒 | $6.80$% | $0.10$% |
| $1000$ | prefetch_related |
$1.45 \times 10^{-2}$ 秒 | $5.14$% | $0.20$% |
5.3.2. ManyToManyField
ManyToMany においては、select_related は使用できないため、prefetch_related のみを比較する。
クエリ数は理論通り、prefetch_related では常に2回となる。
そのため、$N$ が大きくなるにつれてクエリ数比は $\frac{2}{N+1}$ に近づいており、こちらも理論値と一致していることが確認できる。
| N | 手法 | 実行時間 | 実行時間比 | クエリ数比 |
|---|---|---|---|---|
| $10$ | N+1 |
$3.19 \times 10^{-3}$ 秒 | $100.00$% | $100.00$% |
| $10$ | prefetch_related |
$1.03 \times 10^{-3}$ 秒 | $32.15$% | $18.18$% |
| $100$ | N+1 |
$3.28 \times 10^{-2}$ 秒 | $100.00$% | $100.00$% |
| $100$ | prefetch_related |
$5.67 \times 10^{-3}$ 秒 | $17.29$% | $1.98$% |
| $1000$ | N+1 |
$2.59 \times 10^{-1}$ 秒 | $100.00$% | $100.00$% |
| $1000$ | prefetch_related |
$4.92 \times 10^{-2}$ 秒 | $19.03$% | $0.20$% |
6. 参考資料
- [1]. The N+1 Database Query Problem: A Simple Explanation and Solutions
- [2]. SQLのN+1問題完全ガイド：原因から解決策まで
- [3]. What is the N+1 Query Problem and How to Solve it?
- [4]. [解説] SQLクエリのN+1問題