Indexes Rose Hulman Institute of Technology Curt Clifton Overview Introduction to Indexes Index Architecture How SQL Server Retrieves Stored Data How SQL Server Maintains Index and Heap Structures Deciding Which Columns to Index Storing and Accessing Data How Data Is Stored Rows are stored in data pages Heaps are a collection of data pages for a table Data Pages Page 4 Con Funk White Page 5 Rudd White Barr Page 6 Akhtar Funk Smith Martin Page 8 Page 7 Smith Ota Jones Martin Phua Jones Smith Page 9 Ganio Jones Hall Whether to Create Indexes Why to Create an Index Speeds up data access Enforces uniqueness of rows Why Not to Create an Index Consumes disk space Incurs overhead Using Heaps SQL Server Uses Index Allocation Map Pages That Contain information on where the extents of a heap are stored Navigate through the heap and find available space for new rows being inserted Connect data pages Reclaims Space for New Rows in the Heap When a Row Is Deleted Using Clustered Indexes Each Table Can Have Only One Clustered Index The Physical Row Order of the Table and the Order of Rows in the Index Are the Same Key Value Uniqueness Is Maintained Explicitly or Implicitly Using Nonclustered Indexes Nonclustered Indexes Are the SQL Server Default Existing Nonclustered Indexes Are Automatically Rebuilt When An existing clustered index is dropped A new clustered index is created The DROP EXISTING option is used to change which columns define the clustered index Maintaining Index and Heap Structures Page Splits in an Index INSERT member last name VALUES lastname Jackson Index Pages Non Leaf Level Akhtar Martin Akhtar Ganio Jackson Lang Smith Leaf Leaf Level Level Key Value Akhtar Barr Barr Borm Buhl Ganio Akhtar Hall Barr Hart Barr Borm Buhl Jackson Ganio Jones Hall Jones Hart Jones Jones Lang Martin Martin Martin Moris Smith Smith Smith Smith Smith Forwarding Pointer in a Heap sysindexes Page 37 Akhtar Ganio really id indid 2 Akhtar Martin Page 12 Root UPDATE member SET Address long WHERE lastname Ota Page 41 Akhtar 4 706 01 Barr 4 705 03 Con 4 704 01 Funk 4 706 02 Funk 4 704 02 Page 51 Ganio 4 709 01 Hall 4 709 04 Jones 4 709 02 Jones 4 708 03 Jones 4 707 03 root Non Leaf Level Page 28 Martin Smith Page 61 Martin 4 708 01 Martin 4 706 04 Ota 4 707 02 Ota Phua 4 708 02 Rudd 4 705 01 Non Clustered clustered Index Page 71 Leaf Level Smith 4 706 03 Key Value Smith 4 708 04 Smith 4 707 01 White 4 704 03 White 4 705 02 Heap Page 704 01 Conn 02 Funk 03 White File ID 4 Page 705 01 Rudd 02 White 03 Barr Page 706 01 Akhtar 02 Funk 03 Smith 04 Martin Page 707 01 Smith 02 02 Ota 03 Jones 04 Corets 05 Nash Page 708 01 Martin 02 Phua 03 Jones 04 Smith Page 709 01 Ganio 02 Jones 03 Hall 04 Ota Row Updates Generally do not cause rows to move Like a delete followed by an update Logically Sometimes practically Batch updates touch each index once Deletion Deletion creates ghost records Reclaiming space Free pages when empty For indexed table Can overwrite ghost records immediately For non indexed table Compact records when more space is needed for insert Deciding What to Index What You Need to Know Logical and Physical Database Design Data Characteristics How Data Is Used The types of queries performed The frequency of queries that are typically performed Indexing Guidelines Columns to Index Primary and foreign keys Those frequently searched in ranges Those frequently accessed in sorted order Those frequently grouped together during aggregation Columns Not to Index Those seldom referenced in queries Those that contain few unique values Those defined with text ntext or image data types Choosing the Clustered Index Heavily Updated Tables Sorting A clustered index with an identity column keeps updated pages in memory A clustered index keeps the data pre sorted Column Length and Data Type Limit the number of columns Reduce the number of characters Use the smallest data type possible Data Characteristics Density last name first name Randall Joshua Randall Randall Ota Cynthia Tristan High Density SELECT FROM member WHERE last name Randall Low Density Lani SELECT FROM member WHERE last name Ota Data Characteristics Selectivity How effective is a column at selecting a subset of the data A property of a given query Rows matching property Total number of rows Determining Selectivity member no last name first name 1 2 Randall Flood Number of rows meeting criteria Total number of rows in table Anderson Bill Low selectivity member no last name first name 1 2 Randall Flood Joshua Kathie Number of rows meeting criteria Total number of rows in table SELECT FROM member WHERE member no 9001 10000 1000 10000 10 SELECT FROM member WHERE member no 8999 10000 Joshua Kathie High selectivity Anderson Bill 9000 10000 90 Indexing to Support Queries Writing Good Search Arguments Specify a WHERE clause in the query Verify that the WHERE clause limits the number of rows Verify that an expression exists for every table referenced in the query Avoid using leading wildcards Introduction to Statistics Standard Distribution of Values Number of Last Names A E F J K O P U Last Name V Z Even Distribution of Values Number of Last Names A B C F G K L N Last Name O Z How Statistics Are Gathered DMBS reads samples column values Performs a full scan or sampling of rows Produces an evenly distributed sorted list of values Depending on size of table and granularity wanted Selects samplings if necessary Picks rows to be sampled Includes all rows on the page of selected rows Creating Statistics Automatically Creating Statistics Indexed columns that contain data Non indexed columns that are used in a join predicate or a WHERE clause Manually Creating Statistics Columns that are not indexed All columns other than the first column of a composite index Viewing Statistics The DBCC SHOW STATISTICS Statement Returns Statistical Information in the Distribution Page for an Index or Column Statistical Information Includes The time when the statistics were last updated The number of rows sampled to produce the histogram Density information Average key length Histogram step information Performance Considerations Create Indexes on Foreign Keys Create the Clustered Index Before Nonclustered Indexes Consider Creating Composite Indexes Create Multiple Indexes for a Table That Is Read Frequently