SQL 2000 UNION ALL разрушает оптимизацию запросов

У меня есть хранимая процедура, для нормальной работы которой требуется менее секунды. Пользователи хотели получить данные из другой таблицы в этом запросе, поэтому я объединил эти данные с UNION ALL и кучей фиктивных столбцов, которые отсутствовали в новой таблице.

Он работал нормально при тестировании, но когда мы развернули его в SQL 2000 Server начал получать таймауты. Старый запрос выполняется менее чем за секунду, и два новых запроса выполняются менее чем за секунду, но когда они объединяются с использованием UNION ALL, время ожидания запроса истекает.

Вот общее представление о том, как выглядит запрос. Настоящий запрос имеет около 20 входных параметров и возвращает около 30 или 40 столбцов, но это должно дать основную идею:

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

В приведенном выше примере @ Criteria1 не равно нулю, поэтому части 1 и 2 вернут 0 строк, а часть 3 возвращает только 3 строки. Но если я закомментирую часть 1 и 2, она сразу же закончится; если я оставлю их, у меня будет тайм-аут.

Как убедить SQL Server не возиться с планом выполнения в подобной ситуации?