Sunday, October 14, 2012

SQL Server Index internals (SQL Server)

What Is an Index?
One of the best ways to reduce logical reads and I/ O reads is Index. An Index can be used to search the data in table without scanning the entire table. An Index in database is analogous to Index of book. Say, for example if you want to look up a phrase in book, you can directly go to that page using Index of Book.

You can use two different approaches to create Index on the Table.

Like a dictionary:
A Dictionary stores data in alphabetical order. An Index on table can maintain data in similar fashion. The data is ordered, although it will be duplicates. Data can be directly accessed once it is sorted. This type of index is clustered Index.

Like an Index:
Just like Index of book, Index on table can contain Index values and pointer to actual data. This type of index is non-clustered Index.

Index Design Recommendations:

1. Examine the WHERE Clause and Join Criteria Columns:
a.       Optimizer identifies list of columns used in Joins and Where Clause.
b.       Optimizer then examines indexes on those columns and chooses the best clause to improve the performance
c.        Finally, Optimized estimate least costly method of retrieving the rows

Download Adventure Works database from codeplex and restore it as:

    ON (FILENAME = 'D:\Programming\AdventureWorks2008_Data.mdf'),
    (FILENAME = 'D:\Programming\AdventureWorks2008_Log.ldf')

When WHERE Clause is not included:
SELECT * FROM Person.Person

(19972 row(s) affected)
Table 'Person'. Scan count 1, logical reads 3816, physical reads 0

Once WHERE Clasue is included in query:

SELECT * FROM Person.Person A
WHERE A.BusinessEntityID = 2
(1 row(s) affected)
Table 'Person'. Scan count 0, logical reads 3, physical reads 0

2. Use Narrow Index:
If more will be size of data page, more will be time taken to search the data (A narrow index can accommodate more rows in a 8KB data page). So, minimize the use of wide data types in an index.
Following example shows, how Index is represented in B Tree:

FROM sys.indexes A
      INNER JOIN sys.dm_db_index_physical_stats(DB_ID(N'MyAdventureWorks'), OBJECT_ID(N'Person.Person'), NULL, NULL, 'DETAILED') AS B
            ON A.index_id = B.index_id
WHERE A.object_id = object_id (N'Person.Person')

If more wider will be index, more Pages/ levels will be required to represent B Tree and more time Index it will take to search data.

3. Examine column Uniqueness:

Query optimizer will not able to narrow down the result if column values are not unique.
For example: Creating Index on Gender column will not help narrow down the result for Optimizer

The column with highest number of unique values can be best candidate for Indexing when referred to WHERE 
or Join clause.

Note: It is highly recommended that you create Index on column having high selectivity.

                  Selectivity = Total Number of rows in table / Total Unique values of column 

3. Consider column ordering:

An Index key is sorted on the column of Index. If Index is created on more than one column (Composite Index), Index key will be sorted on first column then on rest of the column.

CREATE NONCLUSTERED INDEX [IX_Person_LastName_FirstName_MiddleName] ON [Person].[Person]
      [LastName] ASC,
      [FirstName] ASC,
      [MiddleName] ASC

FROM Person.Person
WHERE FirstName = 'Isabella' 

FROM Person.Person
WHERE LastName = 'Miller'          

Look up is performed to get other column since in this case only 3 columns are leaf node. A clustered Index is already created on table hence Leaf node will point to Clustered Index and uses Clustered Key Look up.

FROM Person.Person
WHERE LastName = 'Miller'          
      AND MiddleName = 'A'

Clustered Index: Table rows are sorted on clustered Index column in data Pages, and since there can be one order table data, a table can have only Clustered Index

Heap Table: A table with no Clustred index in Heap Table

Relationship with Non Clustered Index:
1.       If table contains no Clustered Index, the leaf node of nonClustered Index will contain the Index
column and Pointer to heap table containg the actual data rows
2.       If table contains Clustered Index, the leaf node of nonClustered Index will contain the Index column and Pointer to Clustered Index column


If NonClustered Index is created on Col2

Case 1: Non Clustered Index with no Clustered Index
Pointer to Col1 = 1
Pointer to Col1 = 2

Case 2: Non Clustered Index with Clustered Index

Clustered Index Recommendations:
1.       Create Clustered Index first then create Non Clustered Index. If we create Non Clustered Index first then Row Locator will point to heap but not Clustered Index
2.       Keep Index Narrow
3.       Rebuild the Index in single step using DROP_EXISTING clause

When Not to use a Clustered Index:
1.       Do not create Clustered Index on most updated column since it will change the row locator of NonClustered Index, increasing the cost of queries.
2.       Wide Keys

In both above mentioned cases, NonClustered Index will be recommended.

Advance Indexing Techniques
1.      Covering Index: A Covering Index is created on all the columns required to satisfy the a SQL query without going to a Base Table

SELECT PostalCode
FROM Person.Address
      WHERE StateProvinceID = 42

Lookup is required to get PostalCode  column of table hence we can create NonClustered Index on StateProvinceID and PostalCode. We can use INCLUDE operator to create Covering Index.

 ON [Person].[Address]
            [StateProvinceID] ASC
INCLUDE (PostalCode)

If we rerun the query, then Index Seek is performed without any Lookup.

If the column is not in the WHERE/JOIN/GROUP BY/ORDER BY, but only in the column list in the SELECT clause.
The INCLUDE clause adds the data at the lowest/leaf level, rather than in the index tree. This makes the index smaller because it's not part of the tree
This means it isn't really useful for predicates, sorting etc as I mentioned above. However, it may be useful if you have a residual lookup in a few rows from the key column(s) 

2.      Index Intersections: SQL Server can use two or more Indexes to optimize query execution Plan.
If there is more than one Index in table then SQL Server can perform intersection of all the Indexes and Optimize the query.
For Example: If NonClustered Index is created on SalesPersonID column and no Index is created on OrderDate, SQL Server uses Clustered Index Scan to get the result

FROM Sales.SalesOrderHeader
WHERE SalesPersonID = 276
            AND OrderDate BETWEEN '4/1/2002' AND '7/1/2002'

We can include OrderDate column in NonClustered Index of SalesPersonID to improve the performance. Sometimes, it is not permissible to include other column in NonClustered Index. We can create another NonClustered Index in that case.
      ON Sales.SalesOrderHeader

Now, if we rerun the query Index Intersection will perform and resulting Index seek.

3.      Index Joins: Index Join is variation of index intersection. When covering Index Technique is applied to Index Intersection then Index Join is performed.
For example:
SELECT SalesPersonID, OrderDate
FROM Sales.SalesOrderHeader
WHERE SalesPersonID = 276
      AND OrderDate BETWEEN '4/1/2002' AND '7/1/2002'

4.      Filtered Index: A NonClustered index that uses a filter, basically a WHERE clause, to create a highly selective set of keys against a column. For example, a column with a large number of null values having NonClustered Index created on it. We can recreate NonClustered Index containing Not Null values, after filtering NULL values

Sales.SalesOrderHeader (PurchaseOrderNumber, SalesPersonId)
INCLUDE (OrderDate, ShipDate)
WHERE PurchaseOrderNumber IS NOT NULL
 AND SalesPersonId IS NOT NULL

5.      Indexed View: A database view can be materialized on the disk by creating a unique index on the view. Such view is referred as indexed view. Views result set is persisted immediately on physical storage in database. After the view is materialized, multiple NonClustered Index can be created on Indexed view.

Further Reading:

1. Video on Index Structure:

2. Video on Index Structure:

3. Column Store Index:

1 comment: