Meu primeiro pensamento quando vejo variações como essa é garantir que você tenha gerado estatísticas para todas as suas tabelas. Existem muitos scripts na web para fazer isso e muita discussão sobre usar os sprocs internos, fazer fullscan etc. Aqui está um script rápido e sujo que eu executaria antes de fazer comparações.
CREATE PROCEDURE sp_UtilityUpdateStats AS
SET NOCOUNT ON
DECLARE @iCounter INT
DECLARE @iCounterMax INT
DECLARE @TableList TABLE
(
iTable INT IDENTITY(1,1) PRIMARY KEY,
szTableName VARCHAR(128)
)
INSERT @TableList (szTableName)
SELECT [name] FROM sysobjects
WHERE [type] = 'u'
ORDER BY [name] DESC
SET @iCounterMax = (SELECT MAX(iTable) FROM @TableList)
SET @iCounter = 0
DECLARE @szTableName VARCHAR(128)
RAISERROR(N'------STARTING sp_UtilityUpdateStats------', 10, 1) WITH LOG
WHILE @iCounter < @iCounterMax
BEGIN
SET @iCounter = @iCounter + 1
SELECT @szTableName = szTableName
FROM @TableList
WHERE iTable = @iCounter
RAISERROR(N'UPDATE STATISTICS YourDB.dbo.%s', 10, 1, @szTableName) WITH LOG
EXEC ('UPDATE STATISTICS YourDB.dbo.' + @szTableName)
END
RAISERROR(N'------FINISHING sp_UtilityUpdateStats------', 10, 1) WITH LOG
SET NOCOUNT OFF
GO
