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

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

Он отлично работал при тестировании, но когда мы развернули его на сервере SQL 2000, он начал получать тайм-ауты. Старый запрос выполняется менее чем за секунду, а два новых запроса выполняются менее чем за секунду, но когда они объединяются с помощью 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 не возиться со своим планом выполнения в такой ситуации?