SQL Server query optimization?

Question

I have the following query:

SELECT
  tl.*, d.*
FROM
  TrackerLocations AS tl
  inner join Trackers t on tl.TrackerId = t.TrackerId
  inner join Devices d on t.UserId = d.UserId
WHERE
  tl.ReceivedTime = (SELECT MAX(tl2.ReceivedTime) FROM TrackerLocations tl2 WHERE tl2.TrackerId = tl.TrackerId)
  and tl.ReceivedTime >= DATEADD (MINUTE,-2,GETUTCDATE())
  and d.OSType <> 3
  and d.Notify = 1

...and for my surprise, it does not return the results in an acceptable time. First times I runned it in production environment, was like 3 seconds of execution. Now, it runs until timeout (inside C# application, 30 seconds).
The main purpose is: "give me the most recent locations from any tracker and info about it's users's devices, looking 2 minutes backwards".
Any hints about optimizing this query?

Thanks!

Indexes: Anywhere but where clause columns (ReceivedTime, OSType, Notify).

About the execution plan, it's a huge thing and it's not too familiar to me. Should I paste it here? :)

Answer 1

SELECT tl.*,d.*
 FROM
    TrackerLocations AS tl
    inner join Trackers t on tl.TrackerId = t.TrackerId
    inner join Devices d on t.UserId = d.UserId
 WHERE
    tl.ReceivedTime = (SELECT MAX(tl2.ReceivedTime) 
                         FROM TrackerLocations tl2 
                        WHERE tl2.TrackerId = tl.TrackerId 
                          and tl2.ReceivedTime >= @searchTerm)
    and d.RegistrationId <> ''
    and d.OSType <> 3
    and d.Notify = 1