I love SQL Server execution plans. It is often easy to spot the cause of a performance problem just by looking at one. The task is considerably easier if the plan includes run-time information (a so-called ‘actual’ execution plan), but even a compiled plan can be very useful. Nevertheless, there are still times where the execution plan does not tell the whole story, and we need to think more deeply about query execution to really understand a performance problem. This post looks at one such example, based on a recent question posted on the SQL Performance Q & A site.

The Execution Plan

This plan is reasonably large (20MB cached plan size) but not massively complex once you break it down (click on the image above to view it full-size in a new window). The context of the question is that this query usually executes in less than a minute, but sometimes it runs for nearly twenty minutes – though the plan appears identical.

High-Cost Operators

There are many different things to look for in execution plans. What you choose to look at first is as much a matter of personal preference as anything, but many people are drawn to high-cost operators, so I will start there. In this plan, the cost of one operator dominates all others, shown as being responsible for 100% of the cost of the query. It is highlighted in red in Plan Explorer; I have expanded the relevant plan section (the top right) below:

There is no doubt that this seek is busy little thing. It is executed 249,484 times, though it only produces a grand total of 167,813 rows over all iterations of the loop join – an average of just 0.7 rows per seek. There are all sorts of interesting details in the plan about this seek – I could write a whole blog post about it – but two details that stand out are the “Force Seek: True” and “Partitioned: True” attributes. These tell us that the base table is partitioned, and the query writer had to use a FORCESEEK table hint to get this plan.

Without this hint, the optimizer would almost certainly choose a Hash Match or Merge Join rather than Nested Loops. This is understandable given the optimizer’s cost model and the simplifying assumptions it makes (such as assuming every query starts with a cold buffer cache). That’s fine, but we can see from the query plan that the inner-side table has 643 million rows. Left to its own devices, the optimizer would estimate that it would be faster to perform a sequential scan of 643 million rows (with large-block read-ahead) than it would be to run a quarter-million randomly-distributed seeks driven by a Nested Loops join.

I doubt that the optimizer’s reasoning here is sound (at least on any reasonably modern hardware) but there we go. The query author probably knows that a good fraction of this table is likely to be in cache, so with all that in mind, I think we can reasonably assume at this stage that the FORCESEEK hint is genuinely needed here, and this part of the plan is at least reasonably optimal.

Important note: The seek certainly does not account for 100% of the runtime cost of this query. Remember cost percentages are always estimates – even in ‘actual’ plans. It can be useful to check the reasons for high-estimated-cost operators, but they should never be used as a primary tuning metric.

Execution Warnings

This query was executed on SQL Server 2012, so there is a handy warning triangle on the Sort operator indicating that one or more sort runs had to be spilled to physical tempdb disk. The plan clearly shows this spilling is a result of an inaccurate cardinality estimate at the Filter operator (the estimates are not bad at all prior to this). The Sort expects 9,217 rows totalling approximately 5MB, but actually encountered 61,846 rows in 35MB. As you may know, memory for sorts and hashes is allocated before execution starts, and generally cannot expand dynamically at run time.

The spilled sort is undesirable, of course, but it is unlikely to be a major cause of the occasional poor performance given the small size of the spilled data. Nevertheless, this might be a good place to split this query up. The idea would be to write the results of the query (up to and including the Filter) to a temporary heap table using SELECT INTO, and then create a clustered index with the same keys as the Sort operator. The temporary table would not be large, and may well perform better overall than the spilled sort, including the cost of creating the clustered index. Of course, creating this index will involve a sort, but it will be one based on the known cardinality of the temporary heap table. The part of the plan that could be replaced by a temporary table is shown below:

I am a big fan of simplifications like this. Smaller execution plans tend to optimize better for all sorts of reasons, and the source code usually becomes easier to maintain as well. I should mention there is another warning triangle in the 2012 execution plan (shown on the root icon), which relates to some implicit conversions that I will mention later.

I/O Information

The execution plan was captured with Plan Explorer, so we can also easily see I/O statistics for the two executions. The first is for a fast (sub-60-second) run:

Overall, these I/O numbers show pretty much what we would expect: a decent number of logical reads associated with the seeks into the Trans table (but certainly not 100% of the total, ha ha), a very small number of physical reads, and a small amount of read-ahead activity on a couple of tables.

The second set of I/O data is from a slow run (18 minutes or so):

The very obvious difference is the appearance of a work table, with 178 million logical reads and 130 million LOB logical reads. It seems very likely this work table, and its 300 million logical reads, is responsible for the dramatic decrease in query performance. But given that the execution plans are identical (right down to the XML) what is causing this?

My answer to that question (on the Q & A site) was that it is related to the increased level of read-ahead activity, but to see why that is the case, we will need to reproduce the issue and dig a bit deeper.

Execution Outline

Before we really get going on this, it will be useful to take a look at what the execution plan is doing in outline. We saw the first part of the plan earlier when looking at the spilling sort. The data set at that point (which we would like to write to a temporary table, remember) essentially represents source data for a second query, which uses a series of Nested Loops Left Joins to lookup information from other tables:

The inner side of each join involves some reasonably involved logic, which is thankfully not important to the present discussion. What is important is that the result of each lookup is a LOB data type. This begins to shed some light on the LOB logical reads reported against the work table, but it does not explain why the work table (and the 300 million associated reads) do not appear when the query runs quickly (with the same execution plan).

Reproducing the problem

Table Creation

The first part of the repro involves creating six tables that represent the lookup tables in the original query plan. Each table will have 10,000 rows, consisting of a sequential reference number and a second column containing a 2048 single-byte-character string. The source table used to drive the lookups will be a regular Numbers table containing just a single integer column.

CREATE TABLE dbo.T1 (id integer IDENTITY PRIMARY KEY, d char(2048));

CREATE TABLE dbo.T2 (id integer IDENTITY PRIMARY KEY, d char(2048));

CREATE TABLE dbo.T3 (id integer IDENTITY PRIMARY KEY, d char(2048));

CREATE TABLE dbo.T4 (id integer IDENTITY PRIMARY KEY, d char(2048));

CREATE TABLE dbo.T5 (id integer IDENTITY PRIMARY KEY, d char(2048));

CREATE TABLE dbo.T6 (id integer IDENTITY PRIMARY KEY, d char(2048));

GO

INSERT dbo.T1 WITH (TABLOCKX)

SELECT REPLICATE('A', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

GO

INSERT dbo.T2 WITH (TABLOCKX)

SELECT REPLICATE('B', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

GO

INSERT dbo.T3 WITH (TABLOCKX)

SELECT REPLICATE('C', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

GO

INSERT dbo.T4 WITH (TABLOCKX)

SELECT REPLICATE('D', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

GO

INSERT dbo.T5 WITH (TABLOCKX)

SELECT REPLICATE('E', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

GO

INSERT dbo.T6 WITH (TABLOCKX)

SELECT REPLICATE('F', 2048)

FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

The next step is to ensure that each lookup table is optimally organized for read-ahead:

ALTER TABLE dbo.T1 REBUILD WITH (MAXDOP = 1);

ALTER TABLE dbo.T2 REBUILD WITH (MAXDOP = 1);

ALTER TABLE dbo.T3 REBUILD WITH (MAXDOP = 1);

ALTER TABLE dbo.T4 REBUILD WITH (MAXDOP = 1);

ALTER TABLE dbo.T5 REBUILD WITH (MAXDOP = 1);

ALTER TABLE dbo.T6 REBUILD WITH (MAXDOP = 1);

Test Query

The original query translates into our simplified test rig as:

DECLARE @d nvarchar(max) = NCHAR(10000);

SELECT n.n,

    DATALENGTH

    (

        CONCAT

        (

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T1 AS t WHERE t.id = n.n),

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T2 AS t WHERE t.id = n.n),

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T3 AS t WHERE t.id = n.n),

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T4 AS t WHERE t.id = n.n),

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T5 AS t WHERE t.id = n.n),

            (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T6 AS t WHERE t.id = n.n)

        )

    )

FROM dbo.Numbers AS n

WHERE n.n BETWEEN 1 AND 10000

ORDER BY n.n

OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

The broad idea there is to concatenate our 2048-character column to itself five times and include a Unicode character that was used in the original query as a delimiter that could not appear in the source data. Each lookup performs the same basic operation against its target table, and the final result is the result of concatenating all the intermediate results. The query hints are necessary to get the right plan shape, just because my test rig tables are so much smaller than the real ones.

Note that the Unicode delimiter means the 2048-character single-byte data is implicitly converted to Unicode, doubling in size. It is not a crucial feature of the test, but it did appear in the original query and explains the type conversion warnings in the execution plan I mentioned earlier. The execution plan for the test query is (click to enlarge if necessary):

I should also stress that the CONCAT operator (new in SQL Server 2012) is not crucial either. If you are using an earlier version of SQL Server, an equivalent query (for present purposes) is shown below. I’m going to stick with CONCAT for the remainder of the post, however.

DECLARE @d nvarchar(max) = NCHAR(10000);

SELECT n.n,

    DATALENGTH

    (

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T1 AS t WHERE t.id = n.n) +

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T2 AS t WHERE t.id = n.n) +

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T3 AS t WHERE t.id = n.n) +

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T4 AS t WHERE t.id = n.n) +

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T5 AS t WHERE t.id = n.n) +

        (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T6 AS t WHERE t.id = n.n)

    )

FROM dbo.Numbers AS n

WHERE n.n BETWEEN 1 AND 10000

ORDER BY n.n

OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

Warm cache results

With all data in memory, the test query (in either form) completes in about 1.6 seconds on my laptop. The result shows that each output row contains 147,468 bytes of Unicode character data. A typical set of I/O statistics follows:

Nothing too exciting to see there, but this is just our baseline.

Cold cache results

CHECKPOINT;

DBCC DROPCLEANBUFFERS;

With no data in memory, the test query now runs for 18.6 seconds – almost 12x slower. The I/O statistics show the expected (but still mysterious!) work table and its associated reads:

The Extended Events wait statistics show SQL Server spent very little of that time waiting on my laptop’s slow hard drive – just 402 ms:

Explanation

The are a number of factors in play here that we will look at in turn.

Nested Loops Prefetching

One of the reasons the optimizer prefers Hash Match and Merge Join for larger inputs is that the data access patterns tend to favour large sequential read-ahead. Both hash and merge tend to scan (range-scan in the case of a seek) their inputs, and the SQL Server Storage Engine automatically issues read-ahead when it detects this type of access. There is nothing in the execution plan to show that a base table will be read with read-ahead, it just happens.

A very basic implementation of Nested Loops join would not benefit from read-ahead at all on its inner side. The outer (driving) side of the loops join might well be a scan or range-scan of an index, and so benefit from automatic read-ahead, of course. The inner side is executed once per outer row, resulting in a rapid succession of small index seeks for different values. These small seeks will typically not be large enough to trigger the automatic read-ahead mechanism. Indeed, in our test, each inner side seek is for precisely one value.

SQL Server improves on this by implementing a second read-ahead mechanism especially for Nested Loops joins (not all N-L joins, it is a cost-based decision the optimizer makes). The basic idea is to buffer extra rows from the outer side of the join, and to use the row values in the buffer to drive read-ahead for the inner side. The effect is that the Nested Loops join becomes a partly blocking operator as outer-side rows are read into the buffer and read-ahead issued based on buffered index key values.

This read-ahead may be either order-preserving or not, and is indicated in the execution plan by the Nested Loop attributes With Ordered Prefetch and With Unordered Prefetch, respectively. When unordered prefetch occurs, the inner side is processed in whatever order the asynchronous reads happen to complete. With ordered prefetching, the mechanism is careful to ensure that the order of rows entering the join is preserved on the output.

In the test rig, the ORDER BY clause means there is a need to preserve row order, so Ordered Prefetch is used:

The issue described in this post is not specific to ordered prefetching – the same behaviour is just as likely with unordered prefetching. The point is that Nested Loops prefetching is one of the requirements.

Documented trace flags 652 and 8744 may be used (with care, and after serious testing) to disable automatic read-ahead and Nested Loops prefetching respectively. This is sometimes beneficial where all data is expected to be in memory (in which case read-ahead processing consumes resources better used by query execution) or where the I/O subsystem is extremely fast. In case you were wondering, there is no background thread for prefetching – all the work of checking whether the data is in memory, and issuing I/O if not, is performed by the worker thread executing the query.

I should stress that read-ahead and Nested Loops prefetching is generally A Very Good Thing with typical storage solutions (e.g. SANs) and both work best (or at all) when indexes have low logical fragmentation.

Manufactured LOBs

The issue described here also requires that a large object data type is manufactured before prefetching. The Compute Scalar operators in the test execution plan perform that function:

By ‘manufactured’, I mean that the source columns are not LOB types, but the expression output is – notice the implicit conversion to nvarchar(max). To be clear about it, the issue we are analysing here does not occur when Nested Loops prefetching occurs with an expression that was a LOB type to begin with.

The Outer Join

The optimizer is quite good, generally speaking, at moving scalar expressions around. If the query had featured inner joins (whether by query design or through optimizer activities) the chances are quite good that the problematic expressions (the LOB manufacturers) would have moved beyond the prefetching, and so out of harm’s way. It is quite tricky to preserve NULL-extension and other outer-join semantics properly when moving expressions above an outer join, so the optimizer generally does not even try. In essence, the outer join represents an optimization barrier to the LOB-manufacturing expressions.

Memory Allocation

When Nested Loops prefetching occurs with a manufactured LOB, the question arises of where to store the created LOBs when buffering rows for prefetch. If the source data were already a LOB type, the execution engine would already have memory structures in place to handle them. When prefetching encounters a manufactured LOB, it needs to store it somewhere, since the engine is no longer processing a stream of one row at a time. It turns out that there is a small memory buffer set aside for this eventuality, which empirical tests show to be 24KB.

However, this 24KB (directly allocated, not via workspace memory grant) is shared across all concurrently executing prefetching joins in the query. With six such joins in the test rig plan and large manufactured LOBs, the buffer stands no chance. As a result, query execution engages a bail-out option: a work table created in tempdb. Though the pages of the worktable may in fact remain memory-resident, overheads (including latching and using general-purpose code interfaces for access to the buffered rows) mean this is very much slower than using the direct-memory cache.

As with most internal work tables, the logical reads reported on this work table indicate the number of rows processed (not 8KB pages, as for regular I/O statistics). This fact, together with the large number of items processed via the worktable in our test, accounts for the millions of reads reported.

The creation and use of the work table depends on run time conditions and timing. If execution finds the data it needs is already in memory, the prefetch checks are still performed, but no asynchronous read requests end up being posted. The 24KB buffer is never filled, so the need to create a work table never arises. The more prefetch that actually occurs, the higher the chances that the buffer will fill. It is quite possible to experience a low level of prefetch with manufactured LOBs without the engine needing to bail out to a work table, especially if the LOBs are not very big and the I/O system is quite fast.

Workaround

We can rewrite the query to avoid feeding manufactured LOB data to the prefetch buffer. The idea is to use OUTER APPLY to return the data that contributes to the concatenation, rather than the result of the concatenation. We can then perform the CONCAT operation (which handles NULLs nicely without extra work) after the join, avoiding the prefetch buffer issue completely. In SQL Server versions prior to 2012, we would need to use direct string concatenation, and handle rows that are NULL-extended explicitly using ISNULL or COALESCE.

DECLARE @d nvarchar(max) = NCHAR(10000);

SELECT 

    n.n,

    DATALENGTH

    (

        CONCAT

        (

            CONCAT(oa1.i0, oa1.i1, oa1.i2, oa1.i3, oa1.i4, oa1.i5, oa1.i6),

            CONCAT(oa2.i0, oa2.i1, oa2.i2, oa2.i3, oa2.i4, oa2.i5, oa2.i6),

            CONCAT(oa3.i0, oa3.i1, oa3.i2, oa3.i3, oa3.i4, oa3.i5, oa3.i6),

            CONCAT(oa4.i0, oa4.i1, oa4.i2, oa4.i3, oa4.i4, oa4.i5, oa4.i6),

            CONCAT(oa5.i0, oa5.i1, oa5.i2, oa5.i3, oa5.i4, oa5.i5, oa5.i6),

            CONCAT(oa6.i0, oa6.i1, oa6.i2, oa6.i3, oa6.i4, oa6.i5, oa6.i6)

        )

    )

FROM dbo.Numbers AS n

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T1 AS t WHERE t.id = n.n) AS oa1

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T2 AS t WHERE t.id = n.n) AS oa2

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T3 AS t WHERE t.id = n.n) AS oa3

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T4 AS t WHERE t.id = n.n) AS oa4

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T5 AS t WHERE t.id = n.n) AS oa5

OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T6 AS t WHERE t.id = n.n) AS oa6

WHERE n.n BETWEEN 1 AND 10000

ORDER BY n.n

OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

The execution plan for the rewritten query looks visually similar to the problematic one:

However, the Compute Scalars no longer manufacture a LOB data type, they just emit column and variable references:

All the concatenation work (and LOB manufacture) is performed by the final top-level Compute Scalar in a single monster expression [Expr1056]:

Warm cache results

With all data in memory, the new query completes in 1.8 seconds (very slightly up on 1.6 seconds before):

Cold cache results

When all data must be fetched from disk, the query issues optimal prefetching and completes in 7.3 seconds (down from 18.6 seconds) with no work table:

The Extended Events wait statistics now show 3.8 seconds spent waiting for my laptop’s slow spinning disk (which is a good thing!)

Final Thoughts

Work tables can appear in STATISTICS IO output for a wide range of reasons, but if you encounter one with a very large number of reads – particularly LOB reads – you may be encountering this issue. The rewrite proposed above may not always be possible, but you should be able to refactor your query to avoid the issue now you know it exists.

I am not a fan of doing large amounts of string manipulation in SQL Server. I am always particularly suspicious of the perceived need to split or concatenate large volumes of strings.

I am, however, a fan of always using explicit data types (rather than relying on implicit conversions) and generating relatively small query plans that offer the query optimizer clear and obvious choices. By necessity, this often means writing small SQL queries in logical steps (and no, long chains of common table expressions do not count!)

The real world does not always make these things possible, of course, but it is good to have goals :)

© 2013 Paul White – All Rights Reserved
email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

Screenshots acquired using SnagIt by TechSmith
Query plan details obtained using Plan Explorer PRO by SQLSentry

Microsoft have released a fix for incorrect results returned when querying an indexed view. The problem applies to:

• SQL Server 2012
• SQL Server 2008 R2
• SQL Server 2008

The Knowledge Base article does not go into much detail, or provide a reproduction script, but this blog entry does :)

The KB does say that reproducing the bug requires these features:

• An indexed view on two tables that have a foreign key relationship
• An update performed against the base tables
• A query executed against the indexed view using a NOEXPAND hint

There are two important details I would like to add right away:

• The NOEXPAND hint is not required to reproduce the bug on Enterprise Edition
• The update must be performed by a MERGE statement

The fix is available in the following cumulative update packages:

Cumulative Update 2 for SQL Server 2012 SP1 [build 11.0.3339]
Cumulative Update 5 for SQL Server 2012 RTM [build 11.0.2395]
Cumulative Update 4 for SQL Server 2008 R2 SP2 [build 10.50.4270]
Cumulative Update 10 for SQL Server 2008 R2 SP1 [build 10.50.2868]
Cumulative Update 8 for SQL Server 2008 SP3 [build 10.00.5828]

No service pack contains this fix, you must apply one of the hotfix packages above.

Steps to Reproduce

The first thing we will need is two tables:

CREATE TABLE dbo.Parent 

(

    parent_id integer IDENTITY NOT NULL,

    value varchar(20) NOT NULL,

    CONSTRAINT PK_Parent_id 

        PRIMARY KEY CLUSTERED (parent_id)

);

GO

CREATE TABLE dbo.Child

(

    child_id integer IDENTITY NOT NULL,

    parent_id integer NOT NULL,

    CONSTRAINT PK_Child_id 

        PRIMARY KEY CLUSTERED (child_id)

);

And a few rows of data:

INSERT dbo.Child (parent_id)

SELECT New.parent_id 

FROM 

    (

    INSERT Parent 

    OUTPUT inserted.parent_id 

    VALUES 

        ('Apple'), 

        ('Banana'), 

        ('Cherry')

    ) AS New;

The tables now look like this (parent first):

We can now add the required FOREIGN KEY relationship:

ALTER TABLE dbo.Child

ADD CONSTRAINT FK_Child_Parent

FOREIGN KEY (parent_id)

REFERENCES dbo.Parent (parent_id);

Next, a very simple indexed view that joins the two tables (the view could contain more complex features like aggregates):

CREATE VIEW dbo.ParentsAndChildren

WITH SCHEMABINDING 

AS

SELECT 

    p.parent_id, 

    p.value, 

    c.child_id

FROM dbo.Parent AS p

JOIN dbo.Child AS c ON 

    c.parent_id = p.parent_id;

GO

CREATE UNIQUE CLUSTERED INDEX cuq 

ON dbo.ParentsAndChildren (child_id);

The final step is to use a MERGE statement to make some changes to the Parent table:

DECLARE @ParentMerge AS TABLE

(

    parent_id integer PRIMARY KEY, 

    value varchar(20) NOT NULL

);

INSERT @ParentMerge

    (parent_id, value)

VALUES

    (1, 'Kiwi Fruit'),

    (4, 'Dragon Fruit');

MERGE dbo.Parent AS p

USING @ParentMerge AS s ON 

    s.parent_id = p.parent_id

WHEN MATCHED THEN 

    UPDATE SET value = s.value

WHEN NOT MATCHED THEN 

    INSERT (value) VALUES (s.value)

OUTPUT 

    $action, 

    inserted.parent_id, 

    deleted.value AS old_value, 

    inserted.value AS new_value;

This MERGE performs two actions:

1. Updates the value column of parent row 1 from Apple to Kiwi Fruit
2. Adds a new parent row 4 for Dragon Fruit

The statement includes an OUTPUT clause to show the changes it makes (this is not required for the repro):

This confirms that the changes have been made as we requested: parent row 1 has changed; and row 4 has been added. The changes are reflected in the base tables:

SELECT * FROM dbo.Parent AS p;

SELECT * FROM dbo.Child AS c;

As highlighted, row 1 has changed from Apple to Kiwi Fruit and row 4 has been added.

We do not expect to see row 4 in the indexed view because there are no child records for that row, and the indexed view uses an inner join. Checking the indexed view using the NOEXPAND table hint (required in non-Enterprise SKUs to use indexes on a view):

SELECT *

FROM dbo.ParentsAndChildren 

WITH (NOEXPAND);

The results are incorrect. They show the old value of the data for parent row 1.

Now we try using the EXPAND VIEWS query hint to force SQL Server to access the base tables rather than reading view indexes:

SELECT *

FROM dbo.ParentsAndChildren

OPTION (EXPAND VIEWS);

This query produces correct results.

On SQL Server Enterprise Edition, the optimizer chooses whether to access the indexed view or the base tables. For following query, without any hints, the optimizer chooses not to expand the view. It reads the view index and produces incorrect results:

-- Enterprise Edition ONLY

SELECT * 

FROM dbo.ParentsAndChildren;

Perhaps adding a child row to match the new parent row 4 will somehow fix things up?

INSERT dbo.Child (parent_id) VALUES (4);

GO

SELECT * FROM dbo.ParentsAndChildren WITH (NOEXPAND);

SELECT * FROM dbo.ParentsAndChildren OPTION (EXPAND VIEWS);

No. The query plan that accesses the view index still returns an incorrect value for row 1. It seems MERGE has corrupted our indexed view.

Analysis using DBCC CHECKTABLE

Checking the view with DBCC CHECKTABLE returns no errors:

DBCC CHECKTABLE (ParentsAndChildren);

Unless we use the EXTENDED_LOGICAL_CHECKS option:

DBCC CHECKTABLE (ParentsAndChildren) WITH EXTENDED_LOGICAL_CHECKS;

The damage is repairable:

ALTER DATABASE Sandpit 

SET SINGLE_USER 

WITH ROLLBACK IMMEDIATE;

GO

DBCC CHECKTABLE (ParentsAndChildren, REPAIR_REBUILD) WITH EXTENDED_LOGICAL_CHECKS;

GO

DBCC CHECKTABLE (ParentsAndChildren) WITH EXTENDED_LOGICAL_CHECKS;

GO

ALTER DATABASE Sandpit SET MULTI_USER;

You probably do not want to set your database to SINGLE_USER mode and run a DBCC repair after every MERGE statement, however. We could also rebuild the indexed view’s clustered index manually, of course.

Cause

For the MERGE statement above, the query optimizer builds a plan that does not update the indexed view (click to enlarge):

In a version of SQL Server with the fix applied, the same MERGE statement produces a plan that does maintain the indexed view:

The plan operators used to keep the view index in step with the base tables are highlighted. Without these operators, the changes to the base table are not correctly written to any indexes defined on the view. The root cause is related to the same simplification that allows the optimizer to remove the reference to the Parent table in this query:

SELECT 

    COUNT_BIG(*)

FROM dbo.Parent AS p 

JOIN dbo.Child AS c ON 

    c.parent_id = p.parent_id;

The FOREIGN KEY relationship and NOT NULL constraints on the referencing column together mean that the join to Parent cannot affect the result of the query, so the join is simplified away. In SQL Server 2012, we can see when this simplification is performed because the following message appears when undocumented trace flags 8619 and 3604 are enabled during compilation:

The same message is emitted when a MERGE statement contains a WHEN MATCHED THEN UPDATE clause and either a WHEN NOT MATCHED THEN INSERT or WHEN MATCHED … THEN DELETE clause. These conditions combine such that the optimizer incorrectly concludes that a table reference can be removed, when in fact it is needed later on when the update side of the plan is built.

Other details of the query and database can affect whether the simplification can be misapplied. For example, if the FOREIGN KEY constraint contains an ON DELETE CASCADE clause, and the MERGE contains a DELETE clause, the simplification is not performed, the TF 8619 message does not appear, and the bug does not manifest.

The key to determining whether a particular query is vulnerable to this bug (TF 8619 aside) is to check whether the query plan includes operators to maintain the indexed view. At a minimum, you should see a update operator for the view:

SQL Sentry Plan Explorer identifies the operator as applying to a view explicitly, in SSMS you need to click on the graphical operator and inspect the Properties window.

Summary

The updated conditions for incorrect results are:

• An indexed view that joins tables
• Two of the tables have a single-column FOREIGN KEY constraint
• A MERGE statement contains an UPDATE action that affects one of the tables
• The MERGE statement also contains an INSERT or DELETE action (or both)
• The optimizer applies a simplification that removes a table reference based on the FK relationship and other metadata
• As a result, the MERGE execution plan does not contain the operators necessary to correctly maintain the indexed view
• A subsequent query plan accesses an index on the view, either explicitly or via indexed-view matching (Enterprise Edition)

Note:

• The simplification is not applied in tempdb
• The simplification is not applied to multi-column foreign key constraints

Under these conditions, the indexes on the view do not reflect the state of the base tables and incorrect results are returned. Once the hot fix is applied, the optimizer does not misapply the simplification so the correct indexed view maintenance features are built into execution plans.

Update: I am adding this based on Ian Yates’ great question in the comments: my expectation is that applying this hotfix will not remove any existing indexed view corruption. You would need to test the hotfix as usual, apply it, and then either rebuild all affected indexed views manually, or run DBCC CHECKDB with the EXTENDED_LOGICAL_CHECKS option (which could take a long time).

© 2013 Paul White – All Rights Reserved

Twitter: @SQL_Kiwi
Email: SQLKiwi@gmail.com

Most tuning efforts for data-changing operations concentrate on the SELECT side of the query plan. Sometimes people will also look at important storage engine considerations like locking and transaction log throughput that can have dramatic effects. As a consequence, a number of common practices have emerged, such as avoiding large numbers of row locks and lock escalation, splitting large changes into smaller batches of a few thousand rows and combining a number of small changes into a single transaction in order to optimize log flushes.

This is all good of course, but what about the data-changing side of the query plan – the INSERT, UPDATE, DELETE or MERGE operation itself – are there any query processor considerations we should take into account? The short answer is yes. The query optimizer considers different plan options for the write-side of an I/U/D/M query, though there isn’t a huge amount of T-SQL language support that allows us to affect these choices directly. Nevertheless, there are things to be aware of, and things we can look to change.

Side note: In this post I am going to use the term update (lower case) to apply to any operation that changes the state of the database (INSERT, UPDATE, DELETE and MERGE in T-SQL). This is a common practice in the literature, and is used inside SQL Server too as we will see.

The Three Basic Update Forms

First a bit of background. All query plans execute using a demand-driven iterator model, and updates are no exception. Parent operators drive child operators (to the right of the parent) to do work by asking them for a row at a time. Take the following simple AdventureWorks INSERT for example:

DECLARE @T AS TABLE (ProductID int);

INSERT @T (ProductID) 

SELECT p.ProductID 

FROM Production.Product AS p;

Plan execution starts at the far left, where you can think of the green T-SQL INSERT icon as representing rows returned to the client. This root node asks its immediate child operator (the Table Insert) for a row. The Table Insert requests a row from the Index Scan, which provides one. This row is inserted into the heap, and an empty row is returned to the root node (if the INSERT query contained an OUTPUT clause, the returned row would contain data). This row-by-row process continues until all source rows have been processed. Notice that the XML show plan output shows the Heap Table Insert is performed by an Update operator internally. Ok, on to the matter at hand:

1. Wide, per-index updates

Wide per-index update plans have a separate update operator for each clustered and nonclustered index. It is always possible for the optimizer to produce this type of plan; the options described later have not been (or cannot be) implemented when certain engine features are used. For example, if the update target has an indexed view defined on it, a wide update plan has to be used to maintain the indexed view. An example per-index update plan is shown below:

This plan updates the base table using a Clustered Index Delete operator. This operator may also read and output extra column values necessary to find and delete rows from nonclustered indexes. The iterative delete activity on the base table is driven by the Eager Table Spool on the top branch. The spool is eager because it stores all the rows from its input in a worktable before returning the first row to its parent operator (the Index Delete on the top branch). The effect is that all qualifying base table rows are deleted before any nonclustered index changes occur.

The spool in this plan is a common subexpression spool. It is populated once and then acts as a row source for multiple consumers. In this case, the contents of the spool are consumed first by the top-branch Index Delete, which removes index entries from one of the nonclustered indexes. When the Sequence operator switches to asking for rows from the lower branch, the spool is rewound and replays its rows for the second nonclustered index. Note that the spool contains the UNION of all columns required by nonclustered index changes.

2. Narrow, per-row updates

Narrow per-row updates have a single update operator which maintains the base table (heap or clustered) and one or more nonclustered indexes. Each row arriving at the update operator updates all indexes associated with the operator before processing the next row. An example:

DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int UNIQUE, col2 int UNIQUE);

DECLARE @S AS TABLE (pk int PRIMARY KEY, col1 int, col2 int);

INSERT @T (pk, col1)

SELECT

    s.pk,

    s.col1 

FROM @S AS s;

The execution plan viewed using SQL Sentry Plan Explorer shows the nonclustered index maintenance explicitly (hover over the Clustered Index Insert for a tooltip showing the names of the nonclustered indexes involved):

In SQL Server Management Studio, there is no information about the nonclustered index maintenance in the graphical plan or tooltips, we need to click on the update operator (Clustered Index Insert) and then check the Properties window:

This shows the clustered index and two nonclustered indexes being maintained. Because all indexes are updated for each row streaming through the update operator, this plan shape is also known as a per-row update plan.

The query optimizer uses cost-based reasoning to decide whether to update each nonclustered index separately (per-index) or as part of the base table changes (per-row). An example that updates one nonclustered index per-row, and another per-index is shown below:

CREATE TABLE #T (pk int IDENTITY NOT NULL, col1 int, col2 varchar(8000) DEFAULT '');

ALTER TABLE #T ADD CONSTRAINT PK_T PRIMARY KEY (pk);

CREATE INDEX nc1 ON #T (col1);

CREATE INDEX nc2 ON #T (col1) INCLUDE (col2);

The combination strategy can be seen with Plan Explorer (click to expand in a new tab):

The details are also displayed in the SSMS Properties window when the Clustered Index Insert operator is selected as well.

3. Single-operator updates

The third form of update is an optimization of the per-row update plan for very simple operations. The cost-based optimizer still emits a per-row update plan, but a rewrite is subsequently applied to collapse the reading and writing operations into a single operator:

-- Simple operations

DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int);

INSERT @T (pk, col1) VALUES (1, 1000);

UPDATE @T SET col1 = 1234 WHERE pk = 1;

DELETE @T WHERE pk = 1;

The complete execution plans (and extracts from the XML plans) are shown below:

The UPDATE and DELETE plans have been collapsed to a `Simple Update` operation, while the INSERT is simplified to a `Scalar Insert`. We can see the original optimizer output tree with trace flags 3604 and 8607:

DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int);

DBCC TRACEON (3604, 8607);

INSERT @T (pk, col1) VALUES (1, 1000) OPTION (RECOMPILE);

UPDATE @T SET col1 = 1234 WHERE pk = 1 OPTION (RECOMPILE);

DELETE @T WHERE pk = 1 OPTION (RECOMPILE);

DBCC TRACEOFF (3604, 8607);

The trace output for the INSERT statement shown above is:

Notice the two physical operators: a constant scan (in-memory table) containing the literal values specified in the query; and a stream update operator that performs the database changes per row. All three statements produce a similar optimizer tree output (and all use a stream update). We can prevent the single-operator optimization being applied with undocumented trace flag 8758:

DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int);

DBCC TRACEON (8758);

INSERT @T (pk, col1) VALUES (1, 1000) OPTION (RECOMPILE);

UPDATE @T SET col1 = 1234 WHERE pk = 1 OPTION (RECOMPILE);

DELETE @T WHERE pk = 1 OPTION (RECOMPILE);

DBCC TRACEOFF (8758);

This exposes the expanded per-row update plans produced by the optimizer before the single-operator rewrite:

Single operator plans can be significantly more efficient than the original multiple-operator form in the right circumstances, for example if the plan is executed very frequently.

Update plan optimizations

From this point forward, I’m going to use simple AdventureWorks DELETE examples, but the general points apply equally well to INSERT, UPDATE and MERGE as well. The examples will not have a complicated SELECT component, because I want to concentrate on the update side of the plan rather than the reading side.

Per-row updates

It’s worth emphasising again that per-row update plans are an optimization that is not available for every update query. The optimizer favours a per-row plan if the expected number of rows at the update operator is low. In the example below, the optimizer expects to delete 25 rows:

This plan updates the base table (a clustered index in this case) and all nonclustered indexes in sequence per row. The row source here is an ordered scan of a nonclustered index, which means rows will not generally be presented in clustered index key order to the update operator.

An unordered stream like this tends to result in random I/O (assuming physical I/O is required at all, of course). If the plan is expected to process only a small number of rows, the optimizer decides it is not worth adding extra operations to encourage sequential I/O.

Unordered Prefetch

If the expected number of rows is a bit larger, the optimizer may decide to build a plan that applies prefetching to one or more update operators. The basic idea is the same as ordinary prefetching (a.k.a read-ahead) for scans and range seeks. The engine looks ahead at the keys of the incoming stream and issues asynchronous IOs for pages that will be needed by the update operator soon. Prefetching helps reduce the impact of the random I/O mentioned a moment ago. An example of prefetching on the update operator is shown below for the same query and an expected cardinality of 50 rows:

The prefetching is unordered from the perspective of the clustered index. Neither SSMS nor Plan Explorer show the prefetch information prominently. In Plan Explorer, we need to have the With Unordered Prefetch optional column selected. To do this, switch to the Plan Tree tab, open the Column Chooser, and drag the column to the grid. The unordered prefetch property is ticked for the Clustered Index Delete operator in the screenshot below:

In SSMS, click on the Clustered Index Delete icon in the graphical plan, and then look in the Properties window:

If the query plan were reading from the clustered index, the read operation would issue regular read-ahead, so there would be no point prefetching from the Clustered Index Delete as well. The example below shows the expected cardinality increased to 100, where the optimizer switches from scanning the nonclustered index with unordered prefetching to scanning the clustered index. No prefetching occurs on the update operator in this plan:

Where the plan property With Unordered Prefetch is not set, it is simply omitted – it does not appear set to False as you might expect.

Ordered Prefetch

Where rows are expected to arrive at an update operator in non-key order, the optimizer might consider adding an explicit sort. The idea is that presenting rows in key order will encourage sequential I/O for the index pages. The optimizer weighs the cost of the sort against the expected benefits of avoiding random I/O. The execution plan below shows an example of a sort being added for this reason:

The sort is on Transaction ID, the clustering key for this table. With the incoming stream now sorted, the update operator can use ordered prefetching. The plan is still scanning the nonclustered index on the read side, so read-ahead issued by that operator does not bring in the clustered index pages needed by the update operator. Ordered prefetching tends to result in sequential I/O, compared with the mostly random I/O of unordered prefetching. The With Ordered Prefetch column is also not shown by default by Plan Explorer, so it needs to be added as we did before:

Not every update operator with ordered prefetching requires a sort. If the optimizer finds a plan that naturally presents keys in nonclustered index order, an update operator may still use ordered prefetching.

DML Request Sort

When the optimizer decides to explore a plan alternative that requires ordered input to an update operator, it will set the DML Request Sort property for that operator. Plan Explorer shows this setting in the update operator tooltip:

SSMS shows With Ordered Prefetch and DML Request Sort in the Properties window:

Nonclustered index updates

Sorting and ordered prefetching may also be considered for the nonclustered indexes in a per-index update plan.

This plan shows all three update operators with DML Request Sort set. The Clustered Index Delete does not require an explicit sort because rows are being read (with internal ordering guarantees) from the Clustered Index Scan. The two non-clustered indexes do require explicit sorts, however. Both nonclustered index update operators also use ordered prefetching; the clustered index update does not because the scan automatically invokes read-ahead for that index.

The next example shows that each update operator is considered separately for the various optimizations:

That plan features unordered prefetching on the Clustered Index Delete (because the row source is a scan of a nonclustered index), an explicit sort with ordered prefetching on the top branch Index Delete, and unordered prefetching on the bottom branch Index Delete.

The per-index and per-row update plan

Is the following a per-index or per-row update plan?

It appears to be a per-index plan because there are two separate update operators, but there is no blocking operator (eager spool or sort) between the two. This plan is a pipeline: each row returned from the seek will be processed first by the Clustered Index Delete and then by the Index Delete. In that sense, the both updates (clustered and nonclustered) are certainly per-row.

The important thing is not the terminology, it is being able to interpret the plan. Now we know what the various optimizations are for, we can see why the optimizer chose the plan above over the seemingly equivalent but more efficient-looking narrow plan:

The narrow plan has no prefetching. The Seek provides read-ahead for the clustered index pages, but the single non-clustered index has nothing to prefetch any pages from disk it might need. By contrast, the previous wide update plan has two update operators. The Clustered Index Delete has no prefetching for the same reason as in the narrow plan, but the Index Delete has unordered prefetching enabled.

So, although the smaller narrow plan looks like it ought to be more efficient, it might perform less well if nonclustered index pages are required from disk and unordered prefetching proves effective. On the other hand, if all required nonclustered index pages are in memory at the time the query is executed, the wide plan might perform less well since it features an extra operator and has to perform all the work associated with prefetching (even though ultimately no physical reads are issued).

Performance Impacts

You may have noticed a lack of performance numbers (I/O statistics, elapsed times and so on) in this post. There is a good reason for this. The optimizations presented here are quite dependent on SQL Server configuration and hardware. I don’t want you drawing general conclusions based on the performance of the rather ordinary single SATA drive in my laptop, the 256MB of RAM I have allowed for my SQL Server 2012 instance, and some rather trivial AdventureWorks examples.

Which Optimizations are Good?

It depends, naturally.

If the data structures you are changing are very likely to be in memory, and/or if you have a very fast random I/O system, the optimizer’s goal of minimizing random I/O and enhancing sequential I/O may not make much sense for you. The strategies the optimizer employs may well end up costing you much more than they save.

On the other hand, if your system has a much smaller buffer pool than database working set size, and your I/O system works very much faster with large sequential I/O than with smaller random I/O requests, you should generally find the optimizer makes reasonable choices for you, subject to the usual caveats about useful up-to-date statistics and accurate cardinality estimation, of course.

If your system fits the optimizer’s model, at least to a first approximation, you will usually find that narrow update plans are best for low cardinality update operations, unordered prefetching helps a bit when more rows are involved, ordered prefetching helps more, and explicit sorts before nonclustered index updates helps most of all for the largest sets. That is the theory, anyway.

What are the Problems?

The problem I see most often is with the optimization that is supposed to help most: the explicit sort before a nonclustered index update. The idea is that sorting the input to the index update in key order promotes sequential I/O, and often it does. The problem occurs if the workspace memory allocated to the sort at execution time proves to be too small to perform the sort entirely in memory. The memory grant is fixed based on cardinality estimation and row size estimates, and may be reduced if the server is under memory pressure at the time.

In any case, however it occurs, a sort that runs out of memory spills whole sort runs to physical tempdb disk, often repeatedly. Unsurprisingly, this is not at all good for performance, and can result in queries that complete very much slower than if the sort had not been introduced at all. SQL Server reuses the general Sort operator for sorting index keys – it does not have a sort specially optimized for index updates which could make a best effort to sort within the memory allocated, but never spill to disk. Perhaps I should suggest this on Connect :)

The narrow plan optimization can cause problems where it is selected due to a low cardinality estimate, where several nonclustered indexes need to be maintained, the necessary pages are not in memory, and the I/O system is slow at random reads.

The ordered and unordered prefetch options cause problems much more rarely. For a system with all data in memory, there is a small but possibly measurable impact due to the prefetch overhead (finding pages to consider read-ahead for, checking to see if they are already in the buffer pool, and so on). Even if no asynchronous I/O is ever issued by the worker, it still spends time on the task that it could spend doing real work.

What options are there?

The usual answer to deal with poor execution plan choices due to a system’s configuration or performance characteristics not matching the optimizer’s model is to try different T-SQL syntax, and/or to try query hints. There are times when it is possible to rewrite the query to get a plan that performs better, and other times where rethinking the problem a bit can pay dividends. Various creative uses of partitioning, minimal logging, and bulk loading are possible in some cases, for example.

There are very few hints that can help with the update side of a plan that does not respond to the usual tricks, however. The two I use most often affect the optimizer’s cardinality estimation - OPTION (FAST n) and a trick involving TOP and the OPTIMIZE FOR query hint. OPTION (FAST n) affects cardinality estimates in a plan by setting a final row goal, but its effects can be difficult to predict, and may not have much of an effect if the plan contains blocking operators. Anyway, the general idea is to vary the value of ‘n’ in the hint until the optimizer chooses the desired plan shape or optimization options as described in this post. Best of luck.

The idea with TOP is similar, but tends to work better in my experience. The trick is to declare a bigint variable with the number of rows the query should return (or a very large value such as the maximum value of a bigint if all rows are required), use that as the parameter to a TOP, and then use the OPTIMIZE FOR hint to set a value for ‘n’ that the optimizer should use when considering alternative plans. This option is particularly useful for encouraging a narrow plan.

Most of the examples in this post used the TOP trick in the following general form:

DECLARE @n bigint = 9223372036854775807;

DELETE TOP (@n) 

FROM Production.TransactionHistory

OPTION (OPTIMIZE FOR (@n = 50));

No magic trace flags?

Sure there are trace flags that affect the optimizations in this post. They are undocumented and unsupported of course, and may only work on some versions, but they can be handy to validate a performance analysis, or to generate a plan guide for a particularly crucial query. They can also be fun to play with on a personal system to explore their effects. The main ones that affect the optimizations described here are:

2332 : Force DML Request Sort (CUpdUtil::FDemandRowsSortedForPerformance)

8633:  Enable prefetch (CUpdUtil::FPrefetchAllowedForDML and CPhyOp_StreamUpdate::FDoNotPrefetch)

8744 : Disable prefetch (CUpdUtil::FPrefetchAllowedForDML)

8758 : Disable rewrite to a single operator plan (CPhyOp_StreamUpdate::PqteConvert)

8790 : Force a wide update plan (CUpdUtil::PexprBuildWideUpdatePlan)

8795 : Disable DML Request Sort (CUpdUtil::FDemandRowsSortedForPerformance)

9115 : Disable prefetch (CUpdUtil::FPrefetchAllowedForDML)

These trace flags can all be manipulated using the usual DBCC commands or enabled temporarily for a particular query using the OPTION (QUERYTRACEON xxxx) hint.

Final Thoughts

The optimizer has a wide range of choices when building the writing side of an update plan. It may choose to update one or more indexes separately, or as part of the base table update. It may choose to explicitly sort rows as part of a per-index update strategy, and may elect to perform unordered or ordered prefetching as well. As usual, these decisions are made based on costs computed using the optimizer’s model. This model may not always produce plans that are optimal for your hardware (and as usual the optimizer’s choices are only as good as the information you give it).

If a particular update query is performance critical for you, make sure cardinality estimates are reasonably accurate. Test with alternate syntax and/or trace flags to see if an alternative plan would perform significantly better in practice. It is usually possible to use documented techniques like TOP clauses and OPTIMIZE FOR hints to produce an execution plan that performs well. Where that is not possible, more advanced tricks and techniques like plan guides may be called for.

Thanks for reading today, I hope this post was interesting and provided some new insights into update query optimization.

© 2013 Paul White – All rights reserved
email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

Estimated row counts on key or RID lookups where a filtering predicate is applied can be wrong in SSMS execution plans.  This error does not affect the optimizer’s ultimate plan selection, but it does look odd.  There are other cases where estimated row counts are inconsistent (for defensible reasons) but the behaviour shown in this post in certainly a bug.

SQL Server 2005

The following AdventureWorks sample query displays TransactionHistory information for ProductID #1 and the last three months of 2003 (if you are using a more recent version of AdventureWorks, you will need to change the year from 2003 to 2007):

SELECT

    th.ProductID,

    th.TransactionID,

    th.TransactionDate

FROM Production.TransactionHistory AS th 

WHERE 

    th.ProductID = 1 

    AND th.TransactionDate BETWEEN '20030901' AND '20031231';

The query plan is:

The execution flow is pretty straightforward.  The plan seeks a non-clustered index on the ProductID column to find rows where ProductID = 1.  This non-clustered index is keyed on ProductID alone, but the index also includes the TransactionID clustering key (to point to the parent row in the base table).  The index does not cover the query (the TransactionDate column is not present in the index) so a Key Lookup is required for the TransactionDate column.  The nested loops join drives a look up process such that each row from the Index Seek on ProductID = 1 results in a lookup in the clustered index to find the TransactionDate value for that row.  A final Filter operator passes only rows that meet the date range condition.

The next diagram shows the same plan with cardinality estimates and extra details for the Key Lookup:

The cardinality estimate at the Index Seek is exactly correct.  The table is not very large, there are up-to-date statistics associated with the index, so this is as expected.  If you run a query to find all rows in the TransactionHistory table for ProductID #1, 45 rows will indeed be returned.

The estimate for the Key Lookup is exactly correct.  Each lookup into the Clustered Index to find the Transaction Date is guaranteed to return exactly one row (each non-clustered index entry is associated with exactly one base table row).  The Key Lookup is expected to be executed 45 times (shown circled).

The estimate for the Inner Join is exactly correct – 45 rows from the seek joining to one row each time from the lookup, gives a total of 45 rows.

The Filter estimate is also good: SQL Server estimates that of the 45 rows entering the filter, 16.9951 rows will match the specified range of transaction dates.  In reality, only 11 rows are produced by this query, but that small difference in estimates is quite normal and certainly nothing to worry about here.  You might like to keep that estimate of 16.9951 rows in mind, however.

SQL Server 2008 onward

The same query executed against an identical copy of AdventureWorks on SQL Server 2008 (or R2, or 2012) produces a quite different execution plan:

Instead of an explicit Filter to find rows with the requested date range, the optimizer has pushed the date predicate down to the Key Lookup (the Key Lookup now has a predicate on Transaction Date).  This is a good optimization in general terms; it makes sense to filter rows as early as possible.  Unfortunately, it has made a bit of a mess of the cardinality estimates in the process.  The post-Filter estimate of 16.9951 rows seen in the 2005 plan has been moved to the Key Lookup.  Instead of estimating one row per lookup, the plan now suggests that 16.9951 rows will be produced by each clustered index lookup – clearly not right!

To my way of thinking, the execution plan cardinality estimates should look something like this:

As shown, I personally prefer to see the inner side of a nested loops join estimate the number of rows per execution, but I understand I may be in a minority on this point.  If the estimate were aggregated over the expected number of executions, the inner-side estimate would be also be 16.9951 (45 executions * 0.37767 per execution).

Cause

The query tree produced by the 2008+ optimizer looks much the same as the 2005 version – the explicit Filter is still present.  However, a post-optimization rewrite occurs in the ‘copy out’ phase that removes the Filter and incorporates it in the Key Lookup seek, resulting in a residual predicate on that operator.  This rewrite applies to regular scans and seeks too (so all residual predicates on scans and seeks are a result of this late rewrite).

I would like to thank Dima Piliugin (twitter | blog) for introducing me to undocumented trace flag 9130, which disables the rewrite from Filter + (Scan or Seek) to (Scan or Seek) + Residual Predicate.  Enabling this flag retains the Filter in the final execution plan, resulting in a SQL Server 2008+ plan that mirrors the 2005 version, with correct estimates.

The bug is that this rewrite that does not correctly update cardinality estimates when the filter is pushed down to a lookup.  I should stress that the rewrite occurs after all cost-based decisions have been made, so the incorrect estimate just looks odd and makes plan analysis harder than it ought to be.  Cardinality estimates with regular scans and seeks appear to work correctly, as far as I can tell.  The bug applies to both RID lookups and Key Lookups where a residual predicate is applied.

Workarounds

Using the trace flag is not a workaround because (a) it is (very) undocumented and unsupported; and (b) it results in a less efficient plan where rows are filtered much later than is optimal.  One genuine workaround is to provide a covering non-clustered index (avoiding the lookup avoids the problem):

CREATE INDEX nc1 

ON Production.TransactionHistory (ProductID) 

INCLUDE (TransactionDate);

With the Transaction Date filter applied as a residual predicate in the same operator as the seek, the final estimate is again as expected:

We could also force the use of the ultimate covering index (the clustered one) with a suitable table index hint:

SELECT

    th.ProductID,

    th.TransactionID,

    th.TransactionDate

FROM Production.TransactionHistory AS th WITH (INDEX(1))

WHERE 

    th.ProductID = 1 

    AND th.TransactionDate BETWEEN '20030901' AND '20031231';

Again, the estimate is 16.9951 as expected.

Fixed in SQL Sentry Plan Explorer build 7.2.42.0

After this post was published on October 15 2012 I was contacted by the SQL Sentry people to see if a good workaround could be incorporated in their free Plan Explorer product.  I was happy to provide a little testing and general feedback during a process that ultimately resulted in a new build being released on 31 October 2012.  If only SSMS limitations could be addressed so quickly!  Once you upgrade to the new version, the plan displayed for our test query is:

This is exactly the representation we would expect if the SQL Server bug did not exist (note that Plan Explorer aggregates estimated inner-side executions for you, and rounds to integer).  Well done to the SQL Sentry team, especially Brooke Philpott (@MacroMullet).

Summary

Providing a covering non-clustered index to avoid lookups for all possible queries is not always practical, and scanning the clustered index will rarely be the optimal choice either.  Nevertheless, these are the best workarounds we have today in SSMS.

Watch out for poor cardinality estimates when a predicate is applied as part of a lookup.

This particular cardinality estimation issue does not affect the final plan choice (the internal estimates are correct) but it does look odd and will confuse people when analysing query plans in SSMS.  If you think this situation should be improved, please vote for this Connect item.  It will be interesting to see how long it takes to catch up with Plan Explorer.

© 2012 Paul White – All Rights Reserved

twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com

The humble Compute Scalar is one of the least well-understood of the execution plan operators, and usually the last place people look for query performance problems.  It often appears in execution plans with a very low (or even zero) cost, which goes some way to explaining why people ignore it.

Some readers will already know that a Compute Scalar can contain a call to a user-defined function, and that any T-SQL function with a BEGIN…END block in its definition can have truly disastrous consequences for performance (see this post by Rob Farley for details).  This post is not about those sorts of concerns.

Compute Scalars

The Books Online description of this operator is not very detailed:

This leads people to think that Compute Scalar behaves like the majority of other operators: as rows flow through it,  the results of whatever computations the Compute Scalar contains are added to the stream.  This is not generally true.  Despite the name, Compute Scalar does not always compute anything, and does not always contain a single scalar value (it can be a vector, an alias, or even a Boolean predicate, for example).  More often than not, a Compute Scalar simply defines an expression; the actual computation is deferred until something later in the execution plan needs the result.

---

Compute Scalars are not the only operators that can define expressions. You can find expression definitions with labels like [Expr1008] in many query plan operators, including Constant Scans, Stream Aggregates and even Inserts.

---

Deferred expression evaluation was introduced in SQL Server 2005 as a performance optimization.  The idea is that the number of rows tends to decrease in later parts of the plan due to the effects of filtering and joining (reducing the number of expression evaluations at runtime).  To be fair to the Books Online entry, it does mention this behaviour in a note:

The take away from this first section is that a Compute Scalar is most often just a placeholder in the execution plan.  It defines an expression and assigns a label to it (e.g. [Expr1000]) but no calculations are performed at that point.  The defined expression may be referenced by multiple operators later in the execution plan.  This makes counting the number of ‘executions’ more complex than for a regular plan operator., and goes some way to explaining why Compute Scalar operators only ever show estimated row counts (even in an ‘actual’ execution plan).

Execution Plans and the Expression Service

The execution plans you see in Management Studio (or Plan Explorer) are a highly simplified representation that is nevertheless useful for many kinds of plan analysis.  The XML form of show plan has a more detail than the graphical representation, but even that is a shallow depiction of the code that actually runs inside SQL Server when a query is executed.  It is easy to be seduced into thinking that what we see as an ‘execution plan’ is more complete than it actually is.  As a tool for high-level analysis, it is excellent, but do not make the mistake of taking it too literally.  More detail on this later.

One more thing to appreciate before we get into a concrete example: the SQL Server engine contains a component known as the Expression Service.  This is used by components such as the query optimizer, query execution, and the storage engine to perform computations, conversions and comparisons.  It is the call to the expression service in the execution plan that can be deferred and performed by a plan operator other than the source Compute Scalar (or other expression-defining operator).

An Example

I came across a forum thread recently which demonstrated the concepts I want to explore in this post really well.  The topic of discussion was delimited string-splitting (an old favourite of a topic, for sure) but I want to emphasise that the particular code is not at all important – it is the query plan execution I want to focus on.  The particular string-splitting method employed was one I first saw written about by Brad Shultz; it replaces the delimiters with XML tags, and then uses XML shredding to return the results.  I should say that I am not a fan of this technique because it is (a) a strange use of XML; and (b) it does not work for all possible inputs.  Anyway, I said the example was not that important in itself, so let’s get on to the first example:

Test One – XML Split

DECLARE

    @ItemID bigint,

    @Item varchar(8000),

    @Input varchar(8000);

SET @Input = REPLICATE('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z', 32);

SELECT

    @ItemID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), 

    @Item = x.i.value('./text()[1]', 'varchar(8000)')    

FROM

(

    VALUES

        (

        CONVERT

            (xml, 

            '<r>' + 

            REPLACE(@Input, ',', '</r><r>') + 

            '</r>', 0

            )

        )

) AS ToXML (result) 

CROSS APPLY ToXML.result.nodes('./r') AS x(i);

The code above creates a single comma-delimited string containing the letters of the alphabet, repeated 32 times (a total string length of 1632 characters).  The string-splitting SELECT statement replaces the commas with XML tags, fixes up the start and end of the string, and then uses the nodes() XML method to perform the actual splitting.  There is also a ROW_NUMBER call to number the elements returned in whatever order the nodes() method spits them out.  Finally, two variables are used to ‘eat’ the output so returning results to the client does not affect execution time.  The execution plan is as follows (click to enlarge):

The Constant Scan operator defines an expression labelled as [Expr1000] which performs the string replacement and conversion to the XML type.  There are four subsequent references to this expression in the query plan:

• Two XML Reader table-valued functions (performing the nodes() shredding and value() functions)
• The Filter operator (a start-up predicate checks that the expression is not NULL)
• The Stream Aggregate (as part of a CASE expression that determines what the value() XML method should finally return)

The query takes 3753ms to execute on my laptop.  This seems a rather long time to shred a single string containing just 801 elements.

Test Two – The Empty String

The following code makes one small modification to the test one script:

SELECT

    @ItemID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), 

    @Item = x.i.value('./text()[1]', 'varchar(8000)')    

FROM

(

    VALUES

        (

        CONVERT

            (xml, 

            '<r>' + 

            REPLACE(@Input, ',', '</r><r>') + 

            '</r>' +

            LEFT(@@DBTS, 0)  -- NEW

            , 0)

        )

) AS ToXML (result) 

CROSS APPLY ToXML.result.nodes('./r') AS x(i);

The only difference in the execution plan is in the definition of [Expr1000] (click to enlarge):

This plan returns the same correct results as the first test, but it completes in 8ms (quite an improvement over 3753ms).

Beyond the Execution Plan – Test One

There is nothing in the query plan to explain why the second form of the query runs 500 times faster than the first.  To see what is going on under the covers of the execution engine when executing the slow query, we can attach a debugger and look closer at the code SQL Server is really running.  Using SQL Server 2012 and setting a breakpoint on the CXMLTypeProvider::ConvertStringToXMLForES method (as the name suggests, it converts a string to XML for the Expression Service) the first debugger break occurs with this stack trace:

I know that not everyone reading this post will routinely analyse stack traces, so for this first example I will describe the interesting calls from the bottom up (the currently executing code is on top, each line below is the method that called that routine):

1. There is nothing very interesting below CQueryScan::GetRow (it is just start-up code)
2. CQueryScan:GetRow drives the plan as we are used to seeing it.  You might think of it as approximately the code behind the green SELECT query plan icon in a graphical plan.  It reads a row at a time from the first plan operator to its right
3. The first visible plan operator to execute is the leftmost Nested Loops join (CQScanNLJoinTrivialNew::GetRow).  (The Compute Scalar to its left in the graphical plan simply defines an alias for an expression computed by the Stream Aggregate – it does not even exist in the code executed by the execution engine).
4. The nested loops join operator asks the Sequence Project operator for a row (CQScanSeqProjectNew::GetRow)
5. The sequence project operator asks the Segment operator for a row (CQScanSegmentNew::GetRow)
6. The segment operator asks the second Nested Loops Join for a row (CQScanNLJoinTrivialNew::GetRow)
7. The nested loops join has obtained a row from the Constant Scan and is now preparing to fetch a row from the inner side of the join
8. The start-up Filter operator is executing its Open() method (CQScanStartupFilterNew::Open)
9. The start-up Filter calls into the general entry point for the Expression Service to evaluate expression [Expr1000] defined by the Constant Scan
10. CEsExec::GeneralEval4 calls an ES method to convert a string to XML (ConvertFromStringTypesAndXmlToXml)
11. The XML type provider executes the code that actually converts the string to XML (ConvertStringToXMLForES)

The stack trace illustrates two things nicely:

• The iterative nature of plan operators (one row at a time, Open, GetRow, and Close methods)
• An expression defined by one operator (the Constant Scan) being deferred for evaluation until a later operator (the start-up filter) requires the result

Continuing execution with the debugger, the next break occurs when the Table-valued Function to the right of the filter is initialised:

Another break when the Table-valued Function on the lowest branch of the plan initialises:

And finally, a break from the Stream Aggregate, when it needs to evaluate [Expr1016] (which contains a reference to [Expr1000]):

The last two breaks (lowest table-valued function and stream aggregate) execute a total of 801 times.  The reason for the slow performance of this query is now clear: [Expr1000] is being computed more than 1604 times.  Yes, that means the REPLACE and CONVERT to XML really does run 1604 times on the same value – no wonder performance is so poor!

If you are inclined to test it, the expression service method that performs the REPLACE is sqlTsEs!BhReplaceBhStrStr.  It turns out that the string REPLACE is very much faster than conversion to XML (remember XML is a LOB type and also has complex validation rules) so the dominant performance effect is the conversion to XML.

Beyond the Execution Plan – Test Two

Running test two with the debugger attached reveals that only one call is made to CXMLTypeProvider::ConvertStringToXMLForES:

Reading down the stack trace we see that execution of the plan (as we know it) has not started yet.  The call to convert the string to XML is called from InitForExecute() and SetupQueryScanAndExpression.  The conversion to XML is evaluated once and cached in the execution context (CQueryExecContext::FillExprCache).  Once the iterative part of plan execution begins, the cached result can be retrieved directly without calling ConvertStringToXMLForES() 1604 times.

Test Three – Column Reference

Before you go off adding LEFT(@@DBTS, 0) to all your expressions (!) look what happens when we use a table to hold the input data rather than a variable:

DECLARE

    @ItemID bigint,

    @Item varchar(8000);

DECLARE @Table AS TABLE (Input varchar(8000) NOT NULL);

INSERT @Table (Input)

VALUES (REPLICATE('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z', 32));

SELECT

    @ItemID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), 

    @Item = x.i.value('./text()[1]', 'varchar(8000)')    

FROM @Table AS t

CROSS APPLY

(

    VALUES

        (

        CONVERT

            (xml, 

            '<r>' + 

            REPLACE(t.Input, ',', '</r><r>') + 

            '</r>' +

            LEFT(@@DBTS, 0)

            , 0)

        )

) AS ToXML (result) 

CROSS APPLY ToXML.result.nodes('./r') AS x(i);

Instead of the Constant Scan we saw when using a variable, we now have a table scan and a Compute Scalar that defines the expression:

[Expr1003] = Scalar Operator(
CONVERT(xml,'<r>'+replace(@Table.[Input] as [t].[Input],',','</r><r>')+'</r>'+
substring(CONVERT_IMPLICIT(varchar(8),@@dbts,0),(1),(0)),0))

The other plan details are the same as before; the expression label [Expr1003] is still referenced by the Filter, two Table-valued functions and the Stream Aggregate.  The test three query takes 3758ms to complete.  Debugger analysis shows that CXMLTypeProvider::ConvertStringToXMLForES is again being called directly by the Filter, Table-valued Functions, and Stream Aggregate.

Test Four – CRYPT_GEN_RANDOM

This final test replaces @@DBTS with the CRYPT_GEN_RANDOM function:

SELECT

    @ItemID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), 

    @Item = x.i.value('./text()[1]', 'varchar(8000)')    

FROM @Table AS t

CROSS APPLY

(

    VALUES

        (

        CONVERT

            (xml, 

            '<r>' + 

            REPLACE(t.Input, ',', '</r><r>') + 

            '</r>' +

            LEFT(CRYPT_GEN_RANDOM(1), 0)    -- CHANGED

            , 0)

        )

) AS ToXML (result) 

CROSS APPLY ToXML.result.nodes('./r') AS x(i);

The execution plan shows an extra Compute Scalar next to the Table Scan:

[Expr1018] = Scalar Operator('<r>'+replace(@Table.[Input] as [t].[Input],',','</r><r>')+'</r>')

The Compute Scalar to the left of that is the same one seen previously, though it now references the new expression in its definition:

[Expr1003] = Scalar Operator(
CONVERT(xml,[Expr1018]+
substring(CONVERT_IMPLICIT(varchar(8000),Crypt_Gen_Random((1)),0),(1),(0)),0))

The remainder of the query plan is unaffected; the same operators reference [Expr1003] as before.  As you might have been expecting, this query executes in 8ms again.

Explanation

In test one, there is nothing to stop the query processor deferring execution of the expression, which results in the same expensive computation being performed 1604 times (once each for the filter and first table-valued function, and 801 times each for the second function and the stream aggregate).  As an interesting aside, notice that even with OPTION (RECOMPILE) specified, constant-folding only applies to the REPLACE and string concatenation; constant-folding cannot produce a LOB type (including XML).

In test two, we introduced the non-deterministic function @@DBTS.  This is one of the functions (like RAND and GETDATE) that are implemented to always return the same value per query (despite being non-deterministic, see the links in the Further Reading section below for more details).  These runtime constants are evaluated before the query starts processing rows and the result is cached.  There are some hints (ConstExpr labels) in the execution plan that may indicate a runtime constant but I have not found this to be reliable.

In test three, we changed the game again by replacing the reference to a variable with a column reference from a table.  The value of this column reference could change for each table row so the engine can no longer treat the expression as a runtime constant.  As a consequence, the result is no longer cached and we see the same behaviour (and slow performance) as in test one.

In test four, we replaced the @@DBTS function with the side-effecting function CRYPT_GEN_RANDOM (the other such function is NEWID).  One of the effects of this is to disable the deferred evaluation of the expression defined by the Compute Scalar.  The result is a XML LOB and a second optimization occurs where handles to the same LOB (evaluated by the defining operator) can be shared by other operators that reference the LOB.  This combination of effects means the expensive computation is only performed once in test four, even though the runtime constant caching mechanism is not used.  By the way, there was a bug with CRYPT_GEN_RANDOM which meant it was incorrectly assessed by the optimizer in early versions of SQL Server 2008.  If you encounter this issue when running the scripts above, apply a later service pack (or use the NEWID function for SQL Server 2005).

Final Thoughts

• There is a lot more going on in query execution than we can see in execution plans
• In general, there are no guarantees about the order of execution of expressions, or how many times they will be evaluated
• Please do not start using @@DBTS or CRYPT_GEN_RANDOM for their undocumented effects
• It might be nice if show plan output did indicate if a computation was deferred or cached, but it is not there today
• In many cases we can work around the potential for poor performance caused by repeated evaluation by explicitly materializing the result of the expression using a variable, table, non-inline function…though not always
• Please do not suggest improvements to the XML string splitter unless it handles all input characters and can accept a semicolon as a delimiter ;c)
• I always use SQLCLR for string splitting

Acknowledgements

I would like to particularly thank Usman Butt and Chris Morris from SQL Server Central for their contributions and thoughts which helped me write this entry.

Further Reading

When a Function is indeed a Constant – Andrew Kelly
Runtime Constant Functions – Conor Cunningham
RAND() and other runtime constant functions – Conor again
Scalar Operator Costing – Guess who

© 2012 Paul White
twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com

SQL Server 2005 onward caches temporary tables and table variables referenced in stored procedures for reuse, reducing contention on tempdb allocation structures and catalogue tables.  A number of things can prevent this caching (none of which are allowed when working with table variables):

• Named constraints (bad idea anyway, since concurrent executions can cause a name collision)
• DDL after creation (though what is considered DDL is interesting)
• Creation using dynamic SQL
• Table created in a different scope
• Procedure executed WITH RECOMPILE

Temporary objects are often created and destroyed at a high rate in production systems, so caching temporary objects can be an important optimization.  The temporary object cache is just another SQL Server cache (using the general framework) though it’s entries are a bit more visible than most.  The sys.dm_os_performance_counters DMV exposes a number of counters under the ‘Temporary Tables & Table Variables’ instance of the Plan Cache object.  The cache is also visible through the usual cache DMVs, for example as CACHESTORE_TEMPTABLES in sys.dm_os_memory_cache_counters.

Cached Object Names

The cached objects themselves are visible in tempdb.sys.tables, named with a single # character followed by the 8-character hexadecimal representation of the object id.  This is different from the names of ordinary temporary tables, which have the user-supplied name followed by a bunch of underscores and an id.

The following procedure shows a total of nine cache objects created using CREATE TABLE #xyz syntax, table variables, and SELECT…INTO:

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #T1 (dummy int NULL);

    CREATE TABLE #T2 (dummy int NULL);

    CREATE TABLE #T3 (dummy int NULL);

    DECLARE @T1 AS TABLE (dummy int NULL);

    DECLARE @T2 AS TABLE (dummy int NULL);

    DECLARE @T3 AS TABLE (dummy int NULL);

    SELECT * INTO #T4 FROM #T1;

    SELECT * INTO #T5 FROM @T2;

    SELECT * INTO #T6 FROM #T3;

    WAITFOR DELAY '00:00:01'

END;

GO

DBCC FREEPROCCACHE;

EXECUTE dbo.Demo;

GO

SELECT

    t.* 

FROM tempdb.sys.tables AS t 

WHERE

    t.name LIKE N'#[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]';

The results show nine separate cached objects:

Notice the relationship between object id and the name e.g. –1383692523 = hex AD868715.

Caching is per object not per procedure

If any of the temporary objects in a procedure are not cacheable for any reason, the others may still be cached. So, for example, if we modify the test above to create an index on table #T5, that particular table will not be cached, but the other temporary objects will be:

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #T1 (dummy int NULL);

    CREATE TABLE #T2 (dummy int NULL);

    CREATE TABLE #T3 (dummy int NULL);

    DECLARE @T1 AS TABLE (dummy int NULL);

    DECLARE @T2 AS TABLE (dummy int NULL);

    DECLARE @T3 AS TABLE (dummy int NULL);

    SELECT * INTO #T4 FROM #T1;

    SELECT * INTO #T5 FROM @T2;

    SELECT * INTO #T6 FROM #T3;

    -- Prevents caching of #T5

    CREATE INDEX nc1 ON #T5 (dummy);

    WAITFOR DELAY '00:00:01'

END;

GO

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

EXECUTE dbo.Demo;

There are now only eight cached objects:

Apparently, DROP TABLE is not DDL

Dropping a temporary table in a procedure does not count as DDL, and neither does TRUNCATE TABLE, nor UPDATE STATISTICS.  None of these things prevent temporary table caching (so it does not matter whether you explicitly drop a temporary table at the end of a procedure or not).

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #T1 (dummy int NULL);

    CREATE TABLE #T2 (dummy int NULL);

    CREATE TABLE #T3 (dummy int NULL);

    DECLARE @T1 AS TABLE (dummy int NULL);

    DECLARE @T2 AS TABLE (dummy int NULL);

    DECLARE @T3 AS TABLE (dummy int NULL);

    SELECT * INTO #T4 FROM #T1;

    SELECT * INTO #T5 FROM @T2;

    SELECT * INTO #T6 FROM #T3;

    -- Does not prevent caching

    DROP TABLE #T1, #T4, #T6;

    TRUNCATE TABLE #T2;

    TRUNCATE TABLE #T5;

    UPDATE STATISTICS #T3;

    WAITFOR DELAY '00:00:01'

END;

GO

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

EXECUTE dbo.Demo;

There are nine cached objects again:

Concurrent executions

If a stored procedure is executed concurrently, multiple separate cached objects may be created in tempdb.  There is one cached plan for the procedure but one cached temporary object per execution context derived from that cached plan.  Recall that execution contexts are relatively lightweight instances of a cached plan, populated with execution-specific data such as temporary object ids and parameter values (image reproduced from the plan caching white paper):

The runtime contents of a temporary object (table or variable) are obviously specific to a particular execution, so it makes sense for the cached object to be associated with execution contexts rather than the parent plan.  There may also be more than one cached plan for a procedure in cache (for example due to compilations with different SET options) and each parent plan will have its own collection of execution contexts, so there can be one cached tempdb object per execution context per plan.

There does not appear to be a fixed limit on the number of these cached objects; I was able to quickly create 2,000 of them using the test procedures above and Adam Machanic’s SQL Query Stress tool running 200 threads.  This is the reason for the 1 second delay in the procedure – to make sure the procedure runs for a little while so new execution contexts are generated for each execution rather than reused.  The contents of tempdb after that test were as follows:

Statistics on cached temporary objects

Any auto-stats created are linked to the cached temporary table:

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #T1 (dummy int NULL);

    DECLARE @dummy int;

    -- Trigger auto-stats

    SELECT @dummy = dummy 

    FROM #T1

    WHERE dummy > 0;

    WAITFOR DELAY '00:00:01'

END;

GO

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

EXECUTE dbo.Demo;

GO

SELECT

    t.name,

    t.[object_id],

    s.name,

    s.auto_created

FROM tempdb.sys.tables AS t

JOIN tempdb.sys.stats AS s ON

    s.[object_id] = t.[object_id];

In the case of multiple execution contexts, you might be wondering if each of the tempdb objects can have auto-created statistics associated with them.  The answer is no: auto-stats are used to compile the parent plan, and execution contexts are derived from that same plan as needed.  The metadata looks a little odd though; the statistics are explicitly linked to the object id of the cached temporary object that caused the auto-stats to be created.  Other cached tables for the same plan have different ids, and so do not link to the sys.stats entry.

Statistics created using an explicit CREATE STATISTICS statement are not linked to a cached temporary object, for the simple reason that CREATE STATISTICS is considered DDL, and prevents caching from occurring in the first place.

Drop and Create in Detail

The first time a procedure containing a cacheable temporary object is executed, the temporary object is created as normal, then renamed to the hexadecimal internal form described previously when the object is dropped (explicitly or implicitly at the end of the procedure).  On subsequent executions, the cached object is renamed to the normal user-visible name when ‘created’ in the procedure, and renamed back to the internal form when it is ‘dropped’.  The following script demonstrates the creation and renaming of cached temporary objects:

USE tempdb;

GO

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #Demo (i int);

    SELECT 

        t.name,

        t.object_id,

        t.type_desc,

        t.create_date

    FROM sys.tables AS t

    WHERE

        t.name LIKE N'#Demo%';

    DROP TABLE #Demo;

    SELECT

        t.name,

        t.object_id,

        t.type_desc,

        t.create_date

    FROM sys.tables AS t 

    WHERE

        t.name LIKE N'#________';

END;

GO

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

CHECKPOINT;

EXECUTE dbo.Demo;

GO

SELECT

    fd.[Current LSN],

    fd.Operation,

    fd.AllocUnitName,

    fd.[Transaction Name],

    fd.[Transaction ID],

    CONVERT(sysname, SUBSTRING(fd.[RowLog Contents 0], 3, 256)),

    CONVERT(sysname, SUBSTRING(fd.[RowLog Contents 1], 3, 256))

FROM sys.fn_dblog(NULL, NULL) AS fd;

The first time it is run the first part of the output is:

Notice that the object ids are the same, and the object has familiar external name while in scope, but is renamed after the DROP TABLE statement. The transaction log entries displayed are (click to enlarge):

The highlighted section shows the table being renamed in the internal catalogue tables from the user-visible name to the internal name. On the second run, there is an extra renaming log entry in the CREATE TABLE system transaction, as the object is renamed from the internal form to the user-visible name:

The demonstration shows that CREATE TABLE and DROP TABLE for a cached temporary object are replaced by renaming operations.

Cached Object Scope

The cached object is scoped to the query plan that references it.  If the plan is evicted from cache for any reason (perhaps by ALTER or DROP PROCEDURE or an explicit DBCC FREEPROCCACHE command) a background thread removes the tempdb object. This is not synchronous to the command that causes the eviction; the delay seems to be 5 seconds or less on current SQL Server versions, and is performed by a system process id.  The following code shows the link between the cached temporary table and the cached plans for the stored procedure:

USE tempdb;

GO

IF  OBJECT_ID(N'dbo.Demo', N'P') IS NOT NULL

    DROP PROCEDURE dbo.Demo;

GO

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    CREATE TABLE #Demo (i int);

END;

GO

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

EXECUTE dbo.Demo;

GO

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

GO

SELECT

    decp.cacheobjtype,

    decp.objtype,

    decp.plan_handle,

    dest.[text]

FROM sys.dm_exec_cached_plans AS decp

CROSS APPLY sys.dm_exec_plan_attributes(decp.plan_handle) AS depa

CROSS APPLY sys.dm_exec_sql_text(decp.plan_handle) AS dest

WHERE

    decp.cacheobjtype = N'Compiled Plan'

    AND decp.objtype = N'Proc'

    AND depa.attribute = N'objectid'

    AND CONVERT(integer, depa.value) = OBJECT_ID(N'dbo.Demo', N'P');

Example output:

Aside from checking for suitably-named objects in tempdb, there are a number of ways to see how many cached temporary objects (tables and variables) exist, and how many are in use by executing code.  One way is to query the sys.dm_os_memory_cache_counters DMV:

SELECT

    domcc.name,

    domcc.[type],

    domcc.entries_count,

    domcc.entries_in_use_count

FROM sys.dm_os_memory_cache_counters AS domcc

WHERE domcc.[type] = N'CACHESTORE_TEMPTABLES';

Another way is to check the performance counters (also accessible via DMV):

SELECT

    dopc.[object_name], 

    dopc.counter_name, 

    dopc.cntr_value

FROM sys.dm_os_performance_counters AS dopc

WHERE

    dopc.[object_name] LIKE N'MSSQL%Plan Cache%'

    AND dopc.instance_name = N'Temporary Tables & Table Variables'

    AND dopc.counter_name IN (N'Cache Object Counts', N'Cache Objects in use');

This second example shows 200 cached objects on a different run:

On SQL Server 2008 and later, we can evict a particular plan handle from cache to show that this removes the cached temporary table:

DBCC FREEPROCCACHE(0x05000200CC7BDE0940E16D8C000000000000000000000000);

As mentioned, there can be a delay of up to 5 seconds before the cached object is removed after the DBCC statement completes (though the DMVs reflect the cache changes immediately).  The more comprehensive test below shows all these things combined:

-- Cache a temporary object

EXECUTE dbo.Demo;

GO

-- Show the cached table

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

DECLARE @plan_handle varbinary(64);

-- Find the plan handle

SELECT

    @plan_handle = decp.plan_handle

FROM sys.dm_exec_cached_plans AS decp

CROSS APPLY sys.dm_exec_plan_attributes(decp.plan_handle) AS depa

CROSS APPLY sys.dm_exec_sql_text(decp.plan_handle) AS dest

WHERE

    decp.cacheobjtype = N'Compiled Plan'

    AND decp.objtype = N'Proc'

    AND depa.attribute = N'objectid'

    AND CONVERT(integer, depa.value) = OBJECT_ID(N'dbo.Demo', N'P');

-- Truncate the log

CHECKPOINT;

-- Evict the plan

DBCC FREEPROCCACHE(@plan_handle);

-- Show log entries

SELECT

    fd.[Current LSN],

    fd.SPID,

    fd.Operation,

    fd.Context,

    fd.AllocUnitName,

    fd.[Transaction Name],

    fd.[Transaction ID],

    fd.[Begin Time],

    fd.[End Time]

FROM sys.fn_dblog(NULL,NULL) AS fd;

-- Cached object not dropped yet

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

WAITFOR DELAY '00:00:05';

-- Show cleanup

SELECT

    fd.[Current LSN],

    fd.SPID,

    fd.Operation,

    fd.Context,

    fd.AllocUnitName,

    fd.[Transaction Name],

    fd.[Transaction ID],

    fd.[Begin Time],

    fd.[End Time]

FROM sys.fn_dblog(NULL,NULL) AS fd;

-- Gone!

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

The first result set shows the cached temporary object:

The transaction log entries immediately after evicting the plan from cache show no activity aside from the CHECKPOINT we issued to truncate the log:

Then we see that the cached object still exists at this point (though the DMVs now show zero cached temporary objects):

After an up-to-five-second delay, the transaction log contains:

Notice the system transaction named ‘droptemp’ is performed by system SPID 14, and instead of the renaming we saw earlier, all references to the cached object are deleted from the system tables.

More about Table Variables

You might recognise the internal hexadecimal name for cached temporary objects; the same is used for table variables outside a stored procedure:

DECLARE @T AS TABLE (dummy int NULL);

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

GO 5

The batch runs five times and produces output like this:

Notice that the object id is different each time (and so, therefore, is the name).  As already mentioned, table variables in a stored procedure can be cached just like temporary tables:

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    DECLARE @T AS TABLE (dummy int NULL);

    SELECT

        t.name,

        t.[object_id],

        t.type_desc,

        t.create_date

    FROM tempdb.sys.tables AS t

    WHERE

        t.name LIKE N'#________';

END

GO

EXECUTE dbo.Demo;

GO 5

Now, though, we see the same object id and create date each time:

Once a table variable is cached, the transaction log records for a simple procedure are quite interesting:

DBCC FREEPROCCACHE;

WAITFOR DELAY '00:00:05';

GO

CREATE PROCEDURE dbo.Demo

AS

BEGIN

    DECLARE @T AS TABLE (dummy int NULL);

    INSERT @T VALUES (1);

END

GO

-- Cache the table variable

EXECUTE dbo.Demo;

GO

SELECT

    t.name,

    t.[object_id],

    t.type_desc,

    t.create_date

FROM tempdb.sys.tables AS t

WHERE

    t.name LIKE N'#________';

GO

CHECKPOINT;

GO

EXECUTE dbo.Demo;

GO

SELECT

    fd.[Current LSN],

    fd.Operation,

    fd.AllocUnitName,

    fd.[Transaction Name],

    fd.[Transaction ID]

FROM sys.fn_dblog(NULL, NULL) AS fd;

Notice the reference to the internal name #628FA481 and the clean up activity.  The same procedure with a temporary table instead of a table variable generates a bit more work for the server:

Many of the entries are similar to the table variable case, with extra steps to rename the cached object when CREATE TABLE and the implicit DROP TABLE at the end of the procedure are executed.  Clearly, some efforts have been made to make table variables more efficient than temporary tables, while sharing many features in common at quite a low level.

Another interesting thing, as I mentioned right at the start of this post, is that table variables disallow just about all of the actions that prevent caching of a temporary table.  Table variables do not allow named constraints or DDL that affects caching (e.g. CREATE INDEX, CREATE STATISTICS).  Table variables are also scoped more tightly than temporary tables.  While we can create a temporary table in one procedure, and refer to it in  another, the same thing cannot be done with table variables.  For the same scoping reasons, table variables cannot be defined using dynamic SQL and referenced outside that context.  One oddity is TRUNCATE TABLE; disallowed by table variables, but which does not affect caching.

Anyway, the restrictions mean that table variables can always be cached, and don’t allow some of the crazy things that are possible with temporary tables (particularly as regards scoping, but also the cached statistics issue I described in my last post).  They also have the potential to perform better (no hidden renaming) at least in some high-volume circumstances.  If only we were able to create statistics (with intuitive behaviour!) and indexes after creation, table variables might well make the old Sybase ‘non-shareable temporary tables’ finally redundant.  Until then, we are left having to choose one or the other as best we can.

© 2012 Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com