Это слишком долго для комментария.
SQL Server компилирует запросы в хранимых функциях и хранимых процедурах при первом вызове. Решения, принятые оптимизатором, основаны на статистике таблицы и параметрах в то время.
Это называется параметром sniffing (я не поклонник этого термина, потому что решения основаны как на параметрах, так и на статистике таблицы).
Ваш опыт подсказывает, что план запроса был субоптимальным - это обычно было бы разницей между соединением, основанным на хеше, и объединением вложенного цикла. Иногда вы можете исправить это, используя индекс.
Другим распространенным решением является принудительная перекомпиляция запроса (или запросов) в программном коде. Однако это приводит к накладным расходам на перекомпиляцию. Такие накладные расходы должны быть небольшими для запроса, который занимает минуту, чтобы выполнить, но более значителен, если запрос занимает менее секунды.