I am having a weird issue when a running a query that joins some semi-large tables (one table is about 2 million rows and the other about 21 million) together. What happens is the query does not run within the same time frame consistently. If I run the query on a new connection in SSMS it takes about 45 seconds to complete. After it completes if I hit the execute button again it takes almost 4 minutes to complete. If I then open a new query (connection) and execute the query it takes about 45 seconds again. These queries are being run from the server and I can consistently reproduce this.

Any help on what is going on and how to fix is helpful.