Like the title says, I have a stored procedure that suddenly started running very slowly. Previously it took about 5 seconds to execute, now it is taking seven minutes or more. This seems to have started when I altered the procedure, but the change I made should not have impacted the performance, as all I did was change the alias on two columns being returned. I'm not sure if altering the procedure actually caused this, however, because a similar procedure that also used to be very fast is having the same issues. 

I tried updating statistics on the relevant tables and it did not help. I had this same problem last week and was able to fix it by doing that, but now it's a no go. I also tried using `with recompile` to no avail and deleted the procedure then re-added it. 

This is the line that is taking much longer than before: 

    select PK_ShipDataSubsystemConfigID
	,timestamp
	,cast((
			select top 1 Longitude
			from [RemoteServer].[dbo].[Ships].LocationAttributes la
			inner join [RemoteServer].[dbo].[Ships].Locations l on l.ShipLocationId = la.ShipLocationId
			where l.SampleDateTime <= timestamp
				and l.SampleDateTime <= @ToDT
				and ShipId = @ShipId
			order by SampleDateTime desc
			) as varchar(20)) as Longitude
	,'Vessel Position Lng'
    from FuelCalc
    inner join ShipDataSubsystemConfig s on s.PK_ShipDataSubsystemConfigID =       FuelCalc.FK_ShipDataSubsystemConfigId
    where timestamp > @FromDT
	and timestamp < @ToDT
	and FuelCalc.FK_ShipId = @ShipId
    order by timestamp desc

Running the inner select by itself now takes at least 2 seconds, so I can understand why the whole procedure is taking so long. I am wondering if it has something to do with it being a call to a linked server. I tried creating a view  joining the Locations and LocationAttributes tables to see if it made a difference, but it did not. 

Any ideas? I have asked around with my coworkers and they are just saying I need to write a more efficient query (which may be true) but I really don't think that's causing my particular problem seeing as it was working fine until suddenly it wasn't. I looked at the execution plan but all it says is that the remote query is taking 100% of the time, but doesn't show the plan at more detail than that.