Slow query that times-out my application, any advice?
The most likely case is either parameter sniffing or, less likely, bad statistics, with a very unlikely side of index split pages (thousands of rows is pretty small for that).
To prove parameter sniffing:

Turn on profiler or a trace for your particular Session_ID; watch Reads, Writes, CPU, Duration for events SQL:BatchCompleted and RPC:Completed

Invalidate the query cache for your particular query, which you can do by either DBCC FREEPROCCACHE  sql_handle
a. Note that if you do DBCC FREEPROCCACHE without any arguments, it frees the entire procedure cache, which has serious though short lived bad performance impacts on production boxes, since EVERY query plan now needs to be rebuilt.

Run your query for the most common set of parameters

Run your query for the most common set of parameters (again; ignore the results from #2, since they may include caching data)

Run your query for the least common, most unusual (index statistics wise) set of parameters.

Run your query for the least common, most unusual (index statistics wise) set of parameters (again; ignore the results from #4, since they may include caching data)

Do steps 1-5 again, EXCEPT do 1,2,5,6,3,4 - i.e. do the least common first, and the most common second

If your results on the second run of each set are significantly different on reads, writes, and/or CPU, you've proved parameter sniffing!  If not, you may still have parameter sniffing issues on other combinations, or you may not.


If it takes arguments that vary from division to division, it's probably parameter sniffing.  Read Erland Sommarskog's article Dynamic Search Conditions in T‑SQL which covers several ways of handling the various execution plans required.  WITH RECOMPILE is the quick band-aid, multiple stored procedures is the cadillac solution, and very careful dynamic SQL is another option (NEVER concatenating parameters into the SQL statement, only using them as actual parameters and as part of IF statements that put blocks of code in).
You can ALTER INDEX ALL on  REBUILD and it'll also update statistics, and see if that makes a difference.  Use ONLINE=ON if you're on Enterprise edition and need to, otherwise it's going to lock those tables.
Oh - make sure all tables have high cardinality clustered indexes first!