The Key Lookup operator is a bookmark lookup on a table with a clustered index. Key Lookups can be quite expensive, so you should try to eliminate them when you can. Of course, you should consider your overall workload, and how often the query with the key lookup is executed. You can see what the icon for that operator looks like below:

Key lookups occur when you have an index seek against a table, but your query requires additional columns that are not in that index. This causes SQL Server to have to go back and retrieve those extra columns. You can see an example of this (if you squint) in the graphical execution plan shown below:

One way to reduce or even eliminate key lookups is to remove some or all of the columns that are causing the key lookups from the query. This can easily break your application, so you should not do that unless you you talk to your developers and/or look at the data access code that calls the query or stored procedure to see if those columns are actually used by the application. If the columns are explicitly listed in the query (as opposed to being a SELECT * pattern), then they probably are needed by the application. Even so, it never hurts to ask your developers, since you may discover that some columns can be safely removed.

The second method is to see if you can create a “covering index” that satisfies the entire query or at least eliminates the key lookups. A “covering index” is simply a non-clustered index that has all of the columns needed to either satisfy the entire query or in our case, eliminate the need for a key lookup operation. One challenge is to get a list of columns that are generating the key lookup. You can do this in SQL Server Management Studio (SSMS) by right-clicking on the key lookup operator, and then choosing Properties. Then find the Output List row in the Properties window, and click on the ellipsis button. This will open a window (see below) with a list of all of the columns that the key lookup is looking for. You can use this list to help you decide whether and how to create an index to “cover” the query or key lookup.

You need to consider what kind of workload you have, and how volatile this particular table is. You also need to look at your existing indexes, and how they are being used. You want to avoid the common mistake of adding an index that helps a query that is not executed very often, so that you are paying the cost to maintain the index without getting a substantial performance benefit from the index. With an OLTP workload and a volatile table, I tend to be much more hesitant to add new indexes if I already have five or six existing, useful indexes on the table.

One way to reduce the maintenance cost of a “covering” index is to add many of the columns to the index as Included columns. This means that the columns are only included in the leaf level of the index and not in the B-tree of the index.

-- Look at existing indexes on the table
-- This does not list any included columns
EXEC sp_helpindex N'dbo.ActivityEventMeta';

This gives you the output shown below:

index_name                                     index_description                                                       index_keys
IX_ActivityEventMeta_HashCode        nonclustered located on PRIMARY                               HashCode
IX_ActivityEventMeta_UserId_Date     nonclustered located on PRIMARY                               UserId, Date
PK_ActivityEventMeta                       clustered, unique, primary key located on PRIMARY      MetaEventId

You can run the query below to look at the index usage (since the last SQL Server restart) for a single table. This will give you some more information that can help you decide whether you should add any more indexes to the table.

    -- Index Read/Write stats for a single table
    SELECT OBJECT_NAME(s.[object_id]) AS [TableName], 
    i.name AS [IndexName], i.index_id,
    SUM(user_seeks) AS [User Seeks], SUM(user_scans) AS [User Scans], 
    SUM(user_lookups)AS [User Lookups],
    SUM(user_seeks + user_scans + user_lookups)AS [Total Reads], 
    SUM(user_updates) AS [Total Writes]     
    FROM sys.dm_db_index_usage_stats AS s
    INNER JOIN sys.indexes AS i
    ON s.[object_id] = i.[object_id]
    AND i.index_id = s.index_id
    WHERE OBJECTPROPERTY(s.[object_id],'IsUserTable') = 1
    AND s.database_id = DB_ID()
    AND OBJECT_NAME(s.[object_id]) = N'ActivityEventMeta'
    GROUP BY OBJECT_NAME(s.[object_id]), i.name, i.index_id
    ORDER BY [Total Writes] DESC, [Total Reads] DESC;

This is an example of how you might create a “covering” index to help eliminate the key lookups from the query:

-- Create a "covering" non-clustered index
CREATE NONCLUSTERED INDEX [IX_ActivityEventMeta_Cover1] ON [dbo].[ActivityEventMeta] 
(
    [HashCode] ASC,
    [UserId] ASC,
    [Date] ASC,
    [MetaEventType] ASC
)
INCLUDE 
    ([EntryText], [ListItemID],[ListId],[WebId],[SiteId],
     [FarmId],[KnownContentType],[ContentTypeId],[Deleted],[IsAnswer]
    ) 
WITH (STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, 
DROP_EXISTING = ON, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY];

Once this new “covering” index is in place, I may want to drop the old IX_ActivityEventMeta_HashCode index, since HashCode is the first column in the new index. I would wait a while, and then run the “Index Read/Write stats for a single table” query shown above to see the usage of all of the indexes on this table after adding the new index. The final caveat is to not go wild adding covering indexes to a table. I have seen many novice but eager DBA’s make that mistake, and end up with far too many indexes for their workload.