Friday, November 19, 2010

A Second in the Life of a Query Operator

There are countless books and blogs out there that tell you that you should read a query plan from right to left.

But unless you’re used to reading Hebrew, isn’t that backwards? We read everything else from left to right… Why should we read query plans in the opposite direction?

The answer is: We really shouldn’t. You’ve been misinformed.

Yes, it’s true that the flow of information is from right to left… All those arrows that are pointing in that direction indicate that. We can see the sources of the data on the right and the eventual destination on the left.

But the query does not start with the operators on the right.

Let’s look at an example:

TOP 3 Query

This is a simple query that produces 3 rows of data. Here is the (actual) execution plan:

TOP 3 Query Actual Execution Plan

The arrows are pointing from right to left, making it look like the Clustered Index Scan and Clustered Index Seek are the ones in charge. But they are NOT. In reality, they are just dumb file cabinets of data that only do what they are told.

Take a look at the properties of the Clustered Index Scan operator:

Clustered Index Scan Properties

The job of a Scan operator is to scan the entire clustered index from beginning to end, isn’t it? In this case, it’s supposed to apply the predicate and only pay attention to those rows with ContactID 216. But the Actual Rows in the property sheet is equal to only 2. There are a heckuva lot more than 2 rows with ContactID 216 in the table. How did this operator know when to stop? Isn’t the TOP operator in charge of limiting the rows? But he’s two positions away from the Scan Operator in the plan!

And look at the properties of the Clustered Index Seek:

Clustered Index Seek Properties

It shows that the Number of Executions is equal to 2. Why does it execute twice? And what does that have to do with 3 rows?

The actual execution of a query does not consist of the operators on the right pushing their rows to the left. Instead, query execution consists of operators on the left requesting rows from their child operators to their right.

Just before you start a query, all those operators are asleep. Pushing the Execute button in SSMS wakes up the operator on the far left (the SELECT in our example above), and that operator is in charge of waking up the other operators down the tree and instigating the action of acquiring and outputting rows.

Let’s take a closer, more intimate look at what really goes on in this plan when you hit the Execute button. We’ll do it in the form of a dramatic play, just to make it more interesting and up close and personal.

So sit back and enjoy. (Note: For those of you reading this on your phone or other mobile device or certain readers, you may not be able to enjoy the full experience. The entire script below is presented in resplendent color for your convenience and amusement).




Brad Schulz Productions Proudly Presents...

A Second in the Life of a Query Operator

A Play in One Act




Dramatis Personæ:

SQL Engine: It is assumed that you already know this character quite well.

Simon Select: A very efficient, reliable man with impeccable manners. Imagine the butler Hudson in Upstairs, Downstairs.

Tony Top: A somewhat impatient guy with a tough exterior that masks a sometimes kinder man inside. Imagine Tony Soprano.

Nora Nested-Loops: A no-nonsense woman who does her work without complaint. Imagine Mrs. Doubtfire.

Stuart Scan: A simple-minded country boy who is eager to please. Imagine Gomer Pyle.

Stanley Seek: An uncomplicated man who’s very fond of napping, since he never seems to get enough sleep. Imagine Dagwood Bumstead.



Act I Scene 1.

The Setting: A Query Plan Universe, consisting of 5 rooms, each containing an Operator, all asleep in their beds.

VOICE OF SQL ENGINE: Simon, wake up. I have a job for you.

Simon wakes up and promptly gets up from his bed, already wearing a suit with a black swallowtail coat that, amazingly, has no wrinkles in it whatsoever. He straightens his tie.

SIMON: Very good, sir. I will attend to it immediately.

He posts a sign in the status bar that reads “Executing query…” and he places a little green spinner icon next to it to indicate that the SPID is busy.

Executing Query...

Then he walks to a door on the opposite side of his room. He has no idea who is in the room behind the door. He politely knocks.

SIMON: (Opening the door a crack) Excuse me.

TONY: Huh?

Tony rubs his eyes and sits up at the edge of his bed.

SIMON: Oh, good morning, Mister Top.

TONY: (Yawning) I keep tellin’ ya, Simon, you don’t have to call me Mister Top. You can call me Tony. How’re ya doin’?

SIMON: Just fine, thank you, Mis---… er… Tony. I have been engaged to display some rows in the SSMS Results Window, and I require your assistance.

TONY: Yeah, sure, no problem. I know the drill.

SIMON: Let us proceed, then. May I please have a row of data?

TONY: Comin’ right up. Just give me a millisecond.

Tony walks across to the door on the opposite side of his room and throws it open, banging the door against the wall.

TONY: Hey you! Get your a** outta bed! I got a job for ya.

Nora is startled out of her sleep by the loud voice, but she soon regains composure and gets up from her bed and approaches Tony and points her finger at him.

NORA: Mister Top! How dare you barge in like that! And there’s no need to be so coarse. I know that I have a job to do, but I will not stand for vulgarity, is that clear?

TONY: Yeah, yeah, okay, sorry, Nora. I didn’t know it was you. Many times the query operators I work with are pretty slow in responding. You ever work with Sonny Sort? Jeez, he takes forever!

NORA: I understand that, but one should always try to treat his or her coworkers with respect.

TONY: Yeah, sure, Nora, whatever. Well, let’s get to work. Gimme a --- … Sorry. (He clears his throat) May I please have a row of data?

NORA: That’s much better, Tony, dear. I’m glad we’re getting down to business. I’ll have that row for you in no time.

Nora walks to the opposite side of her room, where there are two doors. She opens the door on the left.

NORA: Rise and shine! We’ve got work to do.

Stuart stirs in his bed and looks toward the door.

STUART: Well, gawwwllleeee! If it ain’t Nora Nested-Loops!

NORA: Hello, Stuart.

STUART: Well I’m about as excited as a bag full of puppies to be working with you again, Nora. How long has it been since we worked together?

NORA: About 12 seconds, dear.

STUART: Hooo-wheee! Has it really been that long? Well, what can I do for you?

NORA: You know the routine, Stuart. I need a row.

STUART: Right away.

Stuart walks over the file cabinet in his room and looks at the work order that’s tacked to the wall above it.

Stuart Scan's Predicate

STUART: Looks like I have to get rows just for ContactID 216 from this here clustered index. I sure do hope that this clustered index ain’t too large. A second or two ago, I had a job where I had to scan over 10,000,000 rows, and, boy, I was busier than a long-tailed cat in a room full of rocking chairs! In fact, I said to myself that---

NORA: Time waits for no one, Stuart dear. I need more action and less talk.

STUART: Oh, sure, sorry, Nora.

He opens the drawer of the file cabinet. It’s full of pages of data, with each page consisting of rows in order of SalesOrderID. He takes out the first page and examines each row on the page, looking for ones with a ContactID value of 216. He finds one. He checks the work order once again.

Stuart Scan's Output List

STUART: Looks like I only gotta give you the SalesOrderID and OrderDate columns.

He pulls those columns from the row and walks back to the door to hand them (as a row) to Nora.

STUART: Here ya go, Nora.

NORA: Thank you, Stuart.

Nora looks at her work order and sees that she is to perform an INNER JOIN using an outer reference of SalesOrderID. She examines the row in her left hand that she received from Stuart and then opens the second door, which is to the right of the door to Stuart’s room.

NORA: Time to get up!

Stanley is startled out of his sleep and falls out of his bed and bumps his head.

STANLEY: (Rubbing the back of his head) Time to get up already? It seems like I’ve only been sleeping for a few hundred milliseconds.

NORA: Yes, it’s that time again, Stanley. We’ve got a job to do. (She looks again at the row she received from Stuart in her left hand) I need you to get me a row for SalesOrderID 43660.

STANLEY: (Yawning) Okay, just a millisecond.

He walks over to a file cabinet in his room. It has three drawers. They are labeled 43659 thru 51821, 51822 thru 62790, and 62791 thru 75123 respectively. Stanley opens the top drawer, and looks through the folders inside and immediately finds one that is labeled 43659 thru 43875. He leafs through the pages inside and immediately finds the page containing rows for SalesOrderID 43660. He checks his work order.

Stanley Seek's Output List

STANLEY: Looks like I’m only supposed to give you the ProductID and UnitPrice columns.

He pulls those columns from the row and walks back to the door to hand them (as a row) to Nora.

STANLEY: Here it is, Nora… A row for SalesOrderID 43660.

NORA: Thank you, dear.

Nora accepts the row in her right hand. She walks over to the copy machine in her room and makes a Xerox copy of the row she has in her left hand (from Stuart). She takes the copy of that row and joins it with the row in her right hand (from Stanley), creating a new row consisting of columns SalesOrderID, OrderDate, ProductID, and UnitPrice. She walks to the door where Tony is waiting.

NORA: Here’s your row, Tony.

TONY: Thanks, Nora.

Tony accepts the row and looks over his work order.

Tony Top's Expression

TONY: (to himself) Only 3 rows, huh? Okay. (He makes a tick mark to keep track of the number of rows he receives) That’s number one.

He walks over to the door where Simon is waiting.

TONY: Here ya go, Simon.

SIMON: Thank you, Mister Top.

Simon accepts the row. He meticulously writes the columns of the row into a nice grid structure in the SSMS Results Window, using the font indicated in his work order. Then he walks back to the door.

SIMON: Another row, please, Mister Top.

TONY: Okay, I’m on it. (Walking to the opposite door) Nora, I need another row.

NORA: Alright, Tony. (She looks at the row from Stuart that’s still in her left hand and walks to Stanley’s door) Stanley, dear, I need another row for SalesOrderID 43660.

STANLEY: (Jerking his head up from almost nodding off) Huh? Oh, okay, Nora.

He goes back to the page where he had acquired the previous row. He finds another row for SalesOrderID 43660 and pulls out the appropriate columns and walks back towards Nora.

STANLEY: Here you go, Nora.

NORA: Thank you.

Nora once again makes a Xerox copy of the row in her left hand and joins that copy with the row acquired from Stanley and walks back to Tony.

NORA: Here you are, Tony dear.

TONY: Thanks. (Making another tick mark on his worksheet) That’s two. (Walking back to Simon) Here’s your row, Simon.

SIMON: Very good, Mister Top.

Simon writes the columns of the new row to the grid in the SSMS Results Window and returns once again to Tony’s door.

SIMON: Another row, if you please, Mister Top.

TONY: Okay, you got it. (Walking to the opposite door) Nora, I need another row.

NORA: Alright, Tony. (She looks once again at the row from Stuart that’s still in her left hand and walks to Stanley’s door) Stanley, dear, once again I need another row for SalesOrderID 43660.

STANLEY: (Yawning) Okay.

He goes back to the page where he had acquired the previous row. But there isn’t another row for SalesOrderID 43660.

STANLEY: Sorry, Nora, I’ve already given you all I’ve got for that SalesOrderID.

NORA: Well, thank you for your help, Stanley. You can go back to sleep now.

STANLEY: Thank goodness!

As Stanley shuts the drawer of the file cabinet and rushes towards the bed, Nora closes his door. She throws the row in her left hand into the trash and then goes to the door on her left, where Stuart is standing.

NORA: Stuart, dear, I need another row from you.

STUART: Okay, Nora… I can get that for you faster than green grass goes through a goose.

He goes to the file cabinet and continues scanning rows, looking for the next one with ContactID 216.

STUART: I found one. (Walking back towards Nora) Here it is.

NORA: Thank you, dear.

She accepts the row in her left hand and examines the SalesOrderID in the row, then walks over to Stanley’s door and opens it.

NORA: Wake up, Stanley, dear! I need a row for SalesOrderID 47660.

Stanley falls out of his bed, bumping his head once again.

STANLEY: (Groaning) What? You told me to go back to sleep only a few nanoseconds ago.

NORA: Well, that’s the nature of the job, Stanley, dear. Every time I get a row from Stuart here, I have to wake you up and get rows from you to join to his. Once you give me all the rows relating to Stuart’s then you get to go back to sleep. This is my second row from Stuart, so I’m waking you up for the second time. Every time I wake you up, it’s called an execution.

STANLEY: Yeah, I know. But all this going to sleep and waking up over and over again is killing me! I think the word “execution” is very appropriate! (Yawning) Okay, hold on… What was that SalesOrderID again?

NORA: 47660, dear.

STANLEY: Okay.

Stanley goes to his file cabinet and opens the appropriate drawer and the appropriate folder and the appropriate page and finds the first row for SalesOrderID 47660.

STANLEY: Got one. (Walking back to Nora) Here you go.

NORA: Thank you.

Nora once again makes a Xerox copy of the row in her left hand and joins that copy with the row acquired from Stanley and walks back to Tony.

NORA: Here you are, Tony dear.

TONY: Thanks. (Making another tick mark on his worksheet) That’s three. (Walking back to Simon) Here ya go, Simon.

SIMON: Excellent… Thank you, Mister Top.

Simon adds the new row to the grid in the SSMS Results Window and returns once again to Tony’s door.

SIMON: May I have another row, please, Mister Top?

TONY: (Double-checking his tick marks against his work order) Sorry, Simon, but I can’t give you any more rows. I’ve reached my quota.

SIMON: Well, I suppose that’s it, then. Thank you for your assistance, Mister Top. Time to shut down the operation.

TONY: Okay, Simon. Hey, Nora, time to shut down.

NORA: Alrighty. Stanley and Stuart, it’s time to shut down. You can go both go back to sleep.

STANLEY: Yes! Sleep-time again!

Stanley closes his door and jumps into his bed and is out cold before his head even hits the pillow.

STUART: Okay, Nora. I actually am a little tired. In fact, I’m more exhausted than a mule in---

Nora closes his door before he can finish his hokey down-home analogy. Stuart shrugs his shoulders and climbs into his bed and goes to sleep.

NORA: (Walking back to the door of Tony’s room) Good night, Tony, dear.

TONY: See ya later, Nora.

Nora closes the door, turns off the light, and slips into her bed.

TONY: (Walking back to the door of Simon’s room) Well, Simon, until next time…

SIMON: Always a pleasure, Mister Top.

Tony closes the door, turns off the light, and gets into his bed.

Simon writes the message “(3 row(s) affected)” to the Messages Window. Then he posts a sign that reads “Query executed successfully.” and removes the green spinner icon, replacing it with a checkmark icon.

Another Job Well Done

Then Simon sits at the edge of his bed and smiles to himself on another job well done. He lies down and reaches over for the light and turns it off.

And then he gently closes his eyes.

THE END.

23 comments:

  1. That's Entertainment!

    But... how can I use this knowledge to improve my queries?

    ReplyDelete
  2. Very nice Brad, though I do worry about your sanity sometimes :)

    Paul

    ReplyDelete
  3. I assume parallel processing has something to do with twins?

    Wilfred

    ReplyDelete
  4. That was fun to read. Thanks again Brad

    ReplyDelete
  5. @bbacher: It won't nbecessarily help you to improve your queries per se, but it does give you more insight into how a query actually works. Once I discovered this, I started looking at queries in a whole new light, and I was able to see what was going on with more complex queries that involve recursion or window functions, for example.

    ReplyDelete
  6. @Paul: Regarding my sanity: I asked my imaginary friend Harvey about it, and he said that as far as he's concerned, I'm perfectly sane. So there!

    ReplyDelete
  7. @Wilfred: Parallel processing and twins: LOL. Very good! Either that, or Nora's copying machine could be used to create clones.

    ReplyDelete
  8. Awsome...Thats a very nice and simple way to explain what goes on inside the sql server engine when a query is fired

    ReplyDelete
  9. That is simply the BEST way anyone has ever described the workings of a query!

    Thanks Brad!

    -Aashish

    ReplyDelete
  10. @Aashish and @Anonymous:

    Thanks for the great feedback! I'm so glad you enjoyed it.

    --Brad

    ReplyDelete
  11. This is just great.Wonderfully written. Very informative. I am sure it took a bit of work on your part to craft a nice tight story and your hard work was not wasted.

    ReplyDelete
  12. Awesome! This is one of the best sqlserver article I ever read. I can literally visualise how the query is being executed .. only downside - I do hesitate to fire a query immediately after another - hoping somewhere Stanley gets some sleep.

    ReplyDelete
  13. @Sabyasachi:

    LOL... poor Stanley!

    I have to admit that ever since I wrote this post, I look at query plans in a whole new light, thinking of Nora and Simon and all the rest.

    Thank you for your comment!

    --Brad

    ReplyDelete
  14. I love this blog post. I made an homage to it called "Silverlight View Model (MVVM) - A Play In One Act" http://openlightgroup.net/Blog/tabid/58/EntryId/141/Silverlight-View-Model-MVVM-A-Play-In-One-Act.aspx

    ReplyDelete
  15. Brad,

    To add to my previous comment:

    You did miss a bit from the script concerning the initialization step (no doubt for space reasons). For these details and more, please see http://sqlblog.com/blogs/paul_white/archive/2010/08/05/iterators-query-plans-and-why-they-run-backwards.aspx

    I do still routinely read plans from the top-right and working left, because I am usually interested in the flow of data, rather than the flow of control.

    Cheers!

    Paul

    ReplyDelete
  16. @Paul:

    By "initialization", do you mean more about the Open() method of the individual iterators?

    True, I didn't want to muddy stuff up too much... I wanted to get across the general idea that (as Rob Farley so eloquently states) query plans "suck"... i.e. the iterators request or "pull" data from their children to the right... they don't "push" data from right to left.

    A little over a year ago, at least 3 MVP's were puzzling over a query plan at the MSDN forum and couldn't figure out why the counts were the way they were, until the light bulb finally went off over my head as to how they actually worked, and then it all became clear.

    I, too, also read plans from right to left to get a feel for the flow of data... but you have to understand the control flow when you get down into more complicated plans like recursive queries or windowed aggregates, for example.

    Thanks again, as always for the comment. Your blog post you mentioned promised future posts on the topic... I'm looking forward to it!

    --Brad

    ReplyDelete
  17. Brad,

    I have been trying to decide if this post is more misleading than it is pointless. I can't really decide. On one hand you clearly have some things messed up in your head about query plans (thanks for passing those on to the SQL Server community Mr. MVP!). On the other hand though, we are only talking about ways to abstract away what SQL Server is doing for the purpose of better being able to solve problems.

    Anyway, your profound and deep paradigm of reading left to right is just awful. I would save this explanation only for the most junior of people that I couldn't get through to any other way. Regardless, it begs the question, if they can't handle the more correct and difficult way of reading query plans then why are you explaining it in the first place?

    Sorry for the scathing post but someone had to write it.

    Thanks, Jason

    ReplyDelete
  18. Jason,

    Many people don't need to understand execution plans at all. For them, getting correct results, and being able to create useful-enough indexes to help performance may get them as far as they need to go.

    When people start to read execution plans, they see many resources explain that the data moves from right-to-left, and get stuck there.

    Unfortunately if your understanding stops at this point, there are many aspects of plans that remain completely unexplained, particularly around the way that operators know what to do based on operators to their left.

    Different people realise the need to consider plans from both directions at different times. I know many people who have found this post from Brad incredibly helpful and enlightening.

    Rob

    ReplyDelete
  19. Rob,

    Off the top of my head I can only think of two operators that affect operators to their right: TOP and filters where the Startup Expression Predicate is specified. There may be others that I forgot or am unaware of, but the point is they are few and far between.

    To your point that "Different people realise the need to consider plans from both directions at different times", I agree despite it being very infrequently useful. However, the third line of Brad's post emphatically states that reading from right to left is wrong.

    Personally, I think an MVP should be doing things to help the SQL Server community and this post is only going to steer aspiring SQL Server query plan readers down the wrong path.

    That's just my two cents though.

    Jason

    ReplyDelete
  20. Jason,

    He didn't say it was wrong, he said we said we *shouldn't* read plans from right-to-left. He even says that he reads plans from right-to-left to get a feel for the flow of data.

    I don't agree with you that it's the wrong path. In fact, Brad is providing an explanation here which is far more complete than many other explanations of how execution plans work.

    I'm pleased you've said it's 'just your two cents', but I also think you need to be wary of criticising such an excellent post anonymously, and in such a personal way.

    If you'd like to email me on this directly, you can find my email address in the right-hand panel of my own blog. You'll find my name (above) is a link there.

    Rob

    ReplyDelete
  21. Wow, the comments on this post are starting to get longer than the original post itself!

    Jason, I wasn't sure at first how to respond to your original post. I appreciate the criticism, but I didn't appreciate the condescending tone... "Mr. MVP"? Gimme a break.

    Rob and Paul's comments have already communicated what I want to say on the subject.

    Sure, I suppose I could have worded the third paragraph differently... not make it so abrupt... but I wanted to get readers' attention.

    As Paul and I had mentioned in these comments, we do generally look at a plan from right to left to get a feel for where the data is going and in what order, but when you get down into detail of record counts processed by the operators and get into plans that involve spools and such, the whole "right-to-left" paradigm only takes you so far.

    I wanted to explain, in a hopefully entertaining way, how a query actually works under the hood. I've explained this at SQL user groups, and I can see the revelations in people's eyes as I talk about it, and I've had people express thanks for explaining it.

    The first several pages of Craig Freedman's 100-page chapter in Kalen Delaney's "Query Tuning and Optimization" book goes into great detail about how the operators work in the way I described, just as Paul had in his blog.

    In short, this is a concept worth knowing, and that's why I wrote about it. We can agree to disagree about its importance, but I'm certainly not doing anything to destroy the SQL Server community... It's not like I'm advocating murder or anything here... I'm surprised and sorry that you felt a need to respond so vehemently.

    --Brad

    ReplyDelete
  22. I found the article entertaining but also enjoyed the bit of insight - I'll read the query plans in both directions.

    After all, there is that expression for somebody who really knows their stuff: 'He/she knows it backwards and forwards'.

    Peace and ignore the hatas,
    Steve

    ReplyDelete
  23. Hello,

    Thank you for an excellent read! Just what I needed as I am in the process of trying to fully understand query plans.

    I do have a few minor questions, I hope it is not too late to ask.

    Quote "NORA: Wake up, Stanley, dear! I need a row for SalesOrderID 47660."

    - This implies that the GetNext() method called on the Seek (from Nora/Sort) is called with SalesOrderID as an argument. Is this correctly understood?

    - This also implies that the Seek has to wait and can not start about its job before at least one row is returned from the Scan, that is, the Seek is not independent of the scan.

    This last point is very confusing as these things are always explained differently in every place I have read, and I would love a
    clarification (the recommendation in the comments to get Delaneys book is noted).


    Best Regards,
    Geir

    ReplyDelete