Another month, another T-SQL Tuesday. Our host in October, the amazing Rob Volk (b|t), wants us to explain database concepts like he is five. I like that concept. A lot. In fact, I have in the past already written similar posts, such as my explanation of SQL injection in non-technical terms to a twelve-year old grandmother.

But that’s an old post, so I cannot use it for this T-SQL Tuesday. So instead, I’ll try to explain the physical join operators SQL Server supports in execution plans using a real life analogy. I don’t think a five year old would understand (if they do, you really should let your child watch less crime series on TV). But I do think (hope?) this explanation should work even for those with zero computer experience.

Join (at) the police!

Imagine we are at a police precinct. To your left, you see a rather grumpy looking middle-aged woman in uniform, sitting at her desk. Her name tag lists her as Sergeant Jane Oin. Jane used to be a detective, until … well, let’s just call it “the incident”. The files on exactly what she did are still sealed, but she has been demoted to desk duty since, and her colleagues make sure to give her the most boring tasks they can find. So whatever happened, it didn’t exactly help her career much.

Every morning when Jane starts work, she finds two stacks on his desk. In the left corner is a stack of requests, sent from the courthouse. Each lists a case number that will be tried the next day. The court wants the relevant documentation by the end of today. And that’s where the top right corner of Janes desk comes in. There, all the casefiles produced by the field workers are piled up in a large stack. Each is marked with a case number.

So poor Jane has the boring task to go through the casefiles her co-workers made during their exciting work in the street, match them to the courthouse requests, make photocopies of the relevant documents, add them to the request, and put those on a new stack, to be delivered to the courthouse at the end of the day.

Yes, kids. That’s how exciting it can be to work for the police!

Nested Loops (basic)

So let’s watch Jane as she goes through her routine. She heads to the coffeemaker, presses the button for a cappuccino, and returns to her desk. She has already given up on attempt to socialize with her colleagues. Whether she talks or not, whether she greets them or not, they always pretend not to notice and ignore her.

Jane carefully places the cup of hot brew in the holder, as she sits down, sighs, and grabs the first paper from the stack on her left. “Case 732863,” she mumbles, “domestic violence.” Her eyes glaze and a slight smile curls her lips as memories of her active duty come back. But she can’t spend too much time on that. There’s a lot of work to be done.

So she starts working her way through the pile of casefiles on her right. Picks up a casefile. Checks the number. Compares it to the number on the court document. Not the right one, so she puts it aside and picks up the next. Rinse. Repeat. Not at all the life she envisioned when she decided to become a cop. But what can you do, right? At least it pays the rent.

Halfway through the pile, she finds a casefile with the same case number. She takes out the reports, carefully photocopies them one page at a time, then puts back the original and staples the copies to the courthouse request.

Jane is briefly tempted to save some time and move on to the next courthouse request right away. But she’ll never forget the verbal abuse she got from her supervisor when she did this on her first day on the job.

“You need to check the rest of the pile too! There may be more reports on this case!”

“How so? Dispatch never assigns two officers to the same case!”

“No, they shouldn’t. I know. But they’re human. They make mistakes. And they have no checks in place to prevent those. So it’s always possible that another officer has a report on the same case. Keep searching.”

So Jane sighs as she works her way through the rest of the pile, obviously not finding any match. Finally, as she reaches the end, she stick the court request and the attached copies in an envelope, drops it in the out box, and finishes her coffee.

“Time for a donut,” she realizes. She deserves one. She quickly grabs one from officer Can’s locker. “He’ll never notice,” she mumbles, as she enjoys the sugar rush. And then it’s time for the second court request. Only 83 left.

We’ll leave her here. Trust me, it won’t get any more exciting than this.

Nested Loops (with Outer References)

We return to the precinct a few weeks later. Jane is still at the same desk. And still grumpy. But the desk looks different now. To her left is the same stack of courthouse requests. But to her right is now a telephone. What has happened?
Well, the precinct has been visited by three business consultants, sent from the downtown precinct with the task “to optimize the workflow and the processes”. Yadda yadda yadda, the usual stuff. But Jane had to admit, the visit of Cunningham, Lopes, and Sack did turn out very well for her. Her work still sucks, but not as much anymore.

So let’s watch her again, as she places her morning cappuccino and the cup holder and picks up the first court document.

“Hmmm. Case 904671. Petty theft. Boring.”

She takes a sip of coffee, then picks up the phone and dials 1. An upbeat voice can be heard on the other end of the line.

“Simon Eek, archive. That you, Jane? How can I help you?”

“Case number … wait, let’s make sure I see this right, … yes. Case 904671, please.”

“Case nine oh four six seven one, confirmed. Coming your way!”

Two floors down, Simon lays down the phone. He is a young man, just in his twenties, and he has known all his life that being an archivist is his calling. And the job opening at the local police station was just what he needed to get his first experience. Eventually he wants to be part of the Congress’ archive staff, but he knows he has to start small.

He turns to face the fruits of his labour. All police reports of the last six years, perfectly organized. Without even a moment of hesitation, Simon directly cruises towards the corner where he knows the documents for case 904671 to be, grabs them, makes photocopies, and puts the originals carefully back. And then he skipped up the stair, softly whistling the romantic Survivor song that was stuck in his head.

“Finally,” Jane grunts as Simon hands her the documents, “that’s all for now. I’ll call you when I need more.”

She then sits down in the chair, ready to enjoy what she considers to be the real perk of this new process. As Simon turns to leave, she shamelessly ogles what she describes as “the best bottom I’ve seen all my life”. (That’s actually just one of several descriptions she uses to describe how Simon looks; but this is a family friendly blog so I cannot reproduce the rest).

After Simon turns the corner, Jane staples the documents to the court request letter and drops it in her out box. Then, after a quick donut, she picks up the next document. She’s pretty sure Simon should be back in his archive room already, so she picks up the phone again.

Merge Join

Jane’s relative happiness doesn’t last long. Two days and a sexual harassment complaint later, the phone is removed and Jane is not allowed within 50 feet of Simon. Steve Can will again make sure to dump all open casefiles on Jane’s desk before she comes in, so she can do her work. Once more using her old method.

But as the workload increases, her superiors realize that she is struggling to keep up. They make sure to let her suffer at least a week longer then needed, but then they cave.

“Jane, starting next week we have assigned you an intern to help you out. But we expect results!”

“Hello, miss Oin! My name is Sally. Sally Ort. I’m your intern. How can I help you?”

“See those two stacks on my desk? As of tomorrow, I’ll start work at ten. You be here at eight. Your job is to sort both stacks by case number. I expect a hot cappuccino in the cup holder at ten, and a fresh bag of donuts.”

“Donuts? Where do I find …”

“That’s your problem. You don’t tell me how to do my job, I won’t tell you how to do yours.”

The next day, Jane sits down at her desk, sips her coffee, stuffs a donut in her mouth, then picks up the first court document.

A creepy smile distorts her face as she reads the description. “Murder two. Wow. Okay, case number 166417.”

Then she picks up the top casefile from the pile on the right side of her desk.

“Oh, that’s 142064. Don’t need that.”

She picks up the next.

“Aha! 166417, got it.”

She quickly runs the documents through the copy machine, then just to be sure picks up one more document from the pile on the right.

“Yeah, 264687. Thought so. Never actually a duplicate. Good, the murder two file is done. What’s next?”

The next court document requests information on case 251789. Jane double checks the number on the casefile she’s holding, but it’s definitely higher. So she quickly scribbles “no documents available” on the request and drops it in the out box.

“Next!”

Hash Match

Not even a week later, Sally Ort’s request to be assigned other work is honoured. Something about “not being taken seriously” and “given stupid work assignments”. Jane snorts angrily as she sits down at her desk. As if her work is any more interesting. Oh, how she sometimes wishes she could return to active duty.

But she refuses to do the sorting herself. No matter what happened, she has still some dignity left. Sorting is work for an intern. Not for a sergeant.

And then Jane notices that Sally’s desk is still there, and she realizes she can use that to make her work a bit easier.

Using a piece of chalk, she draws a few quick lines on Sally’s abandoned desk, to divide it into 10 rectangles that she then marks with the numbers 0 to 9. She then returns to her desk, picks up the entire stack of court documents, and returns to Sally’s desk.

“First case, 736602, that ends in a 2,” Jane mumbles, as she places the document in the rectangle marked “2”.

“Second case, 732250, that’s a zero.” And that document goes to rectangle “0”.

Half an hour later, the stack of court documents has been rearranged into ten new, smaller stacks. Jane sits exhausted on her chair, wiping the sweat of her brows.

“Guess I deserve at least three donuts now.”

Half an hour later, Jane picks up the top casefile of the pile on her right.

“Hmmm, case 673667, that should be in stack 7.”

She heads to Sally’s desk and quickly looks at the five documents in rectangle 7. None of them request this exact case number, so Jane returns the casefile to the pile and picks the next.

“Case 736602. That’s a 2.”

There are six documents in rectangle 2, and one of them does indeed have this case number, so Jane goes through the routine of copying the paperwork and returning the originals to the casefile. She staples the copies to a copy of the court document and drops it in the out box.

“Never know if another officer investigated this one too,” she giggles as she puts the original court document back in its rectangle, carefully pencil marking it.

It’s four as Jane returns the last case file to the pile. Almost done, she knows. One more coffee break. Then she’ll wrap up.

While still chewing on her last donut, Jane picks up the court documents from Sally’s desk. She bins the ones with a pencil mark. But when she finds one that has no mark, she scribbles “no documents available” on it and drops it in the out box.

Adaptive Join

As we all know, all good things come to an end. The same goes for bad things, such as Jane’s boring job. Eventually she decided to move out of state. With her records still sealed, she realized that this was her last chance for a new start. We’ll wish her the best and lots of luck. She’ll need it.

Her position at the precinct is now filled by a junior officer, miss Ada P. Tive. (Stop laughing. I don’t make up these names, you know. You’re being really hurtful to poor miss Tive now). And Ada decides that to succeed, she better avoid Janes mistakes and combine her best methods. But no intern is available right now, the precinct is severely over budget, so having someone sort the stacks is, unfortunately, not possible.

So on her first day, she invites Simon Eek and Steve Can to her office.

“Look, I know you had issues with my predecessor, miss Oin. But I’d like to make a fresh start. And most of all, I’d like to work with you to find the most efficient process. Not just for me, or for Simon, or for Steve, but for the precinct as a whole. Can we discuss some options?”

At the end of that afternoon, Ada had two good friends in the precinct. And a magic number in her head that she would use going forward.

(In case you don’t realize, I’m using one of the oldest narrative tricks here. By carefully omitting the details of what she talked about and then mentioning a magic number without going into details, I’m creating extra tension. If this were a TV series, the episode would end here and we’d call it a cliffhanger. But no worries. I’ll finish this story now, as soon as I’m done breaking the fourth wall.)

So the next day, as Ada starts her work, she finds a stack of courthouse documents and a phone on her desk. She grabs herself a nice black coffee, introduces herself to the coworkers on her floor, offers them each a donut from the large box she brought, then returns to her desk. First thing she does is exactly what Jane did on her last day: she picks up the court documents, and sorts them by last digit into the ten rectangles on Sally’s old desk. With one exception. If you listen carefully, you’ll hear her mumble as she puts down the documents: “One … two … three … four …”. She’s counting them!

Once done, she knows that she’ll need to process 53 court requests today. That’s more than the magic number, 45. She picks up the phone and dials 2.

“Steve? Yes, Ada here. There’s more than 45 today, so can you bring them?”

A few minutes later, Steve walks in with a huge pile of casefiles.

“These are all the files you might possibly need today, Ada. Good luck!”

And then Ada gets to work. First casefile. Case 678265. Last number 5, so she looks for matches in rectangle 5.

We’ve seen this before so we’ll leave her to it, while wondering: how is this an improvement?

The next day, Ada soon finds out that all the prejudice about police and donuts are true. She is now immensely popular, and spends an hour chatting with people before she asks everyone to leave her alone.

“Okay guys. I really need to focus on the next part. Give me some quite please?”

She then quickly distributes the court requests on Sally’s desk, and again carefully keeps a running count.

“Hmmm, only 37. That’s below the magic number.”

This time she dials 1, and gets Simon.

“Hey Simon! Yeah, indeed, I didn’t need you yesterday, there were too many. But you did get your donut, right? Anyway, today I’ve got only 37 requests, so I guess Steve gets a break today. So the first number is, …, let’s see, …,” she quickly runs back to Sally’s desk and grabs the first document from the first rectangle, “… number 371550. Yup, correct. Okay!”

Not even a minute later, Simon arrives with the casefile for case 371550. Ada attaches the copies to the court request, then picks up the next request from the “0” rectangle.

“Next case is 692610, Simon.”

Conclusion

….. and they all lived happy ever after. Well, all except Jane. She got the fate she deserved, as it should be in fictional stories.

As with all analogies, this analogy is not perfect. But I do hope that you at least got a somewhat better idea of how the different join algorithms work. How each has its own benefits, and how each also has its own drawbacks.

If you now want to read more about the actual technical operation of each of these join operators, then you can find very detailed descriptions in the Execution Plan Reference.

Rob, I absolutely loved the theme you chose for this week. Writing this was way more fun than it should have been, and I’m already eagerly looking forward to what others make of this theme. Thanks for hosting!