Query Tuning example 1 - NOT IN

Here's a real life example showing NOT IN really hurts query performance.
Below is the SQL code snippet extracted from a query to generate a report, which is written by a programmer from external vendor (I don't wanna mention which one, although I'm quite disappointed at it's work):
SELECT ... FROM ... WHERE ... AND demand.time_expense_sheet_id NOT IN (SELECT order_id FROM c_order_line) ...
The c_order_line table contains 1 million of rows in our production environment. That query takes 2 minutes to execute. My boss asked me to troubleshoot it, as users complain again and again that the report cannot be loaded and timeout error raised.
First, I used SQL Profiler to trace what queries are really running, and which query is the slowest one.

I pick the slowest query, execute it on testing environment by using Management Studio, with the "Include Actual Execution Plan" enabled. Then I execute the query, and open the returned actual execution plan by SQL Sentry Plan Explorer (a free tools you must love), and identified the top operation was a Index Scan on that huge table c_order_line.

By checking the SQL query, I found that table was being used in a NOT IN clause. So I send these findings to that favorable vendor (just kidding), they replied me that NOT IN checking may be unnecessary (-_-"). Later they sent me the fix, just removed that NOT IN clause, that report now can be generated within 10 seconds. My users feel happy, my boss feel happy :)