SQL Server's execution plan has changed the representation of these operations over the years...
SQL 2000 : Bookmark Lookup
SQL 2005 : Nested Loop Join + Clustered Index Seek (confusing)
SQL 2005 SP2+ :
Key Lookup (Clustered) - When table has a clustered index
RID Lookup - when table has NO clustered index
Definition according to MSDN >
"Introduced in SQL Server 2005 Service Pack 2, the Key Lookup operator is a bookmark lookup on a table with a clustered index "
And according to SQL MVP Gail Shaw
" the one that fetches extra columns from the clustered index when the nonclustered index that’s used to retrieve the rows doesn’t have all of the columns required. "
Gail explains them well here...
Pinal Dave tells us how to get round them...
One method is to add 'Included columns'
Pinal Dave lists the advantages of included columns as >
" 1) Index can exceed the 900-byte limitation of the index key.
2) Index can include datatypes that are not allowed as key columns – varchar(max), nvarchar(max) or XML.
3) Size of the key index can be reduced, which improves the overall performance of the index operation. "
SSC : Covering Index using Included Columns
SQL Solace : Index Sizes using Included Columns