インデックス張るのコスト高いけど、やっぱり効果は大きいよ。あと、PostgreSQLならCREATE INDEX CONCURRENTLYで運用しながら貼れるよ（もちろん完了までは時間が掛かる）