I have previously very often talked on my weblog about Bookmark Lookups in SQL Server, and how bad they can be regarding the various problems they introduce. In today’s blog posting I want to talk a little bit more about the performance aspect of Bookmark Lookups, and how they can slow down your whole SQL Server installation.

Let’s do it – over and over again!

Bookmark Lookups are introduced by the Query Optimizer of SQL Server if you have a Non-Clustered Index in place that isn’t a Covering Non-Clustered Index. For every row that you return from the Non-Clustered Index, SQL Server has to perform an additional Lookup Operation in the Clustered Index or in the Heap Table.

For example when your Clustered Index consists of 3 levels, to return the necessary information you need 3 additional page reads for every row processed. Therefore the Query Optimizer only chooses a Lookup Operation in the Execution Plan when it makes sense – based on the selectivity of your query. The following picture shows you a simple Execution Plan with a Bookmark Lookup operation.

Normally people don’t really care about Bookmark Lookups, because they are only executed a few times. If the selectivity of your query is too low, the Query Optimizer will just scan the complete table with a Clustered Index Scan or Table Scan operator. But it can still happen that SQL Server reuses a cached plan with a Bookmark Lookup (based on the initially provided input parameters) with different runtime parameter values, and therefore it can very easily be the case that such a Bookmark Lookup operation is executed over and over again.

To simulate such a performance problem, in the following query I hint the Query Optimizer to use a specific Non-Clustered Index. The query itself returns 80000 rows, so for every query execution SQL Server has to perform the Bookmark Lookup operation 80000 times – over and over again.

CREATE PROCEDURE RetrieveData
AS
	SELECT * FROM Table1 WITH (INDEX(idxTable1_Column2))
	WHERE Column3 = 2
GO

The following picture shows the Actual Execution Plan after query execution.

The execution plan looks really terrible (the Query Optimizer has even chosen a Parallel Plan!), because the Bookmark Lookup operator was executed here 80000 times, and the query itself produced more than 165000 logical reads! (The number of logical reads is based on the output of STATISTICS IO).

Now to show you what happens to SQL Server when you execute such a bad query with a lot of parallel users, I’ll use ostress.exe (part of the RML Utilities) to run that query with 100 parallel users:

ostress.exe -Q”EXEC BookmarkLookupsPerformance.dbo.RetrieveData” -n100 -q

It now takes around 15 seconds on my test system to complete the 100 parallel queries. During that time the CPU consumption was also quite high, because SQL Server needs the Nested Loop operator to perform the Bookmark Lookup operation. And the Nested Loop operation is of course very CPU intensive.

Now let’s change our Indexing Strategy, and create a Covering Non-Clustered Index for this query. With a Covering Non-Clustered Index in place, the Query Optimizer doesn’t need to create an Execution Plan where it performs a Bookmark Lookup. A simple Non Clustered Index Seek will return the same result for us – with less overhead.

CREATE NONCLUSTERED INDEX idxTable1_Column2 ON Table1(Column3)
INCLUDE (Column2)
WITH (DROP_EXISTING = ON)
GO

This time when we execute this query again with ostress.exe and with 100 parallel users, we will see that the individual queries finish in around 5 second. That’s a huge difference compared to the 15 seconds that we saw previously. That’s the power of a Covering Non-Clustered Index: everything that we request in our query will be found directly in the Non-Clustered Index, and therefore the expensive Bookmark Lookup can be avoided.

Summary

In this blog posting I wanted to show you how bad Bookmark Lookups can be in relation to performance. For your very important queries it is therefore very important that they finish as fast as possible – and therefore an Execution Plan with a Bookmark Lookup is not really a great choice. A Covering Non-Clustered Index can help you a lot here. Just think about that the next time you are working on your Indexing Strategy.

Thanks for your time,

-Klaus