Performance problem with big query on first run
What can I do to make sure the query executes quickly enough every time?


It's unlikely that this is a query performance issue. You're doing very little IO, using very little CPU time, and the query isn't processing very much data. The likely solution will be to resolve the hardware or configuration issue that is causing your query to run for so long sometimes. In one of your executions the query 92636 ms of elapsed time but only used 546 ms of CPU time  That means that SQL Server was waiting for something for over 92 seconds during query execution. Based on your description of the problem it's likely that there's a severe IO problem on the server. 11000 physical reads isn't that much and what you're seeing isn't normal.

You didn't include your version of SQL Server, but to get more information about the problem I would look at wait stats. You seem to have control over the server so you can try taking a before and after snapshot of the sys.dm_os_wait_stats DMV and seeing which waits increase after the query finishes executing. That DMV is server wide so you'll want to avoid running other queries if possible. You can also reset the DMV immediately before running your query by running the following T-SQL:

DBCC SQLPERF ("sys.dm_os_wait_stats" , CLEAR);


The wait stats should let you confirm if IO is indeed the problem. You may need to work with the admin in charge of the VM or storage to resolve this issue.