After putting good indexes and optimizing the query, I could not achieve an optimized performance and I still received an unoptimized response from the SQL Server. On examination, I figured out that the culprit was statistics. The database that I was trying to optimize had auto update of the statistics was disabled.
Once I enabled the auto update of statistics, the database started to respond as expected. If you ever face situation like this, please do the following:
1) Enable Auto Creation of Statistics
2) Enable Auto Update of Statistics
3) Update Statistics for whole database