Searching from Database having billion records, which database should i use
You could use a parallel system such as Azure SQL DW. This would basically split your data up into sixty parts, and should be able to optimise just as well as your regular SQL database, but spreading the work out across sixty databases. You would still need to make sure that your design was optimal, in regard to table structures and indexing, but you should be able to shrink the size of your problem down by a large factor. Your 20 minutes could become half a minute quite easily.

Of course, there are probably good ways to tune your current system.