You’re probably most familiar with
the terms ‘Seek’ and ‘Scan’ from
the graphical plans produced by SQL Server Management Studio (SSMS).
The image to
the left shows
the most common ones, with
the three types of scan at
the top, followed by four types of seek. You might look to
the SSMS tool-tip descriptions to explain
the differences between them: Not hugely helpful are they? Both mention scans and ranges (nothing about seeks) and
the Index Seek description implies that it will not scan
the index entirely (which isn’t necessarily true). Recall also yesterday’s post where we saw two Clustered Index Seek operations doing very different things.
The first Seek performed 63 single-row seeking operations; and
the second performed a ‘Range Scan’ (more on those later in this post). I hope you agree that those were two very different operations, and perhaps you are wondering why there aren’t different graphical plan icons for Range Scans and Seeks? I have often wondered about that, and
the first person to mention it after yesterday’s post was Erin Stellato (twitter | blog): Before we go on to make sense of all this, let’s look at another example of how SQL Server confusingly mixes
the terms ‘Scan’ and ‘Seek’ in different contexts.
The diagram below shows a very simple heap table with two columns, one of which is
the non-clustered Primary Key, and
the other has a non-unique non-clustered index defined on it.
The right hand side of
the diagram shows a simple query, it’s associated query plan, and a couple of extracts from
the SSMS tool-tip and Properties windows. Notice
the ‘scan direction’ entry in
the Properties window snippet. Is this a seek or a scan?
The different references to Scans and Seeks are even more pronounced in
the XML plan output that
the graphical plan is based on. This fragment is what lies behind
the single Index Seek icon shown above: You’ll find
the same confusing references to Seeks and Scans throughout
the product and its documentation. Making Sense of Seeks Let’s forget all about scans for a moment, and think purely about seeks. Loosely speaking, a seek is
the process of navigating an index B-tree to find a particular index record, most often at
the leaf level. A seek starts at
the root and navigates down through
the levels of
the index to find
the point of interest: Singleton Lookups
The simplest sort of seek predicate performs this traversal to find (at most) a single record. This is
the case when we search for a single value using a unique index and an equality predicate. It should be readily apparent that this type of search will either find one record, or none at all. This operation is known as a singleton lookup. Given
the example table from before,
the following query is an example of a singleton lookup seek: Sadly, there’s nothing in
the graphical plan or XML output to show that this is a singleton lookup – you have to infer it from
the fact that this is a single-value equality seek on a unique index.
The other common examples of a singleton lookup are bookmark lookups – both
the RID and Key Lookup forms are singleton lookups (an RID lookup finds a single record in a heap from
the unique row locator, and a Key Lookup does much
the same thing on a clustered table). If you happen to run your query with STATISTICS IO ON, you will notice that ‘Scan Count’ is always zero for a singleton lookup. Range Scans
The other type of seek predicate is a ‘seek plus range scan’, which I will refer to simply as a range scan.
The seek operation makes an initial descent into
the index structure to find
the first leaf row that qualifies, and then performs a range scan (either backwards or forwards in
the index) until it reaches
the end of
the scan range.
The ability of a range scan to proceed in either direction comes about because index pages at
the same level are connected by a doubly-linked list – each page has a pointer to
the previous page (in logical key order) as well as a pointer to
the following page.
The doubly-linked list is represented by
the green and red dotted arrows in
the index diagram presented earlier. One subtle (but important) point is that
the notion of a ‘forward’ or ‘backward’ scan applies to
the logical key order defined when
the index was built. In
the present case,
the non-clustered primary key index was created as follows: CREATE TABLE
dbo.Example
(
key_col INTEGER NOT NULL,
data INTEGER NOT NULL,
CONSTRAINT [PK dbo.Example key_col]
PRIMARY KEY NONCLUSTERED (key_col ASC)
)
;
Notice that
the primary key index specifies an ascending sort order for
the single key column. This means that a forward scan of
the index will retrieve keys in ascending order, while a backward scan would retrieve keys in descending key order. If
the index had been created instead on key_col DESC, a forward scan would retrieve keys in descending order, and a backward scan would return keys in ascending order.
A range scan seek predicate may have a Start condition, an End condition, or both. Where one is missing,
the scan starts (or ends) at one extreme end of
the index, depending on
the scan direction. Some examples might help clarify that:
the following diagram shows four queries, each of which performs a single seek against a column holding every integer from 1 to 100 inclusive.
The results from each query are shown in
the blue columns, and relevant attributes from
the Properties window appear on
the right:
Query 1 specifies that all key_col values less than 5 should be returned in ascending order.
The query plan achieves this by seeking to
the start of
the index leaf (there is no explicit starting value) and scanning forward until
the End condition (key_col < 5) is no longer satisfied (SQL Server knows it can stop looking as soon as it finds a key_col value that isn’t less than 5 because all later index entries are guaranteed to sort higher).
Query 2 asks for key_col values greater than 95, in descending order. SQL Server returns these results by seeking to
the end of
the index, and scanning backwards (in descending key order) until it comes across a row that isn’t greater than 95. Sharp-eyed readers may notice that
the end-of-scan condition is shown as a Start range value. This is a bug in
the XML show plan which bubbles up to
the Properties window – when a backward scan is performed,
the roles of
the Start and End values are reversed, but
the plan does not reflect that. Oh well.
Query 3 looks for key_col values that are greater than or equal to 10, and less than 15, in ascending order. This time, SQL Server seeks to
the first index record that matches
the Start condition (key_col >= 10) and then scans forward through
the leaf pages until
the End condition (key_col < 15) is no longer met.
Query 4 performs much
the same sort of operation as Query 3, but requests
the output in descending order. Again, we have to mentally reverse
the Start and End conditions because of
the bug, but otherwise
the process is
the same as always: SQL Server finds
the highest-sorting record that meets
the condition ‘key_col < 25’ and scans backward until ‘key_col >= 20’ is no longer true.
One final point to note: seek operations always have
the Ordered: True attribute. This means that
the operator always produces rows in a sorted order, either ascending or descending depending on how
the index was defined, and whether
the scan part of
the operation is forward or backward. You cannot rely on this sort order in your queries of course (you must always specify an ORDER BY clause if order is important) but SQL Server can make use of
the sort order internally. In
the four queries above,
the query optimizer was able to avoid an explicit Sort operator to honour
the ORDER BY clause, for example.
Multiple Seek Predicates
As we saw yesterday, a single index seek plan operator can contain one or more seek predicates. These seek predicates can either be all singleton seeks or all range scans – SQL Server does not mix them. For example, you might expect
the following query to contain two seek predicates, a singleton seek to find
the single record in
the unique index where key_col = 10, and a range scan to find
the key_col values between 15 and 20:
SELECT key_col
FROM dbo.Example
WHERE key_col = 10
OR key_col BETWEEN 15 AND 20
ORDER BY key_col ASC
;
In fact, SQL Server transforms
the singleton seek (key_col = 10) to
the equivalent range scan, Start:[key_col >= 10], End:[key_col <= 10]. This allows both range scans to be evaluated by a single seek operator. To be clear, this query results in two range scans: one from 10 to 10, and one from 15 to 20.
Final Thoughts
That’s it for today – tomorrow we’ll look at monitoring singleton lookups and range scans, and I’ll show you a seek on a heap table.
Yes, a seek. On a heap. Not an index!
If you would like to run
the queries in this post for yourself, there’s a script below. Thanks for reading!
IF OBJECT_ID(N'dbo.Example', N'U')
IS NOT NULL
BEGIN
DROP TABLE dbo.Example;
END
;
-- Test table is a heap
-- Non-clustered primary key on 'key_col'
CREATE TABLE
dbo.Example
(
key_col INTEGER NOT NULL,
data INTEGER NOT NULL,
CONSTRAINT [PK dbo.Example key_col]
PRIMARY KEY NONCLUSTERED (key_col)
)
;
-- Non-unique non-clustered index on
the 'data' column
CREATE NONCLUSTERED INDEX
[IX dbo.Example data]
ON dbo.Example (data)
;
-- Add 100 rows
INSERT dbo.Example
WITH (TABLOCKX)
(
key_col,
data
)
SELECT key_col = V.number,
data = V.number
FROM master.dbo.spt_values AS V
WHERE V.[type] = N'P'
AND V.number BETWEEN 1 AND 100
;
-- ================
-- Singleton lookup
-- ================
;
-- Single value equality seek in a unique index
-- Scan count = 0 when STATISTIS IO is ON
-- Check
the XML SHOWPLAN
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col = 32
;
-- ===========
-- Range Scans
-- ===========
;
-- Query 1
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col <= 5
ORDER BY
E.key_col ASC
;
-- Query 2
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col > 95
ORDER BY
E.key_col DESC
;
-- Query 3
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col >= 10
AND E.key_col < 15
ORDER BY
E.key_col ASC
;
-- Query 4
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col >= 20
AND E.key_col < 25
ORDER BY
E.key_col DESC
;
-- Final query (singleton + range = 2 range scans)
SELECT E.key_col
FROM dbo.Example AS E
WHERE E.key_col = 10
OR E.key_col BETWEEN 15 AND 20
ORDER BY
E.key_col ASC
;
-- === TIDY UP ===
DROP TABLE dbo.Example;
© 2011 Paul White
email:
[email protected]
twitter: @SQL_Kiwi
