By altering the query to not use the (does not exist) and instead using it in the where clause to check for cancelled orders, that along with the stats update,...

An update:

I bit the bullet and ran an 'update statistics fullscan' on all the tables in the database and that seemed to do the trick. Our report writers said their...

Ok. So I have a statement and a question.

I tried the various suggestions offered. Swapping orders and track didn't have an effect, neither did adding the option to recompile or...

Awesome. Tomorrow morning I will begin implementing these suggestions. I will then post the results of my findings. Thanks so much.

Thanks so much. There is obviously a different style of processing going on when looking at the two plans. Let me know what you find.

GRRR I highlighted the sql results and clicked on "plain" on the left and it still inserted those stupid faces. Sorry.

I changed the option in 'results' from 256 to 8000.

GOOD PLAN:

|--Parallelism(Gather Streams)

|--Stream Aggregate(GROUP BY:([o].[o_num]) DEFINE:([Expr1004]=MAX([t].[t_num])))

...

Oops, sorry for the icons, next time I'll edit that properly.

Yes yes. I'm looking at the graphical plan and the clustered index scan on that bad plan produced over 1...

Oh, sorry I forgot to include, this is being run on SQL 2000 SP3A. It's the actual execution plan.

Here is the quick plan:

|--Parallelism(Gather Streams)

...