Search results matching tag 'query plans'

Execution Plan Analysis: The Mystery Work Table

Paul White — Thu, 07 Mar 2013 19:42:04 GMT

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 :)

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

Halloween Protection – The Complete Series

Paul White — Wed, 20 Feb 2013 23:29:42 GMT

I have just published a four-part series for SQLPerformance.com on the Halloween Problem. Some of you will never have heard of this issue, and those that have might associate it only with T-SQL UPDATE queries. In fact, the Halloween problem affects execution plans for INSERT, UPDATE, DELETE and MERGE statements.

This is a topic I have been meaning to write about properly for years, ever since I read Craig Freedman’s 2008 blog post on the topic, which ended with the cryptic comment:

“…although I've used update statements for all of the examples in this post, some insert and delete statements also require Halloween protection, but I'll save that topic for a future post.”

That future post never materialized, sadly, so I thought I would have a go. The four parts of the series are summarized and linked below, I hope you find the material interesting.

Part 1 – The Halloween Problem and UPDATE statements

The SQL standard and three-phase separation
Logical update processing
Pipelined execution
The Halloween problem
Avoiding the problem in UPDATE statements

Part 2 – The Halloween Problem in INSERT and DELETE queries

INSERT examples
DELETE examples
Constraint checking and phase separation

Part 3 – Halloween Problem optimizations for MERGE

MERGE contains several optimizations the other DML statements do not
Hole-filling with merge join
Hole-filling with nested loops
Avoiding an extra B-tree navigation
Avoiding the join

Part 4 – The Halloween Problem and the Query Optimizer

Early optimization approaches
The SQL Server optimizer approach
The case of the redundant sort
HP levels and properties
Plan changes for Halloween Protection
Non-spool options
Row versioning
Heaps and forwarded records
T-SQL functions

As always, I appreciate your comments and feedback.

Paul White
@SQL_Kiwi
SQLkiwi@gmail.com

Geek City: Join With Me!

Kalen Delaney — Thu, 14 Feb 2013 22:16:00 GMT

I remember one of the most surprising changes in SQL Server ~~2000~~ 2005 was how the graphical plans showed the use of a nonclustered index to seek, and the plan included something that looked like a JOIN to find rows in the base table. Here’s an example. Although I used SQL Server 2008R2, the graphical plan will be pretty similar to what it looked like back in SQL Server ~~2000~~ 2005. My code will make a copy of a table in the AdventureWorks2008 database, and then build an index on one of the columns.

USE AdventureWorks2008;
GO
IF object_id('dbo.Sales') IS NOT NULL
DROP TABLE dbo.Sales;
GO
SELECT * INTO dbo.Sales FROM Sales.SalesOrderHeader;
GO
CREATE INDEX Sales_SalesPersonID_index on dbo.Sales(SalesPersonID);
GO

Now look at the estimated graphical execution plan for this query, that searches for a particular value for the SalesPersonID column:

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 280;
GO

You should see something like this:

It shows a JOIN even though there is only one table involved! What’s with that? It took me a few minutes to figure out what I was seeing, and I must admit that over the years since then I have come to appreciate this graphical representation. You’ll have a problem if you think of a JOIN as only finding matching rows between two tables, but can be solved if you realize that a JOIN can be used when finding matches between any two ROWSETS, i.e. any two sets of rows. There is a set of rows in the nonclustered index on SalesPersonID, and a set of rows in the table. The index seek finds all the index rows with a SalesPersonID value of 280, but those index rows only contain an index key value and a row pointer (RowID or RID). Because the query is requesting all the columns in the table, not just the SalesPersonID value, SQL Server must find the rows in the dbo.Sales table that have a matching value for the RowID. Internally, it is doing a join, even though there is only one table. It is joining index rows with table rows.

If the table had a clustered index, the plan would look almost exactly the same, with one difference. In SQL Server, if a table has a clustered index, nonclustered index rows do not contain RowIDs, they contain the clustered key value to be used a pointer to the row. SQL Server can take this clustered key from the nonclustered index row and look up in the clustered index to find the desired row. So I create a clustered index on SalesOrderNumber:

CREATE UNIQUE CLUSTERED INDEX Sales_ident on dbo.Sales(SalesOrderNumber);
GO

Now when I run the same query as above, I get the following plan:

The only difference in the two plans above is the icon for the lookup into the base table. One is looking up into a heap using a RowID, which is an address containing the File ID, the page number and the slot or row number on the page. The other icon represents taking a key value from the nonclustered index row and looking it up by seeking through the clustered index. If you look again at these two icons, which one looks like a picture of directly addressing a row, and which looks like a picture of following another index into the table itself?

The icon on the left is used for a RID lookup, and the icon on the right is used for a clustered index key lookup. I know that nobody asked me, but I think they got these backwards.

But wait, there’s more…

Prior to SQL Server 7, there was basically a rule of thumb with query plans that SQL Server would use one index (at most) per table per query. It could never (well, hardly ever) use two indexes on the same table in a single query. That changed in SQL Server 7 when a new algorithm called Index Intersection was introduced.

I’m going to build another index on SalesOrderDate:

CREATE INDEX Sales_OrderDate_index on dbo.Sales(OrderDate);
GO

This index will be used if I look for all orders place on July 1, 2002. The query plan for the following query is shown:

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01';

We saw that the index on SalesPersonID is useful when looking for the value 280, and the index on SalesOrderDate is useful when looking for '2002-07-01'. But what if one query looks for rows that satisfy both conditions?

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01'
AND SalesPersonID = 280

Here’s the plan:

We see two JOINs ! First, SQL Server finds the sets of index rows meeting each of the WHERE filter conditions and those two index row sets are joined together, using the clustered key value as the join column. Then only after SQL Server finds rows that meets both conditions, it takes the common clustered index key and uses it to find the row in the underlying table.

But wait, there’s more!

Both of these queries use a table scan, because the filter conditions are not selective enough. There are way more rows with a SalesPersonID value of 289 than there were for a value of 280, and there are more rows with an OrderDate of March 1, 2004 than there are with an OrderDate of July 1, 2002.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01' ;
GO

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 289;
GO

Both of the above queries show the same plan. Because the table now has a clustered index, the plan shows a clustered index scan, but it is exactly the same work as a table scan:

However, if you look at the plan for a query that uses both filter conditions, we don’t get a clustered index scan.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01'
AND SalesPersonID = 289;

Even though each filter alone is not very restrictive, they can both be used for index intersection. The reason SQL Server usually doesn’t choose index seeks on non-restrictive filters is because the cost of then accessing the base table for all the qualifying rows can be very high. But even though each individual index returns a lot of rows, the optimizer’s estimate of the number of rows that meet BOTH conditions is very small, and therefore the number of lookups into the base table is quite small and affordable.

So, what can you learn? Just because you think an column might not be selective enough to build a nonclustered index on, don’t discount it. If that column will frequently be used in queries with multiple conditions, it just might turn out to be more useful than you thought!

So make sure you test many possible choices of indexes and combinations of indexes before you know what the best choices are.

Have fun!

~Kalen

MERGE Bug with Filtered Indexes

Paul White — Sun, 09 Dec 2012 17:54:00 GMT

A MERGE statement can fail, and incorrectly report a unique key violation when:

The target table uses a unique filtered index; and
No key column of the filtered index is updated; and
A column from the filtering condition is updated; and
Transient key violations are possible

Example Tables

Say we have two tables, one that is the target of a MERGE statement, and another that contains updates to be applied to the target. The target table contains three columns, an integer primary key, a single character alternate key, and a status code column. A filtered unique index exists on the alternate key, but is only enforced where the status code is ‘a’:

     CREATE TABLE #Target 

    (

        pk          integer NOT NULL, 

        ak          character(1) NOT NULL,

        status_code character(1) NOT NULL,

        PRIMARY KEY (pk)

    );

    CREATE UNIQUE INDEX uq1

    ON #Target (ak)

    INCLUDE (status_code)

    WHERE status_code = 'a';

The changes table contains just an integer primary key (to identify the target row to change) and the new status code:

    CREATE TABLE #Changes

    (

        pk          integer NOT NULL,

        status_code character(1) NOT NULL,

        PRIMARY KEY (pk)

    );

Sample Data

The sample data for the example is:

    INSERT #Target 

        (pk, ak, status_code)

    VALUES 

        (1, 'A', 'a'),

        (2, 'B', 'a'),

        (3, 'C', 'a'),

        (4, 'A', 'd');

    INSERT #Changes

        (pk, status_code)

    VALUES

        (1, 'd'),

        (4, 'a');

         Target                     Changes
╔════╦════╦═════════════╗    ╔════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣
║ 1 ║ A ║ a           ║    ║ 1 ║ d           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ a           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝
║ 4 ║ A ║ d           ║
╚════╩════╩═════════════╝

The target table’s alternate key (ak) column is unique, for rows where status_code = ‘a’. Applying the changes to the target will change row 1 from status ‘a’ to status ‘d’, and row 4 from status ‘d’ to status ‘a’. The result of applying all the changes will still satisfy the filtered unique index, because the ‘A’ in row 1 will be deleted from the index and the ‘A’ in row 4 will be added.

Merge Test One

Let’s now execute a MERGE statement to apply the changes:

    MERGE #Target AS t

    USING #Changes AS c ON 

        c.pk = t.pk

    WHEN MATCHED 

        AND c.status_code <> t.status_code 

        THEN UPDATE SET status_code = c.status_code;

The MERGE changes the two target rows as expected. The updated target table now contains:

╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣
║ 1 ║ A ║ d           ║ <—changed from ‘a’
║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║
║ 4 ║ A ║ a           ║ <—changed from ‘d’
╚════╩════╩═════════════╝

Merge Test Two

Now let’s repopulate the changes table to reverse the updates we just performed:

    TRUNCATE TABLE #Changes;

    INSERT #Changes

        (pk, status_code)

    VALUES

        (1, 'a'),

        (4, 'd');

This will change row 1 back to status ‘a’ and row 4 back to status ‘d’. As a reminder, the current state of the tables is:

         Target                        Changes
╔════╦════╦═════════════╗    ╔════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣
║ 1 ║ A ║ d           ║    ║ 1 ║ a           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ d           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝
║ 4 ║ A ║ a           ║
╚════╩════╩═════════════╝

We execute the same MERGE statement:

    MERGE #Target AS t

    USING #Changes AS c ON 

        c.pk = t.pk

    WHEN MATCHED 

        AND c.status_code <> t.status_code 

        THEN UPDATE SET status_code = c.status_code;

However this time we receive the following message:

Msg 2601, Level 14, State 1, Line 1
Cannot insert duplicate key row in object 'dbo.#Target' with unique index 'uq1'. The duplicate key value is (A).
The statement has been terminated.

Applying the changes using UPDATE

Let’s now rewrite the MERGE to use UPDATE instead:

    UPDATE t

    SET status_code = c.status_code

    FROM #Target AS t

    JOIN #Changes AS c ON

        t.pk = c.pk

    WHERE

        c.status_code <> t.status_code;

This query succeeds where the MERGE failed. The two rows are updated as expected:

╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣
║ 1 ║ A ║ a           ║ <—changed back to ‘a’
║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║
║ 4 ║ A ║ d           ║ <—changed back to ‘d’
╚════╩════╩═════════════╝

What went wrong with the MERGE?

In this test, the MERGE query execution happens to apply the changes in the order of the ‘pk’ column.

In test one, this was not a problem: row 1 is removed from the unique filtered index by changing status_code from ‘a’ to ‘d’ before row 4 is added. At no point does the table contain two rows where ak = ‘A’ and status_code = ‘a’.

In test two, however, the first change was to change row 1 from status ‘d’ to status ‘a’. This change means there would be two rows in the filtered unique index where ak = ‘A’ (both row 1 and row 4 meet the index filtering criteria ‘status_code = a’).

The storage engine does not allow the query processor to violate a unique key (unless IGNORE_DUP_KEY is ON, but that is a different story, and doesn’t apply to MERGE in any case). This strict rule applies regardless of the fact that if all changes were applied, there would be no unique key violation (row 4 would eventually be changed from ‘a’ to ‘d’, removing it from the filtered unique index, and resolving the key violation).

Why it went wrong

The query optimizer usually detects when this sort of temporary uniqueness violation could occur, and builds a plan that avoids the issue. I wrote about this a couple of years ago in my post Beware Sneaky Reads with Unique Indexes (you can read more about the details on pages 495-497 of Microsoft SQL Server 2008 Internals or in Craig Freedman’s blog post on maintaining unique indexes). To summarize though, the optimizer introduces Split, Filter, Sort, and Collapse operators into the query plan to:

Split each row update into delete followed by an inserts
Filter out rows that would not change the index (due to the filter on the index, or a non-updating update)
Sort the resulting stream by index key, with deletes before inserts
Collapse delete/insert pairs on the same index key back into an update

The effect of all this is that only net changes are applied to an index (as one or more insert, update, and/or delete operations). In this case, the net effect is a single update of the filtered unique index: changing the row for ak = ‘A’ from pk = 4 to pk = 1. In case that is less than 100% clear, let’s look at the operation in test two again:

         Target                     Changes                   Result
╔════╦════╦═════════════╗    ╔════╦═════════════╗    ╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║    ║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣    ╠════╬════╬═════════════╣
║ 1 ║ A ║ d           ║    ║ 1 ║ d           ║    ║ 1 ║ A ║ a           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ a           ║    ║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝    ║ 3 ║ C ║ a           ║
║ 4 ║ A ║ a           ║                            ║ 4 ║ A ║ d           ║
╚════╩════╩═════════════╝                            ╚════╩════╩═════════════╝

From the filtered index’s point of view (filtered for status_code = ‘a’ and shown in nonclustered index key order) the overall effect of the query is:

Before           After
╔════╦════╗    ╔════╦════╗
║ pk ║ ak ║    ║ pk ║ ak ║
╠════╬════╣    ╠════╬════╣
║ 4 ║ A ║    ║ 1 ║ A ║
║ 2 ║ B ║    ║ 2 ║ B ║
║ 3 ║ C ║    ║ 3 ║ C ║
╚════╩════╝    ╚════╩════╝

The single net change there is a change of pk from 4 to 1 for the nonclustered index entry ak = ‘A’. This is the magic performed by the split, sort, and collapse. Notice in particular how the original changes to the index key (on the ‘ak’ column) have been transformed into an update of a non-key column (pk is included in the nonclustered index). By not updating any nonclustered index keys, we are guaranteed to avoid transient key violations.

The Execution Plans

The estimated MERGE execution plan that produces the incorrect key-violation error looks like this (click to enlarge in a new window):

The successful UPDATE execution plan is (click to enlarge in a new window):

The MERGE execution plan is a narrow (per-row) update. The single Clustered Index Merge operator maintains both the clustered index and the filtered nonclustered index. The UPDATE plan is a wide (per-index) update. The clustered index is maintained first, then the Split, Filter, Sort, Collapse sequence is applied before the nonclustered index is separately maintained.

There is always a wide update plan for any query that modifies the database. The narrow form is a performance optimization where the number of rows is expected to be relatively small, and is not available for all operations. One of the operations that should disallow a narrow plan is maintaining a unique index where intermediate key violations could occur.

Workarounds

The MERGE can be made to work (producing a wide update plan with split, sort, and collapse) by:

Adding all columns referenced in the filtered index’s WHERE clause to the index key (INCLUDE is not sufficient); or
Executing the query with trace flag 8790 set e.g. OPTION (QUERYTRACEON 8790).

Undocumented trace flag 8790 forces a wide update plan for any data-changing query (remember that a wide update plan is always possible). Either change will produce a successfully-executing wide update plan for the MERGE that failed previously.

Conclusion

The optimizer fails to spot the possibility of transient unique key violations with MERGE under the conditions listed at the start of this post. It incorrectly chooses a narrow plan for the MERGE, which cannot provide the protection of a split/sort/collapse sequence for the nonclustered index maintenance.

The MERGE plan may fail at execution time depending on the order in which rows are processed, and the distribution of data in the database. Worse, a previously solid MERGE query may suddenly start to fail unpredictably if a filtered unique index is added to the merge target table at any point.

Connect bug filed here

Bug reproduced on the following SQL Server versions (all x64 Developer Edition):

2012 SP1 CUI (build 11.0.3321 – November 2012)
2008 R2 SP2 CU3 (build 10.50.4266 – October 2012)
2008 SP3 CU8 (build 10.0.5828 – November 2012)

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Cardinality Estimation Bug with Lookups

Paul White — Mon, 15 Oct 2012 06:25:05 GMT

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.

Why Doesn’t Partition Elimination Work?

Paul White — Tue, 11 Sep 2012 20:52:00 GMT

Given a partitioned table and a simple SELECT query that compares the partitioning column to a single literal value, why does SQL Server read all the partitions when it seems obvious that only one partition needs to be examined?

Sample Data

The following script creates a table, partitioned on the char(3) column ‘Div’, and populates it with 100,000 rows of data:

     USE Sandpit;

    GO

    CREATE PARTITION FUNCTION PF (char(3))

    AS RANGE RIGHT FOR VALUES

    (

        '1', '2', '3', '4', '5', '6', '7', '8', '9',

        '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'

    );

    GO

    CREATE PARTITION SCHEME PS

    AS PARTITION PF

    ALL TO ([PRIMARY]);

    GO

    CREATE TABLE dbo.Test

    (

        Div     char(3) NOT NULL,

        Data    char(50) NOT NULL,

    )

    ON PS(Div);

    GO

    INSERT dbo.Test WITH (TABLOCKX)

        (Div, Data)

    SELECT TOP (100000)

        CONVERT(char(3), CONVERT(char(36), NEWID())),

        CONVERT(char(50), REPLICATE('X', 50))

    FROM sys.columns AS c

    CROSS JOIN sys.columns AS c2

    CROSS JOIN sys.columns AS c3;

Sample data:

The ‘Div’ column is pseudo-random so your results will be slightly different, but this is the distribution across partitions I saw:

    SELECT

        PartitionID = F.PartitionID,

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t WITH (TABLOCK)

    CROSS APPLY (VALUES($PARTITION.PF(t.Div))) AS F (PartitionID)

    GROUP BY

        F.PartitionID

    ORDER BY

        F.PartitionID;

(The partition function defines a total of 36 partitions but only 16 are used by the sample data.)

The Test Query

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF';

Since ‘Div’ is the partitioning column, the expectation is that only one partition will be scanned to count the rows that match the WHERE clause predicate. However, the execution plan shows that query execution scans all 36 partitions (a full table scan):

Why did SQL Server not just look at the one partition it knows the value ‘ABF’ must lie in?

Here’s Why:

The answer lies in the predicate:

The value ‘ABF’ is nowhere to be seen; it has been replaced by [@1]. This means the query has been considered for simple parameterization by SQL Server to promote query plan reuse. The presence of the [@1] does not mean that simple parameterization was successful (considered safe for all possible values by the optimizer). We have to check the plan cache to see if an associated prepared plan exists and is reused for different ‘parameter’ values. It turns out that this time the simple parameterization attempt is considered safe, so a prepared plan is created and is reused for different values. The full parameterized text is:

(@1 varchar(8000))SELECT COUNT_BIG(*) [RowCnt] FROM [dbo].[Test] [t] WHERE [t].[Div]=@1

Static Partition Elimination

The reason SQL Server cannot apply static partition elimination (determining the partition number at compile time) is that the plan now contains a parameter. Subsequent executions that reuse the plan might specify a different value for the parameter, so static elimination would not be safe. It is not possible to disable simple parameterization, but we can prevent it applying to this query in a number of ways. One way is to incorporate an inequality predicate of the form expression <> constant:

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

        AND 1 <> 2;

The redundant 1 <> 2 predicate is completely removed by the optimizer, and the query still qualifies for TRIVIAL optimization as it did previously:

There are a number of interesting things to notice here:

The query is no longer parameterized (the literal value ‘ABF’ appears)
Only one partition is touched (partition 11)
This unindexed heap table has a seek predicate
The ‘ordered’ property has changed from False to True

The problem with this plan is that it cannot be reused for different predicate values – so you could end up with a separate cached plan for each possible literal value.

Adding OPTION (RECOMPILE) also defeats simple parameterization and therefore achieves static elimination. In an ad-hoc SQL batch, OPTION (RECOMPILE) also means the query plan will not be cached (stored procedures are not so lucky). The downside is a fresh trip through the optimizer on each call. This query does qualify for trivial plan, so optimization time is minimal, but more complex queries with the same desire for partition elimination might well require full optimization.

Dynamic Partition Elimination

Ideally, we would like a query plan that is reusable but still only touches one partition for any given string literal value. What we need is dynamic partition elimination. In case the concept is new to you, the optimizer can produce plans that determine the correct partition at execution time (rather than at compile-time, as for static elimination). To achieve this, the optimizer builds a plan that uses an internal function called RangePartitionNew(). One might think the original simple-parameterized plan ought to have included this feature; the reason it didn’t is quite interesting.

When SQL Server parameterizes a query using simple or forced parameterization, it has to decide on a data type for the parameter. For string literals, it always chooses varchar(8000) for non-Unicode strings and nvarchar(4000) for Unicode strings. If it chose a specific type like varchar(3), we could end up with the same plan cache bloating and non-reuse problem as for the non-parameterized case – and there are potentially 8000 different lengths for varchar. Also, prior to SQL Server 2005 SP2, the parameter-declaration part of the query text was not included in the hash value used to decide in which cache bucket to store the plan. This could result in hundreds of same-text plans (with different parameters) occupying the same hash bucket (this does not work well).

Anyway, faced with the parameterized predicate Div = [@1], where Div is char(3) and [@1] is varchar(8000), dynamic partition elimination does not occur because the value of [@1] might be truncated. One way to address this is to explicitly convert the to-be-parameterized string literal to the same type as the target column (char(3)):

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(3), 'CDC');

Now we have a parameterized query plan that uses dynamic partition elimination:

This plan has all the interesting features of the static elimination plan, but the heap seek no longer selects a hard-coded partition ID. The single partition searched is the one returned at runtime by the call to RangePartitionNew(). The explicit convert prevents data truncation when the parameterized value is compared with the partition boundary values (defined as char(3) in the partition function). The extra CONVERT_IMPLICIT to char(3) is required for internal reasons, and only appears with non-Unicode partition function types.

If we explicitly convert to char(4) instead of char(3), the possibility of truncation arises again and we are back to scanning all 36 partitions:

Using varchar(3) instead of char(3) also results in dynamic elimination, which surprises some people:

Implicit Conversions and Precedence

An alternative explanation I have seen for the original behaviour is that the string literal ‘ABF’ is implicitly typed as a varchar(3) by SQL Server and data type precedence means the char(3) ‘Div’ column has to be implicitly converted to varchar(3) to perform the comparison. This is incorrect, but it is interesting to look at why that is so:

Literal Types

We can see the implicit type of the string literal ‘ABF’ using a query:

    SELECT

        BaseType = SQL_VARIANT_PROPERTY(V.v, 'BaseType'),

        MaxLength = SQL_VARIANT_PROPERTY(V.v, 'MaxLength')

    FROM (VALUES(CONVERT(sql_variant, 'ABF'))) AS V (v);

The implied type of ‘ABF’ does seem to be varchar(3), so that checks out.

Type Precedence

The data type precedence table in Books Online shows that varchar does indeed have a higher precedence than char:

Also, from the Books Online topic Data Types (Transact-SQL):

The example below uses a UNION ALL over char(5) and varchar(3) columns:

    DECLARE @T1 AS TABLE (col1 char(5) NOT NULL);

    DECLARE @T2 AS TABLE (col1 varchar(3) NOT NULL);

    INSERT @T1 VALUES ('12345');

    INSERT @T2 VALUES ('123');

    SELECT

        BaseType = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'BaseType'),

        MaxLength = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'MaxLength'),

        t.col1

    FROM

    (

        SELECT col1 FROM  @T1 

        UNION ALL

        SELECT col1 FROM @T2

    ) AS t;

The result column ‘col1’ has to have a well-defined type. As expected, the result is varchar(5) since varchar has a higher precedence than char and 5 is the maximum length of the result. All good so far.

Strings Are Special

We get used to seeing (and preferably avoiding) implicit conversions in query plans where two mismatched types are compared:

    DECLARE @T1 AS TABLE (col1 integer NULL);

    DECLARE @v tinyint;

    SELECT col1 FROM @T1 AS t WHERE col1 = @v;

The plan shows the tinyint variable being implicitly converted to the higher-precedence integer data type, as expected. Now let’s do the same thing with varchar and char (perhaps expecting char to be converted to the higher-precedence varchar):

    DECLARE @T1 AS TABLE (col1 varchar(5) NULL);

    DECLARE @v char(3);

    SELECT col1 FROM @T1 AS t WHERE col1 = @v;

Note the lack of an implicit conversion in the predicate.

Important

SQL Server can compare char with varchar without performing a conversion. They are fundamentally the same type, it’s just that one is fixed-length and the other is variable-length. The SQL standard requires padding for the character strings used in comparisons so that their lengths match before comparing, thereby removing the only distinction between char and varchar. The same optimization can apply to a comparison between nchar and nvarchar (though not to Unicode versus non-Unicode comparisons, since they are genuinely different types of course).

The present case involves a predicate “WHERE Div = ‘ABF’”. This is a comparison that can use this optimization, so there is no implicit conversion. This is the reason the explicit conversion to varchar(3) works in the main example – the precedence rules do not need to be invoked, and the data column is not converted from char(3) to varchar(3).

Why Use a Partitioned Heap?

In case you were wondering, the only reason I chose a partitioned heap for this post is just because I could (it’s more interesting in many ways). All the demonstrations work just as well for a partitioned clustered table. A complete script using a clustered partitioned table is below:

    USE Sandpit;

    GO

    CREATE PARTITION FUNCTION PF (char(3))

    AS RANGE RIGHT FOR VALUES

    (

        '1', '2', '3', '4', '5', '6', '7', '8', '9',

        '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'

    );

    GO

    CREATE PARTITION SCHEME PS

    AS PARTITION PF

    ALL TO ([PRIMARY]);

    GO

    CREATE TABLE dbo.Test

    (

        ID      integer IDENTITY NOT NULL,

        Div     char(3) NOT NULL,

        Data    char(50) NOT NULL,

        CONSTRAINT PK__dbo_Test_Div_ID

        PRIMARY KEY CLUSTERED (Div, ID)

        ON PS(Div)

    );

    GO

    INSERT dbo.Test WITH (TABLOCKX)

        (Div, Data)

    SELECT TOP (100000)

        CONVERT(char(3), CONVERT(char(36), NEWID())),

        CONVERT(char(50), REPLICATE('X', 50))

    FROM sys.columns AS c

    CROSS JOIN sys.columns AS c2

    CROSS JOIN sys.columns AS c3;

    GO

    -- Show the distribution of data

    SELECT

        PartitionID = F.PartitionID,

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t WITH (TABLOCK)

    CROSS APPLY (VALUES($PARTITION.PF(t.Div))) AS F (PartitionID)

    GROUP BY

        F.PartitionID

    ORDER BY

        F.PartitionID;

    GO

    -- Seek on all 36 partitions

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF';

    GO

    -- Static elimination = 1 hard-coded partition ID

    -- Cached plan unlikely to be reused

    SELECT

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

        AND 1 <> 2;

    GO

    -- Static elimination

    -- Compilation overhead

    SELECT

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

    OPTION (RECOMPILE);

    GO

    -- Dynamic elimination with convert to char(3)

    -- Reusable plan

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(3), 'ABF');

    GO

    -- Dynamic elimination with convert to varchar(3)

    -- Data type precedence not applied:

    -- varchar(3) convert does not cause the char(3)

    -- column Div to be converted (would prevent a seek)

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(varchar(3), 'ABF');

    GO

    -- char(4) means truncation could occur when

    -- comparing with the char(3) partition function

    -- No partition elimination, seek on 36 partitions

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(4), 'ABF');

    GO

    -- Clean up

    DROP TABLE dbo.Test;

    DROP PARTITION SCHEME PS;

    DROP PARTITION FUNCTION PF;

This post applies to SQL Server 2008, 2008 R2 and 2012 only (partitioned table query execution was very different in 2005). As far as I can tell, SQL Server 2005 did not attempt simple parameterization on a partitioned table. I’m in two minds whether the SQL Server 2008+ behaviour is a bug, an oversight, or an undesirable consequence of fixing something else…so I opened a Connect item for it. Update: fixing this is under consideration for the next release.

Sean Broadley raises an important practical point in the comments below – the issue highlighted in this post only occurs when a literal value is used. By correctly parameterizing your queries (including application code and dynamic SQL) you will avoid simple parameterization, achieve dynamic partition elimination, and cache a more reusable query plan.

Acknowledgement

Thanks to Jonathan Kehayias (blog | twitter) who first altered me to the MSDN forum question that prompted this post.

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

Compute Scalars, Expressions and Execution Plan Performance

Paul White — Tue, 04 Sep 2012 22:22:00 GMT

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):

There is nothing very interesting below CQueryScan::GetRow (it is just start-up code)
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
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).
The nested loops join operator asks the Sequence Project operator for a row (CQScanSeqProjectNew::GetRow)
The sequence project operator asks the Segment operator for a row (CQScanSegmentNew::GetRow)
The segment operator asks the second Nested Loops Join for a row (CQScanNLJoinTrivialNew::GetRow)
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
The start-up Filter operator is executing its Open() method (CQScanStartupFilterNew::Open)
The start-up Filter calls into the general entry point for the Expression Service to evaluate expression [Expr1000] defined by the Constant Scan
CEsExec::GeneralEval4 calls an ES method to convert a string to XML (ConvertFromStringTypesAndXmlToXml)
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.

Temporary Tables in Stored Procedures

Paul White — Tue, 14 Aug 2012 15:22:00 GMT

Ask anyone what the primary advantage of temporary tables over table variables is, and the chances are they will say that temporary tables support statistics and table variables do not. This is true, of course; even the indexes that enforce PRIMARY KEY and UNIQUE constraints on table variables do not have populated statistics associated with them, and it is not possible to manually create statistics or non-constraint indexes on table variables. Intuitively, then, any query that has alternative execution plans to choose from ought to benefit from using a temporary table rather than a table variable. This is also true, up to a point.

The most common use of temporary tables is in stored procedures, where they can be very useful as a way of simplifying a large query into smaller parts, giving the optimizer a better chance of finding good execution plans, providing statistical information about an intermediate result set, and probably making future maintenance of the procedure easier as well. In case it is not obvious, breaking a complex query into smaller steps using temporary tables makes life easier for the optimizer in several ways. Smaller queries tend to have a smaller number of possible execution plans, reducing the chances that the optimizer will miss a good one. Complex queries are also less likely to have good cardinality (row count) estimates and statistical information, since small errors tend to grow quickly as more and more operators appear in the plan.

This is a very important point that is not widely appreciated. The SQL Server query optimizer is only as good as the information it has to work with. If cardinality or statistical information is badly wrong at any point in the plan, the result will most likely be a poor execution plan selection from that point forward. It is not just a matter of creating and maintaining appropriate statistics on the base tables, either. The optimizer does use these as a starting point, but it also derives new statistics at every plan operator, and things can quickly conspire to make these (invisible) derived statistics hopelessly wrong. The only real sign that something is wrong (aside from poor performance, naturally) is that actual row counts vary widely from the optimizer’s estimate. Sadly, SQL Server does not make it easy today to routinely collect and analyse differences between cardinality estimates and runtime row counts, though some small (but welcome) steps forward have been made in SQL Server 2012 with new row count information in the sys.dm_exec_query_stats view.

The benefits of using simplifying temporary tables where necessary are potentially better execution plans, now and in the future as data distribution changes and new execution plans are compiled. On the cost side of the ledger we have the extra effort needed to populate the temporary table, and maintain the statistics. In addition, we expect a higher number of recompilations for optimality reasons due to changes in statistics. In short, we have a trade-off between potential execution plan quality and maintenance/recompilation cost.

The problem, though, is that temporary tables do not work quite how (almost) everyone expects them to…

A World Without Temporary Objects

Imagine if temporary tables and table variables did not exist, and we had a complex query with cardinality-estimation difficulties that would be best addressed by breaking the query into parts. The example presented below is necessarily simplified, and uses the AdventureWorks sample database to make it accessible. It is not a query with insurmountable optimization problems by any means, but bear with me.

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

        DROP PROCEDURE dbo.Demo;

    GO

    CREATE PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        SELECT

            p.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM Production.Product AS p

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = p.ProductID

        WHERE

            p.Name LIKE @StartsWith + N'%'

        GROUP BY

            p.Name;

    END;

This procedure returns a count of orders containing a part whose name starts with the specification passed in as a parameter. For example:

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'E';

A Short Digression about Parameter Sniffing

The only real optimization issue in this simplified example is parameter-sniffing. The number of rows that match the LIKE predicate varies widely depending on the value of the parameter, which can impact execution plan selection. When the SELECT query is compiled or recompiled, SQL Server uses the actual value of the parameter at the time to estimate the number of rows qualified from the Product table. If the SELECT statement happens to compile or recompile with a parameter that matches very few rows, we get an execution plan like this (click to enlarge the graphic):

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'[0-9]';

This plan is cached and reused next time the procedure is called, perhaps with a parameter value that matches more rows than before, but not enough to cause a recompilation:

    EXECUTE dbo.Demo @StartsWith = N'M';

This results in a large number of Key Lookups and a Sort that spills to tempdb physical disk (the warning triangle is new in SQL Server 2012). The memory grant for the sort was sized for the expected 370 rows, not the 22,527 that actually turned up. (If you are curious about the Constant Scan and Compute Scalar in these plans, see my previous post on dynamic seeks for details).

One way (certainly not the only way) to address this parameter-sniffing problem is to ask SQL Server to compile a fresh query plan for the SELECT statement on every execution, using the OPTION (RECOMPILE) query hint:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        SELECT

            p.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM Production.Product AS p

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = p.ProductID

        WHERE

            p.Name LIKE @StartsWith + N'%'

        GROUP BY

            p.Name

        OPTION (RECOMPILE);

    END;

Now we get plans optimized for the particular parameter value at runtime, and (in SQL Server 2008 SP1 CU5 or later) the added bonus that the runtime value of the parameter is embedded into the query so the dynamic seek is not required:

    EXECUTE dbo.Demo @StartsWith = N'[0-9]';

    EXECUTE dbo.Demo @StartsWith = N'M';

Back to the Main Example

However, we are imagining that the example query is much more complex than shown, and we decide to break it into two parts. The first part will fetch qualified items from the Products table, and the second will join the results (with statistics) to the History table. Remember that temporary objects do not exist for this part of the discussion, so we have to use a permanent table:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        -- Real table to hold intermediate result

        CREATE TABLE dbo.Temp

        (

            ProductID   integer NOT NULL, 

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        -- First part of the 'complex' query

        INSERT INTO dbo.Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        -- Second part referencing the 'temp' table

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM dbo.Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name;

        -- Show the statistics for the Name column

        DBCC SHOW_STATISTICS (Temp, Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE dbo.Temp;

    END;

This procedure is not very practical as it stands, because the CREATE TABLE and DROP TABLE statements would make it impossible for more than one user to execute it at the same time. Nevertheless, it does show how most people expect things to work regarding statistics, temporary table lifetimes, and compilation:

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'A';

There are three matching Product records, shown below together with the SHOW_STATISTICS output:

Nothing too surprising in the execution plans: the table INSERT is a trivial plan (no choices for the optimizer to make), and the SELECT query has cardinality estimates that are very close to the actual numbers encountered. The warning triangle on the SELECT (again, new for SQL Server 2012) is just suggesting an index for the History table, which we won’t be adding on this occasion.

While the procedure was executing, a Profiler trace captured the following compilation and statistics activity:

The table is created, and since this is the first time the procedure has been run, the INSERT and SELECT statements both incur a deferred compilation. As part of the SELECT compilation, new statistics are created on the Name and ProductID columns of the new table, the DBCC SHOW_STATISTICS command executes, and finally the table is dropped. Now we execute the procedure again but for products that start with ‘E’ rather than ‘A’ as above:

    EXECUTE dbo.Demo @StartsWith = N'E';

This time there are nine matching records, though the statistics-gathering algorithms compress the information into the five histogram steps shown. The execution plan is below (trivial INSERT plan not repeated):

Again, the cardinality estimates are extremely good, and the optimizer selected a nested loops plus key-lookup plan based on costs computed according with the smaller number of expected rows. The trace captured the following:

The only change is that this time recompilation is triggered because the cached INSERT and SELECT plans reference a table that no longer exists, leading to a ‘schema changed’ recompilation. The crucial observations here are that the table is recreated and new statistics are gathered on every execution. This is the way most people expect tables, statistics, and compilations to behave inside stored procedures, so don’t worry if there’s nothing too surprising so far.

Using a Temporary Table

The previous example is not terribly practical. It is possible to conjure up schemes where ordinary tables can serve the purpose effectively, but as it stands, the procedure would likely cause runtime errors if more than one user or process attempted to execute it concurrently. In addition, ordinary tables do not benefit from engine optimizations that only apply to genuine temporary tables, so they tend to be less efficient, even if created in tempdb. We now return to the real world (where temporary tables do exist) and modify the procedure to use a temporary table instead of a permanent table:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        CREATE TABLE #Temp

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        INSERT INTO #Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM #Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name;

        DBCC SHOW_STATISTICS (N'tempdb..#Temp', Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE #Temp;

    END;

Executing this procedure with an ‘E’ parameter produces exactly the same output as when the permanent table was used. Same execution plan, same statistics, same Profiler output, everything:

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'E';

Now we will execute the procedure with a parameter value of ‘T’, which has 65 matching records in the Product table. This is the output (only the first nine of the 65 matching names are shown in the first result set):

The results are as expected (products that begin with ‘T’) but the SHOW_STATISTICS output displays ‘E’ statistics from the previous execution!

The execution plan has serious cardinality estimation errors. It has the same nested loops and key-lookup shape and estimated row counts as the ‘E’ execution, instead of being optimized for the ‘T’ data. This causes slow performance and a sort that spills data to physical tempdb disk.

The Profiler output explains why: no recompilations occurred, and no statistics were created. In fact, with the AdventureWorks database, there is no way to persist a different execution plan or update the statistics for this procedure without changing it (more on that later). Even executing with [A-Z] as the parameter reuses the plan optimized for the ‘E’ value:

    EXECUTE dbo.Demo @StartsWith = N'[A-Z]';

The key lookup is now executed 113,443 times, and the sort has to perform a multi-pass spill to tempdb (previously only a single pass spill was required). Executing the procedure with the WITH RECOMPILE option will produce better plans, at the cost of recompiling the whole procedure, and the resulting plans will not be cached for reuse. In general, recompiling the whole procedure every time could be bad since many procedures have many more statements to recompile than just a single INSERT and SELECT. Although we have not yet identified a cause for the behaviour we are seeing, perhaps the answer lies in adding a RECOMPILE query hint to the SELECT statement as we did earlier for the parameter-sniffing example?

OPTION (RECOMPILE) to the Rescue?

Thinking that the cause might be a new form of the parameter-sniffing problem, we now modify the procedure to add the RECOMPILE query hint to just the SELECT statement. This avoids recompiling the whole procedure on each call as EXECUTE … WITH RECOMPILE would do, and will hopefully solve our optimization problems:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        CREATE TABLE #Temp

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        INSERT INTO #Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM #Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name

        OPTION (RECOMPILE);

        DBCC SHOW_STATISTICS (N'tempdb..#Temp', Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE #Temp;

    END;

Unsurprisingly, clearing the plan cache and executing with a parameter value of ‘E’ produces the exact same nested loops and key lookup plan as previously shown (and the same statistics and Profiler events too).

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'E';

This is fine because it is the optimal plan for this value. The test for OPTION (RECOMPILE) comes when we try a second execution with the 65-row ‘T’ value:

    EXECUTE dbo.Demo @StartsWith = N'T';

The execution plan has a different shape now, with the optimizer correctly preferring a hash join over the nested loops plus key lookup. The estimated cardinality is correct for the temporary table (65 rows versus 9 previously seen for ‘E’), but it is badly wrong for the hash join (811 rows expected, 12,273 actual) and the distinct sort, which has to perform a single-pass spill to tempdb disk. The query output shows the reason for the inaccuracy:

The results are correct of course (65 products starting with ‘T’) but the statistics are again still reflecting the parameter value ‘E’. The RECOMPILE query hint allows the optimizer to see the true cardinality of the temporary table (65 rows) but the 100% wrong statistics on the ProductID column used to estimate the cardinality of the join to the History table result in a mess of a plan from that point forward. (Note that statistics on the Name column are also considered interesting by the optimizer for this query due to the GROUP BY clause. The SHOW_STATISTICS output above shows the Name statistics because it more immediately shows that ‘E’ values are stored; the ProductID statistics are integers, and much harder for the reader to correlate with the parameter).

The Profiler output above confirms the recompilation due to the query hint, and that no statistics were created or updated. An interesting thing occurs if we execute the procedure four more times with the same ‘T’ parameter (a total of five times with ‘T’):

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

The first three of those executions are exactly as before, but the fourth one suddenly produces this different execution plan:

The estimates are now well within the boundaries of expected accuracy, and the sort now receives enough workspace memory to avoid spilling rows to tempdb.

The statistics have been updated, and now show 65 rows that start with ‘T’ sampled (compressed into 49 histogram steps). This is confirmed by the trace output:

Notice the StatMan and AutoStats entries showing the ProductID and Name statistics being updated. Unfortunately, executing the procedure again with a new parameter value takes us back to inaccurate cardinality estimates again. The execution plans for this procedure aren’t always a disaster, but this is pure luck – poor estimates are poor estimates, whether the query plan happens to perform acceptably or not. We really need to get to the root cause here. Perhaps OPTION (RECOMPILE) was not the way to go, and we should try a manual statistics update instead of relying on automatic statistics updates…?

Manual Statistics Update to the Rescue?

We know we want to add an UPDATE STATISTICS command to our stored procedure instead of the OPTION (RECOMPILE) … but where to put the new statement exactly? The statistics we want to update are created during compilation or recompilation of the SELECT statement, suggesting the UPDATE STATISTICS should come after the SELECT; but then how could it possibly affect the preceding SELECT plan? It seems the only sensible place to put it is before the SELECT, however counter-intuitive it might seem.

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        CREATE TABLE #Temp

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        INSERT INTO #Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        UPDATE STATISTICS #Temp;

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM #Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name;

        DBCC SHOW_STATISTICS (N'tempdb..#Temp', Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE #Temp;

    END;

Following the same pattern as before, we clear the plan cache (though this isn’t strictly necessary since the ALTER PROCEDURE evicts plans from the cache anyway) then execute with ‘E’ and ‘T’ parameters as before.

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'E';

    EXECUTE dbo.Demo @StartsWith = N'T';

The results for the ‘E’ execution are the same as always, so here are just the results for the ‘T’ execution:

The above output looks very promising: correct results and the statistics have been updated to reflect the ‘T’ parameter.

The trace output shows the statistics updates too…but no recompilation.

The execution plan is a disaster. The estimated number of rows in the temporary table is 9 (the number of rows the ‘E’ execution produced not the 65 actually present), and everything is wrong from that point forward, including the sort spilling to tempdb again. The UPDATE STATISTICS command did its job, but the cached query plan did not recompile – though we might expect that it should, right?

As with the first temporary table example (no RECOMPILE or UPDATE STATISTICS) this plan is stuck in cache, given the AdventureWorks database. No parameter value will cause a recompilation, and every subsequent execution will use the ‘E’ plan. This is very reminiscent of the parameter-sniffing problem we encountered earlier, though the SELECT query in question has no direct parameter value to be sniffed! In a final effort to produce reliable plans, our last attempt will be to combine both RECOMPILE and UPDATE STATISTICS…

RECOMPILE and UPDATE STATISTICS to the Rescue?

Our stored procedure now includes an UPDATE STATISTICS before the SELECT, and an OPTION (RECOMPILE) query hint on the SELECT itself:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        CREATE TABLE #Temp

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        INSERT INTO #Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        UPDATE STATISTICS #Temp;

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM #Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name

        OPTION (RECOMPILE);

        DBCC SHOW_STATISTICS (N'tempdb..#Temp', Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE #Temp;

    END;

Our usual test executions:

    DBCC FREEPROCCACHE;

    EXECUTE dbo.Demo @StartsWith = N'E';

    EXECUTE dbo.Demo @StartsWith = N'T';

The first ‘E’ execution performs as it always has: correct statistics and an optimal query plan. The results for ‘T’ are:

The output is correct, and so are the statistics: 65 rows sampled, stored in 49 histogram steps.

Success! All estimates are very good, the sort is performed in memory, and the query executes quickly. Further experimentation with other parameter values shows that new statistics are always generated, and the SELECT query plan always recompiles to use those statistics. If you are concerned by the small discrepancy after the hash join (estimate 10,449 rows; actual 12,273) don’t be. Cardinality estimation is a tough problem – try using the statistics histograms yourself to predict how the ProductID values in the temporary table (65 rows in 49 steps, remember) will join to the histogram on the same column for the much larger History table. You’ll find the data there even more compressed, so the task of matching values to values using RANGE_ROWS, EQ_ROWS and so on is really not an easy one at all.

Enter the Table Variable…

The final option we are going to look at is using a table variable instead of a temporary table:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        DECLARE @Temp AS TABLE

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) NOT NULL

        );

        INSERT INTO @Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM @Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name

        OPTION (RECOMPILE);

    END;

There are a couple of small changes to the procedure here. The COLLATE clause is not necessary in the definition of the Name column, since the default for table variables is the collation of the host database anyway (the default for temporary tables is the collation of tempdb). There is no need (or option) to drop the table at the end of the procedure; table variables simply go out of scope. There is no SHOW_STATISTICS statement either, since table variables do not support statistics (even on constraint-supporting indexes). The first execution with a parameter value of ‘E’ produces this execution plan and trace output:

The OPTION (RECOMPILE) on the SELECT statement ensures that the cardinality estimate for the table variable is exactly right, but the lack of statistics means the optimizer resorts to guesses after that point. The guessed estimates turn out to be higher than the actual number of rows, so no performance problems result, although the sort is allocated more memory than it needs. The trace output is a bit smaller than before, since no statistics are created.

The second test is with a parameter value of ‘T’:

Again, the number of rows in the table variable is exactly right due to the RECOMPILE, and the later guesswork also turns out to work quite well. As you can see, the overall shape of the plan is quite different for this parameter value (hash joins versus nested loops for example). There is one cardinality estimation problem at the middle hash operator, but whether it causes performance problems or not depends on your version of SQL Server. To make the issue clearer, we will perform one final test, a parameter value of ‘[A-Z]’, qualifying all 504 products:

Once more, the table variable cardinality is exactly right (504 rows). Both inputs to the hash join look exactly right, and the guessed output from that join is also very close to the actual. The lack of statistical information makes itself felt at the middle hash operator though; the optimizer has no idea how many distinct values there might be of the combination (Name, OrderID), so it guesses at 2,825. This is very much smaller than the 113,338 actual, and the hash table spills out to tempdb physical disk as a result.

The table variable approach happens to produce reasonable plans in some cases, based on the sniffed table cardinality provided by OPTION (RECOMPILE) but the lack of statistics leads to wild guesses and potential performance issues deeper in the tree. It’s interesting that one of the main perceived benefits of table variables – fewer recompilations – has to be abandoned in order to produce semi-reasonable plans. This follows hard on the heels of our seeing the main benefit of temporary tables – statistics – being 100% wrong earlier!

The last thing I want to mention about table variables is that for all their limitations, they do something else temporary tables cannot: a join from a table variable is estimated for the average case summed over all rows. This is similar to hinting OPTIMIZE FOR UNKNOWN for a temporary table query with a parameter, but the average-case estimation occurs for all joined rows, not just one predicate, and of course there is no parameter variable in a join for OPTIMIZE FOR UNKNOWN to work on anyway.

Question Time

At this point, you should have some questions. Why does the temporary table behave so differently from the permanent table? Do you really have to UPDATE STATISTICS before they are created, and add OPTION (RECOMPILE) when you use temporary tables this way? Why does the RECOMPILE query hint only produce the desired effect with temporary tables every so often? Part of the answer to these questions lies with the caching of temporary tables first introduced to SQL Server in the 2005 version.

CREATE and DROP, Don’t

I will talk about this in much more detail in my next post, but the key point is that CREATE TABLE and DROP TABLE do not create and drop temporary tables in a stored procedure, if the temporary object can be cached. The temporary object is renamed to an internal form when DROP TABLE is executed, and renamed back to the same user-visible name when CREATE TABLE is encountered on the next execution. In addition, any statistics that were auto-created on the temporary table are also cached. This means that statistics from a previous execution remain when the procedure is next called. The following code demonstrates the object id of a temporary table remaining the same between executions (there will be a more comprehensive demonstration in my next post):

    ALTER PROCEDURE dbo.Demo

    AS

    BEGIN

        CREATE TABLE #Temp (col1 int NULL);

        SELECT ObjectID = OBJECT_ID(N'tempdb..#Temp');

        DROP TABLE #Temp;

    END;

    GO

    EXECUTE dbo.Demo;

    EXECUTE dbo.Demo;

    EXECUTE dbo.Demo;

This is very different from the case where we used a permanent table. With a permanent table, CREATE and DROP definitely do create and drop a table on each execution of the procedure. The table is new each time, new statistics are created, and new plans are compiled on each execution. The permanent table behaviour is probably more intuitive than the apparently strange behaviour of cached temporary tables, but it does allow temporary tables an opportunity to cache plans and temporary objects for reuse, which is not possible when using a permanent table in the way we did.

Recompilation Thresholds

Most of you will be familiar with the concept of recompilation thresholds, as described in the Plan Caching in SQL Server White Paper. Briefly though, cached query plans include a Recompilation Threshold (RT) for statistics considered interesting by the optimizer while compiling the plan. The query plan also records the cardinality of tables and indexed views referenced by the plan, at the time the plan is compiled. (I demonstrated how to determine which statistics are considered ‘interesting’ by the optimizer during compilation in a previous post).

Generally, if the column modification counter (colmodctr) for interesting statistics change by RT or more, the query recompiles. Similarly, if the table cardinality has changed by RT or more compared with the value stored at the time the cached plan was created, the query plan also recompiles. The value of RT depends on the type of table (permanent or temporary) and the number of rows (n) in the table or indexed view at the time of compilation. The following summary of RT values is taken from the White Paper:

There is another condition not listed above. If the table is empty at compilation time, RT is set to 1.

I say “generally” above because although queries referencing permanent tables recompile when interesting statistics modification counters change by RT or more, this is not the case for cached temporary tables in stored procedures, which only recompile when table cardinality changes by RT or more, unless OPTION (RECOMPILE) is used, when statistics counters come back into play. If this sounds confusing, that’s because it is. It may be a bug, but on the other hand, it does seem reasonable that a cached temporary table should not cause a recompilation simply because the procedure is called a number of times with the same parameter, with the number of modifications accumulating on each call to eventually pass RT. In that specific case, we would probably prefer no recompilations. I will probably file a Connect item to get the situation with statistics modification counters and temporary tables clarified. Update: the Connect item can be found here.

In our experiments, this explains why the vanilla temporary table procedure (with no RECOMPILE or UPDATE STATISTICS) stuck with the same plan, whereas adding RECOMPILE meant the plan would occasionally recompile (when accumulated changes passed RT). The vanilla procedure was initially called with a parameter value of ‘E’, which compiled a SELECT execution plan when 9 rows were in the temporary table. Following the rules above for n=9, this means RT was set to 500, so the plan would recompile when n reached 9 + 500 = 509. The AdventureWorks Product table only contains 504 rows, so that target could not be reached, and the plan never recompiled.

When OPTION (RECOMPILE) was added, the modification counters did accumulate to eventually pass RT. The first execution was the same, with the ‘E’ parameter value resulting in 9 rows in the temporary table at compilation time, with RT = 509 as before. We then ran the procedure a total of five times with a parameter value of ‘T’. There happen to be 65 product names that start with ‘T’, so five executions resulted in 5 * 65 = 325 changes. This does not reach the target of 509, but there is a second factor in play here. Although the temporary table is not dropped at the end of the procedure (just renamed), it is implicitly truncated (whether an explicit DROP TABLE is included in the procedure or not). This implicit truncation removes 65 rows on each execution, and this action adds to the modification counters.

On each ‘T’ execution then, 65 modifications are counted when the rows are added to the temporary table, and 65 more when the table is silently cleared at the end of the procedure. In total, the first four ‘T’ executions result in 65 * 2 * 4 = 520 modifications, which is enough to pass the 509 target. That in itself is not enough to cause a recompilation though, because the RT test is performed as each query is retrieved from the plan cache for execution, and the final 65-row truncation happens at the end of the procedure, after the SELECT has already completed. On the next execution, whatever parameter is passed in, a recompilation will occur at the SELECT query. The OPTION (RECOMPILE) version of the procedure is reproduced below:

    ALTER PROCEDURE dbo.Demo

        @StartsWith nvarchar(50)

    AS

    BEGIN

        SET NOCOUNT ON;

        CREATE TABLE #Temp

        (

            ProductID   integer NOT NULL,

            Name        nvarchar(50) COLLATE DATABASE_DEFAULT NOT NULL

        );

        INSERT INTO #Temp

            (ProductID, Name)

        SELECT

            p.ProductID,

            p.Name

        FROM Production.Product AS p

        WHERE

            p.Name LIKE @StartsWith + N'%';

        SELECT

            t.Name,

            OrderCount = COUNT_BIG(DISTINCT th.ReferenceOrderID)

        FROM #Temp AS t

        JOIN Production.TransactionHistory AS th ON

            th.ProductID = t.ProductID

        GROUP BY

            t.Name

        OPTION (RECOMPILE);

        DBCC SHOW_STATISTICS (N'tempdb..#Temp', Name) WITH STAT_HEADER, HISTOGRAM;

        DROP TABLE #Temp;

    END;

Now run the tests as described above:

    -- 9 rows, RT = 509

    EXECUTE dbo.Demo @StartsWith = N'E';

    -- 65 rows, 4 times = 260

    -- Plus truncation modifications = 520

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

    EXECUTE dbo.Demo @StartsWith = N'T';

    -- No rows, but plan still recompiled

    EXECUTE dbo.Demo @StartsWith = N'5';

There are no products that start with ‘5’, but the 520 modifications already performed cause a recompilation anyway:

No results, and NULL statistics created! Luckily, the new RT value after this compilation is 1, so just one row is needed to produce a new plan. This is demonstrated by calling the same procedure again with a ‘K’ parameter value (just one product name starts with ‘K’):

    EXECUTE dbo.Demo @StartsWith = N'K';

After this compilation, the new RT is 1 + 6 = 7, which can be confirmed by executing the procedure with a parameter value of ‘P’ (there are exactly seven Product rows where the name starts with ‘P’). And so on.

I should mention though, that it is just the carry-over of accumulated modifications that requires OPTION (RECOMPILE). Without this query hint, modifications are still accumulated within a single execution of the procedure (and may result in recompilation local to that single execution) but any accumulation is not carried over to the next procedure execution.

Statistics Updates

So far we have explained how the vanilla and OPTION (RECOMPILE) procedures produce the observed behaviour. The next configuration to examine is where OPTION (RECOMPILE) is not specified, but an UPDATE STATISTICS statement appears before the problematic SELECT query. It should now be apparent that the placing of the UPDATE STATISTICS statement works because auto-created statistics from a previous execution are cached, and available for update by the next execution. The one remaining question is why the updated statistics do not cause a recompilation in our example – remember we saw correct statistics, but the execution plan was not rebuilt to reflect the new information. This is either a bug, or another example of different behaviour for cached temporary tables. In any case, the observed behaviour does not match that described in the White Paper (the same diagram appears in the SQL Server Internals books from Microsoft Press):

Whether this is a bug or undocumented designed behaviour (and it is the same on all versions of SQL Server from 2005 to 2012 inclusive) the effect is clear: UPDATE STATISTICS on a cached temporary table in a stored procedure is not enough on its own to force recompilation of a query plan. A recompilation may still occur for other reasons, for example if the cardinality of the table has changed by RT or more compared with the cardinality value stored with the cached plan. This cannot happen with our UPDATE-STATISTICS-only test procedure as shown earlier, since the first execution with the ‘E’ parameter value adds 9 rows to the temporary table, setting RT to 509, and the AdventureWorks Product table only has 504 rows in total as mentioned earlier.

For the moment, at least, we may need to specify OPTION (RECOMPILE) as well as UPDATE STATISTICS if we want to be sure of a plan specific to the contents of a cached temporary table on each execution.

Summary and Final Thoughts

Temporary tables in stored procedures have a number of characteristics that may seem unexpected:

Temporary objects may be cached across executions, despite explicit CREATE and DROP statements
Statistics associated with a cached temporary object are also cached
Statistics may be 100% wrong compared with the current contents of a temporary table
An implicit TRUNCATE TABLE at the end of the procedure doubles the expected impact on column modification counters
It is possible to update cached statistics before the statement that caused them to be created
OPTION (RECOMPILE) changes the way column modifications are carried over between procedure calls
Manual UPDATE STATISTICS is not enough to force a recompilation

It is possible that one or more of these behaviours is unintentional, but they have been this way for a very long time, and so are very unlikely to be changed. Temporary tables behave quite similarly (aside from the UPDATE STATISTICS behaviour) to an in-procedure reference to a permanent table that was created outside the procedure. It may be that some of the features of temporary tables shown in this post have their roots in a design that sought to mimic permanent table behaviours using non-sharable local temporary tables. On the other hand, it might be simply that the current arrangement provides the best chances for caching and reuse, and we are expected to take action where we suspect reusing the cached plan, temporary object, and/or statistics may not be optimal. Who knows.

How likely you are to be affected by the issues illustrated in this post depends on usage. A temporary table that contains wildly differing numbers of rows on every execution is unlikely to be affected. If the recompilation threshold is passed, chances are you will get good statistics and any cached plan with recompile without intervention. For a plan cached when the temporary table contained 10,000 rows the default threshold is 500 + 0.2 * 10,000 = 2,500 rows. This means the next execution with more than 12,500 rows or fewer than 7,500 rows will pass the threshold test. The formula to compute RT values when trace flag 2371 is enabled is unknown to me.

In principle, in later versions of SQL Server, we can look in the plan cache to check the cardinality of a temporary table and deduce the RT from there, but this is not convenient to do routinely. In practice, RT moves around a fair bit, so it can be hard to know how often a procedure might use stale cached statistics or a sub-optimal cached plan. Avoiding temporary table caching removes the risk of stale statistics, but a cached plan may still be used unless the RECOMPILE query hint is used. Avoiding temporary table caching will also tend to increase contention on tempdb, and can be difficult to enforce in practice.

Procedures that routinely store relatively small result sets and use cached temporary tables are probably most at risk. This is quite a common scenario: temporary tables are often used for smaller sets (writing away large temporary tables is more difficult to justify). One scenario that springs to mind is where a delimited string is passed as a parameter, split to a cached temporary table, which is then used to drive a more complex query. The plan for the complex query may be very sensitive to the cardinality and statistical distribution of values in the temporary table, so 100% wrong cached statistics and/or inappropriate plan reuse may be a problem. I’m sure there are many other scenarios.

It is quite ironic that the poor temporary table execution plans shown in this post are caused by the thing that is perceived to be their greatest strength: the availability of distribution statistics. Some care is needed when choosing between table variables, temporary tables or another technique; the right choice in any particular circumstance will depend on many factors, only a few of which have been discussed today. Whichever option you choose, be sure to understand the choice you have made and the trade-offs that result.

There are also times where the best-performing solution will be to carefully craft one huge query, perhaps using hints and/or specific syntax tricks. This approach is perfectly valid but requires careful thought as future maintenance may be harder, and data changes over time may mean the carefully-designed manual execution plan gradually (or suddenly) becomes sub-optimal. My general preference is still for simpler relational queries and, where necessary, for temporary tables over table variables as a starting point, but the details do indeed depend on the details. If you happen to be attending the PASS Summit 2012, I will be speaking more about these sorts of things in my half day and regular sessions.

I hope you enjoyed this post, the next one will cover details of temporary table caching that I did not have space for today. I would like to thank Dave Ballantyne (blog | twitter) for his help with today’s post.

Parallel Execution Plans Suck

Paul White — Wed, 02 May 2012 17:57:00 GMT

Summary: A deep dive into SQL Server parallelism, and a potential performance problem with parallel plans that use TOP.

There was an interesting question asked by Mark Storey-Smith on dba.stackexchange.com back in October 2011. He was looking at the execution plan for a query that counts a million rows from a virtual auxiliary table of numbers. The query below is a slightly-modified version of the one in the original post:

     WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L CROSS JOIN N1 AS R), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L CROSS JOIN N2 AS R), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L CROSS JOIN N3 AS R), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L CROSS JOIN N1 AS R), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 1);

This particular virtual numbers table is capable of producing up to a (short-scale) billion rows, via a number of cross joins, but the final common table expression N6 limits it to one million with the TOP clause. The query plan is just a sequence of cross joins of the ten in-memory rows defined by the first common table expression, N1 (click to enlarge):

As usual, the Constant Scan operator is used to generate rows in memory without accessing a physical table, but this one has an interesting property: the ‘virtual table’ contains ten rows, but no columns. The query itself only counts rows, it does nothing at all with any column in those rows, and the optimizer contains logic to only project columns that are needed later in the query plan. If you look at the query plan in SSMS or SQL Sentry Plan Explorer, you will see that the Constant Scans have a blank output columns list; they project no columns at all.

Execution Plans Suck

The plan above does illustrate an important concept in plan-reading: execution plans start executing at the left-most node. People are often told to read execution plans from the top-right, and that is fine if you just want to follow the flow of data – so long as you bear in mind that the flow of program control starts at the root (far left).

Rob Farley (blog | twitter) sums this up by saying “execution plans suck”; a reference to the fact that rows are pulled up the tree by parent operators requesting rows, one at a time, from the its child operator(s). Query execution follows a demand-based pipeline model (except in batch mode in parallel 2012 column-store plans, but that is a tangent we will not be pursuing today). I’m not going to labour the point, but if you are interested to understand this better, take a look at my previous post on the topic, or Brad Schulz’s entertaining overview.

Let’s look at the execution plan (with runtime statistics) changing the TOP specification from one million to one hundred to make it easier to see what’s going on:

I’m just showing part of the plan for clarity. There are another four Constant Scans off to the right that all produce one row. If query plans really did start executing at the top right, we would expect one row from the right-most Constant Scan, ten rows from its parent, and one hundred at the next operator up the tree (working right to left). As it is, the expected pattern (one, then ten, then one hundred) appears closest to the Top operator. This only makes sense if a row at a time is sucked up the plan from the root. The pipelined (row-by-row) model also explains why execution stops after 100 rows; the Top operator in the plan simply stops requesting a new row from its immediate child at that point.

The Question

Back to the main thrust of today’s post. The question arose when Mark ran his query with parallelism enabled:

    WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L CROSS JOIN N1 AS R), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L CROSS JOIN N2 AS R), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L CROSS JOIN N3 AS R), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L CROSS JOIN N1 AS R), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 2);

That produces an actual execution plan like this (click to enlarge):

The question relates to the actual number of rows shown entering and leaving the Gather Streams exchange operator:

As expected, one million rows leave the exchange operator, but the plan shows 1,004,588 rows entering it. So the question is, are the row counts wrong, or if not, where did the rows go?

The Answer

As you may know, the answer lies in the fact that exchanges contain buffers. For efficiency reasons, rows are not passed across threads one by one as in the normal model discussed above. Instead, producer threads (on the right side of the exchange operator) pack rows one at a time into packets, and push completed packets across the exchange. Consumer thread(s) on the left side of the exchange retrieve rows one at a time from the current packet on demand, re-establishing the demand-based pipeline model. The internal class name for the packets, by the way, is Class eXchange PACKET – which gives us the familiar CXPACKET moniker.

Exploring the detail at little more, we can see from the execution plan that the two independent producer threads to the right of the exchange pack a total of 499,225 + 505,363 = 1,004,588 rows into packets, and the single consumer thread (thread zero) retrieves just the one million rows needed by the Top operator:

So, the actual row counts shown on the execution plan are correct, and the ‘missing rows’ are accounted for by rows that were added to packets but not ultimately needed by the consumer. After the one millionth row is passed by the Top to the Stream Aggregate (and remember all these things happen one row at a time), the next time the Top gets control, it starts the process of shutting down the pipeline below it, rather than asking the Gather Streams exchange for another row. Glossing over the finer details a little, instead of the Top calling a GetRow() method on the Gather Streams iterator, it calls a Close() method instead.

SQL Server 2008+

On SQL Server 2005 that is the end of the story. On SQL Server 2008 and later (including 2012), there is more. Let’s run the query one more time, but this time with a degree of parallelism of three, rather than two. Sometimes, we will get a plan that contains this sort of row count arrangement at the Gather Streams:

Much the same as before, a few thousand extra rows are processed by the producer threads than are ultimately needed by the consumer. That’s fine, of course, the threads in a parallel plan execute independently, so there are bound to be small timing differences that lead to this sort of effect. Every so often, however, executing this query on SQL Server 2008 or above will produce a result like this:

Whoa. Nearly 335 million rows entering the exchange – and the query now runs for 50 seconds or so, having run consistently for around 200ms previously. Looking at the per-thread actual row counts is revealing:

If everything were perfectly balanced, we might expect each of the three producer threads to process around 333,000 rows. Indeed, thread 1 and thread 2 are in this ballpark area, but thread 3 ground through 334 million rows on its own! I should mention that there is nothing special about thread 3 (you are as likely to find the huge row count on thread 1 or thread 2, the labels are arbitrary). Indeed, the problem can occur on any or all threads, as a second example run at DOP 3 shows below:

This time two threads went rogue, resulting in over 667 million rows being processed in a total execution time of 67 seconds.

Parallelism Problems?

There are other parallelism (exchange) operators in the plan, though we have concentrated only on the final Gather Streams operator so far. By the way, Gather Streams is also known as a Start Parallelism operator – a name that might surprise you since it seems to mark the end of parallelism in the plan, rather than the start. Remember that execution plans suck. The ‘final’ Gather Streams is in fact the first operator to start executing, and it is responsible for starting the parallel workers and attaching them to the threads that were reserved for this plan at the very start of execution. Anyway, I digress. Let’s look at the next exchange in the plan – reading left to right of course. This is a Repartition Streams exchange operating in Round Robin distribution mode:

This shows that 1,000 rows arriving on the producer side of the exchange, and a total of 668 on the consumer side. Not shown in the diagram above, the producer side has 340 rows on thread 1, and 330 rows on each of thread 2 and thread 3. Note that these are not the same threads as the ones we saw numbered the same way before. The numbering scheme is restarted for each independent parallel zone in the plan (and zones are bounded by a parallelism operator of one sort or another). Anyway, the point is that the rows are pretty evenly distributed on the producer side of the exchange.

On the consumer side (row counts illustrated above), things are rather different. Thread 1 (in this zone) processes 334 rows, thread 2 gets 333, and thread 3 gets only one. Now these are the same threads as shown in the 667 million row diagram. I mentioned that parallel zones are bordered by parallelism operators; the current zone is bordered by the Repartition Streams on its right side, and by the Gather Streams on its left. The same three threads are consumers at the Repartition Streams, and producers at the Gather Streams operator:

There is a clear relationship between the thread row counts at the consumer side of the Repartition Streams (334, 333, and 1 row) and the row counts at the producer side of the Gather Streams (334 million, 333 million, 338,614 rows). The two problematic threads have multiplied their row counts by a factor of one million – precisely the effect of the six cross joins in this parallelism zone. The Constant Scan virtual tables contain ten rows each, and multiplying by ten, six times over, gives a factor of one million.

Rogue Row Goals

Thread 3 in the example above ends up processing 338,614 rows. This number has no special significance, except it shows that this thread did not run this portion of the plan to completion. If it had, the single row it started with would have ended up as one million rows by the time it had been cross-joined six times with the ten-row Constant Scan table.

This is the row goal in action (if you need a details on exactly what a row goal is, please see my previous post). Essentially, though, things like a TOP operator or a FAST n hint set a row goal. Plans normally run to completion, but row goals modify this, producing a plan that tries to optimize for a certain number of rows rather than the full potential set. The TOP operator is even more special. As discussed briefly before, TOP can bring execution to an early end – instead of continuing to ask for rows from its child iterator, it calls the Close() method instead. This call filters down the tree, and execution comes to an early end. (Strictly, row goals affect optimizer choices and plan costing rather than being associated with the early end of execution, but I like the phrase ‘rogue row goal’).

So, thread 3 did not run to completion – it responded to the early Close() call and only processed 338 thousand of the one million rows it could have produced if left alone. Threads 1 and 2 never received the Close() call, or chose to ignore it. These two rogues went on to process their full potential row set – 667 million rows – despite the fact that the TOP had seen the million rows it needed and was waiting for operations elsewhere in the parallel plan to stop. We can see this by looking at the sys.dm_os_waiting_tasks DMV while the long-running query is executing:

The output is split across two lines for readability, and shows execution context zero blocked on a CXPACKET wait by both execution context 1 and execution context 3. Execution context zero is always thread zero – the so-called coordinator thread that runs the serial part of the execution plan to the left of the left-most Gather Streams operator. Put another way, context zero always runs the part of the plan before (reading left to right) the Start Parallelism operator (and therefore always runs a serial plan).

OK, so CXPACKET means the thread is involved in a parallelism-related wait. The extra detail in the resource_description column tells us that the wait is occurring at the node id 2. Checking the execution plan, we see that node 2 is indeed the Gather Streams exchange:

The wait type of e_waitPortClose means the consumer is waiting for the port to close. If you are wondering what a port is in this context, I will just say the parallelism architecture is more complex than just CXPACKET – the wiring includes a CXPort class, a CXPipe class, a CXTransLocal (local transport) class and a CXTransRemote class (for the Parallel Data Warehouse edition). There is also a linked map structure that shows how the various pipes, ports, and transports connect together. Closing the port is one step in shutting down part of a parallel plan which is running on the other side of an exchange (via a transport, pipe, and port). The stack trace below shows thread zero waiting for the port to close:

The important things are that (a) this problem does not occur in SQL Server 2005; and (b) a number of changes were made to the internal parallelism implementation in SQL Server 2008. These changes seem to have introduced a bug, where the consumer can wait for the port to close, but one or more producers either ignore the request, or fail to check for it, and go on to process the whole potential result set instead of stopping early.

Not Just Nested Loops

Fellow SQLblogger Joe Chang (blog) suggested in the comments that this problem may only occur with parallel nested loops joins. The script below reproduces the problem with parallel hash joins:

    WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L JOIN N1 AS R ON L.n % 1 = R.n % 1), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L JOIN N2 AS R ON L.n % 1 = R.n % 1), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L JOIN N3 AS R ON L.n % 1 = R.n % 1), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L JOIN N1 AS R ON L.n % 1 = R.n % 1), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 4, QUERYTRACEON 8649);

The full execution plan is rather large, but the key part is shown below (click to enlarge):

Yes, that is 700 million rows entering the Gather Streams exchange (click to enlarge):

The bug does not occur in every query plan with Top and parallelism, but the choice of nested loops join is not the cause.

Final Thoughts

The potential for poor performance and excessive processor usage here is obvious; and the chance of hitting the race condition gets worse at higher DOP. With eight threads per parallel zone (DOP 8), I hit this issue almost every time on SQL Server 2008, 2008 R2, and 2012. Because this behaviour does not occur on SQL Server 2005, but does on 2008 and later, I have filed this as a bug on Connect:

https://connect.microsoft.com/SQLServer/feedback/details/740234/poor-performance-with-parallelism-and-top

Fun with Aggregates

Paul White — Sun, 11 Mar 2012 15:49:00 GMT

There are interesting things to be learned from even the simplest queries. For example, imagine you are given the task of writing a query to list AdventureWorks product names where the product has at least one entry in the transaction history table, but fewer than ten.

One possible query to meet that specification is:

     SELECT

        p.Name

    FROM Production.Product AS p

    JOIN Production.TransactionHistory AS th ON

        p.ProductID = th.ProductID

    GROUP BY

        p.ProductID,

        p.Name

    HAVING

        COUNT_BIG(*) < 10;

That query correctly returns 23 rows (execution plan and data sample shown below):

The execution plan looks a bit different from the written form of the query: the base tables are accessed in reverse order, and the aggregation is performed before the join. The general idea is to read all rows from the history table, compute the count of rows grouped by ProductID, merge join the results to the Product table on ProductID, and finally filter to only return rows where the count is less than ten.

This ‘fully-optimized’ plan has an estimated cost of around 0.33 units. The reason for the quote marks there is that this plan is not quite as optimal as it could be – surely it would make sense to push the Filter down past the join too? To answer that, let’s look at some other ways to formulate this query. This being SQL, there are any number of ways to write logically-equivalent query specifications, so we’ll just look at a couple of interesting ones. The first query is an attempt to reverse-engineer T-SQL from the optimized query plan shown above. It joins the result of pre-aggregating the history table to the Product table before filtering:

    SELECT p.Name

    FROM

    (

        SELECT 

            th.ProductID, 

            cnt = COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th 

        GROUP BY

            th.ProductID

    ) AS q1

    JOIN Production.Product AS p 

        ON p.ProductID = q1.ProductID

    WHERE

        q1.cnt < 10;

Perhaps a little surprisingly, we get a slightly different execution plan:

The results are the same (23 rows) but this time the Filter is pushed below the join! The optimizer chooses nested loops for the join, because the cardinality estimate for rows passing the Filter is a bit low (estimate 1 versus 23 actual), though you can force a merge join with a hint and the Filter still appears below the join. In yet another variation, the < 10 predicate can be ‘manually pushed’ by specifying it in a HAVING clause in the “q1” sub-query instead of in the WHERE clause as written above.

The reason this predicate can be pushed past the join in this query form, but not in the original formulation is simply an optimizer limitation – it does make efforts (primarily during the simplification phase) to encourage logically-equivalent query specifications to produce the same execution plan, but the implementation is not completely comprehensive.

Moving on to a second example, the following query specification results from phrasing the requirement as “list the products where there exists fewer than ten correlated rows in the history table”:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) < 10

    );

Unfortunately, this query produces an incorrect result (86 rows):

The problem is that it lists products with no history rows, though the reasons are interesting. The COUNT_BIG(*) in the EXISTS clause is a scalar aggregate (meaning there is no GROUP BY clause) and scalar aggregates always produce a value, even when the input is an empty set. In the case of the COUNT aggregate, the result of aggregating the empty set is zero (the other standard aggregates produce a NULL). To make the point really clear, let’s look at product 709, which happens to be one for which no history rows exist:

    -- Scalar aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709;

    -- Vector aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709

    GROUP BY th.ProductID;

The estimated execution plans for these two statements are almost identical:

You might expect the Stream Aggregate to have a Group By for the second statement, but this is not the case. The query includes an equality comparison to a constant value (709), so all qualified rows are guaranteed to have the same value for ProductID and the Group By is optimized away.

In fact there are some minor differences between the two plans (the first is auto-parameterized and qualifies for trivial plan, whereas the second is not auto-parameterized and requires cost-based optimization), but there is nothing to indicate that one is a scalar aggregate and the other is a vector aggregate. This is something I would like to see exposed in show plan so I suggested it on Connect. Anyway, the results of running the two queries show the difference at runtime:

The scalar aggregate (no GROUP BY) returns a result of zero, whereas the vector aggregate (with a GROUP BY clause) returns nothing at all. Returning to our EXISTS query, we could ‘fix’ it by changing the HAVING clause to reject rows where the scalar aggregate returns zero:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) BETWEEN 1 AND 9

    );

The query now returns the correct 23 rows:

Unfortunately, the execution plan is less efficient now – it has an estimated cost of 0.78 compared to 0.33 for the earlier plans. Let’s try adding a redundant GROUP BY instead of changing the HAVING clause:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY th.ProductID

        HAVING COUNT_BIG(*) < 10

    );

Not only do we now get correct results (23 rows), this is the execution plan:

I like to compare that plan to quantum physics: if you don’t find it shocking, you haven’t understood it properly :) The simple addition of a redundant GROUP BY has resulted in the EXISTS form of the query being transformed into exactly the same optimal plan we found earlier. What’s more, in SQL Server 2008 and later, we can replace the odd-looking GROUP BY with an explicit GROUP BY on the empty set:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    );

I offer that as an alternative because some people find it more intuitive (and it perhaps has more geek value too). Whichever way you prefer, it’s rather satisfying to note that the result of the sub-query does not exist for a particular correlated value where a vector aggregate is used (the scalar COUNT aggregate always returns a value, even if zero, so it always ‘EXISTS’ regardless which ProductID is logically being evaluated).

The following query forms also produce the optimal plan and correct results, so long as a vector aggregate is used (you can probably find more equivalent query forms):

WHERE Clause

    SELECT

        p.Name

    FROM Production.Product AS p

    WHERE 

    (

        SELECT COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

    ) < 10;

APPLY

    SELECT p.Name

    FROM Production.Product AS p

    CROSS APPLY

    (

        SELECT NULL

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    ) AS ca (dummy);

FROM Clause

    SELECT q1.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT COUNT_BIG(*) 

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID 

                GROUP BY ()

            )

        FROM Production.Product AS p

    ) AS q1 

    WHERE

        q1.cnt < 10;

This last example uses SUM(1) instead of COUNT and does not require a vector aggregate…you should be able to work out why :)

    SELECT q.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT SUM(1)

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID

            )

        FROM Production.Product AS p

    ) AS q

    WHERE q.cnt < 10;

The semantics of SQL aggregates are rather odd in places. It definitely pays to get to know the rules, and to be careful to check whether your queries are using scalar or vector aggregates. As we have seen, query plans do not show in which ‘mode’ an aggregate is running and getting it wrong can cause poor performance, wrong results, or both.

Twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com