Trouble with some linq2sql generated T-SQL

Question

I'm having some trouble with SQL timeout for the following LINQ2SQL query:

DateTime date = DateTime.Parse("2013-08-01 00:00:00.000");

Clients.Where(e => 
    (
        !Orders.Any(f => f.ClientId.Equals(e.Id) && f.OrderDate >= date)
        ||
        Comments.Any(f => f.KeyId.Equals(e.Id))
    )
).Count().Dump();

When running this in LinqPad it will take forever to finish and will become an SQL timeout if running on the server.

The SQL-code generated:

-- Region Parameters
DECLARE @p0 DateTime = '2013-08-01 00:00:00.000'
-- EndRegion
SELECT COUNT(*) AS [value]
FROM [Clients] AS [t0]
WHERE (NOT (EXISTS(
    SELECT NULL AS [EMPTY]
    FROM [Orders] AS [t1]
    WHERE ([t1].[ClientId] = [t0].[Id]) AND ([t1].[OrderDate] >= @p0)
    ))) OR (EXISTS(
    SELECT NULL AS [EMPTY]
    FROM [Comments] AS [t2]
    WHERE [t2].[KeyId] = [t0].[Id]
    ))

Works fine in SQL-studio!

But:

SELECT COUNT(*) AS [value]
FROM [Clients] AS [t0]
WHERE 

(NOT (EXISTS(SELECT NULL AS [EMPTY] FROM [Orders] AS [t1] WHERE ([t1].[ClientId] = [t0].[Id]) AND ([t1].[OrderDate] >= '2013-08-01 00:00:00.000')))) 

OR  

(EXISTS(SELECT NULL AS [EMPTY] FROM [Comments] AS [t2] WHERE [t2].[KeyId] = [t0].[Id]))

And will get me a the problem as actually running the query in LinqPad.

What is the difference of using DECLARE @p0 DateTime = '2013-08-01 00:00:00.000' compared to using the constant date and how do I get my Linq2SQL to work?

EDIT:

See execution plans for both queries:

Timeouts:

Fine:

Some other things I've noticed is that if I remove the NOT it works fine:

SELECT COUNT(*) AS [value]
FROM [Clients] AS [t0]
WHERE 

((EXISTS(SELECT NULL AS [EMPTY] FROM [Orders] AS [t1] WHERE ([t1].[ClientId] = [t0].[Id]) AND ([t1].[OrderDate] >= '2013-08-01 00:00:00.000')))) 

OR  

(EXISTS(SELECT NULL AS [EMPTY] FROM [Comments] AS [t2] WHERE [t2].[KeyId] = [t0].[Id]))

Or if I remove the OR EXISTS parts it also works fine:

SELECT COUNT(*) AS [value]
FROM [Clients] AS [t0]
WHERE 

((EXISTS(SELECT NULL AS [EMPTY] FROM [Orders] AS [t1] WHERE ([t1].[ClientId] = [t0].[Id]) AND ([t1].[OrderDate] >= '2013-08-01 00:00:00.000')))) 

Thanks /Niels

Answer 1

The solution for me was to rebuild the index of OrderDate.