Avoiding Key Lookup when using MIN and MAX I have a somewhat simple table that takes 

 Id guid (pk)
 SoftwareId guid (FK to software table)
 OnlineUsers int
 OnlineDevices int
 SampleDate datetime
 SDHour (persisted computed field, holding just the hour) 
 SDMinute (persisted computed field, holding just the minute / 5) 


The goal is between two dates draw a line graph of samples every 5 minutes, sometimes there is more than one sample every 5 minutes so to deal with that we just take the max amount of OnlineUsers and OnlineDevices 

SELECT
    MAX(OnlineUsers), -- Only select the most users
    MAX(OnlineDevices), -- Only select the most devices
    SDHour, -- Used to allow creating the graph split into 5 minute increments
    SDMinute, -- Used to allow creating the graph split into 5 minute increments
    SoftwareId,
    Software.FriendlyName as FriendlyName, -- Each software peice has a name
    Software.MaxUsers as MaximumSupportedUsers, -- Maximum supported users
    Software.MaxDevices as MaximumSupportedDevices, -- Maximum supported devices
    DATEDIFF(SECOND, @dtStartDate, min(SampleDate)) as OrderTime -- Used to sort
FROM SoftwareUserSamples 
JOIN Software on Software.Id = SoftwareUserSamples.SoftwareId-- Get sw details
LEFT OUTER JOIN SoftwareTypes on Software.SoftwareTypesId = SoftwareTypes.Id
WHERE Software.ClientId = @gClientID -- Multi tannancy 
AND (@bFilterHiddenRows = 0 OR Software.HideByDefault = 0) -- hide some rows
AND SoftwareUserSamples.SampleDate &gt; @dtStartDate -- Don't get all rows
AND SoftwareUserSamples.SampleDate &lt; @dtEndDate -- Don't get all rows
GROUP BY 
    SDHour, 
    SDMinute, 
    SoftwareId, 
    Software.FriendlyName,  --Need to group so we can use data in the select
    Software.MaximumSupportedUsers, 
    Software.MaximumSupportedDevices,       
    UserDivsor 
ORDER BY 
    OrderTime Asc,
    SoftwareId


This query was perfectly fine when we had a couple of hundred thousand rows. However now the data has grown to 42,000,000 rows it started to take aronud 10 seconds for the query to run for just a 20 day period. 

Looking at the query plan it looks like because I'm using the MAX() on both the OnlineUsers and OnlineDevices. If I remove these then the time to execute drops to &lt;1second if I put them back in it jumps to >10 seconds. NOTE Most of the time there is actually only 1 sample per 5 minutes

Any suggestions on how to avoid this either by modifying the query or addition of indexes. The only thing I can't do is change the output format. 

The Indexes I currently have are 

Clustered on
Id

Non-Clustered on 
SoftwareId
SampleDate
I would rewrite the query like this:

SELECT
    sus.MaxOnlineUsers, -- Only select the most users
    sus.MaxOnlineDevices, -- Only select the most devices
    sus.SDHour, -- Used to allow creating the graph split into 5 minute increments
    sus.SDMinute, -- Used to allow creating the graph split into 5 minute increments
    s.Id AS SoftwareId,
    s.FriendlyName AS FriendlyName, -- Each software peice has a name
    s.MaxUsers AS MaximumSupportedUsers, -- Maximum supported users
    s.MaxDevices AS MaximumSupportedDevices -- Maximum supported devices
    -- DATEDIFF(SECOND, @dtStartDate, min(sus.SampleDate)) as OrderTime -- Used to sort
FROM dbo.Software AS s -- Get sw details
--Not used: LEFT JOIN dbo.SoftwareTypes AS st ON s.SoftwareTypesId = st.Id

--- Run this once for each software:
CROSS APPLY (
    SELECT x.SDHour, x.SDMinute, x.UserDivsor,
           MIN(x.SampleDate) AS OrderColummn,   --- Just order by this column
           MAX(x.OnlineUsers) AS MaxOnlineUsers,
           MAX(x.OnlineDevices) AS MaxOnlineDevices
    FROM dbo.SoftwareUserSamples AS x
    WHERE x.SoftwareId=s.Id
      AND x.SampleDate &gt; @dtStartDate -- Don't get all rows
      AND x.SampleDate &lt; @dtEndDate -- Don't get all rows
    GROUP BY x.SDHour, x.SDMinute, x.UserDivsor) AS sus

WHERE s.ClientId = @gClientID -- Multi tannancy 
  AND (@bFilterHiddenRows = 0 OR s.HideByDefault = 0) -- hide some rows

ORDER BY 
    sus.OrderColumn,    
    s.Id;


The CROSS APPLY construct lets SQL Server "loop" over each row in dbo.Software and for each query in that table, it runs an aggregate query on the much larger dbo.SoftwareUserSamples table, for which we'll optimize with the following index:

INDEX ON dbo.SoftwareUserSamples (SoftwareId, SampleDate, SDMinute, SDHour, UserDivsor)
    INCLUDE (OnlineUsers, OnlineDevices)


This should give you a nice, efficient seek (range scan, really) on (SoftwareId, SampleDate).

I removed the DATEDIFF expression and just sorted by the MIN(SampleDate) expression instead. It'll make your code a little more readable and perhaps even save you a few microseconds of CPU time. :)

Just crossing Ts and dotting Is, here's an index recommendation on dbo.Software as well, although I suspect this table doesn't really contain that many rows:

INDEX ON dbo.Software (ClientId, SoftwareTypesId)
    INCLUDE (Id, FriendlyName, HideByDefault, MaxUsers, MaxDevices)


A few best practices that I could gleam from your post:


Every table (with very few exceptions) should have a clustered index. It doesn't absolutely have to be unique if that's a problem.
Always prefix the table with the schema name.
Qualify all the column names with table aliases, so you can easily see which column belongs to which table.
If you're on SQL Server 2014/2016 Enterprise Edition or on 2016 SP1+, you should really try putting a columnstore index on the SoftwareUserSamples table for performance.