Optimizing queries vs. adding indexes I have this very old and SLOW query that I am trying to optimize, but I am not sure I can do anything to it, but add more indexes on columns involved in WHERE, JOIN and ORDER BY.

Query:

SELECT TOP 400 jobticket.jobnumber, jobticket.typeform, jobticket.filename, jobticket.req_number, jobticket.reqd_del_date, jobticket.point_of_contact, jobticket.status, jobticket.DapsDate, jobticket.elpod, job_info.IDOrderMaskedStatus, job_info.job_status, job_info.SalesID, job_info.location, job_info.TOMetadataID 
FROM jobticket WITH (NOLOCK) 
INNER JOIN job_info WITH (NOLOCK) ON job_info.jobnumber = jobticket.jobnumber 
WHERE  
(
    NOT(
        (jobticket.status = 'Complete' OR jobticket.status = 'Completed') 
         and (job_info.job_status = 'Actualized' OR job_info.job_status = '' 
              OR job_info.job_status = 'Actualized Credit Billed' 
              OR job_info.job_status = 'DWAS Actualized' OR job_info.job_status = 'DWAS Actualized Credit Billed'
             )
        )  
    or 
    ((SELECT COUNT(job_status) AS Expr1 FROM tblConsolidatedBilling AS tblConsolidatedBilling_1 WITH (NOLOCK)  
      WHERE  (job_status &lt;&gt; 'Actualized' 
      AND  job_status &lt;&gt; 'Actualized Credit Billed') 
      AND (master_jobnumber = jobticket.jobnumber)) &gt; 0) 
) 
and (jobticket.status != 'Waiting Approval' or (jobticket.status = 'Waiting Approval' and jobticket.DPGType is null))  
and jobticket.typeform &lt;&gt; 'todpg'  
and ((job_info.isHidden &lt;&gt; 1 or job_info.isHidden is null) and job_info.isInConcurrentRelease is null)  
and job_info.deleted != '1' 
and jobticket.status != 'New Job'  
and jobticket.status != 'PRFYCLSFD'  

ORDER BY 
job_info.expediencyLevel DESC, 
jobticket.jobnumber DESC


Execution Plan:


In all honesty I don't know what to do with this query. 

Should I add individual nonclustered indexes on all columns involved in WHERE JOIN and ORDER BY?

There are many indexes on these tables, but I am not sure whether they are helpful in this query:
You have a whole lot of looping going on
Give this a try
The exists will be faster then count
And bring stuff up into the join can help the optimizer  

SELECT TOP 400 jobticket.jobnumber, jobticket.typeform, jobticket.filename, jobticket.req_number, jobticket.reqd_del_date, jobticket.point_of_contact, jobticket.status, jobticket.DapsDate, jobticket.elpod
     , job_info.IDOrderMaskedStatus, job_info.job_status, job_info.SalesID, job_info.location, job_info.TOMetadataID 
 FROM jobticket WITH (NOLOCK) 
 JOIN job_info  WITH (NOLOCK) 
       ON job_info.jobnumber = jobticket.jobnumber 
      and jobticket.typeform &lt;&gt; 'todpg'  
      and (    (job_info.isHidden &lt;&gt; 1 or job_info.isHidden is null) 
            and job_info.isInConcurrentRelease is null 
          )  
      and job_info.deleted &lt;&gt; '1' 
      and jobticket.status not in ('New Job', 'PRFYCLSFD') 
      and (     jobticket.status != 'Waiting Approval' 
            or (jobticket.status  = 'Waiting Approval' and jobticket.DPGType is null) 
          )         
WHERE jobticket.status    not in ('Complete','Completed') 
   or job_info.job_status not in ('Actualized','','Actualized Credit Billed','DWAS Actualized','DWAS Actualized Credit Billed') 
   or ( exists ( SELECT job_status AS Expr1 
                   FROM tblConsolidatedBilling AS tblConsolidatedBilling_1  WITH (NOLOCK)  
                  WHERE job_status not in ('Actualized', 'Actualized Credit', 'Billed') 
                    AND master_jobnumber = jobticket.jobnumber ) 
      )           
ORDER BY job_info.expediencyLevel DESC, jobticket.jobnumber DESC