Query Performance depending on parameter 21seconds vs. > 14hours I have the following query:

SELECT DISTINCT DATEADD(ms,DATEDIFF(ms,0,[Time]),DATEADD(dd,0,DATEDIFF(dd,0,[DATE]))),
                [DATE],
                DATEPART(YY,[DATE]),
                DATEPART(MM,[DATE]),
                DATENAME(MONTH,[DATE]),
                DATEPART(DD,[DATE]),
                [Time],
                DATEPART(HH,[Time]),
                DATEPART(MI,[Time]),
                DATEPART(SS,[Time])
FROM [SourceTable]
WHERE ([DATE] BETWEEN '2012-01-08' AND '2012-01-08') AND
       DATEADD(ms,DATEDIFF(ms,0,[Time]),DATEADD(dd,0,DATEDIFF(dd,0,[DATE]))) NOT IN
       (SELECT [DateTime]
        FROM [DIM].[DateTime] 
        WHERE [Date] BETWEEN '2012-01-08' AND '2012-01-08')
ORDER BY [DATE], [Time]
OPTION (MAXDOP 6)


When I use this specific date I had to cancel the query after 14hours running time, any other date the same query takes normally 21 seconds. I did check the query execution plan independent on what date I use it is the same, the amount of rows impacted by the query is for each day nearly the same (around 500'000 Rows). I checked the indexes and the statistics are up to date. How is such a behaviour explainable and how to fix this ?

The Hardware of the machine is sufficient (8 Cores, 192 GB RAM)
I don't know about sqlserver but in an Oracle database, I would suggest making a trace of the sql execution, one that includes all waits and events that cause the query to spend time. This shows the exact circumstances where the sql is executing in and that might be very different than those in the environment where you did the explain plan. Sqlserver without doubt has a similar feature to show the real execution, including waits.

In Oracle we have sql plan stability. Maybe sqlserver has something similar? In that case, try to use that.