実際に動かしてみてわかった、N+1問題の恐ろしさ

## はじめに
ご閲覧いただきありがとうございます！
Sun* という会社で Backend Engineer をやっている 24 卒の Campanule と申します。
普段は Ruby on Rails を使った Web アプリの開発を行っております。

今回が初投稿となります。どうぞお手柔らかにお願いいたします。

本記事ではデータベースを用いる際にいつも頭を悩まされる **N+1 問題** について簡単に説明し、またパフォーマンスの簡易的な測定をしてみようと思います。

## 目的
- N+1 問題 とは何なのかざっと理解したい
- パフォーマンスの測定を行い、N+1 問題 の影響について考えたい

## 想定読者
- N+1 問題 を知らない方、あるいは言葉だけ聞いたことがある方
- N+1 問題 によるパフォーマンスの低下が気になっている方

## N+1 問題とは
こちらがわかりやすいです。

https://qiita.com/muroya2355/items/d4eecbe722a8ddb2568b

簡単に言うと、あるテーブルのレコード N 件 に対応した別テーブルのレコードを引っ張るとき、別テーブルに対して N 回 クエリを発行してしまう問題です。（1 回 のクエリを発行したあとに N 回 のクエリを発行するため、直感的には 1+N 問題 とも言えなくもない…かも）

最適化すれば多くても数回のクエリ発行ですむため、これは大変な問題です。

## 対策
対策としては、関連するテーブルの要素をあらかじめ取得しておくとよいです（**eager loading** とよばれます）。これによりクエリの個数を N+1 個 から劇的に減らすことができます。Rails なら `eager_load`, `preload`, `includes` などを用いて実現できます。それぞれの違いについては以下の記事をご参考ください。

https://qiita.com/k0kubun/items/80c5a5494f53bb88dc58

## パフォーマンスの違い
eager loading を行ったとき、ランダウの記号を用いるとクエリ発行回数は $O(1)$ 回であり、アプリ側での処理件数は $O(N)$ 回となります。それに対し、N+1 問題 が発生したとき、クエリ発行回数が $O(N)$ 回と膨れ上がり、アプリ側での処理件数は同じく $O(N)$ 回です。要するに、クエリ発行回数に対する計算量が大きくなってしまう問題です。

ランダウの記号については以下を参照。

https://manabitimes.jp/math/1200

「あれ？総合したときの計算量変わらなくね？」と思った方がいらっしゃるかもしれません。しかし、アプリケーションにより 1 回の処理を行うのと比べて、**DB に対して 1 回クエリを発行するほうが遥かに遅い**です。
そのため、定数倍の増加といった形で考えてもよいでしょう。この定数倍が意外と馬鹿になりません。

## 計測してみた
今回は Rails と MySQL を用いてやってみました。

### 前提
前提として、company, user, pet の 3 モデル（名前は適当です）を用意し、conpany - user 間は 1 対 多、user - pet 間は 1 対 1 の関係にあるものとします。
また、DB に対するチューニングは一切行っていません。

計測の際には、Rails 標準の benchmark を用いています。

https://qiita.com/gggk/items/af9008e3ec9c3384e7ca

以下のコードを用いて、全ユーザが飼っているペットの名前を取得します。

```rb:N+1 problem
company = Company.last

###ここから計測###
users = company.users

users.each do |user|
  puts(user.pet.name)
end
###ここまで計測###
```

```rb:eager loading
company = Company.last

###ここから計測###
users = company.users.includes(:pet) # eager loading

users.each do |user|
  puts(user.pet.name)
end
###ここまで計測###
```

### 結果
#### N = 20
| eager loading   | N+1問題   | 差（倍率）  | 
| --- | --- | --- | 
| 15.5ms   | 100.2ms   | 6.46倍   | 

データ数が小さいこともあり、まだまだ使える範囲内でしょう。
#### N = 100
| eager loading   | N+1問題   | 差（倍率）  | 
| --- | --- | --- | 
| 20.7ms   | 328.5ms   |  15.87倍  | 

まだデータ数が小さいため、なんとか使えます。

#### N = 2000
| eager loading   | N+1問題   | 差（倍率）  | 
| --- | --- | --- | 
| 118.1ms   | 3518.7ms   | 29.79倍   |

この辺りから全件取得のためには eager loading が必須になってきます。N+1 問題 が発生していても使えないことはないですが、正直使いたくはないです。

#### N = 10000
| eager loading   | N+1問題   | 差（倍率）  | 
| --- | --- | --- | 
| 523.0ms   | 24340.9ms   | 46.54倍   | 

この時点で eager loading をしないともはや使い物になりません。ユーザ数が多くなればそのぶんパフォーマンスに対する考慮の優先度が高くなるでしょう。

#### N = 200000
| eager loading   | N+1問題   | 差（倍率）  | 
| --- | --- | --- | 
| 13294.5ms   | 534503.6ms   | 40.20倍   | 

もはや N+1 問題 が発生していると日が暮れてしまいますね…。読み込みだけで 9 分弱費やしています。eager loading をしても 10 秒ちょいと長いですが、20 万件のデータを全件取得しているのでデータ数から考えれば妥当…かもしれません。

## まとめ
N+1 問題 って思ったより怖かった…！
データが増えてくると、特に気をつけなければいけない問題になってきます。ふとしたときに発生しうるので、Rails なら **bullet** を入れておくと注意喚起が入るのでおすすめです。

https://qiita.com/sazumy/items/7157446d7c3bfe377d63

考えたくもないですが、N+1 問題 に N+1 問題 をネストしてしまうなんてことがあれば最悪クエリ発行回数が $O(N^2)$ 回になってしまう可能性があるので、DB 絡みのネストを行う際には特に気をつけましょう…！

パフォーマンスに関する記事としては他にも Index に関する記事を書くつもりなので、よければ気長にお待ちいただけると幸いです！

## 参考

https://zenn.dev/goldsaya/articles/3af48dadc6cc0f

https://zenn.dev/d0ne1s/articles/fdf4832d478da6

https://qiita.com/asksaito/items/59e0d48408f1eab081b5

## PR
Sun*では、一緒に働く仲間を募集しています。
まずはカジュアル面談からでもお気軽にご応募ください！

▼会社情報はこちら

https://sun-asterisk.com/

▼募集要項・ご応募はこちら

https://sun-asterisk.com/recruitment/