{"id":1064,"date":"2011-01-11T00:00:00","date_gmt":"2011-01-11T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/showplan-operator-of-the-week-merge-interval\/"},"modified":"2021-08-16T15:02:09","modified_gmt":"2021-08-16T15:02:09","slug":"showplan-operator-of-the-week-merge-interval","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/learn\/showplan-operator-of-the-week-merge-interval\/","title":{"rendered":"Showplan Operator of the Week – Merge Interval"},"content":{"rendered":"
\n

 <\/p>\n

\"1214-merge_1.gif\"
\n Merge
\n Interval<\/div>\n

Hello dear readers. Once again here I am to talk with you about ShowPlan operators. Over the past few weeks and months, we’ve featured the ShowPlan operators that are used by SQL Server to build the query plan. If you’re just getting started with my Showplan series, you can find a list of all my articles here<\/a>.<\/p>\n

Introduction<\/h1>\n

In my last article I wrote about the Merge Join operator, and now I would like to continue with the subject “Merge” but now is time to feature another kind of merge, the Merge Interval operator.<\/p>\n

Last week I was working, with a customer in Finland, to optimize some queries when I saw this operator in the execution plan. Because this is not very well documented, I’ll try to cover all aspects<\/i><\/b> and bugs<\/i><\/b> related to this operator (a.k.a. iterators).<\/p>\n

In short, this is used to remove duplicated predicates in a query, and to find possible overlapping intervals in order to optimize these filters so as to avoid\u00a0 scanning the same data more than once.<\/p>\n

As always, I completely understand that this is not as simple as I’ve just stated. You may have to read what I wrote more than three times to understand what I mean: Don’t worry about that, because I’ll go deep into this subject step by step so as to make it easier for you to understand.<\/p>\n

Creating sample data<\/h1>\n

To illustrate the Merge Interval behaviour, I’ll start by creating one table called “Pedidos” (which means ‘Orders’ in Portuguese). The following script will create the tables and populate them with some garbage data:<\/p>\n

USE tempdb\r\nGO\r\n\u00a0\r\nIF OBJECT_ID('Pedidos') IS NOT NULL\r\n\u00a0 DROP TABLE Pedidos\r\nGO\r\n\u00a0\r\nCREATE TABLE Pedidos (ID INT IDENTITY(1,1) PRIMARY KEY,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ID_Cliente INT NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Quantidade SmallInt NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Valor Numeric(18,2) NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Data DATETIME NOT NULL)\r\nGO\r\n\u00a0\r\nDECLARE @I SmallInt\r\nSET @I = 0\r\n\u00a0\r\nWHILE @I < 10000\r\nBEGIN\r\n\u00a0 INSERT INTO Pedidos(ID_Cliente, Quantidade, Valor, Data)\r\n\u00a0\u00a0\u00a0 SELECT ABS(CheckSUM(NEWID()) \/ 100000000),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ABS(CheckSUM(NEWID()) \/ 10000000),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ABS(CONVERT(Numeric(18,2), (CheckSUM(NEWID()) \/ 1000000.5))),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 GETDATE() - (CheckSUM(NEWID()) \/ 1000000)\r\n\u00a0 SET @I = @I + 1\r\nEND\r\nGO\r\n<\/pre>\n
Now that we have the table, we have to create two non-clustered indexes. The first uses the column ID_Cliente <\/b>as a Key, including the column Valor<\/b> to create a covered index to our query. And another using the column Data <\/b>as a Key and including the column Valor<\/b>.<\/p>\n
CREATE NONCLUSTERED INDEX ix_ID_Cliente ON Pedidos(ID_Cliente) INCLUDE (Valor)\r\nGO\r\nCREATE NONCLUSTERED INDEX ix_Data ON Pedidos(Data) INCLUDE (Valor)\r\nGO\r\n<\/pre>\n
Merge Interval<\/h1>\n
Now that we have the data, we can write a query to see the merge interval. The following query is selecting the amount of sales for four customers:<\/p>\n
SELECT SUM(Valor) AS Val\r\n\u00a0 FROM Pedidos\r\n\u00a0WHERE ID_Cliente IN (1,2,3,4)\r\nGO\r\n<\/pre>\n
For the query above we’ve the following execution plan:<\/p>\n
\"1214-image002-630x303.jpg\"<\/p>\n
Figure 1 – Execution Plan (click on this to see it full-size)<\/p>\n
In the execution plan above we can see that QO chose to use the index ix_ID_Cliente <\/b>to seek the data for each ID_Cliente<\/b> specified in the IN clause, and then uses the Stream Aggregate<\/a> to perform the sum.<\/b><\/p>\n
This is a classic Index Seek task, for each value SQL Server will read the data throw the balanced index tree searching for the ID_Cliente<\/b>. For now, It doesn’t require the Merge Interval.<\/p>\n
Now let’s looks at a similar query:<\/p>\n
DECLARE @v1 Int = 1, \r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v2 Int = 2,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v3 Int = 3,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v4 Int = 4\r\n\u00a0\r\nSELECT SUM(Valor) AS Val\r\n\u00a0 FROM Pedidos\r\n\u00a0WHERE ID_Cliente IN (@v1, @v2, @v3, @v4)\r\nGO\r\n<\/pre>\n
For the query above we’ve the following execution plan:<\/p>\n
\"1214-image005.jpg\"<\/p>\n
Figure 2 – Execution Plan \u00a0(click on this to see it full-size)<\/p>\n
As you can see, the only difference between the queries is that now we are using variables instead of constant values, but the Query Optimizer creates a very different execution plan for this query. So the question is: What do you think? Do you think that SQL should have used the same execution plan for this query?<\/p>\n
The right answer is No. Why not? Because at the compile time SQL Server doesn’t know the values of the constants, and if the values turn out to be duplicates, then it will read the same data twice. Suppose that the value of the @v2<\/b> is also “1”, SQL will read the ID 1 twice, one for variable @v1<\/b> and another for variable @v2<\/b>, something that we don’t expect to see since we expect performance, read the same data twice is not good. So it has to uses the Merge Interval to remove the duplicate occurrences.<\/p>\n
Let’s wait a minute Fabiano! Are you saying that for the first query, QO automatically removes the duplicated occurrences in the IN clause?<\/p>\n
Yes. Do want to see it?<\/p>\n
SELECT SUM(Valor) AS Val\r\n\u00a0 FROM Pedidos\r\n\u00a0WHERE ID_Cliente IN (1,1,3,4)\r\nGO\r\n<\/pre>\n
For the query above we’ve the following execution plan:<\/p>\n
\"1214-image006-630x230.jpg\"<\/p>\n
Figure 3 – Execution Plan \u00a0(click on this to see it full-size)<\/p>\n
You will see that now we only have three Seek Predicates. Perfect.<\/p>\n
Let’s back to Merge Interval plan.<\/p>\n
The plan is using the operators Compute Scalar<\/a>, Concatenation<\/a>, Sort<\/a> and Merge Interval to eliminate the duplicated values at the execution plan phase.<\/p>\n
At this time, maybe some questions are rising in your mind. First: Why SQL Server don’t just uses a DISTINCT in the IN variables to remove the joins? Second: Why this is called a “Merge”, I didn’t see anything related to a merge here.<\/p>\n
The answer is that the Query Optimizer (QO) uses this operator to perform the DISTINCT because, with this code, the QO also recognize overlapping intervals and will potentially merge these to non-overlapping intervals that will then be used to seek the values. To understand this better let’s suppose that we have the following query that doesn’t use variables.<\/p>\n
SELECT SUM(Valor) AS Val\r\n\u00a0 FROM Pedidos\r\n\u00a0WHERE ID_Cliente BETWEEN 10 AND 25\r\n\u00a0\u00a0\u00a0 OR ID_Cliente BETWEEN 20 AND 30\r\nGO\r\n<\/pre>\n
Now, let’s look at the execution plan:<\/p>\n
\"1214-image008-630x239.jpg\"<\/p>\n
Figure 4 – Execution Plan \u00a0(click on this to see it full-size)<\/p>\n
Notice how smart the Query Optimizer was. (That’s is why I love it!) It recognizes the overlap between the predicates, and instead of doing two seeks in the index (one for each between filter), it creates a plan that performs just one seek.<\/p>\n
Now let’s change the query to use the variables.<\/p>\n
DECLARE @v_a1 Int = 10,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v_b1 Int = 20,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v_a2 Int = 25,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 @v_b2 Int = 30\r\n\u00a0\r\nSELECT SUM(Valor) AS Val\r\n\u00a0 FROM Pedidos\r\n\u00a0WHERE ID_Cliente BETWEEN @v_a1 AND @v_a2\r\n\u00a0\u00a0\u00a0 OR ID_Cliente BETWEEN @v_b1 AND @v_b2\r\nGO\r\n<\/pre>\n
For this \u00a0query \u00a0we’ve the following execution plan:<\/p>\n
\"1214-ExecutionPlan.jpg\"<\/p>\n
Figure 5 – Execution Plan \u00a0(click on this to see it full-size)<\/p>\n
Let’s check what the plan is doing using a different perspective. First let’s understand the overlap.<\/p>\n
\"1214-image013.jpg\"<\/p>\n
Figure 6 – Overlap between 20 and 25<\/p>\n
In the figure 6 we can see that if SQL Server reads the ranges separately, it will read the range from 20 to 25 twice. I’ve used a small range to test with, but think in terms of a very large scan that we’d see in a production database; \u00a0if we can avoid this step, then we’ll see a great performance improvement.<\/p>\n
\"1214-image015.jpg\"<\/p>\n
Figure 7 – After Merge Interval<\/p>\n
After the Merge Interval runs, SQL Server can seek only the final range. It knows that is possible to go to @v_a1<\/b> to @vb_2<\/b> directly.<\/p>\n
Finally<\/h1>\n
To finish this subject I would like to recommend you to read about a bug in SQL Server 2005 caused by a mistake in this process, you could take a better look in the blog of \u00a0Mladen Prajdic<\/a> a SQL Server MVP from Slovenia.<\/p>\n
I wouldn’t miss the opportunity to congratulate the Microsoft guys that build Icons in SQL Server\/Windows. I once read a book called “The Icon Book”, it was amazing how beautiful and meaningful the icons in the graphical query plan \u00a0are. The Merge Interval icon is perfect, if you look at the icon you will see what it is exactly doing. Brilliant, it’s incredible how they can express something in a small picture. Well Done!<\/p>\n
That’s all folks, I hope you’ve enjoyed learning about Merge Join operator, and I’ll see you soon with more “Showplan Operators”.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
When Fabiano agreed to undertake the epic task of describing each showplan operator, none of us quite predicted the interesting ways that the series helps to understand how the query optimiser works. With the Merge Interval, Fabiano comes up with some insights about the way that the Query optimiser handles overlapping ranges efficiently…<\/p>\n","protected":false},"author":65554,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143525],"tags":[4178,4149,5335,5084,5162,5192,4150],"coauthors":[6809],"class_list":["post-1064","post","type-post","status-publish","format-standard","hentry","category-learn","tag-bi","tag-learn-sql-server","tag-merge-interval","tag-optimiser","tag-showplan","tag-showplan-operators","tag-sql"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1064","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/65554"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=1064"}],"version-history":[{"count":4,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1064\/revisions"}],"predecessor-version":[{"id":74793,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1064\/revisions\/74793"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=1064"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=1064"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=1064"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=1064"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}