Похоже, что этот запрос относится к хранимой процедуре, ее план выполнения будет скомпилирован при первом выполнении процедуры, а затем повторно использован для последующих выполнений.
Вполне возможно, что скомпилированный план действительно плох для ситуаций, когда firstid действительно близок к lastid, однако это действительно хорошо, когда значения находятся далеко друг от друга.
Попробуйте включить опцию WITH RECOMPILE в вашем сохраненном процессе. Если это решит проблему, и вы будете довольны тем, что процесс перекомпилируется каждый раз, когда он выполняется (вы получите снижение производительности), оставьте его там. Если вы все еще недовольны производительностью, подумайте о ре-архитектуре процесса, чтобы он не нуждался в перекомпиляции.