Если вы обрабатываете 3 или 4 миллиона строк данных и действительно выполняете настоящую работу, 20 или 30 секунд - это довольно приличная производительность, ИМХО. Проверьте план выполнения вашей хранимой процедуры. В идеальном мире каждая таблица будет получать результаты поиска индекса, а не сканирования таблицы. Проконсультируйтесь с вашим администратором базы данных, если вы не уверены, как интерпретировать результаты showplan. Я предполагаю, что вы используете SQL Server.
Убедитесь, что ваши таблицы имеют соответствующие индексы и что статистика актуальна. Обновите их, если нет. Перекомпилируйте хранимую процедуру. Параметры, передаваемые хранимой процедуре, могут запутывать кэшированный план выполнения, если значения являются странными. Вы можете предотвратить это, кодируя вашу хранимую процедуру следующим образом:
create proc myProc
@p1 varchar(32)
as
declare
@p1Local varchar(32)
set @p1Local = @p1
...