THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Kalen Delaney

T-SQL Tuesday: What kind of Bookmark are you using?

TSQL2sDay150x150

I’m glad there is no minimum length requirement for T-SQL Tuesday blog posts, because this one will be short. I was in the classroom for almost 11 hours today, and I need to be back tomorrow morning at 7:30.

Way long ago, back in SQL 2000 (or was it earlier?) when a query indicated that SQL Server was going to use a nonclustered index to get row pointers, and then look up those rows in the underlying table, the plan just had a very linear look to it. The operator that indicated going from the nonclustered leaf to the data row was called a ‘Bookmark Lookup’, and it just looked a simple, single operator. Those of us that did troubleshooting of query plans knew that it could hide a multitude of sins, but to many people it looked very innocuous.

Then in the next version, that simple, single Bookmark Lookup Operator was replaced by something that looked like a JOIN! When I first saw query plans showing a JOIN when doing a nonclustered index lookup, I was almost distraught, but it turns out that was only because it was new and different. The more I thought about it, the more I realized it was a Good Thing.

Some people might get confused because they think of a JOIN as an operation that finds matches rows between two tables. But in fact, a JOIN can be used to find matches between any two sets of rows. And in the case of a nonclustered index lookup, SQL Server is finding rows in the leaf level of a nonclustered index (the ones that meet your filter condition(s) ) , and then is finding the matching rows in the underlying table. Internally, this is a JOIN operation.

But when we look at the plans, there are two different operators used to show the actual lookup into the underlying table.

There is a RID Lookup, used when the table is a heap. The nonclustered index contains Row ID, or RID, values (composed of a File ID, a Page ID and a Slot/Row number on the page). This RID is then used to ‘match’ with rows in the underlying table that have the same RID.

There is also a KEY Lookup, used when the table has a clustered index.  The leaf level of a nonclustered index contains pointers that are the key values for the rows being pointed to. So to find the matching rows in the table, SQL Server takes the clustered key value from the nonclustered index, and then searches for that value in the clustered index, following the clustered index from the root down to its leaf.

Below are the two icons used for these operations. If I were to give you a quiz, and ask which operator indicates we are finding a row in a table directly using a RID value, and which indicates we are finding a row in a table using a clustered index key, which would you say is which?  Take a moment to think about it.

image       image

I don’t know about you, but when I just try to figure out these two icons, I think the one on the left looks like it should be the KEY Lookup, and the one on the right should be the RID Lookup.

But if you check the page in Books Online, or if you check your own query plans, you see that they are backwards!

Here is a plan showing a RID Lookup:

image

 

And here is a plan showing a KEY Lookup:

image

Fortunately, the graphical query plan tells you what kind of operation it’s performing, so you can just ignore the picture and read the words. But what’s the point of a graphical plan in that case?

So are they really backwards? Did someone just make a mistake and link in the wrong file when compiling the SQL Server graphical query plan code? Or am I misinterpreting this?

I still think graphical query plans are one of the best thing ever added to product, so I’m really not complaining, but I’m just sayin….

 

Have fun, and Happy T-SQL Tuesday!

~Kalen

Published Monday, June 10, 2013 9:21 PM by Kalen Delaney

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

They seem graphically correct to me.... said:

... from what you've said, the RID lookup is actually a search/join, and the image showing the "joined" sets with a magnifying (search) icon matches that to my eye.

That leaves the other one for a key lookup, and given that it is a lookup "straight" to the values from a binary key, (and in fact, may have the values you need in the clustered index, or one of your other indexes, so you may not even need to go to the table) seems representative (although not quite as much as the first)

In any case, looking at them the RID lookup icon looks more "expensive" than the KEY icon, so I think they do their job.

June 11, 2013 8:25 AM
 

James Hammond said:

I would agree with Kalen on this one. To my eye, the pointer directly into a page should be the RID lookup, and the search in an index tree should be the key lookup.

Is an RID lookup more expensive? I would think it would be significantly cheaper.

--James

June 11, 2013 4:48 PM
 

Greg Low said:

Yes, have always thought so. One looks like it's using an index, the other doesn't.

June 11, 2013 6:48 PM
 

Adam Machanic said:

Agreed, Kalen, some designer was clearly on something when coming up with these icons!

@James: RID lookup is indeed cheaper. It requires 1 logical I/O per row, whereas key lookup requires at least 2 logical I/Os per row. But in the vast majority of cases you'll want a clustered index so it's probably not a great design tradeoff.

--Adam

June 11, 2013 8:01 PM
 

Greg Linwood said:

Why would you want the more expensive option in the vast majority of cases?

June 12, 2013 11:29 AM
 

Adam Machanic said:

@Linwood: Because I design for bookmarks to be the exception rather than the norm.

June 12, 2013 12:49 PM
 

Rob Farley said:

Eighteen posts for T-SQL Tuesday #43 this month , discussing Plan Operators. I put them together and

June 13, 2013 7:00 AM
 

Boris Hristov said:

Ha! I have never ever thought about this icons! Thanks for pointing this out, Kalen! I think I can use this as some kind of a joke during a training or something! :)

July 3, 2013 3:20 AM

Leave a Comment

(required) 
(required) 
Submit

This Blog

Syndication

Favorite Non-technical Sites or Blogs

Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement