Search results matching tags 'Undocumented' and '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

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.

How to Find the Statistics Used to Compile an Execution Plan

Paul White — Tue, 20 Sep 2011 15:22:15 GMT

In this post, I show you how to determine exactly which statistics objects were used by the query optimizer to produce an execution plan.

Trace Flags

We will need three undocumented trace flags. The first one (3604) is well-known – it redirects trace output to the client so it appears in the SSMS messages tab.

The second trace flag is 9292. With this enabled, we get a report of statistics objects which are considered ‘interesting’ by the query optimizer when compiling, or recompiling the query in question. For potentially useful statistics, just the header is loaded.

The third trace flag is 9204. With this enabled, we see the ‘interesting’ statistics which end up being fully loaded and used to produce cardinality and distribution estimates for some plan alternative or other. Again, this only happens when a plan is compiled or recompiled – not when a plan is retrieved from cache.

You can enable and disable these flags with the usual DBCC TRACEON and TRACEOFF commands, but it is also possible to enable them just for a particular statement using the undocumented QUERYTRACEON query hint (demonstrated below).

Sample Query

     DBCC FREEPROCCACHE

    SELECT 

        p.Name,

        total_quantity = SUM(th.Quantity)

    FROM AdventureWorks.Production.Product AS p

    JOIN AdventureWorks.Production.TransactionHistory AS th ON

        th.ProductID = p.ProductID

    WHERE

        th.ActualCost >= $5.00

        AND p.Color = N'Red'

    GROUP BY

        p.Name

    ORDER BY

        p.Name

    OPTION

    (

        QUERYTRACEON 3604,

        QUERYTRACEON 9292,

        QUERYTRACEON 9204

    )

The DBCC FREEPROCCACHE is just there to empty the plan cache so we get a compilation. You can also evict the current plan from cache if you know its handle (SQL Server 2008) or use a RECOMPILE query hint. Using RECOMPILE is often convenient, but you may get a different plan compared to that obtained without the hint. Note that compiling the query is enough – we do not need to execute the query; simply requesting an ‘estimated plan’ will do. It doesn’t hurt to run it either though, just to be clear.

Sample Output

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 1, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 1, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 3, 

        ColumnName: Name, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 3, 

        ColumnName: Name, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 11, 

        ColumnName: Color, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 11, 

        ColumnName: Color, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 2, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 2, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 5, 

        ColumnName: ActualCost, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 5, 

        ColumnName: ActualCost, 

        EmptyTable: FALSE

There’s no sign of an official way to get this very useful information in Denali, despite it being requested many times over the years. Trace flag 9204 works at least as far back as SQL Server 2005. Both 92xx flags work in 2008, R2, and Denali CTP 3.

Enjoy!

SQLkiwi@gmail.com
@SQL_Kiwi

Can a SELECT query cause page splits?

Paul White — Mon, 29 Aug 2011 17:46:15 GMT

Books Online has this to say about page splits:

When a new row is added to a full index page, the Database Engine moves approximately half the rows to a new page to make room for the new row. This reorganization is known as a page split. A page split makes room for new records, but can take time to perform and is a resource intensive operation. Also, it can cause fragmentation that causes increased I/O operations.

Given that information, how can a SELECT statement be responsible for page splits? Well, I suppose we could SELECT from a function that adds rows to a table variable as part of its internal implementation, but that would clearly be cheating, and no fun at all from a blogging point of view.

Tables & Sample Data

To demonstrate the effects I want to talk about today, I’m going to use a couple of tables with data from the sales data in the Adventure Works sample database. There’s a full script at the end of this post for those of you that like to run these things for yourselves, but the data generally looks like this: (header table on the left; detail table on the right):

Both tables have a clustered index on the Sales Order ID column. The query I’m going to run is this:

I have expressed the natural join predicate as (X >= Y) AND (X <= Y) instead of (X = Y) to prevent the optimizer choosing a hash or merge join (both of which require at least one equality predicate to perform an inner join). The “+ 0” is there to prevent the optimizer from using an indexed nested loop join (that is, using a seek on the inner side of the join). These tricks are necessary to generate a plan with an eager index spool on this small sample data set.

Checking for Splits

There are several ways to check for page splits while this query is running. I’m going to use the new extended events UI in SQL Server 2012, which, by the way, I’m quite impressed with: it’s a lot like using Profiler inside SSMS and does away with all that tedious mucking about with CREATE EVENT SESSION statements and XQuery (there are also no improbability factors to compute). Ok, so running the query above and looking for page splits via extended events, I get output like this:

These page splits are all caused by the Index Spool in the query plan. This iterator builds a temporary b-tree index on the data produced by its sub-tree, and like any index insert operation, page splits will occur. In fact this is a bit of a cheat, because these page splits aren’t really page splits at all – notice the sequential nature of the pages being ‘split’ (the page_id column), and its relationship with the new page.

Index Spool Internals

Having shown page splits that aren’t really page splits, let’s get to demonstrating an index spool that ‘really does’ split pages. To do that, we need to know something about the way index spools build their temporary index. You have probably noticed that most query plans that build permanent indexes involve a sort, which in turn requires a memory grant.

Index spools do not get a memory grant, and are not preceded by an explicit sort operator in query plans. Given that indexes require sorting, how does an index spool manage to build a b-tree index structure at all? The answer is that index spools just insert rows into an empty b-tree in the order they are received. In general, the rows used for the index will not be received in sorted order, resulting in lots and lots of page splits in the temporary index b-tree.

The first run of the query did not suffer from this problem due to the clustered index on the header table, which tends to produce rows ordered by Sales Order ID – exactly the order of the index built by the index spool. Let’s rebuild the header table clustered index to use the Customer ID column instead, and re-run the test. The query plan looks exactly the same – the only difference is that the index spool is fed by a clustered index scan that is now extremely unlikely to produce rows in Sales Order ID sorted order:

The page splits reported by the extended events ‘trace’ are now very different:

Notice the same source page (page_id) being split over and over again as rows arrive in unsorted order. There are now very many more page splits than before, and they are a lot more expensive because we are now not just allocating new empty pages at the end of the index – we have to shift half the rows and fix up all the page pointers. In practice, this is the sort of splitting you are likely to see in tempdb with an index spool – rows are very unlikely to be in index order (else why would we need the spool at all?). On that last point, consider the hoops I had to jump through to demonstrate a plan where the rows were in temporary index order – all that mess with “>= AND <=” and “+ 0”…

Note: You can distinguish between mid-page splits and the end-of-index ‘splits’ using the technique Jonathan Kehayias (blog | twitter) shows here (it won’t work for our current example because work table index builds are not logged).

Parallel Index Spools

The last thing I want to cover about index spools is how they behave in parallel plans. You might have noticed the MAXOP 1 hint in the previous examples. Let’s remove that now, add some wait type monitoring, and see how we go:

Don’t be fooled by the parallelism indicator on the index spool – the index building portion of its execution happens on a single thread. One way to see this is to capture thread and task information using the page splitting event session, where the same task and thread ids are reported for every one of the hundreds of events:

The wait statistics provide additional confirmation:

Ignore the CXPACKET waits (they are perfectly normal) and look at the EXECSYNC waits. This query ran at DOP 8 on my machine, so 7 parallel threads had to wait while a single thread built the temporary index. The index build took 114ms, and 7 threads waiting simultaneously for that time gives 7 x 114 = 798ms. That’s within one quantum (4ms) of the total recorded EXECSYNC wait time. EXECSYNC is used for lots of different things – whenever synchronization of parallel workers needs to occur outside a Parallelism operator, so please don’t take away the idea that EXECSYNC = index spool.

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Script:

     -- Any AdventureWorks version should be fine

    USE AdventureWorks2008R2

    GO

    -- Tables

    CREATE TABLE #OrdHeader

    (

        SalesOrderID        INTEGER NOT NULL,

        OrderDate           DATETIME NOT NULL,

        SalesOrderNumber    NVARCHAR(25) NOT NULL,

        CustomerID          INTEGER NOT NULL

    )

    GO

    CREATE TABLE #OrdDetail

    (

        SalesOrderID        INTEGER NOT NULL,

        OrderQty            SMALLINT NOT NULL,

        LineTotal           NUMERIC(38,6) NOT NULL

    );

    GO

    -- Data

    INSERT #OrdHeader

    SELECT

        h.SalesOrderID,

        h.OrderDate,

        h.SalesOrderNumber,

        h.CustomerID

    FROM Sales.SalesOrderHeader AS h

    GO

    INSERT #OrdDetail

    SELECT

        d.SalesOrderID,

        d.OrderQty,

        d.LineTotal

    FROM Sales.SalesOrderDetail AS d

    GO

    -- Clustered indexes

    CREATE UNIQUE CLUSTERED INDEX cuq ON #OrdHeader (SalesOrderID) WITH (MAXDOP = 1)

    CREATE CLUSTERED INDEX cuq ON #OrdDetail (SalesOrderID) WITH (MAXDOP = 1)

    GO

    -- Test query

    SELECT

        d.OrderQty,

        h.SalesOrderNumber,

        h.OrderDate

    FROM #OrdDetail AS d

    JOIN #OrdHeader AS h ON

        d.SalesOrderID >= h.SalesOrderID + 0

        AND d.SalesOrderID <= h.SalesOrderID + 0

    OPTION  (MAXDOP 1)

    GO

    -- Lose the ordering

    CREATE CLUSTERED INDEX cuq ON #OrdHeader (CustomerID) 

    WITH (DROP_EXISTING = ON, MAXDOP = 1)

    GO

    SELECT

        d.OrderQty,

        h.SalesOrderNumber,

        h.OrderDate

    FROM #OrdDetail AS d

    JOIN #OrdHeader AS h ON

        d.SalesOrderID >= h.SalesOrderID + 0

        AND d.SalesOrderID <= h.SalesOrderID + 0

    OPTION  (MAXDOP 1)

    GO

    -- Parallelism

    DBCC SQLPERF('sys.dm_os_wait_stats', 'CLEAR')

    GO

    SELECT

        d.OrderQty,

        h.SalesOrderNumber,

        h.OrderDate

    FROM #OrdDetail AS d

    JOIN #OrdHeader AS h ON

        d.SalesOrderID >= h.SalesOrderID + 0

        AND d.SalesOrderID <= h.SalesOrderID + 0

    GO

    SELECT

        ows.wait_type,

        ows.waiting_tasks_count,

        ows.wait_time_ms,

        ows.max_wait_time_ms,

        ows.signal_wait_time_ms

    FROM sys.dm_os_wait_stats AS ows

    WHERE

        ows.wait_type IN (N'CXPACKET', 'EXECSYNC')

    GO

    DROP TABLE 

        #OrdHeader, 

        #OrdDetail

    GO

    /*

    -- Denali Extended Events Session Script (change the session_id filter!)

    -- Try the UI :)

    CREATE EVENT SESSION [Page Splits] ON SERVER 

    ADD EVENT sqlserver.page_split

        (

        ACTION(sqlos.system_thread_id,sqlos.task_address,sqlserver.sql_text)

    WHERE 

        ([package0].[equal_uint64]([sqlserver].[session_id],(60)))) 

    ADD TARGET 

        package0.ring_buffer(SET max_memory=(65536))

    WITH 

    (

        MAX_MEMORY=4096 KB,

        EVENT_RETENTION_MODE=ALLOW_SINGLE_EVENT_LOSS,

        MAX_DISPATCH_LATENCY=30 SECONDS,

        MAX_EVENT_SIZE=0 KB,

        MEMORY_PARTITION_MODE=NONE,

        TRACK_CAUSALITY=OFF,

        STARTUP_STATE=OFF

    )

    */

Join Performance, Implicit Conversions, and Residuals

Paul White — Mon, 18 Jul 2011 11:17:21 GMT

You probably already know that it’s important to be aware of data types when writing queries, and that implicit conversions between types can lead to poor query performance. Some people have gone so far as to write scripts to search the plan cache for CONVERT_IMPLICIT elements, and others routinely inspect plans for that type of thing when tuning.

Now, that’s all good, as far as it goes. It may surprise you to learn that not all implicit conversions are visible in query plans, and there are other important factors to consider too. To demonstrate, I’m going to use two single-column heap tables, containing a selection of pseudo-random numbers, as shown in the diagram below (there’s a script to create the test tables and data at the end of this post):

The first table contains 5,000 rows and the second table contains 5,000,000 rows. The basic test query is to count the number of rows returned by a simple inner join between the two tables. We’ll run a number of tests to explore the performance issues, using a number of tables using different data types to store the data.

Test One – INTEGER NOT NULL

The first test features two tables where both columns are typed as INTEGER, and constrained to be NOT NULL:

Since one table is significantly smaller than the other, the query optimizer chooses a hash join. To avoid the (very useful) bitmap filter optimization featured in my last post, each query features a MAXDOP 1 query hint to guarantee a serial plan. The test query gives this query plan:

This returns its result in 900ms.

Test Two – INTEGER to REAL

Now let’s try the same query, but where the larger table’s column uses the REAL data type (the smaller table is INTEGER as before):

There are a couple of new things here. First, SQL Server needs to convert the data type of one of the columns to match the other before it can perform the join. The rules for data type precedence show that REAL has a higher precedence than INTEGER, so the integer data is converted to REAL using the CONVERT_IMPLICIT operation shown in the Compute Scalar iterator.

The join then probes the hash table (built on the converted REAL values) for matches. The possibility of hash collisions means that a residual predicate is applied to check that the values indicated as a possible match actually do match. Nothing much new or surprising here then. The query performs slightly less well than before, completing in 1000ms.

Test Three – INTEGER to DECIMAL

Same query again, but this time the larger table’s column is defined as a DECIMAL(7, 0):

The first surprise is that this query takes 1600ms.

The second surprise is that the query plan does not contain a Compute Scalar or a CONVERT_IMPLICIT anywhere, despite the fact that we are joining columns with different data types. In fact there is no indication anywhere that an implicit conversion is occurring – not in the graphical plan, not even in the more detailed XML show plan representation.

This is very bad news. Whether you are tuning the query by hand, or using a script to scan the plan cache for implicit conversions, there really is no way to see the invisible type conversion here. Even the new implicit type conversion warnings built into Denali CTP3 do not detect the problem.

Test Four – DECIMAL to INTEGER

Now let’s reverse the situation, so the smaller table’s column is DECIMAL(7,0) and the larger table is INTEGER:

Now the query runs for 1900ms.

The data precedence rules mean each INTEGER value from the large table has to be converted to DECIMAL to compute a hash value, and converted again to check the residual. Again, there is no Compute Scalar, no CONVERT_IMPLICIT…absolutely no visible indication anywhere why this query should run over twice as long as the original.

Adding an Explicit Conversion

Let’s see what happens if we introduce an explicit conversion here, choosing to convert the DECIMAL values to INTEGER in order to perform the conversion on the smaller table:

Ok, so now we have a Compute Scalar, an explicit CONVERT, and a Probe Residual that references the converted expression. This query completes in 1000ms. Compare this query plan with the one shown immediately above it – would you pick that the plan with the extra Compute Scalar would be nearly twice as fast?

Conversion Families

So what’s going on here? Why is SQL Server hiding conversion details from us that have such a profound effect on execution speed? It turns out that certain implicit conversions can be performed inside the join, and so do not require a separate Compute Scalar. This is the case if the join columns have different types, but both types come from the same ‘family’. The five families are:

In our example, DECIMAL and INTEGER are from family [1] so the implicit conversion can be performed inside the join, without a CONVERT_IMPLICIT or Compute Scalar. Stop for a moment and think about how many joins you have in production code where the columns involved are INTEGER to BIGINT, or SMALLINT to INTEGER, to take just two possible examples. Are those joins running at half speed?

The NULL Issue

There is one more subtlety to consider. Let’s run our test query one last time, using tables with INTEGER columns, but this time the columns are declared as allowing NULLs (there are no NULLs in the test data, by the way).

This query runs in around 1000ms. Remember that the first query we ran (where both columns were defined as INTEGER NOT NULL) completed in 900ms. Let’s look at the first query plan again:

Notice the lack of a Probe Residual. If the join is on a single column typed as TINYINT, SMALLINT or INTEGER and if both columns are constrained to be NOT NULL, the hash function is ‘perfect’ – meaning there is no chance of a hash collision, and the query processor does not have to check the values again to ensure they really match.

This optimization is the reason that the NOT NULL query performs 11% faster than when either or both join columns allow NULLs. Also notice that this optimization does not apply to BIGINT columns.

Summary

Here’s my general advice for best join performance:

Be aware that conversions may occur without a CONVERT_IMPLCIT or Compute Scalar
Join on a single column
Ensure join column types match exactly
Constrain potential join columns to be NOT NULL
Use TINYINT, SMALLINT, or INTEGER types to avoid residual predicates
Keep reading my blog for further reasons to prefer INTEGER NOT NULL :)
Introduce explicit conversions where necessary, as a workaround

email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

A Tale of Two Index Hints

Paul White — Wed, 22 Sep 2010 21:44:00 GMT

If you look up Table Hints in Books Online, you’ll find the following statement:

If a clustered index exists, INDEX(0) forces a clustered index scan and INDEX(1) forces a clustered index scan or seek.
If no clustered index exists, INDEX(0) forces a table scan and INDEX(1) is interpreted as an error.

The interesting thing there is that both hints can result in a scan. If that is the case, you might wonder if there is any effective difference between the two. This blog entry explores that question, and highlights an optimizer quirk that can result in a much less efficient query plan when using INDEX(0). I’ll also cover some stuff about ordering guarantees.

Test Environment

As usual, we need to create a test table:

USE     tempdb;
SET     NOCOUNT ON;
GO
IF      OBJECT_ID(N'Test.Orders', N'U')
        IS NOT NULL
        DROP TABLE Test.Orders;
GO
IF      SCHEMA_ID(N'Test')
        IS NOT NULL
        DROP SCHEMA Test;
GO
CREATE  SCHEMA Test

        CREATE  TABLE Orders
                (
                order_id    INTEGER NOT NULL,
                product_id  INTEGER NOT NULL,
                quantity    INTEGER NOT NULL,
                padding     CHAR(980) NOT NULL DEFAULT (SPACE(0)),
                
                CONSTRAINT  [PK Test.Orders order_id]
                PRIMARY KEY CLUSTERED (order_id ASC)
                );
GO
CREATE  NONCLUSTERED INDEX  [IX Test.Orders quantity]
ON      Test.Orders (quantity ASC)
        INCLUDE (padding);
GO
DECLARE @Counter    INTEGER = 1,
        @RowCount   INTEGER = 64 * 8;
        
WHILE   @Counter <= @RowCount
BEGIN
        INSERT  Test.Orders
                (order_id, product_id, quantity)
        VALUES  (
                @RowCount - @Counter,
                @RowCount - @Counter,
                @RowCount - @Counter
                );
                
        SET     @Counter += 1;
END;
GO

The test table has 512 rows, padded so that eight rows fit on each 8KB data page. The table is clustered on the order_id column, and there is a nonclustered index on the quantity column, with the padding column INCLUDEd to again ensure that eight rows fit on each nonclustered index page.

The script also deliberately generates a very high level of logical fragmentation, which we can see with the following query:

SELECT  SI.name,
        IPS.index_type_desc,
        IPS.avg_fragmentation_in_percent,
        IPS.fragment_count,
        IPS.page_count
FROM    sys.dm_db_index_physical_stats
        (
        DB_ID(),
        OBJECT_ID(N'Test.Orders', N'U'),
        DEFAULT,
        DEFAULT,
        DEFAULT
        ) IPS
JOIN    sys.indexes SI
        ON  SI.[object_id] = IPS.[object_id]
        AND SI.index_id = IPS.index_id
ORDER   BY
        IPS.index_id;
GO

The reason for the fragmentation will become apparent later on. These are the results I saw on my machine:

Background Information on Scans

A scan of a table or index processes every row, whereas a seek returns one or more rows from one or more ranges of the index.

Scan Strategies

When the SQL Server optimizer produces a plan containing a scan of an index or clustered table, the Storage Engine may be able to choose from two different strategies: scanning the pages in logical order, or the order in which they were allocated. In the first case, it follows the doubly-linked list at the leaf level of the index. In the second case, it can use the Index Allocation Map (IAM) pages to drive the scan.

A scan of a heap always uses the IAM pages of course (there is no clustered index to provide a logical page order), but this post is concerned mainly with indexes and clustered tables, so I won’t talk much more about heaps.

The advantage of an IAM-driven scan is that pages will tend to be read in physical order on the disk, which generally results in sequential I/O, and promotes effective read-ahead. How efficient scanning the pages in logical order is depends on the level of logical fragmentation: if fragmentation is high, the scan will tend to result in a high proportion of random I/Os, and read-ahead may be much less effective.

The downside to the IAM-driven scan is that it is not guaranteed to return results in logical key order (in fact it usually won’t), and there is an extra start-up cost in accessing the IAM pages, and planning the scan.

IAM-driven scans

The Storage Engine may choose an IAM-driven scan if:

The index contains 64 or more pages (giving the method a chance to recover the start-up cost);
The optimizer indicates that an ordered scan is not required for correct results; and
Either the data cannot change during the scan, or the query indicates that incorrect results are acceptable.

Hopefully the first point makes sense on it’s own. The second point refers to a flag that the optimizer can set on a scanning iterator in a query plan. This flag shows up as an “Ordered:True” or “Ordered:False” property of the iterator. When set to true, it indicates that the Storage Engine must perform a scan in logical key order for the plan to produce correct results. When set to false, it means that the order does not matter. In the latter case, the Storage Engine has the choice of performing either type of scan. The query plan does not show which type of scan was chosen.

The third point comes in two parts, but both relate to the fact that an IAM-driven scan does not take the locks necessary to prevent other concurrent operations from changing the data in the table, or moving the pages around (perhaps as the result of a page split).

The simplest way to satisfy the first part (to ensure that the data cannot be changed or moved) is to take a shared table lock. The second part (acceptable incorrect results) refers to transaction isolation level. If the scan runs at an effective isolation level of READ UNCOMMITTED (either explicitly or through the use of a NOLOCK hint) we are effectively saying that we don’t care about reading consistent data. More than that, we imply that we are happy to read the same data twice, or not at all.

The Reason for the Fragmentation

Our test table has been created with a high level of fragmentation. This allows us to see whether the Storage Engine used an IAM-driven scan or not. If the results come back in logical key order, we can be sure (in these specific examples) that the scan was performed by following the doubly-linked list at the leaf level of the index. If the results come back in allocation order, they will look very different, and we can infer that an IAM-driven scan was performed.

Important: Please don’t take any of that to mean that you can rely on query results to come back in a particular order in more general cases. The very simple tests shown here are carefully crafted to encourage the ordering behaviour I have just described, but there are no guarantees. Never rely on plan details to provide ordering – always use an ORDER BY clause if you require ordered results.

Scanning Examples

Let’s look first at two simple queries that return all columns and all rows from our test table:

-- Query 1
SELECT  T.*
FROM    Test.Orders T;
 
-- Query 2
SELECT  T.*
FROM    Test.Orders T 
ORDER   BY 
        T.order_id ASC;

Both queries produce very similar execution plans, but the first specifies “Ordered:False” while the second specifies “Ordered:True”. The second example avoids an expensive explicit Sort iterator by requiring the Storage Engine to return rows from the scan in logical key order (the clustered index is on order_id, remember).

Both queries return records ordered by the clustering key; Query 1 because the Storage Engine cannot perform an IAM-driven scan (we haven’t met all the conditions); and Query 2 because an ordered scan was requested by the optimizer.

Query 1 is not guaranteed to return records in that order, but Query 2 (almost) is. In case you are wondering what might cause Query 1 to return records in a different order, consider the effect of a parallel plan, or Enterprise Edition’s Advanced Scan feature. For anyone that follows that second link, I should mention that Advanced Scan is only possible when the Ordered flag is set to False.

An IAM-driven Scan

Query 1 above meets two of the conditions for an IAM-driven scan: the index contains at least 64 pages, and the optimizer did not specify Ordered:True. We can meet the third condition by adding a WITH (TABLOCK) hint:

SELECT  T.*
FROM    Test.Orders T WITH (TABLOCK);

We receive the following result set:

Each group of eight records (each 8KB page) comes back ordered by the clustering key, but the overall order of pages is in the order the pages were written. This is the result of an IAM-driven scan: pages in allocation order, records within the pages in clustered key order. As you may have guessed, neither of these two observed orderings can be relied on either – I mention them for pure geek interest value.

Adding the TABLOCK hint to Query 2 does not result in an IAM-driven scan, because the optimizer continues to specify Ordered:True on the scan (to avoid the sort that would be necessary to honour the ORDER BY clause).

For Query 2, the optimizer does still consider a plan with an unordered scan followed by a sort, but rejects it as being more expensive than an ordered scan. For very large tables, the optimizer may calculate that an IAM-driven scan might save more time than would be consumed by the extra sort, and a plan featuring the unordered scan + sort would be chosen. This is a heuristic optimization: the optimizer knows nothing about the actual fragmentation level of an index (though it does know how many pages it occupies).

Index Hints

Let’s now run the Query 1 test again, this time specifying INDEX(0) or INDEX(1) hints, as well as choosing to specify TABLOCK or not:

SELECT  T.* FROM Test.Orders T WITH (INDEX(0));
SELECT  T.* FROM Test.Orders T WITH (INDEX(1));
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK);
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK);

In all cases, the results are the same: if we specify TABLOCK, we meet the conditions for an IAM-driven scan, and the records comes back in physical order. If we omit TABLOCK, we happen to get results in clustered-key order – but we know that is just coincidental. All four query plans look exactly the same as the simple clustered index scans shown earlier, and all feature “Ordered:False”.

Let’s try the same thing with the ORDER BY clause (Query 2):

SELECT  T.* FROM Test.Orders T WITH (INDEX(0)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK) ORDER BY T.order_id;

All four queries produce the same results, in the same order, and are guaranteed to do so thanks to the ORDER BY clause. The execution plans are rather different, however:

Both INDEX(1) plans produce the plan shown on the left, with the scan showing “Ordered:True”, and a cost of 0.05.
Both INDEX(0) plans produce the plan shown on the right, with the scan showing “Ordered:False”, and a cost of 0.07.

Optimizer Bug, Limitation, or “By Design”?

It seems that INDEX(0) forces “Ordered:False” on the scan. As a consequence, we get an explicit Sort iterator when the ORDER BY clause is present. Why should INDEX(0) force an unordered scan?

One can imagine a line of reasoning that says we would normally specify INDEX(0) only on a heap table, where an ordered scan is not possible. The flaw in this argument is that INDEX(1) does not enable us to force a scan of a clustered table – it will result in a seek if at all possible.

INDEX(0) and Ordered:True

Nevertheless, it is possible to produce “Ordered:True” when INDEX(0) is specified, in an INSERT, UPDATE or DELETE query. Let’s look at three alternative formulations of a trivial UPDATE query on our test table:

All three plans feature the “Ordered:True” flag, but the one with INDEX(0) includes a sort on order_id. That sort is probably redundant, since the Clustered Index Scan (with “Ordered:True”) ought to be guaranteed to produce rows in that same order. Not only will that sort slow down your query, it will require a memory grant, and might even spill to tempdb.

A Data Modification Optimization

When performing our UPDATE query, the optimizer takes into account the effect of ordering. If rows arrive at the update iterator in clustered index order, the pattern of updates will likely result in sequential I/O. If rows are in a different order, the updates will likely cause random I/O as the index is updated row by row.

Often, the optimizer may choose to pre-sort the records on the clustered index key to optimize for sequential I/O. On other occasions, it may decide that the cost of the sort would exceed the savings made – this is seen when the number of rows to be updated is very small, and the rows can be located most efficiently from a nonclustered index.

When the rows are sourced from the clustered index, the optimizer always adds the “Ordered:True” flag to maximize the chances for sequential I/O, regardless of the estimated number of rows. This explains how the Clustered Index Scan above manages to acquire the “Ordered:True” flag when INDEX(0) was specified. It seems that the optimizer misses the fact that by adding the ordering flag, the sort is now redundant.

Final Thoughts

Although I have concentrated very much on clustered indexes in this entry, I want to stress that the two scanning strategies apply to both clustered and non-clustered indexes. I created a nonclustered index on the test table so you can verify for yourself that IAM-driven scans are possible with nonclustered indexes, and the rules are exactly the same.

It is also not necessary to specify TABLOCK explicitly to get an IAM-driven scan: if the index in question happens to have row and page locks disabled (using ALTER INDEX (…) SET ALLOW_ROW_LOCKS = OFF, ALLOW_PAGE_LOCKS = OFF) the Storage Engine will recognise that a table lock has to be taken. Other circumstances like the database being read-only will also meet the underlying requirement that the data cannot change during the scan.

Beware of using NOLOCK when the other conditions for an IAM-driven scan are met. Not only might you read data that has not been committed yet, you can also read committed data twice, or not at all. Your query might also fail completely with the dreaded error: “Could not continue scan with NOLOCK due to data movement”.

Finally, watch out for unnecessary sorts in plans that use the INDEX(0) table hint – consider using INDEX(1) instead, or rewriting the query to avoid the hint altogether.

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

Search results matching tags 'Undocumented' and 'Query Plans'

Execution Plan Analysis: The Mystery Work Table

The Execution Plan

High-Cost Operators

Execution Warnings

I/O Information

Execution Outline

Reproducing the problem

Table Creation

Test Query

Warm cache results

Cold cache results

Explanation

Nested Loops Prefetching

Manufactured LOBs

The Outer Join

Memory Allocation

Workaround

Warm cache results

Cold cache results

Final Thoughts

Temporary Tables in Stored Procedures

A World Without Temporary Objects

A Short Digression about Parameter Sniffing

Back to the Main Example

Using a Temporary Table

OPTION (RECOMPILE) to the Rescue?

Manual Statistics Update to the Rescue?

RECOMPILE and UPDATE STATISTICS to the Rescue?

Enter the Table Variable…

Question Time

CREATE and DROP, Don’t

Recompilation Thresholds

Statistics Updates

Summary and Final Thoughts

Further Reading

How to Find the Statistics Used to Compile an Execution Plan

Trace Flags

Sample Query

Sample Output

Can a SELECT query cause page splits?

Tables & Sample Data

Checking for Splits

Index Spool Internals

Parallel Index Spools

Join Performance, Implicit Conversions, and Residuals

Test One – INTEGER NOT NULL

Test Two – INTEGER to REAL

Test Three – INTEGER to DECIMAL

Test Four – DECIMAL to INTEGER

Adding an Explicit Conversion

Conversion Families

The NULL Issue

Summary

Further Reading

Test Script:

A Tale of Two Index Hints

Test Environment

Background Information on Scans

Scan Strategies

IAM-driven scans

The Reason for the Fragmentation

Scanning Examples

An IAM-driven Scan

Index Hints

Optimizer Bug, Limitation, or “By Design”?

INDEX(0) and Ordered:True

A Data Modification Optimization

Final Thoughts

Further Reading