title: SQL Server "ORDER BY" optimization - massive performance decrease
body: <p>Using SQL Server 2000. I have a table that receives a dump from a legacy system once a day, I am trying to write a query that will process this table with a few reference table joins and an order by clause. </p>
  
  <p>This is the SQL I have:</p>
  
  <pre><code>select  d.acct_no,
          d.associate_id,
          d.first_name,
          d.last_name,
          d.acct_bal,
          plr.long_name p_lvl,
          tlr.long_name t_lvl,
          d.category,
          d.status,
          tm.site_name,
          d.addr1 + ' ' + isnull(d.addr2,'') address,
          d.city,
          d.state,
          d.country,
          d.post_code,
          CASE WHEN d.home_phone_ok = 1 THEN d.home_phone END home_phone,
          CASE WHEN d.work_phone_ok = 1 THEN d.work_phone END work_phone,
          CASE WHEN d.alt_phone_ok = 1 THEN d.alt_phone END alt_phone,
          CASE WHEN d.email_ok = 1 THEN d.email END email,
          d.last_credit last_paid,
          d.service,
          d.quantity,
          d.amount,
          ar.area_desc area
  from    item_dump d
          left outer join territory_map tm on tm.short_postcode = left(post_code,3) and country in ('United States','Canada')
          left outer join p_level_ref plr on plr.p_level_id = d.p_lvl_id
          left outer join t_level_ref tlr on tlr.t_level_id = d.t_lvl_id
          left outer join (select distinct master_item_id, site_item_id from invoice_detail) as map on map.item_id = d.item_no
          left outer join item_ref i on i.item_id = map.master_item_id
          left outer join area_ref ar on ar.area_id = i.area_id
  where   (d.cat_id &gt; 80 or d.cat_id &lt; 70)
          and d.standing &lt; 4
          and d.status not like 'DECEASED'
          and d.paid = 1
  order by d.associate_id
  </code></pre>
  
  <p>Most of these columns are straight from the legacy system dump table <code>item_dump</code>. All the joins are only reference tables with few rows. The legacy table itself has about 17000 records but with the where statements the query comes out to 3000. </p>
  
  <p>I have a non-clustered index on the <code>associate_id</code> column. </p>
  
  <p>When I run this query without the <code>order by associate_id</code> clause it takes about 2 seconds. With the <code>order by</code> clause it takes a full minute!</p>
  
  <p>I've tried adding the <code>where</code> clause columns to the index along with <code>associate_id</code> but that didn't change the performance at all.</p>
  
  <p>The end of the execution plan without the <code>order by</code> looks like this:</p>
  
  <p><img src="https://i.stack.imgur.com/uYtLj.png" alt="enter image description here"></p>
  
  <p>Using <code>order by</code>, parallelism kicks in on the order by argument and it looks like this:</p>
  
  <p><img src="https://i.stack.imgur.com/NZjhp.png" alt="enter image description here"></p>
  
  <p>I thought maybe it was <a href="https://stackoverflow.com/questions/2477818/sql-server-2000-stored-procedure-prevent-parallelism-or-something">weird SQL Server 2000 parallelism handling</a>, but adding the <code>(maxdop 1)</code> hint made the query take 3 minutes instead!</p>
  
  <p>It isn't really sensible for me to put sorting in the application code because this query caches for about 6 hours before it gets run again and I would have to sort it in the application code many times a minute.</p>
  
  <p>I must be missing something very basic but after straining at the query for an hour i.e. running it 10 times, I can't see what it is anymore.</p>