Yes - one needs to ensure that the data is well indexed - that is reasonable.

But indices does not need to yield a single result. It is OK that indices reduce the result set to tens or couple of hundreds of result. That is well within the performance requirements (... of our app)