SQL Server 2000
Storage and Access Methods
Don Vilen
Program Manager
SQL Server Development Team
Agenda
? SQL Server Overview
? SQL Server Architecture
? Storage and Access Methods
? Query Processing and Optimization
? Transaction Processing
? Other Topics
Storage and Access Methods
Storage and Access Methods
? Heap – A table with no Clustered Index
? General Index Structure
? Clustered and Non-clustered Indexes
? Covering Indexes
? Index Intersection
? Fillfactor and Performance
? Index Reorganization
? Locking and Indexes
Heap – A Table with no Clustered
Index
Heap
Extent 160 Extent 168 Extent 176
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Con
Funk
White
...
...
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
04
05
Con
Funk
White
Durki
Lang
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Con
Funk
White
...
...
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
04
05
Dunn
Randall
Ota
Slichter
LaBrie
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Con
Funk
White
...
...
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Con
Funk
White
...
...
…
…
…
...
...
01
02
03
…
…
Smith
Ota
Jones
…
...
…
…
…
...
...
01
02
03
04
…
Akhtar
Funk
Smith
Martin
...
…
…
…
...
...
01
02
03
…
…
Rudd
White
Barr
...
...
…
…
…
...
...
01
02
03
…
…
Graff
Bacon
Koch
...
...
…
…
…
...
...
Extent 184
01
02
03
04
…
Seattle
Paris
Tokyo
Atlanta
...
…
…
…
...
...
IAM
…
160 1
168 1
176 0
184 1
…
Extent Bit Map
id indid = 0 First IAM
sysindexes
General Index Structure
Page 140 - Root
Page 141 Page 145
Akhtar
Ganio
…
Akhtar
…
Martin
Martin
Smith
…
Node Pages
id indid = x rootsysindexes
Page 100 Page 120 Page 130
Akhtar
Barr
Con
Funk
Funk
...
2334
5678
2534
1334
1534
...
...
...
...
...
...
...
Martin
Martin
Ota
Phua
Rudd
...
1234
7778
5878
7878
6078
...
...
...
...
...
...
...
Smith
Smith
Smith
White
White
...
1434
5778
7978
2234
1634
...
...
...
...
...
...
...
Page 110
Ganio
Hall
Jones
Jones
Jones
...
7678
8078
2434
5978
2634
...
...
...
...
...
...
...
Leaf
Pages
Clustered and Nonclustered
Indexes
? Common features
? Set of pages stored in B-Tree
? Node levels contain pointers to pages at the
next level
? Leaf level contains all key values
? Size and data distribution information is
stored in sysindexes
? Differences
? What else is stored in leaf level?
Clustered Indexes
? Leaf level is the data
? Uniqueness is maintained in key values
Finding Rows in a Clustered
Index
Clustered Index
Page 140 - Root
Page 100 Page 120 Page 130
Page 141 Page 145
Akhtar
Barr
Con
Funk
Funk
...
2334
5678
2534
1334
1534
...
...
...
...
...
...
...
Martin
Martin
Ota
Phua
Rudd
...
1234
7778
5878
7878
6078
...
...
...
...
...
...
...
Smith
Smith
Smith
White
White
...
1434
5778
7978
2234
1634
...
...
...
...
...
...
...
Akhtar
Ganio
…
Akhtar
…
Martin
Martin
Smith
…
Page 110
Ganio
Hall
Jones
Jones
Jones
...
7678
8078
2434
5978
2634
...
...
...
...
...
...
...
SELECT lastname,firstname
FROM member
WHERE lastname = 'Ota'
t,..
id indid = 1 rootsysindexes
Nonclustered Indexes
? Leaf level contains
? Columns of index
? Bookmark to data row
? Bookmark is either:
? RID (File #,Page #,Slot #)
? Unique clustered index key
? If overlap between clustered and nonclustered keys,value is
stored only once
? Rows are in order by first index column
? A Scan can be done on the leaf level
Heap
Page 707 Page 808 Page 709
01
02
03
04
...
...
...
...
...
...
Akhtar
Funk
Smith
Matey
...
Page 704 Page 705 Page 706
01
02
03
...
...
...
...
...
...
...
Conn
Funk
White
...
...
01
02
03
...
...
...
...
...
...
...
Rudd
White
Barr
...
...
01
02
03
...
...
...
...
...
...
...
Smith
Ota
Jones
...
...
01
02
03
04
...
...
...
...
...
...
Martin
Phua
Jones
Smith
...
01
02
03
...
...
...
...
...
...
...
Ganio
Jones
Hall
...
...
File ID #4
0202
SELECT lastname,firstname
FROM member
WHERE lastname
BETWEEN 'Masters' AND 'Rudd'
Non
clustered
Index
Leaf Level
(Key Value)
Page 41 Page 51 Page 61 Page 71
Akhtar
Barr
Con
Funk
Funk
4:706:01
4:705:03
4:704:01
4:706:02
4:704:02
Smith
Smith
Smith
White
White
4:706:03
4:708:04
4:707:01
4:704:03
4:705:02
Ganio
Hall
Jones
Jones
Jones
4:709:01
4:709:04
4:709:02
4:708:03
4:707:03
Martin
Matey
Ota
Phua
Rudd
4:708:01
4:706:04
4:707:02
4:708:02
4:705:01
t
Ota
Finding Rows With a NC Index On a
Heap
Non-Leaf
Level
Page 28Page 12 - RootPage 37
Akhtar
...
Martin
Martin
Smith
...
Akhtar
Ganio
...
id indid = 2 rootsysindexes
Clustered Index
On Last Name
Nonclustered
Index on
First Name
Non-Leaf
Level
Leaf Level
(Clustered
Key Value)
Aaron
Deanna
…
Aaron
...
Jose
Jose
Nina
…
Deanna
Don
Doug
Daum
Hall
Hampton
… …
Aaron
Adam
Amie
Con
Barr
Baldwin
… …
Jose
Judy
Mike
Lugo
Kaethler
Nash
… …
Barr Adam
Cox
Daum
Arlette
Deanna
… …
…
…
…
…
Kim
Kobara
LaBrie
Shane
Linda
Ryan
… …
…
…
…
…
Nagata
Nash
Nixon
Susanne
Mike
Toby
… …
…
…
…
…
Barr
Kim
Nagata
O’Melia
Finding Rows With a NC Index on a
Clustered Table
id indid = 2 rootsysindexes
SELECT lastname,firstname,phone
FROM member
WHERE firstname = 'Mike'
Covering Indexes
? A covering index contains all data needed
by query,in its leaf level
? This may include the clustered index key(s)
? A query satisfied by a covering index is a
covered query
? Meaningful only to nonclustered indexes
? Fastest type of data access
? Performance consideration
? Add one or two extra columns to an index to
allow it to cover crucial queries
Index Intersection
? Multiple indexes can be used for a single
table
? Microsoft SQL Server retrieves a set of
rows using each useful index,and then
sets must be combined
? SQL Server can use any JOIN technique to
combine intermediate result sets
? Example:
? SELECT * FROM charge
WHERE charge_amt < 5
AND provider_no = 301
Fillfactor and Performance
? Low fillfactor implies internal
fragmentation
? DBCC SHOWCONTIG shows,Avg,Page
Density”
? Low density is good for inserts
? Space for new rows on page
? Page splits are expensive
? Low density is bad for scans
? More pages must be accessed for same
amount of data
Index Reorganization
? DBCC SHOWCONTIG Shows three kinds of
external fragmentation
? Extent scan fragmentation
? Logical scan fragmentation
? Scan density
? DBCC INDEXDEFRAG Fixes logical scan
fragmentation
? Use FAST option of SHOWCONTIG to see if
DEFRAG is needed
? Rebuilding index removes all fragmentation
Indexed Views and Indexes on
Computed Columns
? Logical data can be materialized
? Seven SET options must be properly set
? All operations must be deterministic
? Indexed views must be built with schema
binding
? Indexed views can used without direct
reference
? Optimizer in Enterprise Edition can detect if
query matches the query tree of an indexed
view
Using Index Tuning Wizard
? Index Tuning Wizard Overview
? Index Tuning Architecture
? ITWiz.EXE Command Line Options
? Tips and Hints
Index Tuning Wizard Overview 1 of 2
? Allows you to select and create an optimal set of
indexes and statistics for a SQL Server 2000
database using a ?workload? provided
? A workload consists of a SQL script or a SQL
Profiler trace saved to a file or table containing a
SQL batch or remote procedure call (RPC)
events
? Index Analysis in 7.0 Query Analyzer is replaced
with full Index Tuning Wizard in SQL Server
2000 Query Analyzer
? Works on current script file or selection within Query
Analyzer
Index Tuning Wizard Overview 2 of 2
? Optionally limit the number of queries to tune
? Recommendations not only include creation of
new indexes,but also dropping of ineffective
indexes
? Supports Indexed Views and indexes on
computed columns
? Supports projected volumes
? Customizes recommendations via advanced
options like disk space constraints for new
indexes
? See,Index Tuning Wizard for SQL Server 2000”
white paper in MSDN
http://msdn.microsoft.com/library/default.asp?U
RL=/library/techart/itwforsql.htm
Index Tuning Architecture
Database
? Trace File
? Trace Table
? SQL Script
Index
Tuning
Wizard
Input Workload:
SQL Script File
Reports:
? Index Usage
(Recommended)
? Index Usage
(Current)
? Table Analysis
? View – Table Relations
? Query – Index Relations
(Recommended)
? Query – Index Relations
(Current)
? Query Cost
? Workload Analysis
? Tuning Summary
Exec Query -
Returns Only
Execution Plan Costs Cost
(I/O,CPU)
Index variations
ITWiz.EXE
? Index Tuning Wizard can be started from
command line
? Minimum parameters,using local server:
itwiz -D orders -i orders_wkld.sql
? Remote server:
itwiz -S servername -Usa -P -D northwind -i sample1.sql
? Storage bound of 3 GB for new indexes:
itwiz -D orders -i orders1.sql -B 3072 -o d:\script1.sql
? Only tune 10 queries:
itwiz -D orders -i orders_wkld.sql -n 10
? Thorough analysis mode:
itwiz -D orders -i script1.sql -M 2
Tips and Hints
? Index Tuning Wizard cannot effectively tune stored
procedures that use temporary objects
? Tuning should be performed against a test server (with
production data and schema loaded) to minimize
performance impact to the actual production server
? All indexes specified as hints will always be part of the
final recommendation
? Hints can prevent the Index Tuning Wizard from choosing a
better execution plan
? Index Tuning Wizard cannot recommend indexes for
cases involving triggers
? The default number of queries to be tuned is 200;
should increase this value to at least 1000
Questions?