Why does a query run slower in a Stored Procedure than in the Query window? I have a complex query which runs in 2 seconds in the query window, but about 5 minutes as a Stored Procedure. Why is it taking so much longer to run as a stored procedure?

Here's what my query looks like. 

It takes a specific set of records (identified by @id and @createdDate), and a specific time frame (1 year starting from @startDate) and returns a summarized list of letters sent and estimated payments received as a result of those letters.

CREATE PROCEDURE MyStoredProcedure
    @id int,
    @createdDate varchar(20),
    @startDate varchar(20)

 AS
SET NOCOUNT ON

    -- Get the number of records * .7
    -- Only want to return records containing letters that were sent on 70% or more of the records
    DECLARE @limit int
    SET @limit = IsNull((SELECT Count(*) FROM RecordsTable WITH (NOLOCK) WHERE ForeignKeyId = @id AND Created = @createdDate), 0) * .07

    SELECT DateSent as [Date] 
        , LetterCode as [Letter Code]
        , Count(*) as [Letters Sent]
        , SUM(CASE WHEN IsNull(P.DatePaid, '1/1/1753') BETWEEN DateSent AND DateAdd(day, 30, DateSent) THEN IsNull(P.TotalPaid, 0) ELSE 0 END) as [Amount Paid]
    INTO #tmpTable
    FROM (

        -- Letters Table. Filter for specific letters
        SELECT DateAdd(day, datediff(day, 0, LR.DateProcessed), 0) as [DateSent] -- Drop time from datetime
            , LR.LetterCode -- Letter Id
            , M.RecordId -- Record Id
        FROM LetterRequest as LR WITH (NOLOCK)
        INNER JOIN RecordsTable as M WITH (NOLOCK) ON LR.RecordId = M.RecordId
        WHERE ForeignKeyId = @id AND Received = @createdDate
            AND LR.Deleted = 0 AND IsNull(LR.ErrorDescription, '') = ''
            AND LR.DateProcessed BETWEEN @startDate AND DateAdd(year, 1, @startDate)
            AND LR.LetterCode IN ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o')
    ) as T
    LEFT OUTER JOIN (

        -- Payment Table. Payments that bounce are entered as a negative payment and are accounted for
        SELECT PH.RecordId, PH.DatePaid, PH.TotalPaid
        FROM PaymentHistory as PH WITH (NOLOCK)
            INNER JOIN RecordsTable as M WITH (NOLOCK) ON PH.RecordId = M.RecordId
            LEFT OUTER JOIN PaymentHistory as PR WITH (NOLOCK) ON PR.ReverseOfUId = PH.UID
        WHERE PH.SomeString LIKE 'P_' 
            AND PR.UID is NULL 
            AND PH.DatePaid BETWEEN @startDate AND DateAdd(day, 30, DateAdd(year, 1, @startDate))
            AND M.ForeignKeyId = @id AND M.Created = @createdDate
    ) as P ON T.RecordId = P.RecordId

    GROUP BY DateSent, LetterCode
    --HAVING Count(*) &gt; @limit
    ORDER BY DateSent, LetterCode

    SELECT *
    FROM #tmpTable
    WHERE [Letters Sent] &gt; @limit

    DROP TABLE #tmpTable


The end result looks like this:


Date        Letter Code     Letters Sent    Amount Paid
1/1/2012    a               1245            12345.67
1/1/2012    b               2301            1234.56
1/1/2012    c               1312            7894.45
1/1/2012    a               1455            2345.65
1/1/2012    c               3611            3213.21


I'm having problems figuring out where the slowdown is, because everything runs extremely fast in the query editor. It's only when I move the query to a stored procedure that it starts taking so long to run. 

I'm sure it has something to do with the query execution plan getting generated, but I don't know enough about SQL to identify what could be causing the problem.

It should probably be noted that all the tables used in the query have millions of records.

Can someone explain to me why this is taking so much longer to run as a stored procedure than in the query editor, and help me identify what part of my query could be causing performance issues when run as a stored procedure?
As Martin pointed out in the comments, the problem is that the query is using a cached plan which is inappropriate for the parameters given.

The link he provided on Slow in the Application, Fast in SSMS? Understanding Performance Mysteries provided a lot of useful information which lead me to some solutions.

The solution I am currently using is to copy the parameters to local variables in the procedure, which I think makes SQL re-evaluate the execution plan for the query anytime it's run, so it picks the best execution plan for the parameters given instead of using an inappropriate cached plan for the query.

Other solutions which may work are using the OPTIMIZE FOR or RECOMPILE query hints.