The following script creates a single-column clustered table containing
the integers from 1 to 1,000 inclusive. IF OBJECT_ID(N'tempdb..#Test', N'U')
IS NOT NULL
DROP TABLE #Test
;
GO
CREATE TABLE #Test
(
id INTEGER PRIMARY KEY CLUSTERED
);
;
INSERT #Test (id)
SELECT V.number
FROM master.dbo.spt_values AS V
WHERE V.[type] = N'P'
AND V.number BETWEEN 1 AND 1000
;
Let’s say we need to find
the rows with values from 100 to 170, excluding any values that divide exactly by 10. One way to write that query would be:
SELECT T.
id
FROM #Test AS T
WHERE T.
id IN
(
101,102,103,104,105,106,107,108,109,
111,112,113,114,115,116,117,118,119,
121,122,123,124,125,126,127,128,129,
131,132,133,134,135,136,137,138,139,
141,142,143,144,145,146,147,148,149,
151,152,153,154,155,156,157,158,159,
161,162,163,164,165,166,167,168,169
)
;
That query produces a pretty efficient-looking query plan:
Knowing that
the source column is defined as an INTEGER, we could also express
the query this way:
SELECT T.
id
FROM #Test AS T
WHERE T.
id >= 101
AND T.
id <= 169
AND T.
id % 10 > 0
;
We
get a similar-looking plan:
If you look closely, you might notice that
the line connecting
the two icons is a little thinner than before.
The first query is estimated to produce 61.9167 rows – very close to
the 63 rows we know
the query will return.
The second query presents a tougher challenge for SQL Server because it doesn’t know how to predict
the selectivity of
the modulo expression (T.
id % 10 > 0). Without that last line,
the second query is estimated to produce 68.1667 rows – a slight overestimate. Adding
the opaque modulo expression results in SQL Server guessing at
the selectivity. As you may know,
the selectivity guess for a greater-than operation is 30%, so
the final estimate is 30% of 68.1667, which comes to 20.45 rows.
The second difference is that
the Clustered Index Seek is costed at 99% of
the estimated total for
the statement. For some reason,
the final SELECT operator is assigned a small cost of 0.0000484 units; I have absolutely no idea why this is so, or what it models. Nevertheless, we can compare
the total cost for both queries:
the first one comes in at 0.0033501 units, and
the second at 0.0034054.
The important point is that
the second query is costed very slightly higher than
the first, even though it is expected to produce many fewer rows (20.45 versus 61.9167).
If you run
the two queries, they produce exactly
the same results, and both complete so quickly that it is impossible to measure CPU usage for a single execution. We can, however, compare
the I/O statistics for a single run by running
the queries with STATISTICS IO ON:
Table '#Test'. Scan count 63, logical reads 126, physical reads 0.
Table '#Test'. Scan count 01, logical reads 002, physical reads 0.
The query with
the IN list uses 126 logical reads (and has a ‘scan count’ of 63), while
the second query form completes with just 2 logical reads (and a ‘scan count’ of 1). It is no coincidence that 126 = 63 * 2, by
the way. It is almost as if
the first query is doing 63 seeks, compared to one for
the second query.
In fact, that is exactly what it is doing. There is no indication of this in
the graphical plan, or
the tool-tip that appears when you hover your mouse over
the Clustered Index Seek icon. To see
the 63 seek operations, you have click on
the Seek icon and look in
the Properties window (press F4, or right-click and choose from
the menu):
The Seek Predicates list shows a total of 63 seek operations – one for each of
the values from
the IN list contained in
the first query. I have expanded
the first seek node to show
the details; it is seeking down
the clustered index to find
the entry with
the value 101. Each of
the other 62 nodes expands similarly, and
the same information is contained (even more verbosely) in
the XML form of
the plan.
Each of
the 63 seek operations starts at
the root of
the clustered index B-tree and navigates down to
the leaf page that contains
the sought key value. Our table is just large enough to need a separate root page, so each seek incurs 2 logical reads (one for
the root, and one for
the leaf). We can see
the index depth using
the INDEXPROPERTY function, or by using
the a DMV:
SELECT S.index_type_desc,
S.index_depth
FROM sys.dm_db_index_physical_stats
(
DB_ID(N'tempdb'),
OBJECT_ID(N'tempdb..#Test', N'U'),
1,
1,
DEFAULT
) AS S
;
Let’s look now at
the Properties window when
the Clustered Index Seek from
the second query is selected:
There is just one seek operation, which starts at
the root of
the index and navigates
the B-tree looking for
the first key that matches
the Start range condition (id >= 101). It then continues to read records at
the leaf level of
the index (following links between leaf-level pages if necessary) until it finds a row that does not meet
the End range condition (id <= 169). Every row that meets
the seek range condition is also tested against
the Residual Predicate highlighted above (id % 10 > 0), and is only returned if it matches that as well.
You will not be surprised that
the single seek (with a range scan and residual predicate) is much more efficient than 63 singleton seeks. It is not 63 times more efficient (as
the logical reads comparison would suggest), but it is around three times faster. Let’s run both query forms 10,000 times and measure
the elapsed time:
DECLARE @i INTEGER,
@n INTEGER = 10000,
@s DATETIME = GETDATE()
;
SET NOCOUNT ON;
SET STATISTICS XML OFF;
;
WHILE @n > 0
BEGIN
SELECT @i =
T.
id
FROM #Test AS T
WHERE T.
id IN
(
101,102,103,104,105,106,107,108,109,
111,112,113,114,115,116,117,118,119,
121,122,123,124,125,126,127,128,129,
131,132,133,134,135,136,137,138,139,
141,142,143,144,145,146,147,148,149,
151,152,153,154,155,156,157,158,159,
161,162,163,164,165,166,167,168,169
)
;
SET @n -= 1;
END
;
PRINT DATEDIFF(MILLISECOND, @s, GETDATE())
;
GO
DECLARE @i INTEGER,
@n INTEGER = 10000,
@s DATETIME = GETDATE()
;
SET NOCOUNT ON
;
WHILE @n > 0
BEGIN
SELECT @i =
T.
id
FROM #Test AS T
WHERE T.
id >= 101
AND T.
id <= 169
AND T.
id % 10 > 0
;
SET @n -= 1;
END
;
PRINT DATEDIFF(MILLISECOND, @s, GETDATE())
;
On my laptop, running SQL Server 2008 build 4272 (SP2 CU2),
the IN form of
the query takes around 830ms and
the range query about 300ms.
The main point of this post is not performance, however – it is meant as an introduction to
the next few parts in this mini-series that will continue to explore scans and seeks in detail.
When is a seek not a seek? When it is 63 seeks
© Paul White 2011
email:
[email protected]
twitter: @SQL_kiwi
