Optimizations Possible - SQLServer
First of all be aware though that when you are querying on tables that large you have to expect it to take some time.  

That being said assuming you are using SQL 2008 or later you could try a filtered index on CLLab, however that makes several assumptions.


The number of rows where the Dept = "Lab" and Observe_Id = "Reviewed" is a relatively small percentage of the total number of rows.
This is an important enough query to warrant the extra write time to CLLAB for an additional index just for it.


If the answers to both of those are Yes (and of course SQL 2008 or higher) then try this.

CREATE NONCLUSTERED INDEX "IX_CLLAB_REVIEWED_LABS"
ON CLLAB (SSNO, COMPANY, DATEBACK)
WHERE DEPT = "LAB"
  AND OBSERVE_ID = "REVIEWED";


Really I would rather get rid of the subquery all together if possible but that would require more knowledge of the data and what you are trying to get out of the query.

Last but not least if you comment out the small subquery in the field list does it run significantly faster?  If so that part of the query could be incorporated into the main query as a LEFT OUTER JOIN and might save you some time.

It would look like this.

-- In the field list
FACILITY = CASE WHEN B.FACILITY = '' THEN D.FACILITY ELSE B.FACILITY END

-- The FROM &amp; WHERE Clauses
FROM CLLAB A
JOIN CLORDER B
    ON A.COMPANY = B.COMPANY
    AND A.ORDER_ID = B.ID
JOIN CLMASTER C
    ON B.ACCOUNT = C.ACCOUNT
LEFT OUTER JOIN CLDoctor D
    ON  B.PROVCODE = D.DOCTOR  
    AND B.FACILITY = ''          -- optionally. May be more efficient
                                 -- with different indexing
WHERE B.DEPT = 'LAB'
  AND A.DATEBACK NOT IN (.....)