>>>>>>>
>>>>>>>When you run this query with Actual Execution plan information, what you get?
>>>>>>
>>>>>>I don't know what exactly to tell you. I get an Execution Plan tab displayed with some graphical stuff in it but no particular message that I can tell you. What do you need to know?
>>>>>
>>>>>You have the best performance when you have [index seek] in Execution plan, worst is when you have [Table Scan].
>>>>>Try to remove WHERE and see if you get this faster.
>>>>>If yes, then should think about workaround.
>>>>
>>>>I removed the where and it wasn't noticeably faster. Update: it actually was about 10 seconds faster, without was 20 seconds and with was 30.
>>>>
>>>>The execution plan shows index seeks mostly but a couple "Key Lookup (Clustered)"
>>>>
>>>>One of those shows as 81% for "Invoices.PK_Invoices"
>>>
>>>Check : http://blog.sqlauthority.com/2008/03/27/sql-server-2005-find-index-fragmentation-details-slow-index-performance/
>>
>>I've tried doing the rebuild of the indexes but I'm not sure I'm doing it right.
>>
>>I ran the suggested query which shows me the indexes with their fragmentation. So for instance PK_AirWayBills has fragmentation of ninety something
>>
>>Since this is the Primary Key index on my airwaybills table I try this:
>>
>>ALTER INDEX ALL ON airwaybills REBUILD
>>
>>This reduced the fragmentation, but only down to 62.5
>>
>>Having done this on all the tables that had fragmentation over 40, I tried my query again but it hasn't improved.
>
>If you preselect data in the subquery in the where into the temp table and use it instead, will you get any speed imrpovement?

No, I've tried using temp tables for the subquery for the NOT IN part and also for the invoice total but if anything it slowed it down