Bookmark lookup, Rid lookup, B Tree, Index Scan, Index Seek In SQL Server

Bookmark Lookup and Rid Lookup:

When a small number of rows are requested by a query, the SQL Server optimizer will try to use a non-clustered index on the column or columns contained in the WHERE clause to retrieve the data requested by the query. If the query requests data from columns not present in the non-clustered index, SQL Server must go back to the data pages to get the data in those columns. Even if the table has a clustered index or not, the query will still have to return to the table or clustered index to retrieve the data.

In the above scenario, if table has clustered index, it is called bookmark lookup (or key lookup); if the table does not have clustered index, but a non-clustered index, it is called RID lookup. This operation is very expensive. To optimize any query containing bookmark lookup or RID lookup, it should be removed from the execution plan to improve performance.

Index Scan and Index Seek:

Before we go over the concept of scan and seek we need to understand what SQL Server does before applying any kind of index on query. When any query is ran SQL Server has to determine that if any particular index can be applied on that particular query or not.

SQL Server uses search predicates to make decision right before applying indexes to any given query. Let us see the definition of predicates from Book On-Line: Predicate is an expression that evaluates to TRUE, FALSE, or UNKNOWN. Predicates are used in the search condition of WHERE clauses and HAVING clauses, the join conditions of FROM clauses, and other constructs where a Boolean value is required.

In you have not understood so far what I am trying to suggest. Let me put this in simple words in following scenario.

Table1 has five columns : Col1,Col2,Col3,Col4,Col5
Index1 on Table1 contains two columns : Col1,Col3
Query1 on Table1 retrieves two columns : Col1,Col5

Now when Query1 is ran on Table1 it will use search predicates Col1,Col5 to figure out if it will use Index1 or not. As Col1,Col5 of Query1are not same as Col1,Col3 or Index1 there are good chances that Query1 will not use Index1. This scenario will end up in table scan. If Query1 would have used Index1 it would have resulted in table seek.

Index Scan happens when index definition can not point close on single row to satisfy search predicates. In this case SQL Server has to scan multiple pages to find range of rows which satisfy search predicates. In case of Index Seek SQL Server finds single row matchign search predicates using index definition.

B- Tree is a structure to organize index information in sql server which has root node, connecting node and leaf node, actual data are stored under leaf node.