クエリの処理時間を速くしたい

Question

前提

ある期間内のレコードを取得する以下のようなクエリがあるのですが、レコード数が増えたことで処理が完了するまで時間がかかるようになってきました。
そこで、インデックスを貼ろうと思っています。
貼るとしたら、start_timeかused_flgなのかなと思いました。
しかし、あまり変化はありませんでした。良い方法または改善があれば教えていただきたいです。。

・使用テーブル：histories
・結合するテーブル：users, stores

外部キー
・store_id, user_id

インデックス
・usersテーブル

key_name	colum_name
index_users_info	first_name
index_users_info	last_name
index_users_info	nick_name

使用しているソースコード

// model histoy.rb

def find_records(params)
    record =  self.joins(:user, :store)
        .select('histories.*, users.first_name, users.last_name, users.nick_name, stores.name')
        .where("first_name LIKE ?",  "%#{first_name}%")
        .where("last_name LIKE ?",  "%#{last_name}%")
        .where("nick_name LIKE?",  "%#{nick_name}%")
        .where("start_time BETWEEN '#{start_at} AND '#{end_at}'")
        .where("used_flg LIKE ?",  "%#{used_flg}%")
        .order("start_time")

    if params[:store].present?
        record = record.where("store_id = ?", "#{store_id}")
    end
    return record
end

試したこと

start_timeにインデックスを付けてなかったので、インデックスを貼りましたが処理時間はあまり変わりませんでした。

create indx start_at_for_find_record on histories(start_time)

Answer 1

LIKE があるので遅いのですね。それも ほとんどが LIKE。
これでは index使っても高速化の効果は無いです。
LIKE ですと全レコードなめるので。

LIKE を諦めるか高速化を諦めるか

Answer 2

LIKEにワイルドカード（%）を使っていますが、これは必須ですか？
index_users_infoインデックスが作られているようですので、ワイルドカードを外すことができればインデックスが有効になり速度の改善が見込まれると思います。