Why does my ORDER BY sort two tables before the EXCEPT (slow) and not after (fast)?

Question

SQL server 2008 R2 query optimizer puzzle

We have two tables, both containing 9 million rows. 70.000 rows are different, the others are the same.

This is fast, 13 seconds,

select * from bigtable1
except select * from similar_bigtable2

This sorts the output and is also fast, 13 seconds as well,

select * into #q from bigtable1
except select * from similar_bigtable2
select * from #q order by sort_column

While this is enormously slow:

;with q as (
    select * from bigtable1
    except select * from similar_bigtable2
)
select * from q order by sort_column

And even a "trick" that I sometimes use to hint SQL Server that it needs to precalculate a certain part of the query before it moves on, doesn't work and results in slow query as well:

;with q as (
    select top 100 percent * from bigtable1
    except select * from similar_bigtable2
)
select * from q order by sort_column

Looking at the query plans the reason is not hard to find:

SQL Server places two sorts of 9 million rows before the hashmatch, while I would prefer it to have added only one sort of 70.000 rows after the hashmatch.

So the question: how can I instruct the query optimizer to do that?

Answer 1

The main difference between these two query plans is in fact in the difference of Hash Match and Merge Join. Hash Match is more efficient and as you can see the query runs faster in option 1 (not using CTE).

CTE is a great tool, but it seems to be not efficient in two cases,Complex Predicates or Non-Unique Parent/Child Key. In your case there is no unique key and SQL server has to sort the data sets first to be able to fulfill your requirement. Have a look at the link below which tells you more on this issue: http://blogs.msdn.com/b/sqlcat/archive/2011/04/28/optimize-recursive-cte-query.aspx

So it seems either you have to accept its slowness or rewrite the logic with WHILE loop which can be more efficient.

Answer 2

Try this, any better?

select * from
(
    select * from bigtable1
    except 
    select * from similar_bigtable2
) t
order by sort_column

Answer 3

This isn't an ideal solution but if you aren't able to structure the tsql to generate an efficient plan you could set a plan guide to force the plan you want. Doing this would mean that if a more efficient plan becomes available SQL won't consider it but it is an option.