Order by for 2 row result causes 800% performance hit The following query, run against a table of about 6 mil rows takes 25 seconds. When I remove the final order by, it runs in 3 seconds. There are no indexes on the table (it's an intermediate SSIS ETL target that is later pulled into a DW.)

It isn't caching. I've run it multiple times in any order with consistent results.

The query itself checks for gaps in sequence numbers. SSIS will use it to see if it needs to re-fetch anything.

;with edges as
(
    select 
        ROW_NUMBER() over (partition by s1.SiteIDNumber order by s1.SequenceNumber) as rn,
        s1.SiteIDNumber, 
        s1.SequenceNumber
    from TestPlay s1
    left join TestPlay s2 on s2.SiteIDNumber = s1.SiteIDNumber and s2.SequenceNumber = s1.SequenceNumber + 1
    left join TestPlay s3 on s3.SiteIDNumber = s1.SiteIDNumber and s3.SequenceNumber = s1.SequenceNumber - 1
    where s2.SiteIDNumber is null 
    or s3.SiteIDNumber is null
),
gaps as
(
    select 
        e.rn,
        e.SiteIDNumber,
        e.SequenceNumber  + 1 as StartSeq,
        e2.SequenceNumber - 1 as EndSeq
    from edges e
    join edges e2 on e2.SiteIDNumber = e.SiteIDNumber and e2.rn = e.rn+1
    where e.rn = (e.rn / 2) * 2
)
select * from gaps order by rn


Here is the only part of the Execution Plan that seems to be different:

With ORDER BY (25 sec):



No ORDER BY (3 sec):
The merge join works like a zipper - if you don't care about order, SQL Server knows that it can sort the input in any way it wants, and not have to worry about re-ordering anything. When you add the order by, in this case a merge join is no longer the best choice, because materializing and sorting the first CTE twice in the order defined by the ROW_NUMBER() expression must obviously be more expensive than it seems.

One workaround, thinking off the cuff at beer o'clock on a Friday:

;WITH ...
(
)
SELECT * INTO #x FROM gaps;

SELECT * FROM #x ORDER BY rn;


However I bet if you searched around for a fellow named Itzik Ben-Gan you would find more efficient approaches to problems involving gaps and islands (or the advice to not try to sort the way you're sorting).