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