SQL Server : Part 6 : Design consideration of Clustered Index

In our earlier post, we have discussed about the structure and storage of clustered index. In this post we will discuss about the design consideration of clustered index.There are couple of points that need to be considered while selecting clustered index key.There is no hard rule in selecting the clustering key . It is best practices and guidelines and the internal knowledge will help us to select right clustering key.

Uniqueness 

SQL server will allow you to create a clustered index on non unique column, but uniqueness is one of the most desirable attribute for any indexes especially for a clustered index.Even if SQL server allow to create clustered index on a non unique column , internally SQL server add 4 bytes value for all duplicate instance of clustered key and this 4 bytes variable length column is known as uniquiifier .In this case SQL server consider the clustered key as the combination of non unique column on which clustered index is defined and internally generated uniquifier column.This value will be stored where ever the clustered key to be stored. For example in the leaf level of a non clustered index defined on a clustered table.

Let us see an example.I am going to create a copy of SalesOrderDetail table and define clustered index on the productid column which has duplicate values.

Use MyDb
GO
SELECT * INTO dbo.SalesOrderDetailDupCI FROM AdventureWorks2008.Sales.SalesOrderDetail
GO
CREATE CLUSTERED INDEX ix_SalesOrderDetailDupCI ON dbo.SalesOrderDetailDupCI(ProductId)

Now let us run the DBCC IND command

DBCC IND('mydb','SalesOrderDetailDupCI',1)

This returns me 1608 pages and  the root page number is 3570(The value of PagePID column of the record having highest value for indexlevel column ) .  Below is the output of DBCC Page command for the root page and one intermediate page


In the output, we can see one additional column called UNIQUIFIER which we did not seen when we created a unique clustered index in earlier post. When a clustered index created on a non unique column , SQL server add 4 bytes random value for all duplicate occurrence of clustered key. It will not generate the uniquifier value for the first occurrence. That is the reason there are 0 for uniquifier column for some records. So clustered key defined on the non unique column has an overhead of generating the uniquifier value and also widen the cluster index key.In our example we defined clustered index on a 4 bytes column but actual clustered key size become 8 bytes due to uniquifier.This combination has to replicated to leaf level of all non clustered index .The magnitude of the issue will increase when there is non clustered index  defined on non unique column where this clustered index value need to be stored in the non leaf level pages also.(We will discuss about non clustered index on non unique column in later post).

If your table does not have a single unique key to define clustered index, try to make it unique by adding one or two narrow column to the clustering key. That will avoid the overhead of adding the uniquifier and reduce the bookmark look up operation as the non leaf level of non clustered index has more columns (The additional column added to clustered key to make it unique)

Static
Another desired property of the clustered index key is to be a Static. when we define clustered index on a non static column , that makes the update statement(updating the clustered index key)  more costly as it has to move the record into different page  to make sure the data is stored in the logical order of clustered index and leaf level of all non clustered index need to be updated. Let us see a sample 

set statistics io on 
GO

--Unique clustered index on SalesOrderDetailIdUPDATE SalesOrderDetail_StaticIndex SET ProductID =99 WHERE ProductID=707
GO--Nonunique clustered index on ProductIdUPDATE SalesOrderDetail SET ProductID =99 WHERE ProductID=707
                              
    

In the below output you can see a huge change in IO for the second update statement.












Even in small table (Customer_id,Firstname.lastname) on which clustered index defined on a non static column (Lastname) and which has one non clustered index, any change in the clustered index key need to make changes in minimum of two pages.One data page and one leaf level page of non clustered index.

Size of the clustered index key

Size of the clustered index refers to the number of bytes requires to store the clustered index key.As the size of the clustered index increases, more IO required to fetch the records.This is happening because an index page can store lesser index row if the clustered index is wider. That increase number of pages in the intermediate level and depth of the indexes (Levels in the b tree structure) .For example, a table which contain millions of records might need only 3 level in b tree structure if the clustered index in defined on integer column. If we defined clustered index on wider column (say a uniqueidentifier column which need 16 bytes), the depth of index might increase to 4 (Level of index). Any clustered index seek requires 4 IO operation compared to 3( if the clustered index is narrow).

This issue propagate to non clustered index also as the clustered index keys are stored in the leaf level of all non clustered index as a pointer to the clustered index. If the non clustered index is defined on the non unique column , the clustered key need to be stored in non leaf level pages of  the non clustered index . Which again might cause for more page in intermediate level and to increase the depth of the in non clustered index which in turn increase the IO operation in non clustered index seek/scan also. As the clustered index depth is increased to 4, each bookmark look up operation also need to do 4 IO operation.

Sequential 

It is a best practice to define clustered index on a ever increasing(sequential) column. That is the reason we can commonly seen clustered index defined on identity column. Clustered index defined on a  non sequential column cause for fragmentation . To read more on fragmentation refer this posts . A non sequential clustered index key force the SQL server to insert record in between to maintain the logical ordering of the data.This lead to page split which cause for external fragmentation and internal fragmentation.

Conclusion 

We have discussed about the desired qualities of the clustered index key and the reason behind that.The above points that we discussed are general best practices to be considered while deciding the clustered index key.Apart from this, data access pattern also influence in deciding the clustered index key.If we do not have complete understand of the data access pattern , we might need to test the performance with different strategies.                        




If you liked this post, do like my page on FaceBook

SQL Server : Part 5 : Explaining Non clustered Index on Heap

In the last post, we have discussed about non clustered index on a clustered table.In this post we will discuss about the non clustered index on a heap table. 

Non clustered index can be created on clustered table as well as heap table.While creating a non clustered index on clustered table , clustered index key will act as a row pointer. In heap table ,the combination of file id , page number and slot number will act as a row pointer in the non  clustered index.

Let us see a hands on example. We will create a copy of salesorderdetail table with a non clustered index on productid and salesorderid columns

SELECT * INTO dbo.SalesOrderDetailHeap FROM AdventureWorks2008.Sales.SalesOrderDetail
GO
CREATE UNIQUE INDEX Ix_ProductId ON SalesOrderDetailHeap(ProductId,Salesorderid)

A pictorial representation of the b tree structure is given below

Let us run the DBCC IND command to find the root page of the index.

DBCC ind('mydb','SalesOrderDetailHeap',2)



This statement returns 289 records with 1 as maximum value in the indexlevel column. That means the index structure required one page in root node , 287 pages in leaf level and one page for IAM chain.The page number of record, having maximum value for indexlevel column (root page) is 1656. Let us see the root page.

DBCC traceon(3604)
GO
DBCC PAGE ('mydb',1,1656,3)

Below we can see a part of the output of DBCC page command. The structure of the output is same as the structure of root page of non clustered index on clustered table.

Fig 1

Now let us move to the page 1497 which is a leaf level page.

DBCC traceon(3604)
GO
DBCC PAGE ('mydb',1,1497,3)

Fig 2

 In the leaf level of non clustered index on clustered table , we have noticed that , clustered key is added to leaf level pages along with nonclustered key.Here we do not have a clustered index. So SQL server added row identifier (8 bytes in size) which is a combination of fileid (2 bytes) ,pageid(4 bytes) and slot number(2 bytes). The row identifier can be found in the  HeapRID column of Fig 2. From the above figure, it is clear that, the complete information of the record with productid=707 and salesorderid =49464 can be found at the location HeapRID 0x6813000001000600. Below query will help us to split the RID into FileId:PageId:SlotNo format

DECLARE @HeapRid BINARY(8)

SET @HeapRid = 0x6813000001000600SELECT
    
       CONVERT (VARCHAR(5),
                    CONVERT(INT, SUBSTRING(@HeapRid, 6, 1)
                               + SUBSTRING(@HeapRid, 5, 1)))
     + ':'
     + CONVERT(VARCHAR(10),
                    CONVERT(INT, SUBSTRING(@HeapRid, 4, 1)
                               + SUBSTRING(@HeapRid, 3, 1)
                               + SUBSTRING(@HeapRid, 2, 1)
                               + SUBSTRING(@HeapRid, 1, 1)))
     + ':'
          + CONVERT(VARCHAR(5),
                    CONVERT(INT, SUBSTRING(@HeapRid, 8, 1)
                               + SUBSTRING(@HeapRid, 7, 1)))
                               AS 'Fileid:Pageid:slot'

The output of the query is 1:4968:6 which says File id =1, Pageid =4968 and slot no=6. Let us see the page number 4968

DBCC traceon(3604)

GO

DBCC PAGE ('mydb',1,4968,3)

In the output, you can see all columns  of record having productid=707 and  salesordeid = 49464 at slot number 6. 

Let us consider  the below query and analyse how SQL sever fetch the data.

SET STATISTICS IO ON

GO
SELECT *  FROM SalesOrderDetail WHERE productid=707 AND SalesOrderid=49464

SQL Server  has to do two I/O operation to reach the leaf level of non clustered index and one I/O operation to fetch the remaining data using Heap RID from the heap structure.The execution plan of the query is given below

Even if we make changes in the query to fetch only the ProductId,SalesOrderid and SalesorderDetaildId columns, still SQL sever need to do Key lookup operation. This is because SalesOrderDetailid is not declared as clustered key and not available in the leaf level of the nonclustered index. To avoid the key lookup operation, we need to limit the select columns only to the non clustered key(ProductKey ,salesorderid).

If you liked this post, do like my page on FaceBook

SQL Server : Part 4 :Explaining the Non Clustered Index Structure

A table can have only one clustered index as the data rows are stored in the order of the clustered key, but a table can have multiple non clustered indexes.We have discussed about clustered index structure in our earlier post . In this post let us try to understand the non clustered index structure.

Logical Representation of Non Clustered index

In a simple word , a non clustered index is a subset of a table. When we define a non clustered index, SQL server store the set of non clustered key in a different pages.Let us consider a table with four columns (PersonId(PK),PersonType,FirstName,LastName) and a non clustered index on that table.The actual table is stored in the order of personid column (Cluster index key).In the below figure will give you a pictorial representation of non clustered index. The non clustered index key column are stored  apart from the actual table.If you look into the Non clustered index ,you can notice that, records are stored in the order of Firstname and lastname (Non Clustered index key) not as in the order of actual table.To understand easily , non clustered index can be considered as subset table of actual one. 

Fig 1

Now let us assume that we have a task to find out all records whose first name is 'Michael'.If you tried to find out from the Actual table , we need to go through each record from top to bottom to check whether first name matches with our search string 'Michael' as the records are not ordered based on the firstname column. It will be more tedious task if we have thousands of records in that table. The task will be much easier if we look into the the Non Clustered index side as the first name and last name are alphabetically ordered.We can easily locate the records which has firstname as 'Michael' and we do not need go beyond that as we are sure that there will not be any more records with firstname as 'Michael'.

Now we know Firstname and lastname of the record. How do we get the values for other two column ? Let us make a change in the Non clustered index part by associating the PersonId column along with the non clustered index.

Fig 2

Now, once we locate the records , we can go back to the Actual Table using the PersonId (Cluster index key) to find the values of other columns and this operation is called bookmark lookups or RID lookup. 

Clustered index v/s Non clustered index

Non clustered indexes have the same B-tree structure as clustered indexes.The non clustered  index key will not make any change in the sort order of underlying table where as clustered index force the SQL server to store the underlying table in the order of cluster index key. The leaf level of clustered index are made up of data pages which contain the actual data of table where as the leaf level of non clustered index are made up of index pages.

Non clustered index can be defined on a heap table or clustered table.In the leaf level of nonclusterd index, each index row contain the nonclustered key value and a row locator.This locator point to a the data row in the clustered index or heap.The row locator in nonclusterd index rows are either a pointer to a row or a clustered index key for a row. If the table is a heap, which means it does not have a clustered index,the row locator is a pointer to the row.The pointer is built from the file identifier ,page number and slot number of the row on the page. The whole pointer is known as a Row ID(RID). If the table has a clustered index, the row locator is the clustered index key for the row.

Hand on

Let us create a unique non clustered index on the salesorderdetails table that we were working on the clustered index post. The table has a unique clustered index on salesorderdetailid column. Now we are defining a non clustered index using the below statement

CREATE UNIQUE INDEX Ix_ProductId ON SalesOrderDetail(ProductId,Salesorderid)



A pictorial representation of the b-tree structure is given below





















Now let us see how SQL server store the index. Let us see the output of DBCC IND command

DBCC IND('mydb','SalesOrderDetail',2)

The last parameter, 2 is the index id of the index Ix_ProductId. For the usage of DBCC IND refer this post.

The output returns me 229 records which include one IAM page and 228 index page.From this we can find the root page id by locating the record having highest value for  IndexLevel column. Remember that index level increase from leaf level to root. In this case, the root level page id is 4688 with index level 1. That means, the b-tree structure of this index has only root and leaf level  .There is no  intermediate level  in the b tree structure of this non clustered index. Let us see the page 4688.

DBCC traceon(3604)
GO
DBCC page('mydb',1,4688,3)

This returns the 228 records (228 leaf level index pages) .Part of the output is shown below.The output looks same as the clustered index root/intermediate page structure. The output can be read as , all the records where the combination of  productid,salesorderid is less than or equal to (707,51151) can be found in child page 2288. All the records where the combination of  productid,salesorderid is between (707,51151)  and (707,55920) can be found in the child page 2289 and so on.

Fig 3






Let us see the page 2289

DBCC traceon(3604)

GO

DBCC page('mydb',1,2289,3)




This returns 539 records, all with product id 707.As this index use only two level, this is the leaf level of the b tree structure. Here you can notice that, there is no child page id but we have the value of the salesorderdetailid column (Clustered index key) which SQL server use do key or bookmark look up operation.




Fig 4

Let us see, how SQL server perform a select operation using this index. 

SET STATISTICS IO ON
GO
SELECT *  FROM SalesOrderDetail WHERE productid=707 AND SalesOrderid=51192

The execution plan will looks like below.You can see the Key lookup operation in the execution plan.



Fig 5

















As the where condition exactly match with our non clustered index definition, SQL sever use that index to execute this query.As a first step SQL server reads the root page of b tree structure.The combination of our search criteria (707,51192) falls in to the second records (Refer Fig 3). So SQL server goes to the child page (Page id 2289).In that page, we can locate the record with the exact combination of (707,51192) with salesorderdetailid 37793. From here, SQL server do a key look up operation using the salesorderdetailid value. From the earlier post about clustered index, we know that , SQL server need to perform 3 I/O operation while searching on any clustered index key. So to complete this query, SQL server needs to do 5  I/O operation (2 in non clustered index and 3 for bookmark/key lookup operation in the clustered index)  and that is the same you can find in the output of IO statistics. 

To understand it better,let us consider non clustered index as subset table ( let us say table name Saleorderdetail_NC) of salesorderdetail table with columns productid,salesorderid and SalesorderDetailid and having combination ProductId and salesorderid  as clustered index.Then the result of the above query can  be obtained by combining the output of below two query.

SELECT *  FROM SalesOrderDetail_nc WHERE productid=707 AND SalesOrderid=51192

GO

SELECT *  FROM SalesOrderDetail WHERE SalesOrderDetailid=37793







As a last part let us see one more query




SELECT *  FROM SalesOrderDetail WHERE productid=707




This query returns 3083 records and the search condition is matching with the non clustered index first column. Still SQL server will not use the non clustered index to execute the query. Please find below the execution plan of this query.




Fig 6







The reason behind that, if it use the non clustered index, it has to do a key lookup operation for 3083 records . That itself requires  (3083X3)  9249 I/O operation . Instead of that, SQL sever can fetch the output by performing clustered index scan which need only 1501(Total number of pages required for clustered index b-tree structure) I/O operation.If we make slight changes in the query to select only Productid ,SalesOrderDetailid and SalesOrderId, SQL server use the non clustered index as it does not need to do the key lookup operation. The leaf level of the non clustered index have the values of these three column . Please find below the execution plan.

SELECT productid,salesorderdetailid,salesorderid  FROM SalesOrderDetail WHERE productid=707

FIg 7

I know this was a bit lengthy post, but still I feel it will give you the clear picture of the non clustered index structure.

If you liked this post, do like my page on FaceBook

SQL Server : Index Part 3 :Explaining the Clustered Table Structure

In SQL server, there are two types of table based on the storage.A table with clustered index is called Clustered Table and a table with out a clustered index is called Heap Table. In earlier post, we have discussed about the specialty and the storage structure of the heap table. In this post let us discuss about Clustered Table.

A table with clustered index is called clustered table.Clustered index stores the actual data in the order of clustering key using a b tree structure and the data can be stored only in one order.That is the reason SQL server restricted the number of cluster index to one on a table.Let us see a logical representation of b tree structure. I have done this logical representation based on the copy of SalesOrderDetail table from AdventureWorks2008 database.

USE mydb
GO
SELECT * INTO dbo.SalesOrderDetail FROM AdventureWorks2008.Sales.SalesOrderDetail
GO
CREATE UNIQUE CLUSTERED INDEX ix_SalesOrderDetail ON dbo.SalesOrderDetail(SalesOrderDetailID)

Fig 1

This table has 121317 records. SQL server requires 3 level to store this data.Let us look into the Fig 1 and analyse the pages. On top level, you can see only one page which is called root page. In all B tree structure, there will be only one page in the root level which is the entry point to the tree structure.The root level  is always the highest level . In our case root page has index  level 2. The pages in the root level and intermediate levels are called index pages.In the index pages, SQL server stores the clustering key and entry point(page pointer) to the next level of B tree. The clustering key stored against child page id is the lowest value stored in the below level page(Child page). The maximum value of the clustering key on a specific child page can be obtained by looking into the next record. For example, in that root level first record (Salesorderdetailid =NULL,pageid=456) says, salesorderdetailid less than or equal to 29599 can be found in the page number 456. The next entry (Salesorderdetailid =29599 ,pageid=520) says, salesorderdetailid value between 29599 and 60372 can be found on page 520 and son on.The prevpage and nextpage values will work as doubly link list to connect the pages in that level. As there is only one page in the root level, the value of prevpage and nextpage will be always 0.

Let us move to the next level. we have four pages in this level. You can find the values in the nextpage and prevpage which links the pages in that level. This level is called intermediate level. The number of intermediate level and pages in the intermediate levels are depends on the size of the table and clustering key. A large table can have multiple intermediate level  and a small table might not have any intermediate level.The values in this level can be read in the same way as we did in the root level. For example first entry in the first page  of this level ( Salesorderdetailid =NULL,pageid=392) says , all record with salesorderdetailid less than and equal to 72 can be found in the page number 392.

Next level is the bottom level is called leaf level (index level 0). The pages in this level are called  leaf pages or data pages. In this page you can find complete data(all column)  of each record in the salesorderdetails table.In other words , the leaf level of the clustered index is where the actual data is stored.

Let us create a copy of SalesOrderDetail table without any indexes


USE mydb
GO
SELECT * INTO dbo.SalesOrderDetailHeap FROM AdventureWorks2008.Sales.SalesOrderDetail
GO

Now let us run the below set of query.Both will return the same record.We are more interested to see the IO part. 


SET STATISTICS IO ON

GO

SELECT * FROM SalesOrderDetail WHERE SalesOrderDetailID =75
GO
SELECT * FROM SalesOrderDetailheap WHERE SalesOrderDetailID =75

The IO stats result look like as below.The logical read on the table which has clustered index is negligible compared to other one.










Let us see how SQL server manage to fetch the record using clustered index with 3 logical reads.First of all we need to find the root node of the clustered index. The dbcc ind will help us to find that.

DBCC IND('mydb','SalesOrderDetail',1)

This is returning 1501 records.This include one IAM page , one index page and 1499 data pages.Part of the output is shown below 

From the output ,we can see that page 186 (page type 2) is the root page and this page is the entry point to this table. Let us see the out put of DBCC page.

DBCC traceon(3604)

GO
DBCC page('mydb',1,186,3)




SQL server stores the lowest value of clustered key stored in the child page and its page id in the index pages.For example Page 456 will have information of all the records that have value less than or equal to  29599 for salesorderdetailid column . In the same way page 520 will have information of all records that have value between 29599 and 60372 for salesorderdetailid(29599 may be there in both pages)  and so on.The value of salesorderdetailid column for the record that we are searching is less than 29599. So the information about that records can be found in the childpage 456. 

Let us see what we can see inside the page 456

DBCC traceon(3604)

GO
DBCC page('mydb',1,456,3) 




The output contains 401 records and below is part of the output. you can run the DBCC page command with option 1 (last parameter) to see the page header.There we can find the m_type=2 which means it is a index page.As we discussed above,the details of records that we are searching (Salesorderdetailsid=75) can be found in the child page 393.




Let us see what we can see in page number 393.

DBCC traceon(3604)

GO
DBCC page('mydb',1,393,3)  with tableresults

From the page header section we can see that value of m_type is 1. So this page is data page and it is the leaf level of the index. On scrolling down the output we can see the details of the record that we are searching as given below.We have value for all columns of the record that we are searching as the leaf level of the clustered index is the actual data.

SQL server manage fetch the records from clustered index reading only three pages(Root page,one page from intermediate level and one page from level)

Storage Overhead :Let us run the DBCC ind command for both tables(SalesOrderDetail and SalesOrderDetailHeap) 

DBCC IND('mydb','SalesOrderDetail',1)

DBCC IND('mydb','SalesOrderDetailHeap',1)

From the output, we can see that the table, that does not have clustered index need 1496 page where as the table with clustered index need 1501 pages. This extra 5 pages are used to store the intermediate and root level of the b tree structure.Considering the advantage that we have on the select (lesser IO), this is a negligible overhead.

If you liked this post, do like my page on FaceBook