SQL 2000 UNION ALL ruins query optimization

I have a stored procedure which takes under a second to run normally. Users wanted data from another table in that query, so I merged that data in with a UNION ALL and a bunch of dummy columns that were missing in the new table.

It worked fine in testing, but when we deployed it to an SQL 2000 Server, it started getting timeouts. The old query runs in under a second, and the 2 new queries both run in under a second, but when they're combined using UNION ALL, the query times out.

Here's the general idea of how the query looks. The real query has about 20 input parameters and returns about 30 or 40 columns, but this should give the basic idea:

CREATE PROCEDURE dbo.SearchHistory
(
    @Criteria1 bigint,
    @Criteria2 int,
    @Criteria3 varchar(10)
)
AS
BEGIN
    -- Part 1
    SELECT
        A,
        NULL AS B,
        0 AS C,
        D
    FROM TableA
    WHERE @Criteria1 IS NULL
    AND @Criteria3 IS NULL
    AND (A = @Criteria2 OR @Criteria2 IS NULL)

UNION ALL

    -- Part 2
    SELECT
        A,
        NULL AS B,
        0 AS C,
        E
    FROM TableA
    WHERE @Criteria1 IS NULL
    AND @开发者_如何转开发Criteria3 IS NULL
    AND (A = @Criteria2 OR @Criteria2 IS NULL)

UNION ALL

    -- Part 3
    SELECT
        A,
        B,
        C,
        D
    FROM TableB
    WHERE (F = @Criteria1 OR @Criteria1 IS NULL)
    AND (A = @Criteria2 OR @Criteria2 IS NULL)
    AND (G = @Criteria3 OR @Criteria3 IS NULL)
END

In the above example, @Criteria1 is not null, so Part 1 and 2 will return 0 rows, and part 3 is only returning 3 rows. But if I comment out Part 1 and 2, it finishes immediately; if I leave them in, I get a timeout.

How do you convince SQL Server to not mess around with its execution plan in a situation like this?

I think your problem is because of SQL Server's parameter sniffing.

http://elegantcode.com/2008/05/17/sql-parameter-sniffing-and-what-to-do-about-it/

http://blogs.msdn.com/b/queryoptteam/archive/2006/03/31/565991.aspx

I have come across it a good few times. There are a few ways around it. E.g. use WITH RECOMPILE as @Biff MaGriff suggested. The easiest way I found to fix is to convert all your input parameters to local parameters, and use the local ones.

This cannot be answered without seeing the execution plans (please post them as images, one for each part and one for the union query). A workaround is to use a temp table in which you insert the the parts separately. A better solution however would be to fix the query in the first place.