N+1 はなぜ遅いのでしょうか

Question

N+1問題が発生したコードが遅いのは周知の事実だと思いますし、私も実体験として遅いことは確認していますが、

何が原因で遅いのでしょうか？

例えば以下のコードでN+1が発生しますが、(雰囲気を伝えるためのコードなので実際には動きません)

for group in groups.limit(10):
  for user in group.users:
    print(user.name)

クエリをgroup一覧を取得する際にeager loadingやjoinによってuser内容を一度に取得することにより実行速度が向上します。

両者の違いはクエリの実行数ですが、DBにおけるクエリの実行はそれほどオーバーヘッドがあるものなのでしょうか？それとも別の要因で遅くなっているのでしょうか？

オーバーヘッドの要因として思いついたものは以下の要因です

• クエリのパースや実行計画作成が遅い
• ディスクアクセスが発生する場合にシーケンシャルアクセスができない
• DBとプログラムとの通信が遅い

これらの要因が少ない場合にはN+1問題が発生した場合にも影響は少ないのでしょうか？

Answer 1

例えDBが

• オンメモリ(すべてメモリ上に展開されるため、ディスクアスクセスが存在しない)
• 組み込み(そのプロセスの中で実行されるため、プロセス間通信もネットワーク間通信も存在しない)

という場合でもN+1問題は発生する場合があるようです。サンプルを作成し、ベンチマークを取得してみました。

# frozen_string_literal: true
require 'active_record'
require 'sqlite3'
require 'benchmark'

# DB接続 SQLite オンメモリ
ActiveRecord::Base.establish_connection(
  adapter: 'sqlite3',
  database: ':memory:'
)

# テーブル及びモデル
ActiveRecord::Base.connection.create_table :groups do |t|
  t.text :name, null: false
end

ActiveRecord::Base.connection.create_table :users do |t|
  t.text :name, null: false
  t.integer :group_id, null: false
end

class Group < ActiveRecord::Base
  has_many :users
end

class User < ActiveRecord::Base
  belongs_to :group
end

# データ作成
group_size = 100
user_size = 10000

group_size.times do |i|
  group_name = "group#{i}"
  Group.create(name: group_name)
end

user_size.times do |i|
  user_name = "user#{i}"
  group_name = "group#{i % group_size}"
  User.create(name: user_name, group: Group.find_by(name: group_name))
end

# ベンチマーク
Benchmark.bm 10 do |r|
  r.report 'none' do
    list_none = []
    User.all.each do |user|
      list_none << [user.name, user.group.name]
    end
    # SELECT "users".* FROM "users"
    # SELECT  "groups".* FROM "groups" WHERE "groups"."id" = ? LIMIT ?
    #   user_size回繰り返す、N+1問題あり
  end

  r.report 'eager_load' do
    list_eager_load = []
    User.eager_load(:group).all.each do |user|
      list_eager_load << [user.name, user.group.name]
    end
    # SELECT "users"."id" AS t0_r0, "users"."name" AS t0_r1,
    #   "users"."group_id" AS t0_r2, "groups"."id" AS t1_r0,
    #   "groups"."name" AS t1_r1 FROM "users"
    #   LEFT OUTER JOIN "groups" ON "groups"."id" = "users"."group_id"
  end

  r.report 'preload' do
    list_preload = []
    User.preload(:group).all.each do |user|
      list_preload << [user.name, user.group.name]
    end
    # SELECT "users".* FROM "users"
    # SELECT "groups".* FROM "groups"
    #   WHERE "groups"."id" IN (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  end

  r.report 'includes' do
    list_includes = []
    User.includes(:group).all.each do |user|
      list_includes << [user.name, user.group.name]
    end
    # SELECT "users".* FROM "users"
    # SELECT "groups".* FROM "groups"
    #   WHERE "groups"."id" IN (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  end
end

実行結果

                 user     system      total        real
none         3.930000   0.050000   3.980000 (  3.987493)
eager_load   0.480000   0.010000   0.490000 (  0.502292)
preload      0.480000   0.010000   0.490000 (  0.487678)
includes     0.530000   0.010000   0.540000 (  0.543553)

noneがN+1問題があり、10001回クエリを発行します。eager_loadは1回、preloadとincludesは2回です。

結果はDBやORMによって変わる可能性があります。しかし、ディスクアクセスもプロセス間通信/ネットワーク間通信だけが原因となるわけではなく、クエリやORMの処理そのもの(クエリを作る、クエリ結果をオブジェクトに変換する)も負荷が高く、呼び出し回数が膨大の場合は問題となるようです。

ただ、注目すべくは、単純にクエリ数に比例するわけでは無いと言うことです。none(N+1問題あり)はeager_loadに比べて9倍ぐらいしか遅くありません(クエリの実行回数は10000倍違います)。N+1のNが少なければそれほどの差は出なくなるかも知れません。

上のベンチマークは組み込みでオンメモリなSQLiteでActiveRecordを使った場合に過ぎません。ORMを使わない、別のORMにする、と言った場合はどうなるか、ストアドプロシージャを使った実行計画のキャッシュがあった場合はどうなるか、OracleやMariaDBなど別のDBではどうなるかは実測しないとわかりません。テーブル構造やクエリ内容によっても変わってくると思います。結局は実際にベンチマークを取らないとどれだけ遅いかはわからないと思います。

Comments

[mrasu]

ありがとうございます。
確かに、僕の環境でも同じ傾向が現れました。
簡単な原因だけではないのですね。納得できました。
原因が深いこと、またこれ以上はおっしゃるとおり各実装に依存する部分が大きいと思いますので、
自分で調べてみようと思います。本当にありがとうございました。

Answer 2

コンピュータ処理において、データのやり取りは、

1. CPU - 二次キャッシュ
2. CPU - メインメモリ
3. CPU - メインメモリ - 別プロセス
4. CPU - メインメモリ - HDD
5. CPU - メインメモリ - ネットワーク

の順で、数倍から数十倍遅くなります。

N + 1 が起きてない場合、以下が1回だけ行われます。（SQLの生成は省いています）

A APサーバから 5 （SQLの送信）
B DBサーバ内で 3 （SQLの受信）
C DBサーバ内で 2と4 （SQLの実行）
D DBサーバから 5 （結果の転送）
E APサーバ内で 3 （結果の受信）

N + 1 問題が起きると、以下がN + 1回 繰り返されます。

A' APサーバから 5 （SQLの送信）
B' DBサーバ内で 3 （SQLの受信）
C' DBサーバ内で 2と4 （SQLの実行）
D' DBサーバから 5 （結果の転送）
E' APサーバ内で 3 （結果の受信）

C'の部分は、繰り返しを合計した処理量と、1回で処理した C とは、ほぼ一致します。

しかし、コンピュータ処理で特に遅い

CPU - メインメモリ - 別プロセス
CPU - メインメモリ - ネットワーク

の部分が、N回増えることになりますから、それがパフォーマンスが著しく劣化する原因となります。

Comments

[mrasu]

ありがとうございます。
3,5が遅いこと理解しました。
また、回数がN回増えることも理解しました。

では、データのやり取りが遅いということは、データ量が重要な要素となると思うのですが、
その場合、N+1問題が発生するかどうかにかかわらずデータ量が変化しない場合(十分な量を一度に取らずにN+1回に分けて取得する場合)にはなぜ遅くなるのでしょうか？
データ量よりもやり取りの回数のほうが重要な要素なのでしょうか？

[kantomi]

処理に必要なデータ量は、1回で処理しても、N＋1で処理しても同じなのです。
違うのなら、「違う処理」ということになりますね。

[mrasu]

はい。そのつもりで質問しました。
ということは、やはりやり取りをするという「行為」自体が負荷になるということでしょうか？
であれば、どんなに速いDB(例えばRedis)であってもN+1の影響は免れず、
同一サーバー上であってもネットワークの影響が消えるだけ(といってもかなり速くなると思いますが)で、
いくらIOを削ろうとも別プロセスと通信すること自体が速度低下の原因であり、
本質的にはDBに限った問題ではなく、偶々DBとのやり取りが多かったためにDBの部門で有名になったということなのですね。

[kantomi]

比較するとき、ベースを変えたら意味がない！
RedisはKVSなので、N+1しか無理でしょう。
HDDへのアクセスはありませんし、データの保存形式も、RDBMSと違って直接データを読むので高速です。
上の文章でいうと、Cの構造が全く違うため、比較しても意味がありません。

[mrasu]

申し訳ありません。ベースを変えたつもりがありませんでした。

「N+1が遅いのは、プロセス間通信やネットワーク通信によるオーバーヘッドが原因である」ということを確認したつもりでした。

Answer 3

「N+1問題」と言った場合、普通は「データベースからN件のデータを取得する過程で、N+1件のクエリが発行される」ということを指すと思います。

まず、次の二つの処理にかかる時間を考えてみて下さい。
(a) データベースに対してクエリを発行してその結果のデータを受け取る処理。
(b) メモリ内にあるデータを加工してメモリの別の場所に格納する処理。
前者 (a) の処理は後者 (b) よりはるかに時間がかかることは、直感的にわかると思います。

次に、「N+1問題」が発生していない場合と発生している場合をくらべてみます。

• 「N+1問題」が発生していない場合、1回のクエリ発行で全件のデータを取得してメモリに格納します。
  -- (a) が1回、(b) がN回行われます。

• 「N+1問題」が発生している場合、N+1回のクエリ発行で全件のデータを取得してメモリに格納します。
  -- (a) がN+1回、(b) がN回行われます。

あとのほうが、(a)N回分だけ、余計に時間がかかることがわかりますね。たとえば、目的のテーブルに100万件のレコードがあったとしたら、クエリ100万回分だけ時間がかかります。

また、はじめに考えた通り、(a)N回分は、同じ回数の(b)N回分よりも、桁違いに長い時間です。ですから、「N+1問題」が発生すると、処理全体が目に見えて遅くなります。

Comments

[mrasu]

回答ありがとうございます。
ただ、申し訳ありません。私が知りたかったのは、
> 前者 (a) の処理は後者 (b) よりはるかに時間がかかることは、直感的にわかると思います。
この部分を理解したく質問しました。

なぜ、データベースへのアクセスが遅いのかを知りたかったのです。
単一のプログラムではない以上遅くなることは理解できますが、どのような要因で遅くなっているのかを知りたいのです。

[goute]

データベースに限った話ではなくファイルなどでも同じですが、物理的にほかのところへアクセスする（IOがある）というのはコストが大きいです。
相手を探しに行く→接続→読み取り（書き込み）→接続の解放（ほかにもあります）などの処理がありますので。