When Do SQL Server Sorts Rewind?
Introduction
Rewinds are specific to operators on the inner side of a nested loops join or apply. The general idea is to reuse previously-computed results from part of an execution plan where it is safe to do so.
The canonical example of a plan operator that can rewind is the lazy Table Spool. Its raison d’être is to cache result rows from a plan subtree, then replay those rows on subsequent iterations if any correlated loop parameters are unchanged. The idea is that replaying rows is cheaper than re-executing the subtree that generated them. For more background on performance spools see my previous article.
The documentation says only the following operators can rewind:
- Table Spool
- Row Count Spool
- Nonclustered Index Spool
- Table-valued Function
- Sort
- Remote Query
- Assert and Filter operators with a Startup Expression
The first three items are most often performance spools, though they can be introduced for other reasons, and may be eager as well as lazy.
Table-valued functions use a table variable, which can be used to cache and replay results in suitable circumstances. If you’re interested in table-valued function rewinds, please see my Q & A on Database Administrators Stack Exchange.
This article is exclusively about Sorts and when they can rewind.
Sort Rewinds
Sorts use storage (memory and perhaps disk if they spill) so they do have a facility capable of storing rows between loop iterations. In particular, the sorted output can, in principle, be replayed (rewound).
Still, the short answer to the title question, “Do Sorts Rewind?” is:
Yes, but you won’t see it very often.
Sort types
Sorts come in many different types internally, but for our current purposes there are just two:
- In-Memory Sort (
CQScanInMemSortNew).- Always in-memory; cannot spill to disk.
- Uses standard library quick sort.
- Maximum of 500 rows and two 8KB pages in total.
- All inputs must be runtime constants. Typically this means the entire sort subtree must consist of only Constant Scan and/or Compute Scalar operators.
- Only distinguishable in execution plans when verbose showplan is enabled (trace flag 8666). This adds extra properties to the Sort operator, one of which is “InMemory=[0|1]”.
- All other Sorts.
(Both types of Sort operator include their Top N Sort and Distinct Sort variants).
Rewind Behaviours
-
In-Memory Sorts can always rewind when it is safe. If there are no correlated loop parameters, or the parameter values are unchanged from the immediately prior iteration, this type of sort can replay its stored data instead of re-executing operators below it in the execution plan.
-
Non-In-Memory Sorts can rewind when safe, but only if the Sort operator contains at most one row. Please note a Sort input may provide one row on some iterations, but not others. The runtime behaviour can therefore be a complex mixture of rewinds and rebinds. It completely depends on how many rows are provided to the Sort on each iteration at runtime. You cannot generally predict what a Sort will do on each iteration by inspecting the execution plan.
The word “safe” in the descriptions above means: Either a change in parameter did not occur, or no operators below the Sort have a dependency of the changed value.
Important note about execution plans
Execution plans do not always report rewinds (and rebinds) correctly for Sort operators. The operator will report a rewind if any correlated parameters are unchanged, and a rebind otherwise.
For non-in-memory sorts (far and away the most common), a reported rewind will only actually replay the stored sort results if there is at most one row in the sort output buffer. Otherwise, the sort will report a rewind, but the subtree will still be fully re-executed.
To check how many reported rewinds were actual rewinds, check the Number of Executions property on operators below the sort.
History and my explanation
The Sort operator’s rewind behaviour may seem strange, but it has been this way from (at least) SQL Server 2000 to SQL Server 2019 inclusive (as well as Azure SQL Database). I have not been able to find any official explanation or documentation about it.
My personal view is that Sort rewinds are pretty expensive due to the underlying sorting machinery, and implementation details like system transactions in tempdb.
In most cases, the optimizer will do better to introduce an explicit performance spool when it detects the possibility of duplicate correlated loop parameters.
It is possible that replaying a Sort result would only be more cost-efficient than a Spool when the Sort contains at most one row. After all, sorting one row (or no rows!) does not actually involve any sorting at all.
Pure speculation, but someone was bound to ask, so there it is.
Demo 1: Inaccurate Rewinds
This first example features two table variables. The first contains three values duplicated three times in column c1. The second table contains two rows for each match on c2 = c1. The two matching rows are distinguished by a value in column c3.
The task is to return the row from the second table with the highest c3 value for each match on c1 = c2. The code is probably clearer than my explanation:
DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
INSERT @T1
(c1)
VALUES
(1), (1), (1),
(2), (2), (2),
(3), (3), (3);
INSERT @T2
(c2, c3)
VALUES
(1, 1),
(1, 2),
(2, 3),
(2, 4),
(3, 5),
(3, 6);
SELECT
T1.c1,
CA.c2,
CA.c3
FROM @T1 AS T1
CROSS APPLY
(
SELECT TOP (1)
T2.c2,
T2.c3
FROM @T2 AS T2
WHERE
T2.c2 = T1.c1
ORDER BY
T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);The NO_PERFORMANCE_SPOOL hint is there to prevent the optimizer introducing a performance spool. This can happen with table variables when e.g. trace flag 2453 is enabled or table variable deferred compilation is available, so the optimizer can see the true cardinality of the table variable (but not value distribution).
The query results show the c2 and c3 values returned are the same for each distinct c1 value:
The actual execution plan for the query is:
The c1 values, presented in order, match the previous iteration 6 times, and change 3 times. The Sort reports this as 6 rewinds and 3 rebinds.
If this were true, the Table Scan would only execute 3 times. The Sort would replay (rewind) its results on the other 6 occasions. As it is, we can see the Table Scan was executed 9 times, once for each row from table @T1. No rewinds happened here.
Demo 2: Sort Rewinds
The previous example did not allow the Sort to rewind because (a) it is not an In-Memory Sort; and (b) on each iteration of the loop, the Sort contained two rows. Plan Explorer shows a total of 18 rows from the Table Scan, two rows on each of 9 iterations.
Let’s tweak the example now so there is only one row in table @T2 for each matching row from @T1:
DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
INSERT @T1
(c1)
VALUES
(1), (1), (1),
(2), (2), (2),
(3), (3), (3);
-- Only one matching row per iteration now
INSERT @T2
(c2, c3)
VALUES
--(1, 1),
(1, 2),
--(2, 3),
(2, 4),
--(3, 5),
(3, 6);
SELECT
T1.c1,
CA.c2,
CA.c3
FROM @T1 AS T1
CROSS APPLY
(
SELECT TOP (1)
T2.c2,
T2.c3
FROM @T2 AS T2
WHERE
T2.c2 = T1.c1
ORDER BY
T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);The results are the same as previously shown because we kept the matching row that sorted highest on column c3. The execution plan is also superficially similar, but with an important difference:
With one row in the Sort at any one time, it is able to rewind when the correlated parameter c1 does not change. The Table Scan is only executed 3 times as a result.
Notice the Sort produces more rows (9) than it receives (3). This is a good indication that a Sort has managed to cache a result set one or more times—a successful rewind.
Demo 3: Rewinding Nothing
I mentioned before that a non-in-memory Sort can rewind when it contains at most one row. To see that in action with zero rows, we change to an OUTER APPLY and don’t put any rows in table @T2. For reasons that will become apparent shortly, we will also stop projecting column c2:
DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
INSERT @T1
(c1)
VALUES
(1), (1), (1),
(2), (2), (2),
(3), (3), (3);
-- No rows added to table @T2
-- No longer projecting c2
SELECT
T1.c1,
--CA.c2,
CA.c3
FROM @T1 AS T1
OUTER APPLY
(
SELECT TOP (1)
--T2.c2,
T2.c3
FROM @T2 AS T2
WHERE
T2.c2 = T1.c1
ORDER BY
T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);The results now have NULL in column c3 as expected:
The execution plan is:
The Sort was able to rewind with no rows in its buffer, so the Table Scan was only executed 3 times, each time column c1 changed value.
Demo 4: Maximum Rewind!
Like the other operators that support rewinds, a Sort will only rebind its subtree if a correlated parameter has changed and the subtree depends on that value somehow.
Restoring the column c2 projection to demo 3 will show this in action:
DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
INSERT @T1
(c1)
VALUES
(1), (1), (1),
(2), (2), (2),
(3), (3), (3);
-- Still no rows in @T2
-- Column c2 is back!
SELECT
T1.c1,
CA.c2,
CA.c3
FROM @T1 AS T1
OUTER APPLY
(
SELECT TOP (1)
T2.c2,
T2.c3
FROM @T2 AS T2
WHERE
T2.c2 = T1.c1
ORDER BY
T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);The results now show two NULL columns of course:
The execution plan is quite different:
This time, the Filter contains the check T2.c2 = T1.c1, making the Table Scan independent of the current value of correlated parameter c1. The Sort can safely rewind 8 times, meaning the scan is only executed once.
Demo 5: In-Memory Sort
The next example shows an In-Memory Sort operator:
DECLARE @T table (v integer NOT NULL);
INSERT @T
(v)
VALUES
(1), (2), (3),
(4), (5), (6);
SELECT
T.v,
OA.i
FROM @T AS T
OUTER APPLY
(
SELECT TOP (1)
X.i
FROM
(
VALUES
(REPLICATE('Z', 1390)),
('0'), ('1'), ('2'), ('3'), ('4'),
('5'), ('6'), ('7'), ('8'), ('9')
) AS X (i)
ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);The results you get will vary from execution to execution, but here is an example:
The interesting thing is the values in column i will always be the same—despite the ORDER BY NEWID() clause.
You will probably already have guessed the reason for this is the Sort caching results (rewinding). The execution plan shows the Constant Scan executing just once, producing 11 rows in total:
This Sort has only Compute Scalar and Constant Scan operators on its input so it is an In Memory Sort. Remember, these aren’t limited to at most a single row—they can accommodate 500 rows and 16KB.
As mentioned earlier, it is not possible to explicitly see whether a Sort is In-Memory or not by inspecting a regular execution plan. We need verbose showplan output, enabled with undocumented trace flag 8666. With that enabled, extra operator properties appear:
When it is not practical to use undocumented trace flags, you can infer that a Sort is “InMemory” by its Input Memory Fraction being zero, and Memory Usage elements not being available in post-execution showplan (on SQL Server versions supporting that information).
Back to the execution plan: There are no correlated parameters so the Sort is free to rewind 5 times, meaning the Constant Scan is only executed once. Feel free to change the TOP (1) to TOP (3) or whatever you like. The rewinding means the results will be the same (cached/rewound) for each input row.
You may be bothered by the ORDER BY NEWID() clause not preventing rewinding. This is indeed a controversial point, but not at all limited to sorts. For a fuller discussion (warning: possible rabbit hole) please see this Q & A. The short version is that this is a deliberate product design decision, optimizing for performance, but there are plans to make the behaviour more intuitive over time.
Demo 6: No In-Memory Sort
This is the same as demo 5, except the replicated string is one character longer:
DECLARE @T table (v integer NOT NULL);
INSERT @T
(v)
VALUES
(1), (2), (3),
(4), (5), (6);
SELECT
T.v,
OA.i
FROM @T AS T
OUTER APPLY
(
SELECT TOP (1)
X.i
FROM
(
VALUES
-- 1391 instead of 1390
(REPLICATE('Z', 1391)),
('0'), ('1'), ('2'), ('3'), ('4'),
('5'), ('6'), ('7'), ('8'), ('9')
) AS X (i)
ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);Again, the results will vary per execution, but here is an example. Notice the i values are now not all the same:
The extra character is just enough to push the estimated size of the sorted data over 16KB. This means an In-Memory Sort cannot be used, and the rewinds disappear.
The execution plan is:
The Sort still reports 5 rewinds, but the Constant Scan is executed 6 times, meaning no rewinds really occurred. It produces all 11 rows on each of 6 executions, giving a total of 66 rows.
Summary and Final Thoughts
You will not see a Sort operator truly rewinding very often, though you will see it saying it did quite a lot.
Remember, a regular Sort can only rewind if it is safe and there is a maximum of one row in the sort at the time. Being “safe” means either no change in loop correlation parameters, or nothing below the Sort is affected by the parameter changes.
An In-Memory Sort can operate on up to 500 rows and 16KB of data sourced from Constant Scan and Compute Scalar operators only. It will also only rewind when safe (product bugs aside!) but is not limited to a maximum of one row.
These may seem like esoteric details, and I suppose they are. So saying, they have helped me understand an execution plan and find good performance improvements more than once. Perhaps you will find the information useful one day too.
Look out for Sorts that produce more rows than they have on their input!
Thanks for reading.