Thanks all for your help. I've fixed the problem and discovered something truly odd (to me anyway). Can someone explain this?

I followed up on Craig's comment "Your nested loop join is just not behaving itself" and looked at the execution plan. Hovering over the Nested Loops, it says the usual "For each row in the top (outer) input, scan the bottom (inner) input, and output matching rows."

Now, if you look at the actual execution plan I posted for the query using derived tables http://www.sqlservercentral.com/Forums/Attachment8568.aspx, you'll see that the top input to the nested loop is the seek for SROfferID, which comes from a small table and returns a small number of rows (3,734). The bottom input to the nested loop is from the index scan of the large table CrsEvalResponse and contains the gargantuan 468 million rows.

"No way," says I to myself. "For each row in top input, scan the bottom input....." Can it be this easy......?

Sure enough. I simply reversed the order of the 2 WHERE clauses and voila! Execution in milliseconds!!

SELECT Department, CourseID, CourseType, Section, CourseName

FROM SROffer

WHERE TermCalendarID IN (SELECT o.TermCalendarID FROM CrsEvalResponse resp INNER JOIN SROffer o ON resp.SROfferID=o.SROfferID) AND

SROfferID NOT IN (SELECT SROfferID FROM CrsEvalResponse)

See new attached sqlplan.

Does this make any sense to anyone? As a couple of you pointed out, divide and conquer works, but all I did was switch the order of the WHERE clauses.

GSquared, I'd still like to hear what you were originally going to suggest.

Thanks again everyone. Your replies kept me digging at this.

Rich