Common Table Expression Fork Bombs
Video Summary
In this video, I dive into a fascinating concept known as a CTE fork bomb, exploring how recursive Common Table Expressions (CTEs) can lead to exponential growth in query execution. I start by setting the stage with simple sample data and gradually build up complexity, illustrating how nested loops joins within CTEs can multiply the number of rows, leading to significant performance impacts. By breaking down each step of the execution plan, I highlight the importance of understanding these patterns for optimizing queries and avoiding potential performance pitfalls. The video is packed with detailed explanations and visual aids, making it a must-watch for anyone interested in deepening their knowledge of SQL Server query plans and optimization techniques.
Full Transcript
Erik Darling here with Darling Data. Feeling very high energy today, very… very just pumped up. Let’s go. Let’s go get them. Today I want to talk about a CTE fork bomb. If you’re not familiar with what a fork bomb is, you can sort of consider it to be like viral replication where one cell becomes two cells and two cells become four and four. It just keeps, like, getting bigger, right? And that’s what we’re gonna do today. If you would like to support this channel, you can do so. There’s a link to become a member down in the video description below. If you want to ask me questions during my Office Hours episodes, you can do that. Otherwise, the usual like, comment, subscribe stuff is all available to you should you feel so encouraged to do something. So if you need SQL Server consulting help, well, that’s me. Health checks, performance analysis, hands-on tuning, dealing with performance emergencies and training your developers to not write fork bombs on your servers. All good. All good and worthwhile things there. You can get all of my performance tuning content, about 24 hours of it for 75% off. Again, link down in the video description. That brings it down to about 150 bucks and you get that for the rest of your life.
The T-SQL course is now half done. All of the beginner content is online and published. There is about 23 hours of it across, last count, 69 modules. So that’s fun there. Of course, past pre-con attendees will get free access to all of this companion material. It is on sale right now for the pre-sale price of $250. That price will go up in the fall to $500 as soon as everything is said and done. I am doing a lot of outside the house stuff this summer. I will be in New York City, shockingly, August 18th and 19th. I will be in Dallas, Texas, September 15th and 16th.
And I will be in Utrecht, that old Netherlands thing, October 1st and 2nd. And of course, I will be at Pass Data Community Summit from November 17th to 21st in Seattle, Washington, assuming that Seattle is still a city at that time. But with that out of the way, let us talk about this CTE fork bomb thing. Because, you know, making fun of CTE never gets old. At least not for me anyway.
So we’re going to create some sample data here, some simple sample data, because we don’t want to create overly complex sample data that will confound and confuse the masses out there, do we? We want very simple, straightforward demonstrations so that everyone can understand everything. So before I get to the actual fork bomb, there are some agreements that you and I must come to.
We must agree on these concepts so that by the time we get to the fork bomb, you understand fundamentally what is happening. So if we run this query that joins together the two tables that I just created and populated with data, we will get back 255 rows. And if we look at the execution plan, there will be one scan of the table T1, one scan of the table T0, and one merge join in order to produce those 255 rows.
If we look at the details here, there is one number of executions for that scan. And there is one number of executions for this scan. Good stuff.
We can agree on these things. If this query were to use a nested loops join, say like this, where I’m going to force some things to happen, the query plan would change. We would no longer have a merge join.
We would have a nested loops join. And this table would 255 rows would be read from T0. 32,767 rows would be read from T1.
What changes aside from the nested loops join is we had a merge join before, if you remember back that long ago, you little goldfish. This scan still has one execution. But now we have something different on the inner side of the nested loops join.
Now we have an index seek, and we have 255 executions of the index seek. All right, 255 right there. So when you have a nested loops join, the thing on the nested loops join will execute once for every row on the outer side of the join.
That’s this part to go get rows. Since I don’t know how the cops are going to sound on the new microphone. So it’s my first one.
So lucky us get to experiment together. If every time a row comes out of here, since the way that the data is designed, every row will match. Right.
So all 32,000 rows in this table have a match here, which means all 255 rows in this table have a match here. So we do this seek 255 times, we find 32,767 matches, and then we aggregate those down to 255 based on the number of unique IDs that came out of t0. Now, if we were to put that query into a CTE, and we were to join that CTE to itself, the query plan would change yet again.
Now the query plan. Well, I mean, A, we have a hash join up here, but now we have two nested loops joins. We actually have two copies of that query that runs because of course, if you are a frequent watcher of my videos, you will know that Microsoft SQL Server at this point in time does not offer a mechanism to materialize the results of a CTE.
That lack of materialization means that every time you reference a CTE in an outer scope, you will have to rerun the query in the CTE. So we actually have the same plan run twice, right? There’s the first copy of the plan of the execution of the query, if that’s easier for you to deal with.
And down here is the second one. Now, what this means is that we have two scans of the table t0, right? And see a number of executions.
Oh, you know what? That is hiding behind my head. Let’s try that again. So we have two scans of the table here, right? One or rather one scan of the table here. We have another scan count of one for this table here for a grand total of two.
Now, this index seek into t1 has 255 executions and so does this one. So we have two total scans of the table t0 and we have 255 scans a piece, which is, I’m going to guess around 510 seeks into t1 total. Now, since there’s a hash join up here, right?
We have a hash join that brings these two results together. Remember when I said from the CTE, join the CTE to itself on the ID column. So this is how SQL Server chose to join those two CTE queries together with a hash join.
To simplify things quite a bit, let’s just say, you know, for the sake of making sure that we stay in agreement, that the first query plan up there, the one, the uppermost plan above my head, the outer side of the join ran, did all its work, went to the hash join, built a hash table, and then the inner side of the query ran and the hash join did its thing to, you know, compare rows in the hash table and all that other stuff.
So the, let’s just say the outer side of the query ran, got to the hash join, then the inner side of the query ran and like got, then got to the hash join and comparisons were made and we decided which rows matched and which didn’t at the join. So these re you really do have two executions of this. Another sort of easy way to see that is that you like, when you look at the operator times, you know, you have like this part of the plan executes and it takes like four milliseconds of accumulated time across all the operators here.
Then you have this part of the plan and there’s four milliseconds of time across all of the accumulated operators. And then you have the hash join up here, which is happening in row mode. So this is the four milliseconds here plus the four milliseconds here plus one millisecond of time spent in the hash join.
All right. So that’s how that looks. Ergo, which I’m told is the, which I’m told is a word, which is, which is just great, I guess.
If we combine the CTE join situation with a nested loops join, the query inside the CTE will be executed, not just once, but once per row that goes into the loop join. To see what I mean, what we’re going to do is instead of just doing a join, we’re going to do a cross supply with a top one. The cross supply, I’m not saying cross supply is bad.
It’s just there for a little bit of convenience because cross supply does often get optimized to a nested loops join. So we’re going to use this for convenience. So I can show you this execution plan.
Notice the top part of the plan, right? Everything looks the same up there. We still have basically the same two copies of the plan that run, right?
There’s like that looks very similar to the original one. And then down here, we have that second copy of the query that ran just preceded by a top operator here because we had that top one. Right.
So now we’re going to see the one scan here and we’re going to see the 255 seeks here. What’s going to change is that instead of having one scan here. Now, this is an index seek now, and we did 255 seeks into this.
Well, the estimated CPU cost is 255, too. That’s that’s amazing. I was like, huh?
Okay. Number of executions, 255. Okay, cool. So every for every row that came up out of here, right? We got we aggregated everything down to 255 rows here.
All 255 rows went into the nested loops join, let’s say one at a time. And every time this nested loops join got a row, it went down here and said, hey, seek into here. And so we did that 255 times.
From here, we went into a nested loops join and we hit this thing 255 times. Okay, like this is this is the same, right? We still have 255 here and we still have 255 here.
This number didn’t really multiply here because we still we have a nested loops join here that’s sort of protecting us. So let’s have a little fun with this. Let’s add some more work.
Let’s further amuse ourselves. Because we are we are we are nothing if we cannot amuse at least ourselves. If we can’t amuse ourselves, what have we got? So we’re going to add some more work to the initial CTE.
We’re going to add some window functions in. We’re going to add average and row number and count big. Right.
So we’re going to we’re going to make SQL Server do some more work in the initial part of the query. And this is where things I think get kind of interesting. So if we run this whole thing now, we’re going to have to do some multiplication math. Right.
So let’s let’s zoom out a little bit here. I’m actually going to. Oh, let’s see. Can I get that? Let’s see my head. My head is going to be between two operators, but that’s okay. So if we if we look at this top part of the plan, it will be a mirror image of the bottom part of the plan up to a degree.
Up to a point rather. Let’s move this way over here. That’s probably about good.
Oh, tooltip. You just had you had to do it to me, didn’t you? So if we look at this part of the plan, right, if we start up here, you’ll see, you know, like the index scan on T0 255, the index scan on T1 32767. And then going over, there’s a merge join and a segment and a sequence project like that’s doing some like the row numbery stuff.
And if we go over here a little bit further, and if you just kind of keep your eye on the bottom part of the plan, you’ll notice that they are essentially mirror images of each other aside from a couple extra operators here. But they both do the exact same thing. Where things get interesting here, I think, is that we still have the same pattern where every row, the 255 rows that go into this loop join that bring this reference to the CTE and join it to this reference to the CTE.
We still have 255 rows that go in there, but way down over here, things really start to multiply out that didn’t work out. So if we look at this part of the plan specifically, notice that this isn’t 255 anymore. This is 65,025, which if you don’t have a calculator handy or just a lot of fingers, that is 255 times 255.
If you look at this number, this is 8.3 million and change. That’s 255 times 32,767, which is that number up there. So now we have sort of fork bombed our CTE by using, but with the nested loops join, because every time this nested loops join runs, we end up multiplying the number of rows in the table by the number of rows that come out of the loop join.
So if you sort of compare the numbers going across, like this merge join up here, this has 255 rows go in. This merge join down here has 65,025 rows go in. Or rather, like come out, sorry, because you have the 255 rows go into each.
Right. And that’s that that happened because we get we aggregate this down over here. Right.
This gets squished and this gets squished to 65,000. So the 8.3 million gets aggregated to 65,025. Here, the 32,000 gets aggregated down to 255. So now, like like we instead of having 255 rows go out here, we have 65,000 rows go across.
And you can see that the number of rows because we have fork bombed ourselves with the nested loops join, the number of rows that go across here are going to be much larger for the bottom part of the query. And you can actually see far more time end up across all those operators. If you look up here before we go into this nested loops join, we have only used five milliseconds of wall clock time.
If you look down here, look at how the time builds up. I don’t know what my head’s going to be sort of in the way. It’s 518 milliseconds in here, nine milliseconds in here.
We get up over 800 milliseconds by the time we get to here. So all of these accumulated operator times get to 800 right there. And then as we go across SQL Server dealing with the number of rows on a single thread, like we just add more and more time to this.
So there’s a there’s a window spool here. We get up to 1.1 seconds. And then after this segment, we have a we have a table spool and we get to 1.2 seconds.
And then we do this all this stuff and we get up to 1.242 seconds. So depending on like usually when, you know, like we talk like I talk about CTE, I’ll say something like, you know, your CTE will run once for every reference you make to it. But depending on the query plan that SQL Server chooses, your CTE might run way more times than that.
Right. So if you’re if you’re CTE joins to itself or joins to itself or, you know, like just joins repeatedly to like say you, I don’t know, throw a third table in the mix. And let’s say you have to join your CTE to one table and then you have to join your CTE, maybe to another column in that table or to a different table.
Depending on the join choice, your CTE might end up executing way, way more times than just once per reference. If you choose a nested loops join, it’ll execute once for every row that goes into the nested loops join and then has to run your your your reference to that CTE. So isn’t that fun? Isn’t there just so much fun in query plans?
Isn’t there just so much interesting, exciting stuff that just makes your day? Mine too. All right. Cool.
Thank you for watching. I hope you enjoyed yourselves. I hope you learned something. And I will see you in the next video where we will undoubtedly talk about more fun and exciting execution plan stuff. All right.
Cool. 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.