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


# あらすじ

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

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

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

# 前提

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

# 解決策

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

```ruby
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` を持つ行を発見できる。

# 使い方

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

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

```ruby
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に書きなぐってた英語版](https://gist.github.com/tnj/38cfd344d539f2e2882dce10971bce73)