Rerunning query in the same connection takes significantly longer 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.
With that many rows, moving the results from the server to the client will be a significant part of the elapsed time.  Eliminate variablity in that part by wrapping your query in some way such as:

select
    count(*)
from (
    {your query here}
) as xx


This way the network transfer will be a minimal part of the elapsed time and you can eliminate it from your enquiries.