exists?で起きるN+1問題に対処するためにSetを使った話

課題：データを弾くためにN+1問題が発生していた

数年前に実装した、CSVデータをDBにインポートするためのプログラムがありました。単にインポートするだけならいいのですが、除外リストに登録済のデータは弾いてほしい、という要望があり、そのように実装していました。

以下、ダミーのプログラムです。モデル名やCSVの内容は変えてあります。

require 'csv'

csv = CSV.read('list.csv', { headers: true, return_headers: false, skip_blanks: true, encoding: 'UTF-8' })
import_data = csv.reject do |row|
  name = row['名前']
  age = row['年齢']
  hobby = row['趣味']

  # 除外リストに存在するデータは弾く
  IgnoreUser.exists?(name: name, age: age, hobby: hobby)
end

users = import_data.map do
  name = row['名前']
  age = row['年齢']
  hobby = row['趣味']
  User.new(name: name, age: age, hobby: hobby)
end
User.import(users) # activerecord-importでバルクインサートする

しかし、この実装だと、CSVファイルの行数だけIgnoreUser.exists?が実行されてしまいます。が、それも仕方ないかな…と考えていました。

EffectiveRuby読書会で学んだことを活かす

ここで、5〜7月で実施していたEffectiveRuby読書会で学んだことで、このN+1問題を解決する方法を思いつきました。それが、StructとSetを使う方法です。

Structは、データクラスを作るのを簡単にするための組み込みライブラリで、SetはRubyで集合を扱うための標準ライブラリです。

class Struct (Ruby 3.0.0 リファレンスマニュアル)

library set (Ruby 3.0.0 リファレンスマニュアル)

Structで定義すると、サブクラスが作られます。そのサブクラスのオブジェクトの配列をSetに入れるというアイデアです。Setは内部記憶としてHashを使うため、include?メソッドを使ったときの探索がO(1)になるという特長があります。ちなみにArrayでinclude?を呼ぶと、線形探索なので最悪の場合は計算量がO(N)になり、Nが大きくなればなるほど遅くなります。

Structは設定される値が全部同じだと、==がtrueになります。

IgnoreUserStruct = Struct.new(:name, :age, :hobby)
a = IgnoreUserStruct.new("a", 1, "a")
b = IgnoreUserStruct.new("a", 1, "a")
a == b # => true

Setを使って修正する

そこで、修正したコードがこちら。

require 'csv'
require 'set'

# 構造体を定義
IgnoreUserStruct = Struct.new(:name, :age, :hobby)

# 除外リストのデータを構造体の集合にする
# DBへのアクセスはこの箇所のみ
ignore_users = IgnoreUser.find_each.map { |ignore_user|
  IgnoreUserStruct.new(ignore_user.name, ignore_user.age, ignore_user.hobby)
}.to_set

csv = CSV.read('list.csv', { headers: true, return_headers: false, skip_blanks: true, encoding: 'UTF-8' })
import_data = csv.reject do |row|
  name = row['名前']
  age = row['年齢']
  hobby = row['趣味']

  # 除外リストに存在するデータは弾く
  # 集合に対して除外データを確認するのでDBへのアクセスは起きない
  ignore_users.include?(IgnoreUserStruct.new(name, age, hobby))
end

# 以下略

これで、N+1問題をやっつけることができました。めでたしめでたし！

ベンチマークを取る

N+1問題は解決したものの、実際にはどれくらい速くなったのかが気になります。そこで、benchmark-ipsを使ってベンチマークを取りました。

前提

ignore_usersテーブルには1万件のデータを登録済み
CSVファイルの行数は1万行

ignore_usersテーブルへのデータ投入は、PostgreSQLのgenerate_series関数を使いました。

bin/rails dbconsoleでpsqlを開きます。そこから、以下のクエリを流し込んで1万件のデータを生成しました。

truncate ignore_users;
insert into ignore_users(name, age, hobby, created_at, updated_at)
select
  format('名前%s', i), 
  i,
  format('趣味%s', i),
  clock_timestamp(),
  clock_timestamp()
from
  generate_series(1, 10000) as i;

これで準備はできました。

ベンチマークプログラム

rails runnerで実行できるように、script/benchmark.rbにファイルを作りました。 bin/rails runner script/benchmark.rb で実行します。

また、上記ではfind_each.mapで除外リストのモデルから構造体を生成していましたが、これpluckでやればモデルの生成処理が不要になるから更に速くなるんじゃないか？と考えて、それを追加してます。

exists?
Array#include?
Set#include?(model version)
Set#include?(pluck version)

なお、このベンチマークプログラムもダミーです（モデル名とかCSVの内容とかは変えてあります）

require 'csv'
require 'set'

# 構造体を定義
IgnoreUserStruct = Struct.new(:name, :age, :hobby)

Benchmark.ips do |x|
  csv = CSV.read('list.csv', { headers: true, return_headers: false, skip_blanks: true, encoding: 'UTF-8' })
  
  x.report('exists?') do
    csv.reject do |row|
      name = row['名前']
      age = row['年齢']
      hobby = row['趣味']

      IgnoreUser.exists?(name: name, age: age, hobby: hobby)
    end
  end

  x.report('Array<Struct>.include?') do
    ignore_users = IgnoreUser.find_each.map do |ignore_user|
      IgnoreUserStruct.new(ignore_user.name, ignore_user.age, ignore_user.hobby)
    end
    
    csv.reject do |row|
      name = row['名前']
      age = row['年齢']
      hobby = row['趣味']

      ignore_users.include?(IgnoreUserStruct.new(name, age, hobby)
    end
  end

  x.report('Set<Struct>.include? model version') do
    ignore_users = IgnoreUser.find_each.map { |ignore_user|
      IgnoreUserStruct.new(ignore_user.name, ignore_user.age, ignore_user.hobby)
    }.to_set
    
    csv.reject do |row|
      name = row['名前']
      age = row['年齢']
      hobby = row['趣味']

      ignore_users.include?(IgnoreUserStruct.new(name, age, hobby)
    end
  end

  x.report('Set<Struct>.include? pluck version') do
    ignore_users = IgnoreUser.in_batches.flat_map { |records|
      records.pluck(:name, :age, :hobby).map { |data| IgnoreUserStruct.new(*data) }
    }.to_set
    
    csv.reject do |row|
      name = row['名前']
      age = row['年齢']
      hobby = row['趣味']

      ignore_users.include?(IgnoreUserStruct.new(name, age, hobby)
    end
  end
  x.compare!
end

ベンチマーク結果

以下が、実行結果です。

bin/rails runner script/benchmark.rb
Warming up --------------------------------------
             exists?     1.000  i/100ms
Array<Struct>.include?
                         1.000  i/100ms
Set<Struct>.include?     1.000  i/100ms
Set<Struct>.include? pluck version
                         1.000  i/100ms
Calculating -------------------------------------
             exists?      0.035  (± 0.0%) i/s -      1.000  in  28.891907s
Array<Struct>.include?
                          0.057  (± 0.0%) i/s -      1.000  in  17.419491s
Set<Struct>.include?      2.386  (± 0.0%) i/s -     12.000  in   5.045444s
Set<Struct>.include? pluck version
                          3.810  (± 0.0%) i/s -     20.000  in   5.252635s

Comparison:
Set<Struct>.include? pluck version:        3.8 i/s
Set<Struct>.include? model_version:        2.4 i/s - 1.60x  (± 0.00) slower
Array<Struct>.include?:        0.1 i/s - 66.36x  (± 0.00) slower
             exists?:        0.0 i/s - 110.07x  (± 0.00) slower

予想通り、DBからデータを取得した際にIgnoreUserモデルを生成しない分、Setを使ったpluckバージョンが最も速いという結果になりました。 Array#include?はexists?よりも速いとはいえ、66倍も遅い結果に。 exists?を使った結果は110倍も遅い結果になりました。

SetとStructを使うと超速くなりますね！

データが増えたらどうなる？

とはいえ、ignore_usersテーブルに1万件程度なので、これが10万件とか100万件とかになってきたらexists?のほうが速くなるんじゃないのー？と思って、それもベンチマークとってみました。

10万件の場合

ignore_usersテーブルには10万件のデータを登録済み
CSVファイルの行数は1万行(変わらず)

以下、結果です。

bin/rails runner script/benchmark.rb
Warming up --------------------------------------
             exists?     1.000  i/100ms
Array<Struct>.include?
                         1.000  i/100ms
Set<Struct>.include? model version
                         1.000  i/100ms
Set<Struct>.include? pluck version
                         1.000  i/100ms
Calculating -------------------------------------
             exists?      0.010  (± 0.0%) i/s -      1.000  in 102.770187s
Array<Struct>.include?
                          0.005  (± 0.0%) i/s -      1.000  in 216.871624s
Set<Struct>.include? model version
                          0.262  (± 0.0%) i/s -      2.000  in   7.638904s
Set<Struct>.include? pluck version
                          0.436  (± 0.0%) i/s -      3.000  in   6.878924s

Comparison:
Set<Struct>.include? pluck version:        0.4 i/s
Set<Struct>.include? model version:        0.3 i/s - 1.67x  (± 0.00) slower
             exists?:        0.0 i/s - 44.83x  (± 0.00) slower
Array<Struct>.include?:        0.0 i/s - 94.61x  (± 0.00) slower

1位は変わらず、Setを使ったpluckバージョンが最も速いという結果になりました。 exists?を使った結果は44倍なので、多少縮まりましたが、全然遅いです。 Array#include?は遂にexists?よりも遅くなり、94倍という結果になりました。

100万件の場合

ignore_usersテーブルには100万件のデータを登録済み
CSVファイルの行数は1万行(変わらず)
Array#include?は遅くなりすぎて耐えられないのでベンチマークから外す
Setのモデルバージョンはやめてpluckのみにする

以下、結果です。

bin/rails runner script/benchmark.rb
Warming up --------------------------------------
             exists?     1.000  i/100ms
Set<Struct>.include? pluck version
                         1.000  i/100ms
Calculating -------------------------------------
             exists?      0.002  (± 0.0%) i/s -      1.000  in 402.106370s
Set<Struct>.include? pluck version
                          0.043  (± 0.0%) i/s -      1.000  in  23.170393s

Comparison:
Set<Struct>.include? pluck version:        0.0 i/s
             exists?:        0.0 i/s - 17.35x  (± 0.00) slower

100万件でも、Setを使ったpluckバージョンのほうが速いという結果になりました。 exists?を使った結果は17倍なので、だいぶ縮まりました。

しかし、Setを使うバージョンは100万件のデータをRubyのオブジェクトとしてメモリに持っている状態なので、メモリ使用量が気になりますね。その点でいえば、exists?はメモリはあまり使わなくて済むでしょうけど、遅いは遅いですね…。

なんとなくでいいから、どれくらいメモリ使ってるかなーとMacのアクティビティモニタを眺めていたら、100万件の場合は420MBくらいが上限だったのでまぁそれくらいならまだSetを使ってもいいのかな？という気がします。なんといってもまだまだ17倍も速いので。

まとめ

exists?で起きるN+1問題はSet + Structでかなり対応できそうです！ Structを作るには、pluckを使うと速く、簡潔になります。

EffectiveRubyを読んでよかった！

Effective Ruby

作者:Peter J.Jones
翔泳社

Amazon

patorashのブログ

方向性はまだない