{"id":926,"date":"2010-06-25T00:00:00","date_gmt":"2010-06-25T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/operator-of-the-week-index-spool\/"},"modified":"2021-08-16T15:02:14","modified_gmt":"2021-08-16T15:02:14","slug":"operator-of-the-week-index-spool","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/learn\/operator-of-the-week-index-spool\/","title":{"rendered":"Operator of the Week – Index Spool"},"content":{"rendered":"
\n

\"1073-spool_icon.gif\"
\n Nonclustered
\n Index Spool<\/strong><\/p>\n

Indexes, Indexes, Indexes… To misquote a certain prominent Microsoft employee. Indexing is a key issue when we are talking about databases and general performance problems, and so it’s time to feature the NonClustered Index Spool in my SQL Server ShowPlan operator series. If you missed the last article about the Lazy Spool<\/a>, it’s actually very important that you read that before you get too deeply into this next article. If you’re just getting started with my Showplan series, you can find a list of all my articles here<\/a>.<\/p>\n

The Index Spool is used to improve the read performance of a table which is not indexed and, as with other types of Spool operators, it can be used in a “Lazy” or an “Eager” manner. So, when SQL Server needs to read a table that is not indexed, it can choose to create a “temporary index” using the Spool, which can result in a huge performance improvement in your queries. To get started with understanding Index Spool, we’ll use the usual table, called Pedidos (which means “Orders” in Portuguese). The following script will create a table and populate it with some garbage data:<\/p>\n

USE tempdb\r\nGO\r\nIF OBJECT_ID('Pedido') IS NOT NULL\r\n\u00a0\u00a0DROP TABLE Pedido\r\nGO\r\nCREATE TABLE Pedido (ID\u00a0INT IDENTITY(1,1),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Cliente\u00a0INT NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Vendedor\u00a0VARCHAR(30) NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Quantidade SmallInt NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Valor\u00a0Numeric(18,2) NOT NULL,\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Data\u00a0DATETIME NOT NULL)\r\nGO\r\nCREATE CLUSTERED INDEX ix ON Pedido(ID)\r\nGO\r\nDECLARE @I SmallInt\r\n\u00a0\u00a0SET @I = 0\r\nWHILE @I < 50\r\n\u00a0\u00a0BEGIN\r\n\u00a0\u00a0INSERT INTO Pedido(Cliente, Vendedor, Quantidade, Valor, Data)\r\n\u00a0\u00a0\u00a0\u00a0SELECT ABS(CheckSUM(NEWID()) \/ 100000000),\r\n\u00a0\u00a0\u00a0\u00a0'Fabiano',\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CheckSUM(NEWID()) \/ 10000000),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CONVERT(Numeric(18,2), (CheckSUM(NEWID()) \/ 1000000.5))),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0GETDATE() - (CheckSUM(NEWID()) \/ 1000000)\r\n\u00a0\u00a0INSERT INTO Pedido(Cliente, Vendedor, Quantidade, Valor, Data)\r\n\u00a0\u00a0\u00a0\u00a0SELECT ABS(CheckSUM(NEWID()) \/ 100000000),\r\n\u00a0\u00a0\u00a0\u00a0'Amorim',\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CheckSUM(NEWID()) \/ 10000000),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CONVERT(Numeric(18,2), (CheckSUM(NEWID()) \/ 1000000.5))),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0GETDATE() - (CheckSUM(NEWID()) \/ 1000000)\r\n\u00a0\u00a0INSERT INTO Pedido(Cliente, Vendedor, Quantidade, Valor, Data)\r\n\u00a0\u00a0\u00a0\u00a0SELECT ABS(CheckSUM(NEWID()) \/ 100000000),\r\n\u00a0\u00a0\u00a0\u00a0'Coragem',\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CheckSUM(NEWID()) \/ 10000000),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ABS(CONVERT(Numeric(18,2), (CheckSUM(NEWID()) \/ 1000000.5))),\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0GETDATE() - (CheckSUM(NEWID()) \/ 1000000)\r\n\u00a0\u00a0\u00a0\u00a0SET @I = @I + 1\u00a0\r\n\u00a0\u00a0END\r\nSET @I = 0\r\nWHILE @I < 2\r\n\u00a0\u00a0BEGIN\r\n\u00a0\u00a0INSERT INTO Pedido(Cliente, Vendedor, Quantidade, Valor, Data)\r\n\u00a0\u00a0\u00a0\u00a0SELECT Cliente, Vendedor, Quantidade, Valor, Data\r\n\u00a0\u00a0\u00a0\u00a0FROM Pedido\r\n\u00a0\u00a0SET @I = @I + 1\u00a0\r\n\u00a0\u00a0END\r\nGO\u00a0\r\nSELECT *\r\n\u00a0\u00a0FROM Pedido Ped1\r\n\u00a0\u00a0WHERE Ped1.Valor > (\r\n\u00a0\u00a0SELECT AVG(Ped2.Valor)\r\n\u00a0\u00a0\u00a0\u00a0FROM Pedido AS Ped2\r\n\u00a0\u00a0\u00a0\u00a0WHERE Ped2.Data < Ped1.Data)<\/pre>\n
This is what the data looks like in SSMS:<\/p>\n
\n
\"1073-demo1.gif\"<\/p>\n<\/div>\n
Figure 1. The Pedidos demonstration table and data.<\/strong><\/p>\n
To help us understand the Index Spool, I’ve written a query that returns all orders with a sale value higher than the average, as compared to all sales before the date of the order in question:<\/p>\n
SELECT *\r\n\u00a0\u00a0FROM Pedido Ped1\r\n\u00a0\u00a0WHERE Ped1.Valor > (\r\n\u00a0\u00a0SELECT AVG(Ped2.Valor)\r\n\u00a0\u00a0\u00a0\u00a0FROM Pedido AS Ped2\r\n\u00a0\u00a0\u00a0\u00a0WHERE Ped2.Data < Ped1.Data) <\/pre>\n
Before we see the execution plan, let’s make sure we understand the query a little better. The SubQuery returns the average value of all sales (AVG(Ped2.Valor)<\/strong>) dated before the order we’re comparing them to. After that, the average is compared with the principal query, which determines whether the sale value in question is actually bigger than the average. If you’ve read last week’s article, you’ll see that this query has a very similar form to my previous demonstration. So, now we’ve got the following execution plan:<\/p>\n
\n
\"1073-ExPlan1_sml.gif\"<\/a><\/p>\n<\/div>\n
Figure 2. The graphical execution plan of the Index Spool demonstration query (click on the image for an enlarged view).<\/strong><\/p>\n
|--Filter(WHERE:([Pedido].[Valor] as [Ped1].[Valor]>[Expr1004]))\r\n\u00a0\u00a0\u00a0\u00a0 |--Nested Loops(Inner Join, OUTER REFERENCES:([Ped1].[Data]))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Clustered Index Scan(OBJECT:([Pedido].[PK_Pedido] AS [Ped1]))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Index Spool(SEEK:([Ped1].[Data]=[Pedido].[Data] as [Ped1].[Data]))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Compute Scalar(DEFINE:([Expr1004]=CASE WHEN [Expr1011]=(0) THEN NULL ELSE [Expr1012]\/CONVERT_IMPLICIT(numeric(19,0),[Expr1011],0) END))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Stream Aggregate(DEFINE:([Expr1011]=Count(*), [Expr1012]=SUM([Pedido].[Valor] as [Ped2].[Valor])))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Index Spool(SEEK:([Ped2].[Data] < [Pedido].[Data] as [Ped1].[Data]))\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |--Clustered Index Scan(OBJECT:([Pedido].[PK_Pedido] AS [Ped2]))\r\n<\/pre>\n
This is a very interesting plan, and, as we can see, the Optimizer chose to use two Index Spool operators; one working as an Eager and the other as a Lazy spool. We can also see that, after the Nested Loops, SQL Server uses the Filter operator to select just the rows that satisfy the WHERE condition (WHERE PEd1.Valor > <\/strong>…).
\n This execution plan is actually simpler than it looks; first, the Clustered Index Scan reads the rows in the Pedidos<\/strong> table, returning the Data<\/strong> and Valor<\/strong> (Date and Value) columns to the Eager Index Spool. With these rows, the Optimizer uses the Index Spool to create a temporary non-clustered index on Data<\/strong> and Valor<\/strong>, and as it is an Eager spool, it will read all the rows from the clustered scan to create the index.<\/p>\n
\n
Quick Tip:<\/strong> 
\n If you create an index on the Pedidos table <\/em>covering Data and Valor, you will optimizer the query because the operator Index Spool (Eager) will not be necessary.<\/em><\/p>\n<\/div>\n
After that, the optimizer will calculate the average value of the sales, using the following rule: For each row of Ped1, the optimizer computes the average of any orders where the Ped2.Data is lower than Ped1.Data (i.e. the average of any orders which have a date earlier than the order in the given row of Ped1). To do this, SQL Server uses the Stream Aggregate and the Compute Scalar operators, in a manner similar to what was discussed last week<\/a>.<\/p>\n
I’ll explain the Index Spool (lazy) in just a moment, but for now I’ll just say that it optimizes the Nested Loops join, which is joining the average calculated by the sub-query to the Ped1.Data column, and the result, as I mentioned, is then filtered to complete the query.<\/p>\n
Now, let’s look at what makes the Index Spool (lazy) operator special. When SQL Server needs to read a value that it knows is repeated many times, then it can use a Spool to avoid having to do the same work each time it needs to find that value. For instance, suppose that the date column has a high density<\/a> (i.e. it contains a lot of duplicated values); this will mean that SQL Server will have to do the same calculation more than once, since the Nested Loops operator will process the join row by row. However, If the value passed as a condition to the join is equal to a value that has already been calculated, you clearly shouldn’t need to recalculate the same result each time. So how can we reuse the value that has already been found?<\/p>\n
This is exactly what the Nonclustered Index Spool operator (lazy), is designed to do: optimize the process of the Join. It is optimized to predict precisely the case that I’ve described above, so that a value that has already been calculated will not be recalculated<\/em>, but instead read from the index, which is cached (TempDB). So, from the point of view of the Spool, it is very important to know if the required value still needs to be calculated(rebind), or has already been<\/em> calculated (rewind). Now that this simple example has illustrated that point, it’s time to dive a little deeper.<\/p>\n
Understanding Rebind and Rewind<\/strong><\/h1>\n
First of all you need understand that all types of Spool operators use temporary storage to cache the values used in the execution plan, although this temporary storage is truncated for each new read of the operator. This means that, if I use a Lazy Spool<\/a> to calculate an aggregation and keep this calculated value in cache, I can use this cached data in many parts of the plan, and potentially work with just single chunk of data in all the plan’s steps. However, to do this, we need reset the cache for each newly calculated value , otherwise by the end of the plan we’ll be working with the whole table! Thus, for a spool, it is very important to distinguish between executions need the same<\/em> value (rewinds) and executions needing an different \/ new<\/em> value (rebinds).
\n A rewind is defined as an execution using the same value as the immediately preceding execution, whereas a rebind is defined as an execution using a different value. I know this is a little confusing to understand for the first time, so I’ll try and explain it step by step, with some code and practical examples.<\/p>\n
Rebind and Rewinds with <\/strong>Table Spool<\/strong> (Lazy <\/strong>Spool<\/strong>)<\/strong><\/h2>\n
To understand a little more about Rebind and Rewind, let’s suppose our Pedido<\/strong> table has some rows in the Data<\/strong> (Date) column in the following order: “19831203”, “19831203”, “20102206” and “19831203”. A representation of Rewind and Rebind in a table spool operator would be something like this:<\/p>\n