Join Algorithm Limitations In SQL Server
Video Summary
In this video, I delve into some interesting limitations of SQL Server’s join algorithms, particularly focusing on scenarios where the lack of an equality predicate can lead to unexpected errors or suboptimal query plans. I explore these issues through practical examples and demonstrate how implicit predicates work in nested loops joins. Additionally, I discuss a scenario involving right outer joins, which cannot be implemented as nested loops joins due to their nature, highlighting why SQL Server prefers left outer joins for such cases. By walking you through these examples, I aim to provide insights into optimizing queries and understanding the nuances of SQL Server’s query execution engine. Whether you’re working with stored procedures or dynamic SQL, this video offers valuable lessons on how to avoid common pitfalls and improve query performance.
Full Transcript
Erik Darling here with Darling Data. And I’m just now making the rather sad realization that I forgot to re-embiggen myself after recording the last video where I had to shrink myself down. So let’s figure out what an adequate portion of me is. Let’s move this around a little bit. Ooh, ooh, ooh, that’s too big. That’s a little too much me even for me. Let’s get that to a little bit of a bit. more reasonable place. I think this is pretty good. I just have to be really mindful about what I do with my head because when I do that, my head looks preposterously large, I think. I mean, my head is sort of preposterously large. Anyway, if you’ve ever seen me in real life, you know this, but the camera angle and sort of, I don’t know, I don’t know what to call it, depth of field thing just makes it so much worse. But anyway, I don’t know what to call it. Anyway, in today’s video, we’re going to talk about some joint algorithm limitations in SQL Server. These may and probably do exist in other databases. I don’t study other databases as deeply as I study SQL Server. So you’ll have to forgive me if I’m wrong about that. But I can’t imagine that it’s much different anywhere else unless there’s some other database out there that has some totally different joint algorithm that I’m just unaware of. So I’ve got a couple indexes that I created for most of the queries we’re going to be looking at. It’s, I mean, most of the plans are going to be getting our estimated plans, so they don’t matter too, too much. But a couple of them will be actual execution plans. And I don’t want to sit here waiting for those to show up. I don’t want to waste your time, mine, or look foolish.
The eyes of our overlords, whoever they may be. So, first, and this demo is going to play a part in why I’m showing you the next demo, too. But let’s get through this one first.
Oh, my good, good. Headphone hair in back, you’ll have to forgive me. Another reason not to put my head down too far, I suppose. All right, so this query, just get an estimated plan for this. SQL Server chooses a nested loops join plan.
Well, it doesn’t really choose it. It’s forced to use it. And it’s forced to use it because we don’t have an equality predicate. We don’t have column equals other column here. We have greater than equal to, less than equal to. Okay, so without an equality predicate, we cannot have a merge join, and we cannot have a hash join.
All right, so if we try to get an estimated plan for this, we will get an error. And SQL Server will say, query processor cannot produce a query plan because of the hints defined in this query. Please resubmit your query, and we’ll get back to you as soon as possible.
And the same thing will happen with a hash join hint. All right, so you do this, and look at it. It’s that same error. If you didn’t know you could edit query text in the messages tab, it makes it really easy to sort of frame the text a little bit better. If you’re taking screenshots or something, don’t be afraid to do that, so then you don’t have to send one of those, like, preposterously long, skinny screenshots, or, like, assemble your own screenshot later, and everyone’s going to think you, like, photoshopped it.
Like, wow, that’s not a real thing. Liar. It’s completely unrealistic. Bad demo writer. Bad DBA. Bad developer. Whatever. Whatever they may think of you. So, I think I’ve talked about this a little bit before, but stuff like this is often why, if you’re the type of person who has, like, calendar or date tables, or even number tables, and your database has utility tables, I’m not saying you shouldn’t, but when you join to those, you are often joining on, like, greater than, equal to, less than, equal to, and some arrangement there, and, like, if you’re joining, like, if you have, like, really big results set, and you ended up in, like, you end up with a nested loops join because you have to without an equality predicate, that can really drag a query down because SQL Server can only do a nested loops join, and if you get caught in a nested loops join, I don’t know if you’ve ever, like, done a cross join between, like, a small table and a big table, but those get stuck in nested loops hell, and the same thing can kind of happen here, right?
Because, like, especially if that nested loops join ends up in, like, the wrong side of the query plan, like, you know, somewhere where, like, you know, you end up doing, like, billions and billions of nested loops joins into a table because SQL Server has to, well, that can be a pretty bad time for performance.
I’m not saying not to use those tables. I’m just saying that just be careful where you use those tables in your queries. Sometimes you have to, like, get queries down to a smaller result set, like temp tables, and then join those. Other techniques can work, too, like, you know, cross-apply with a big top in it or something like that and can sort of tell SQL Server where you want things to happen a little bit better.
But moving on to, like, where the lack of an equality predicate can cause some sort of unexpected errors, I learned about this from a Craig Friedman blog post from, like, forever ago, but it still works today, but we’re going to talk a little bit more.
We’ll talk about some stuff. We’ll get there. Just stick with me. Hang on tight. Stick your hands deep into your pockets and try to grin and bear this information. So if we create this procedure, and the deal with this procedure is that we are getting a count from posts joined to itself where the ID in one side is the parent ID in the other side.
So we’re sort of just, like, counting, like, questions and answers, right? We’re associating the answers with the question. We’re joining from the question to the answer, whatever order that happens in. It doesn’t really matter much.
But if we create this, and then, sorry, before we go any lower, then we also have this where clause where p.parentID equals this parent ID parameter, which is set to this number.
And we have an option hash join hint down here. Now, if we try to run this, we’re going to get an error message. Very similar, actually identical to the error messages that we just saw, where a SQL Server is going to say, no plan for you.
No query. Can’t do it. You’re screwed. Now, the way to see why that happens is to run the query without the hash join hint in it. So let’s run this, and now let’s execute the store procedure, and let’s see what happens.
And that is, well, something kind of cool. So this isn’t necessarily the fault of, like, the query writer, and it’s not necessarily the fault of the hash join.
There’s a query optimization that kicks in. You can think of it as implied predicates. You can think of it that way because that’s what it’s called. The predicates are implied because our join columns have an equality predicate, and our where clause also has an equality predicate on a value.
So what happens in the query plan is SQL Server. Let’s zoom in on this a little bit. Let’s see if we can make sure that everything is going to work out all right here.
Let’s frame that up nicely. Let’s act professional for once in our lives. So up at the top, we have a clustered index something. I don’t know why SSMS chooses to cut this off.
It’s not like there’s anything. Oh, that’s from my, I mean, I understand why this is where my hand cuts off. Maybe I should make myself bigger so I can reach more places on the screen. I don’t lose fingers.
But we have a nonclustered index. This is going to be a seek. And I’ll show you that in a second. And then down here we have an index seek on my non-cl. I’ve never had my non-cl seeked into before, but rather nice, actually.
Rather pleasant. So we have a seek on both sides of the joiner. I’m going to zoom in on exactly what happens. We seek on the clustered index to where the ID column is equal to the parent ID parameter.
And that’s on the outer side of the join. On the inner side of the join, where we seek into a non-cl. That is, of course, going to be a seek predicate here on parent ID.
So this, again, implied predicate means that a predicate will apply to both sides of the join because we have a where clause column that matches one of our join condition columns. And it’s all equality predicates.
So when we look at the nested loops join, we actually don’t have any join predicate here. We just output the stuff for the count function. So the reason why the hash join hint throws an error is because we’ve removed the equality predicate from the join.
Rather, the optimizer has removed the equality predicate from the join, pushed it to either side of the join, and then basically just kind of brought back everything because all the rows would match. There’s nothing to actually filter out at the join.
The join can’t get rid of any rows. And SQL Server knows that because of the implied predicate. So it basically just assembles everything and shuffles it off. And that’s cool, but it can also lead to some sort of surprising errors sometimes if you add a hash join hint to a query, and that query starts failing with different parameter values because SQL Server implies the predicates.
So this can—it’s not just stored procedures with parameters. And also, like, you can get around this with recompile hints, but if you declare a variable and do the same thing, we will get the same query processor error.
It is worth noting, I think, that this doesn’t happen for some reason with a literal value. I don’t quite get why. SQL Server does a hash join here, and we still imply the predicate.
All right, it’s right there. You can see it down the bottom, 184, whatever. And we have it down here. So I don’t quite get that, but I’m willing to admit that I don’t quite get it. But this could happen with a literal value if you had forced parameterization enabled for your database.
For some reason—well, I mean, literal values skirt a lot of optimizer stuff, so maybe this is just another one to add to the list. So you’ve seen a couple examples now of limitations with join algorithms where there’s a lack of an equality predicate and even a sort of surprising one where there wasn’t a quality predicate, but the optimizer optimized it away.
Now, I want to talk about something a little bit more interesting because I wrote a post recently about joins. And in that post, I made fun of write joins a little bit, probably a little bit more than I should have.
I’m not actually that militaristic about write joins. I guess. I don’t know. I still think that they’re kind of stupid, but really what I do hate are Venn diagrams to explain joins.
That’s obnoxious. Stop doing it. So I have an optimizer compatibility level hint here just to not get adaptive joins because the adaptive joins just make what I’m trying to explain a little bit more confusing.
It’s really just want to show you the join type and whether it’s left outer or right outer. So I’ve got these two queries, one using a left join and one using a right join.
And when we run these, if you’ll note, SQL Server quite often thinks that right joins are goofy too. And SQL Server has rewritten both of these as left outer joins. Left outer joins.
SQL Server took our query, carefully crafted to use a right join and said, no, thank you. I’m going to do a left join instead. Okay.
Well, that’s interesting. Now, if we write our query and use this set of hints, so now I say loop join and do this, right? So we got hash joins before.
If we write this to use loop joins, SQL Server is going to do the same thing. SQL Server is going to say, right joins are stupid, right? Right join, nah. Left join.
But this is a little bit more of an optimizer limitation than just an optimizer being like, I hate right joins type thing. And I’m going to show you exactly what I mean.
So if I add in another hint here, so there’s a new hint in this query, say force order. All right. So I’m saying you write, you create this query plan in the order that I wrote it.
We can do that successfully with the left join. SQL Server says, no problem. Gotcha, pal. You’re good. If we try to do that with a right join, SQL Server is going to say, no.
We cannot write loop join this query. And if we write force order, then SQL Server is going to obey the order of the joins, but we’re going to go back to a hash join.
We do a right outer join, but it’s back to being a hash join. Now the reason why this is an optimizer, or rather an algorithm limitation, is because these are outer joins.
We need to return a value and another value, or like values and whatever values exist, or values and a bunch of nulls when they don’t exist.
And it gets, it’s a little bit easier to see when you visualize it like this. All right. So let’s run these two things.
And what I have here is the wonderful, lovely, talented generate series function. And this is counting from one to 20, skipping, like taking steps of two.
This is counting from one to 30 using steps of three. So if we look at the values that come back from here, right? And the first result set, we have one, three, five, seven, nine, 11, 13, 15, 17, 19, which is, again, counting to, well, would have counted past 20, but by limited to 20, but we get up to 19, right?
One, three, five. So we’re basically doing every third number. And the second one would, I mean, would have gone up to 30, but, you know, counting by, we’re skipping three. So we get one, four, seven, 10, 13, 16, 19, 22, 25, 28.
So if we were to run this as a left join between this result set and this result set, we would find, what is it? One, seven, 13, and 19.
And the second result set, right? And those would join, but then for three, five, nine, 11, 15, 17, we would get that back with a null, right?
So we would get value plus another value where they matched and then value and null where they don’t match. Now, the reason you can’t do this with a right join is because you wouldn’t know what rows exist. In the outer table, right?
Like, think about if we, if we did this as a right join, you would be like, oh, well, here’s one. Returning one in one. And then you say four. And then you say, well, there’s no fours here.
There is a three here. So I could, but like SQL Server doesn’t know to return three and null because it only has the values that are on the outer side of the join to start going to try to find. So right outer joins technically don’t work as a nested loops join because of the way the algorithm is implemented, right?
Like you, like you can’t possibly get the right results with the right outer loop join because you need to figure out if this matches and this matches and return this plus any matches or return this plus a null. It gets a little bit easier to see if you actually write the join out because what you get here is exactly what I’ve been describing.
When we find a match, we get a value and a value. But when we don’t have a match, we get a value and a null, right?
And we don’t know, like, like whatever values are in here that didn’t match. SQL Server is not going to be like, well, hang on, hang on, back it up. We didn’t have a four, but we had a three. So I get a return to three and a null.
It’s just not going to work well. There’s not like a good efficient way to do that with a right loop join. So right joins is a wise man. Once said, if you never want to see nested loops joins, write all your queries is right joins, but the optimizer might say beat it.
This is just kind of a funny limitation. I don’t expect anyone out there to actually try to avoid loop joins for their entire life. But there we have it.
Anyway, these are just some interesting join algorithm sort of limitations. I mean, they’re not even like bad limitations. They’re just things you should be aware of.
Like, a lot of people say limitation, like a lot of people infer or imply that limitations are bad things. But I think quite often limitations are good things because performance would not be great if we didn’t have some limits on the way some things are implemented.
Some of those limits keep the wheels on. This is, I think, a pretty good example of that.
There’s also, you know, the right outer loop join just couldn’t possibly give you correct results in a timely fashion. It just wouldn’t work. It doesn’t work because you take a row, you’ll look for a row, but if you start on the wrong side, you just, you’re going to miss values that you should be bringing back.
So, it could be a pretty bad time. You wouldn’t, you wouldn’t want any more incorrect results than you get with all your no lock hints anyway. So, that’s about it for this.
Thank you for watching. I hope you enjoyed yourselves. I hope you learned something. If you like this video, give it the old thumbs up. If you like this kind of content, please subscribe to my channel so that when I publish videos, you can immediately be notified, drop everything, and, and, and watch them and, and learn more sequels because apparently that’s important.
Yeah. Databases, database, data science, all that stuff. Seems to be, seems to be pretty useful these days.
Seems to be pretty in demand. So, the more you know, the better off you are. Especially, you know, anyone can return correct results. If you can, if you can return correct results faster than everyone else, you’re in better shape than a lot of folks would be.
So, yeah. Learn your sequels. I guess. I should, I should learn my sequels too.
Anyway, I’m going to go, I don’t know, do something else fun and interesting now. Maybe I’ll record more. Maybe I won’t. We’ll see what happens. Anyway, thank you for watching.
Going Further
If this is the kind of SQL Server stuff you love learning about, you’ll love my training. Blog readers get 25% off the Everything Bundle — over 100 hours of performance tuning content. Need hands-on help? I offer consulting engagements from targeted investigations to ongoing retainers. Want a quick sanity check before committing to a full engagement? Schedule a call — no commitment required.