Sql-server – Finding exact row in Clustered index leaf page

Very good question as it is such a important concept. This is a big topic though and what I am going to show you is a simplification so you can understand the base concepts.

Firstly when you see clustered index think table. In SQL server if a table does not contain a clustered index it is a heap. Creating a clustered index on the table actually transforms the table into a b-tree type structure. Your clustered index IS your table it is not separate from the table

Ever wondered why you can only have one clustered index? Well if we had two clustered indexes we would need two copies of the table. It contains the data after all.

I am going to try and explain this by using a simple example.

NOTE: I created the table in this example and filled it with over 3 million random entries. Then ran the actual queries and pasted the execution plans here.

What you really need to grasp is O notation or operational efficiency. Let's assume you have the following table.

CREATE TABLE [dbo].[Customer](
[CustomerID] [int] IDENTITY(1,1) NOT NULL,
[CustomerName] [varchar](100) NOT NULL,
[CustomerSurname] [varchar](100) NOT NULL,
CONSTRAINT [PK_Customer] PRIMARY KEY CLUSTERED 
(
[CustomerID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF
  , IGNORE_DUP_KEY = OFF,ALLOW_ROW_LOCKS  = ON
  , ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

So here we have basic table with a clustered key on CustomerID (Primary key is clustered by default). Thus the table is arranged/ordered based on the primary key CustomerID. The intermediate levels will contain the CustomerID values. The data pages will contain the whole row thus it is the table row.

We will also create a non-clustered index on the CustomerName field. The following code will do it.

CREATE NONCLUSTERED INDEX [ix_Customer_CustomerName] ON [dbo].[Customer] 
 (
[CustomerName] ASC
 )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF
  , SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF
  , DROP_EXISTING = OFF, ONLINE = OFF
  , ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

So in this index you would find on the data pages/leaf level nodes a pointer to the intermediate levels in the clustered index. The index is arranged/ordered around the CustomerName field. Thus the intermediate level contains the CustomerName values and the leaf level will contain the pointer (these pointer values are actually the primary key values or CustomerID column).

Right so if we execute the following query:

SELECT * FROM Customer WHERE CustomerID = 1 

SQL will probably read the clustered index via a seek operation. A seek operation is a binary search which is much more efficient than a scan which is a sequential search. So in our above example the index is read and by using a binary search SQL can eliminate the data that don't match the criteria we are looking for. See attached screen shot for the query plan.

So the number of operations or O Notation for the seek operation is as follows:

1. Do binary search on clustered index by comparing the value searched for to the values in the intermediate level.
2. Return the values that match( remember since the clustered index has all the data in it can return all the columns from the index as it is the row data)

So it is two operations. However if we executed the following query:

SELECT * FROM Customer WHERE CustomerName ='John'

SQL will now use the non-clustered index on the CustomerName to do the search. However since this is a non-clustered index it does not contain the all of the data in the row.

So SQL will do the search on the intermediate levels to find the records that match then do a lookup using the values returned to do another search on the clustered index(aka the table) to retrieve the actual data. This sounds confusing I know but read on and all will become clear.

Since our non-clustered index only contains the CustomerName field(the indexed field values stored in the intermediate nodes) and the pointer to the data which is the CustomerID, the index has no record of the CustomerSurname. The CustomerSurname has to be fetched from the clustered index or table.

When running this query I get the following execution plan:

There are two important things for you to notice in the screen shot above

1. SQL is saying I have a missing index(the text in green). SQL is suggesting I create a index on CustomerName which includes CustomerID and CustomerSurname.
2. You will also see that 99% of the time of the query is spent on doing a key lookup on the primary key index/clustered index.

Why is SQL suggesting the index on CustomerName again? Well since the index contains only the CustomerID and the CustomerName SQL still has to find the CustomerSurname from the table/clustered indexes.

If we created the index and we included the CustomerSurname column in the index SQL would be able to satisfy the entire query by just reading the non-clustered index. This is why SQL is suggesting I change my non-clustered index.

Here you can see the extra operation SQL needs to do to get the CustomerSurname column from the clustered key

Thus the number of operations are as follows:

1. Do binary search on non-clustered index by comparing the value searched for to the values in the intermediate level
2. For nodes that match read the leaf level node which will contain the pointer for the data in the clustered index (the leaf level nodes will contain the primary key values by the way).
3. For each value returned do a read on the clustered index(the table) to get the row values out here we would read the CustomerSurname.
4. Return matching rows

That is 4 operations to get the values out. Twice the amount of operations needed compared to reading the clustered index. The show you that your clustered index is your most powerful index as it contains all the data.

So just to clarify one last point. Why do I say that the pointer in the non-clustered index is the primary key value? Well to demonstrate that the leaf level nodes of the non-clustered index contains the primary key value I change my query to:

SELECT CustomerID
FROM Customer
WHERE CustomerName='Jane'

In this query SQL can read the CustomerID from the non-clustered index. It does not need to do a lookup on the clustered index. This you can see by the execution plan which looks like this.

Notice the difference between this query and the previous query. There is no lookup. SQL can find all the data in the non-clustered index

Hopefully you can begin to understand that clustered index is the table and non-clustered indexes DON'T contain all the data. Indexing will speed up selects due to the fact that binary searches can be done but only clustered indexes contain all the data. So a search on a non-clustered index will almost always result in values being loaded from the clustered index. These extra operations make non-clustered indexes less efficient than a clustered index.

Hope this clears things up. If anything does not make sense please post a comment and I will try clarify. It is rather late here and my brain is feeling a wee bit flat. Time for a red bull.

The reason for this is that the "fixed" physical location of your row - the RID (or row identifier) might (and will!) change over time - think page splits that occur when a row needs to be inserted into a table on a page that's already full.

Updating those RIDs in all the nonclustered indices that exist on a given table is quickly becoming both a hassle, and a huge performance killer. You might have 5, 10, 20 nonclustered indices on your table, and SQL Server would have to scan all those indices (basically scanning the whole index, all rows in the index, and that 10, 20 times) and update all RIDs.... that's just not practical - very quickly so.

If you store the value of the clustering index as a "row pointer" instead, that value should typically never change - and most definitely it doesn't need to be updated every time a page is split. Yes, it does involve a second index seek operation - the key lookup - but for simple scenarios, retrieving a single row or a few rows, that's still much more efficient than anything else.