期間を絞った処理がしたいけどcreated_atにインデックスがなくて辛いときの処方箋

あらすじ

すごく巨大になってしまったログのテーブルで、直近記録されたエラーを探すために日付を絞って、

Log.where('created_at > ?', 24.hours.ago).where(type: 'error')

って叩きたいのだけど、 created_at にインデックスなんて張ってないので全力でフルテーブルスキャンになって結果が返ってこない😱

前提

• created_at にインデックスなんて張ってない
• でも id は auto_increment でだいたい日時順に振られてることが期待できる

解決策

インデックスがなければ自分で二分探索すればいいじゃない！ ってのを書いたのでご活用ください。

class ActiveRecord::Base
  # @param [Time] created_at
  # @return [ActiveRecord::Base]
  def self.find_closest_created_at(created_at)
    return if self.last.created_at < created_at

    high = self.last.id
    low = self.first.id

    while low <= high
      mid = (high - low) / 2 + low
      closest = self.select(:id, :created_at).where('id >= ?', mid).first
      return if closest.nil?
      return self.find(closest.id) if high == low

      if created_at > closest.created_at
        low = mid + 1
      else
        high = mid
      end
    end
  end
end

initializer に入れるか、今すぐ必要であればそのまま rails console に貼り付けても動く。

1000 万行で 17 回、 1000 億行でも 26 回の PRIMARY SELECT で、指定した時間を含むそれ以降の時間で一番近い created_at を持つ行を発見できる。

使い方

errors = Log.
  where('created_at >= ?', 24.hours.ago).
  where(type: 'error').
  count

ってクエリを叩きたいところを、こんな感じに書き換える。

one_day_ago = Log.find_closest_created_at(24.hours.ago)

errors = Log.
  where('id >= ?', one_day_ago.id).
  where(type: 'error').
  count

これなら手元の 12 億行あるテーブルでも大体 60〜70ms 程度で結果がでます。

Explain

前者の created_at を直接使うクエリだと type=ALL になってしまってフルテーブルスキャンになってしまう。

mysql> explain SELECT `logs`.* FROM `logs`  WHERE (created_at >= '2017-03-01 12:00:00') AND `logs`.`type` = "error";
+----+-------------+-------+------+---------------+------+---------+------+------------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows       | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+------------+-------------+
|  1 | SIMPLE      | logs  | ALL  | NULL          | NULL | NULL    | NULL | 1000000000 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------------+-------------+
1 row in set (0.05 sec)

これが id 指定になると type=range になるのでだいぶマシで、かなり人道的な時間で返ってくる。

mysql> explain SELECT `logs`.* FROM `logs`  WHERE (id >= 1165448944) AND `logs`.`type` = "error"
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows   | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+
|  1 | SIMPLE      | logs  | range | PRIMARY       | PRIMARY | 4       | NULL | 388992 | Using where |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+-------------+
1 row in set (0.00 sec)

なお id を探すための数十回のクエリは全部 type=const なので一瞬で返ってくる。

mysql> explain SELECT `logs`.`id`, `logs`.`created_at` FROM `logs`  WHERE `logs`.`id` = 193921304;
+----+-------------+------------+-------+---------------+---------+---------+-------+------+-------+
| id | select_type | table      | type  | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+------------+-------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | activities | const | PRIMARY       | PRIMARY | 4       | const |    1 | NULL  |
+----+-------------+------------+-------+---------------+---------+---------+-------+------+-------+
1 row in set (0.07 sec)

References

• もともとGistに書きなぐってた英語版