SQL Server, Is a Seek Always Only a Seek? Singleton Lookup and Range Scan

Hi Guys,

Welcome back for another important post here on my blog!

Today we are going to deepen the functioning of a seek and see in more detail how it works.
I hope many of you are reading this post. My goal is in fact to explain in the clearest and most interesting way how SQL Server works.
If something is not clear to you, just ask, it will help me to improve.
Last news before start, in case you are genuinely and truly interested in one of the products that appear in advertising ... click the adv from my blog to support my site!

Crew, let's go !!! 

 

Recap about index and the way them works

Well, first of all we must do a recap about indexes and about the way them works.

 

I blogged many times about index for example, i suggest to read here: SQL Server, Difference between a seek and a scan operation and the Latch coupling

An index, clustered or not, has the following structure:

Every search start from the Root Page, then continue to the Intermediate pages and finally arrive to the leaf page.

While you navigate from left to right along these nodes of page you are doing a Seek operation.

Pages are not only connected from left to right so from Root to Intermediate pasges and from intermediate to Lead page.

Page are also connected through a double linked list structure, from top to bottom. Im this way you can pass from an intermediate page to another intermediate page or from a leaf page to another.

This is the way data are read when you do a SCAN: for example you can reach a leaf page and then pass to the next or previous leaf page.

Now, before going deep, let's introduce a simple data structure that we will use further on for the test!

Let's prepare the data for the test

For our tests we will use the simpliest table that came to my mind.

A table with only one field if type integer.

Upon this field i will add a clustered index.

CREATE TABLE ListofNumber ( id INT PRIMARY KEY CLUSTERED )

We insert the first 1000 integers into the table

WITH CTE AS (  
   SELECT 1 AS Numb  
   UNION ALL
   SELECT a.Numb + 1  
   FROM   CTE a
   WHERE  a.Numb < 1000
)
INSERT INTO LISTOFNUMBER(ID)
SELECT Numb 
FROM CTE
OPTION (MAXRECURSION 0)

Is a seek always only a seek?

Now is the time! Let's see how the indices work!

Let's start with a simplest case, the case number 1.

A primary key is a field in a table which uniquely identifies each row/record in a database table. Primary keys must contain unique values.

Since the field ID is a primary key i am sure the field contain only unique value.

I am sure that the following query will return only one value

SELECT * FROM LISTOFNUMBER WHERE ID = 123

In this simple case the seek predicate performs a pure b-tree traversal to find, at most, a single record.

This simple case is called singleton lookup. 

This is the execution plan, where we can see that the clustered index is used in SEEK mode.

These are the proprieties:

I cannot see nowhere is i am doing a singleton lookup but from the theory this can only happen if i have a unique index (or a PK) and an equality predicate (=)

Case number 2.

This time instead of the equality operator we will use the operators ">= "and "<="

SELECT * FROM LISTOFNUMBER WHERE ID > 123 AND ID <= 200

This time we may have rows lines as a result.

The execution plan is the same as the first case:

However, some properties change.

This time we have another type of seek predicate. 

It is called range scan Seek Predicate that stand for "seek followed by a range scan"

 

So, as we asked ourselves in the title: Is a Seek always only a seek? 

The answer is no! Even if we go in seek on an index, the operation can be a mixture of seek and scan.

A Range Scan seek predicate may have a start condition, an end condition, or both.

In this case we have only one seek predicate with a start condition (id>=123) and an end condition (id<=200)

 

 

What happen exactly? 

• The seek operation descent from the root into the index structure to find the first leaf row that qualifies.
• Then performs a range scan (this time forwards in the index) until it reaches the end of the scan range.

As we said at the beginning, 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.

Case number 3.

As a corollary, we will we that we can have multiple seek predicate.

Intuitively we can have multiple seek predicate when we have multiple predicate.

For example we can use an OR operator.

However you can note that the optimizer is smart, in the following case infact it is able to understand that the value 150 is inside the set (123,200).

SELECT * FROM LISTOFNUMBER WHERE ID > 123 AND ID <= 200 OR ID = 150

This query will we processed without the "OR ID=150" part.

If instead we will esecure the follownig query?

SELECT * FROM LISTOFNUMBER WHERE ID > 123 AND ID <= 200 OR ID = 5

What happens?

This time we have really two predicates:

 Note that we don not have a singleton lookup and a range scan but two range scan.

The first from 123 to 200 and the second from 5 to ....5!

Therefore we begin to understand that often a seek on an index means going in seek on the first record and from that record find the others by scanning.

 

Now I ask a question!
In your opinion is the singleton lookup or the range scan faster? 

You just have to follow me, here on the blog and on linkedin. 

That'all for today!

Stay tuned for the next posts!

If you are genuinely and truly interested in one of the products that appear in advertising ... click the adv from my blog to support my site! 

Or click the (    ) button to offer to me an ice-cream!

Previous post: SPEED NEWS! Cumulative Update 16 for SQL Server 2019 is out!