N+1 問題

読了目安約3分

ループの中のクエリが DB への往復を N 回に増やす、ISUCON 最頻出のボトルネックを直します。

この章の目次

前章の「1 回は軽いのに何万回も呼ばれているクエリ」の正体は、ほとんどの場合これから見る ISUCON 最頻出のパターンです。

ループの中のクエリ

Part 5 の掲示板で、投稿の一覧に投稿者の名前を添えて返すハンドラを考えます。参照実装によくあるコードです。

Go
rows, err := db.Query("SELECT id, user_id, body FROM posts ORDER BY created_at DESC LIMIT 100")
if err != nil {
	return err
}
defer rows.Close()

var posts []Post
for rows.Next() {
	var p Post
	if err := rows.Scan(&p.ID, &p.UserID, &p.Body); err != nil {
		return err
	}
	// 投稿ごとに投稿者の名前を引く
	err := db.QueryRow("SELECT name FROM users WHERE id = ?", p.UserID).Scan(&p.UserName)
	if err != nil {
		return err
	}
	posts = append(posts, p)
}

ループの中で、投稿ごとに名前を引くクエリを実行しています。

何が起きているか

一覧のために 1 回、名前のために 100 回、合計 101 回のクエリが走ります。一覧を N 件取るとクエリが 1 + N 回になるので、このパターンを N+1 問題と呼びます。

アプリと DB は別のプロセスなので、クエリのたびにネットワークの往復が発生します。競プロの言葉でいえば、DB への往復という大きな定数を持つ操作を O(N) 回やっています。

なぜ気づきにくいか

「各投稿について名前を引く」という自然な文章がそのままコードになっていて、読んでも悪く見えません。しかも手元のデータが 5 件なら一瞬で終わり、本番相当のデータ量と負荷で初めて表面化します。

スロークエリログでの見つけ方

pt-query-digest では、Calls が突出して大きい SELECT として順位表の上位に出ます。

テキスト

# Rank Query ID           Response time  Calls R/Call
# ==== ================== ============== ===== ======
#    1 0x4E61B1...         120.4s 54.7%  48200 0.0025 SELECT users

R/Call（1 回あたり）は小さいのに、Calls が数万回あって合計時間が 1 位。この形を見たら、そのクエリをコードから検索し、ループの中にいないかを確かめます。

JOIN で 1 つのクエリにまとめる

直し方の 1 つ目は、複数のテーブルと JOIN の実践です。

SQL
SELECT p.id, p.user_id, p.body, u.name
FROM posts p
JOIN users u ON u.id = p.user_id
ORDER BY p.created_at DESC
LIMIT 100

クエリと往復は、101 回から 1 回になります。 Go 側は Scan に &p.UserName を足すだけです。

IN でまとめて引いて map に載せる

直し方の 2 つ目は、必要な ID を集めてから 1 回のクエリでまとめて引く方法です。複数種類の付属データを引くときなど、JOIN で 1 本にしにくいときに使います。

Go
func fillUserNames(db *sql.DB, posts []Post) error {
	if len(posts) == 0 {
		return nil
	}

	// 1. 必要なユーザー ID を重複なく集める
	idSet := map[int]struct{}{}
	for _, p := range posts {
		idSet[p.UserID] = struct{}{}
	}
	args := make([]any, 0, len(idSet))
	placeholders := make([]string, 0, len(idSet))
	for id := range idSet {
		args = append(args, id)
		placeholders = append(placeholders, "?")
	}

	// 2. IN (...) で 1 回のクエリにまとめる
	query := "SELECT id, name FROM users WHERE id IN (" + strings.Join(placeholders, ",") + ")"
	rows, err := db.Query(query, args...)
	if err != nil {
		return err
	}
	defer rows.Close()

	// 3. 結果を map に載せる
	names := map[int]string{}
	for rows.Next() {
		var id int
		var name string
		if err := rows.Scan(&id, &name); err != nil {
			return err
		}
		names[id] = name
	}
	if err := rows.Err(); err != nil {
		return err
	}

	// 4. map から各投稿に埋める
	for i := range posts {
		posts[i].UserName = names[posts[i].UserID]
	}
	return nil
}

クエリ回数は、一覧の 1 回とこの 1 回の 2 回で固定になります。競プロでおなじみの「まとめて引いて、添字で配る」形です。文字列連結していますが、ユーザー入力はすべてプレースホルダ経由なので SQL インジェクションの心配はありません。

IN の組み立ては、ライブラリ sqlx の sqlx.In を使うと 1 行で書けます。

直したらベンチを回し、順位表からこのクエリが落ちたことを確認します。次章では、もう 1 つの典型「回数は少ないのに 1 回が重いクエリ」を扱います。