DB の実行計画を見れば？
インデックスを使わずに、全件探索でもしてるのでは？

2分探索なら、2 ^ 10 = 1,024
2 ^ 12 = 4,096

つまり、12回探索するだけ

ミックの本でも読んだ方がよい