>>>>>
>>>>>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.