Very likely has nothing whatsoever to do with the execution plan. 15 seconds is far longer than SQL takes to compile anything other than a ridiculously complex query.

Restarting cleared the data cache, the cache of data pages. After the restart queries have to read the data from disk (slow), not cache (fast). Hence the first run of any query will be slower than the second or third or subsequent runs